Return to Colloquia & Seminar listing

### Enumeration of Golomb Rulers and Acyclic Orientations of Mixed Graphs

**Algebra & Discrete Mathematics**

Speaker: | Matthias Beck, San Francisco State University |

Location: | 1147 MSB |

Start time: | Thu, Jan 26 2012, 3:10PM |

AGolomb ruleris a sequence of distinct integers (themarkingsof the ruler) whose pairwise differences are distinct. Golomb rulers, also known asSidon setsandB_2 sets, can be traced back to additive number theory in the 1930s and have attracted recent research activities on existence problems, such as the search foroptimalGolomb rulers (those of minimal length given a fixed number of markings). Our goal is to enumerate Golomb rulers in a systematic way: we study

g_m(t) := { x \in \Z^{m+1} : 0 = x_0 < x_1 < .... < x_{ m-1 } < x_m = t, all x_j - x_k distinct} },

the number of Golomb rulers withm+1markings and lengtht. Our main result is thatg_m(t)is a quasipolynomial intwhich satisfies a combinatorial reciprocity theorem:(-1)^{m-1} g_m(-t)equals the number of rulersxof lengthtwithm+1markings, each counted with itsGolomb multiplicity, which measures how many combinatorially different Golomb rulers are in a small neighborhood ofx.

Our reciprocity theorem can be interpreted in terms of certain mixed graphs associated to Golomb rulers; in this language, it is reminiscent of Stanley's reciprocity theorem for chromatic polynomials. Thus we can develop an analogue of Stanley's theorem to mixed graphs, which connects their chromatic polynomials to acyclic orientations.