Jesus De Loera

Generating function algorithms for lattice points problems

1. Lattice Points problems in Polyhedra

   Counting, feasibility, Optimization. Applications in applied math (Optimization and Statistics) and pure math (combinatorics and representation theory). What happens beyond polyhedra?

2. Rational Function Algorithms I

   Ehrhart's structure theorem, Barvinok's algorithm, Vergne's hyperplane arrangement method, Software demo LattE.

3. Rational Function Algorithms II

   Lasserre's asymptotic analysis, digging's algorithm, A glimpse of Pemantle's general algorithmic theory for arbitrary generating functions.

Colin McDiarmid

Randomness and the plane

1. Random planar graphs

   What are typical properties of a graph picked uniformly at random from all planar graphs with n vertices? We shall discuss recent work of Angelika Steger, Dominic Welsh and the speaker. What if we consider such graphs with a given number of edges? We shall discuss very recent work of Stefanie Gerke, Angelika Steger, Andreas Weißl and the speaker.

2. Colouring random geometric graphs

   Suppose that we throw n points uniformly at random into the unit square, and form a graph by saying two points are adjacent if they are at distance at most r=r(n) (or do something like this but more general). How close will the chromatic number and clique number tend to be? We discuss recent work of the speaker and Mathew Penrose, and very recent work of Tobias Mueller.

Manuel Bodirsky

The asymptotic number of cubic labeled planar graphs

In contrast to general planar graphs, the generating function for the number of connected cubic planar graphs is algebraic. We present a decomposition of cubic planar graphs, derive equations for the generating functions, and analyse their singularities. This allows us to compute the asymptotic number of cubic labeled planar graphs. The talk builds on the previous talk "Random planar structures" by Mihyun Kang.

Raymond Hemmecke

Test sets in integer programming: recent developments

In this talk we give an introduction to test set methods in integer programming. Although these sets are exponential in size, they can be encoded efficiently via Barvinok's short rational generating functions. Besides theory and algorithms, we present applications of test sets to stochastic integer programming, to nonlinear convex integer programming, to counting lattice points, and to stochastics.

Benjamin Hiller

Probabilistic Competitive Analysis of an Elementary Dial-a-Ride Problem

We consider an online variant of a special Dial-a-Ride problem where the transportation network is a tree. Requests are generated by chosing source and destination vertex according to an arbitrary probability distribution on the vertices. We show that an algorithm called IGNORE(use-MST) is aas (1+o(1))-competitive wrt the total distance traveled by the server if there is high load.

Mihyun Kang

Random Planar Structures

We consider random planar structures, such as planar graphs, series-parallel graphs, and outerplanar graphs. We ask the following questions: how many of them are there, can we sample a random instance uniformly at random, and what properties does a random planar structure have.

Our approach to answer these questions is to decompose the graphs along their connectivity. For the exact enumeration and the uniform generation we use the so-called recursive method: We derive recursive counting formulas along the decomposition, which yields a polynomial time algorithm to sample a graph that is uniformly distributed. For the asymptotic enumeration we interpret the decomposition in terms of generating funtions and derive the asymptotic numbers of the graphs, using singularity analysis.

On one hand, having the uniform sampling algorithm, we can discuss empirical properties of random planar structures. On the other hand, having the asymptotic number, we can discuss the asymptotic properties of random planar structures that hold when the number of vertices converges to infnity.

Arie Koster

Degree-based Treewidth Lower Bounds - Theory and Computation

Every lower bound for treewidth can be extended by taking the maximum of the lower bound over all subgraphs or minors. This extension is shown to be a very vital idea for improving treewidth lower bounds. The studied lower bounds have in common that they are all the vertex degree of some vertex in a subgraph or minor of the input graph. We study the computational complexity of these lower bounds and present computational experiments on algorithms that compute the bounds exactly/approximately.

Frank H. Lutz

Enumeration and Random Realization of Triangulated Surfaces

It is, in general, a difficult problem to decide realizability for triangulated orientable surfaces of genus \geq 1$. Surprisingly, for triangulations with few vertices, 3-dimensional geometric realizations (with straight edges, flat triangles, and without self-intersections) can be obtained by choosing coordinates randomly: At least 827 of the 865 vertex-minimal 10-vertex triangulations of the orientable surface of genus 2 are realizable. We present some of these examples in the talk. Moreover, we explain the backtracking approach that we used to enumerate the 42.426 triangulated surfaces with 10 vertices.

Rafael Mechtel

Random Edge on Products of Polygons

The random edge rule used as a pivot rule in the simplex algorithm looks quite simple: "Given a polytope and a linear objective function, then move from a given vertex uniformly at random to one of its improving neighbors, until the optimal vertex is reached."
But despite its simplicity the random edge rule seems to be awful to analyze in any nontrivial example. This is allready true for such an easy example as the product of two polygons, which yields a four-dimensional polytope with the number of vertices being quadratic in the number of facets.

We exploit the combinatorial structure of these polytopes and of unique-sink-orientations to show that in expectation the random edge rule visits not more than a linear number of vertices.
The used methods can be extended to analyse four-dimensional dual-cyclic-polytopes. But they become technically more challenging.