#
Monday Lecture and Colloquium

**Monday, October 21, 2013**

Freie Universität Berlin

Institut für Informatik

Takustr. 9

14195 Berlin

Room: 005

** Lecture - 14:15**

### Matthias Beck -
San Francisco State University

### Golomb rulers, graph polynomials, and their geometry

*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, 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**

###
Matthias Lenz - University of Oxford, Merton College

### On splines and counting lattice points in polytopes

*Abstract:*

We consider variable polytopes of type
Π_{X}(u) = { w ≥ 0 : X w = u }. It is known that the function
T_{X} 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 T_{X}.

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.

Letzte Aktualisierung:
14.10.2013