Spring 2012

The Combinatorics Seminar will meet occasionally this semester;
some of our talks will be joint with the
Algebra Seminar: **Tuesday/Thursday, 2:30-3:30 PM, Snow 306.** We will be back to a regular schedule in the fall.

Please contact Jeremy Martin if you are interested in speaking.

**Monday 2/13, 9:00 AM, Snow 306 (note time and place!)**

Matthias Beck (SF State University)

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

Abstract:
A *Golomb ruler* is a sequence of distinct integers (the
*markings* of the ruler) whose pairwise differences are distinct.
Golomb rulers, also known as *Sidon sets* and *\(B_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 for
*optimal* Golomb 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) := \# \left\{ x \in \mathbb{Z}^{m+1} : \, 0 = x_0 < x_1 < \dots < x_{ m-1} < x_m = t , \text{ all } x_j - x_k \text{ distinct} \right\} ,\]
the number of Golomb rulers with \(m+1\) markings and length \(t\). Our main
result is that \(g_m(t)\) is a quasipolynomial in \(t\) which satisfies a
combinatorial reciprocity theorem: \((-1)^{m-1} g_m(-t)\) equals the number
of rulers \(x\) of length \(t\) with \(m+1\) markings, each counted with its
*Golomb multiplicity*, which measures how many combinatorially
different Golomb rulers are in a small neighborhood of \(x\).
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.
This is joint work with Tristram Bogart (Universidad de los Andes) and Tu
Pham (UC Riverside).

**Tuesday 2/14, 2:30-3:30 PM, Snow 306**

Matthias Beck (SF State University)

*Permutation Descent Statistics via Polyhedral Geometry*

Abstract:
Permutations are some of the most fundamental objects of mathematics, and a basic combinatorial statistic of a permutation \(\pi \in S_n\) is the number of *descents* \({\rm des}(\pi) := \{ j : \pi(j) > \pi(j+1) \}\). Euler realized that \[\sum_{k\geq0}(k+1)^nt^k=\frac{\sum_{\pi\in S_n}t^{{\rm des}(\pi)}}{(1-t)^{n+1}}\] and there have been various generalization of this identity, most notably when \(S_n\) gets replaced by another Coxeter group.
We will illustrate how one can view Euler's identity (and its
generalizations) geometrically through enumerating integer points in
certain polyhedra. This gives rise to "short" proofs of known theorems, as
well as new identities.
This is joint work with Ben Braun (Kentucky).

**Tuesday 4/12, 2:30-3:30 PM, Snow 306**

Rebecca Swanson (Nebraska Wesleyan)

*Title TBA*

Jeremy Martin's home page

Last updated Fri 2/17/12