Monday, October 21, 2013
Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
Room: 005
Lecture - 14:15
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 B2 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, giving rise a quasipolynomial counting function which satisfies a combinatorial reciprocity theorem.
Our viewpoint is discrete geometric: it involves lattice-point enumeration in polyhedra and the combinatorics of hyperplane arrangements. 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, and we will outline how these various enumerative, geometric, and graph concepts are interwoven.
This is joint work with Tristram Bogart (Universidad de los Andes) and Tu Pham (UC Riverside).
Colloquium - 16:00
Abstract:
We consider variable polytopes of type
ΠX(u) = { w ≥ 0 : X w = u }. It is known that the function
TX that assigns to a parameter u
the volume of the polytope ΠX(u) is piecewise polynomial.
Formulas of Khovanskii-Pukhlikov and Brion-Vergne imply that the number of
lattice points in ΠX(u) can be obtained by applying a certain
differential operator to the function TX.
In this talk I will explain the facts mentioned above, prove a conjecture of
Holtz-Ron on box splines and interpolation, and deduce an improved version
of the Khovanskii-Pukhlikov formula.
The talk will be based on arXiv:1211.1187 and arXiv:1305.2784.