KAIST Discrete Math Seminar

Helly’s theorem asserts that if a finite family of convex sets in d-space has an empty intersection, then there exists a subfamily of cardinality at most d+1 with an empty intersection. Helly’s theorem and its numerous extensions play a central role in discrete and computational geometry. It is of considerable interest to understand the role of convexity in these results, and to find suitable topological extensions. The class of d-Leray complexes (introduced by Wegner in 1975) is the natural framework for formulating topological Helly type theorems. We will survey some old and new results on Leray complexes with combinatorial and geometrical applications. In particular, we’ll describe recent work on Leray numbers of projections and a topological Helly type theorem for unions. Joint work with Gil Kalai.

The square G² of a graph G is the graph with the same vertex set as G and with two vertices adjacent if their distance in G is at most 2. Thomassen showed that for a planar graph G with maximum degree Δ(G)=3 we have χ(G²)≤7. Kostochka and Woodall conjectured that for every graph, the list-chromatic number of G² equals the chromatic number of G², that is χ_l(G²)=χ(G²) for all G. If true, this conjecture (together with Thomassen’s result) implies that every planar graph G with Δ(G)=3 satisfies χ_l(G²)≤7. We prove that every graph (not necessarily planar) with Δ(G)=3 other than the Petersen graph satisfies χ_l(G²)≤8 (and this is best possible). In addition, we show that if G is a planar graph with Δ(G)=3 and girth g(G)≥7, then χ_l(G²)≤7. Dvořák, Škrekovski, and Tancer showed that if G is a planar graph with Δ(G)=3 and girth g(G)≥10, then χ_l(G²)≤6. We improve the girth bound to show that: if G is a planar graph with Δ(G)=3 and g(G)≥9, then χ_l(G²)≤6. This is joint work with Daniel Cranston.</div>

Fixed-Parameter Tractability (FPT) is a rapidly expanding framework to tackle computationaly hard problems. In many combinatorial problems, the input instance usually comes in pair with an interger k, of which the typical example is found in the VERTEX COVER: Given a graph G and an integer k, is there a VERTEX COVER of size at most k? The motivation is to restrict the presumably inevitable combinatorial explosion to be one in terms of k so that for a relatively small k the problem is expected to be solved in a reasonable amount time. Moreover paramterized framework leads to an elaborate hierarchy of computational compelxity which is analogous to the traditional complexity classes.

Given a digraph D, the Minimum Leaf Out-Branching problem (MinLOB) is the problem of finding in D an out-branching with the minimum possible number of leaves, i.e., vertices of out-degree 0. We describe three parameterizations of MinLOB and prove that two of them are NP-complete for every value of the parameter, but the third one is fixed-parameter tractable (FPT). The FPT parametrization is as follows: given a digraph D and a positive integral parameter k, check whether D contains an out-branching with at least k non-leaves (and find such an out-branching if it exists).

Planar structures, particularly planar graphs, have attracted much attention during the last few years, from the viewpoints of enumeration, sampling, and typical properties. In order to determine the number of graphs of interest, typically graphs are decomposed according to connectivity. Using the decomposition tree we derive recursive counting formulas, from which we can design a uniform sampling algorithm to sample a random instance. Furthermore, we interpret the decomposition in terms of equations of generating functions, from which we can estimate the asymptotic numbers using singularity analysis.

On the other hand, the matrix integral method, a technique of theoretical physics, employs the traces of Hermitian matrices to express the number of embedded graphs on a 2-dimensional surface and planar maps in particular. This leads to the map enumeration results analogous to those obtained by combinatorial methods. A natural question is whether the method may as well be applied to the enumeration of graphs embeddable on a 2-dimensional surface. This can be done by applying the matrix integral to combinatorially defined functions, in order to loosen the strong connection between maps and the traces.

In this talk I will discuss recent results on this subject.

We prove Helly-type theorems for line transversals to disjoint unit spheres in R^d. In particular, we show that a family of n ≥ 2d disjoint unit spheres in R^d has a line transversal if, for some ordering of the balls, any subfamily of 2d balls admits a line transversal consistent with this ordering. We also discuss generalizations that drop the ordering requirement and to spheres with arbitrary radius.</div>