Last updated Fri 2/17/12
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
Last updated Fri 2/17/12