Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

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

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

Matthias Lenz - University of Oxford, Merton College

On splines and counting lattice points in polytopes

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.

Letzte Aktualisierung: 14.10.2013