KAIST Discrete Math Seminar

We consider the problem of finding an unknown graph by using two types of queries with an additive property. Given a graph, an additive query asks the number of edges in a set of vertices while a cross-additive query asks the number of edges crossing between two disjoint sets of vertices. The queries ask sum of weights for the weighted graphs. These types of queries were partially motivated in DNA shotgun sequencing and linkage discovery problem of artificial intelligence.

For a given unknown weighted graph G with n vertices, m edges, and a certain mild condition on weights, we prove that there exists a non-adaptive algorithm to find the edges of G using O((m log n)/log m) queries of both types provided that m≤ n^ε for any constant ε>0. For a graph, it is shown that the same bound holds for all range of m.

This settles a conjecture of Grebinski for finding an unweighted graph using additive queries. We also consider the problem of finding the Fourier coefficients of a certain class of pseudo-Boolean functions. A similar coin weighing problem is also considered. (Joint work with S. Choi)

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.

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.