Graham Brightwell - London School of Economics

Counting Unions of Combinatorial Structures

Abstract: We consider two problems of a similar nature. First, given n and k, we estimate the number of graphs on vertex set [n] that can be built as the edge-union of k-cliques. Second, given n and k, we estimate the number of subsets of the n-dimensional discrete cube that can be built as the union of k-dimensional subcubes. Both problems have alternative natural interpretations.

Colloquium - 16:00

Clemens Huemer - Universitat Polit\'ecnica de Catalunya

Gray Code Enumeration of Plane Straight-Line Graphs

Abstract: Efficient enumeration of objects is a fundamental problem in combinatorics. A Gray code for a given class of objects provides a complete enumeration scheme for this class by means of constant-size operations. We develop Gray code enumeration schemes for geometric graphs in the plane.

The considered graph classes include plane straight-line graphs, plane spanning trees, and connected plane straight-line graphs. Previous results were restricted to the case where the underlying vertex set is in convex position.

This is a joint work with Oswin Aichholzer, Franz Aurenhammer and Birgit Vogtenhuber.