KAIST Discrete Math Seminar

The graph finding problem is to find the edges of an unknown graph by using a certain type of queries. Its extension to hypergraphs is closely related to the problem of learning linkage in molecular biology and artificial intelligence. In this talk, we introduce the hypergraph finding problem and the linkage learning problem and present our recent results for the query complexity of those problems.

In shape matching, we are given two geometric objects and we compute their distance according to some geometric similarity measure. The Fréchet distance is a natural distance function for continuous shapes such as curves and surfaces, and is defined using reparameterizations of the shapes.

The discrete Fréchet distance is a variant of the Fréchet distance in which we only consider vertices of polygonal curves. In this talk, we consider the problem of computing the discrete Fréchet distance between two polygonal curves when their vertices are imprecise, and describe efficient algorithms for the problem.

The fractional weak discrepancy of a poset (partially ordered set) P, written wd(P), is the least k such that some satisfies f(y)-f(x)≤1 for and |f(y)-f(x)|≤k for x|y. Minimal forbidden subposets are often called obstructions. Shuchat, Shull, and Trenk determined the obstructions for the property wd(P)<1: the obstructions are 2+2 and 3+1. We determine the obstructions for the property wd(P)≤k when k is an integer. In this talk, the complete collection of the obstructions for wd(P)≤k for each k≥2 – which is an infinite set – will be discussed.

This is joint work with Douglas B. West.

A graph G on n vertices is pancyclic if it contains cycles of length t for all . We prove that for any fixed , the random graph G(n,p) with asymptotically almost surely has the following resilience property. If H is a subgraph of G with maximum degree at most then G-H is pancyclic. In fact, we prove a more general result which says that if for some integer then for any , asymptotically almost surely every subgraph of G(n,p) with minimum degree greater than contains cycles of length t for all . These results are tight in two ways. First, the condition on p essentially cannot be relaxed. Second, it is impossible to improve the constant 1/2 in the assumption for the minimum degree.

Joint work with Michael Krivelevich and Benny Sudakov

Rao conjectured about 1980 that in every infinite set of degree sequences (of graphs), there are two degree sequences with graphs one of which is an induced subgraph of the other. We recently found a proof, and we sketch the main ideas.

The problem turns out to be related to ordering digraphs by immersion (vertices are mapped to vertices, and edges to edge-disjoint directed paths). Immersion is not a well-quasi-order for the set of all digraphs, but for certain restricted sets (for instance, the set of tournaments) we prove it is a well-quasi-order.

The connection between Rao’s conjecture and digraph immersion is as follows. One key lemma reduces Rao’s conjecture to proving the same assertion for degree sequences of split graphs (a split graph is a graph whose vertex set is the union of a clique and a stable set); and to handle split graphs it helps to encode the split graph as a directed complete bipartite graph, and to replace Rao’s containment relation with immersion.

(Joint with Maria Chudnovsky, Columbia)