KAIST Discrete Math Seminar

In this talk, we shall discuss the following well-known problem, which
is called the disjoint paths problem.

Given a graph G with n vertices and m edges, k pairs of vertices (s₁,t₁),(s₂,t₂),…,(s_k,t_k) in G (which are sometimes called terminals). Are there disjoint paths P₁,…,P_k in G such that P_i joins s_i and t_i for i=1,2,…,k?

We discuss recent progress on this topic, including algorithmic aspect of the disjoint paths problem.

We also discuss some structure theorems without the k disjoint paths. Topics include the uniquely linkage problem and the connectivity function that guarantees the existence of the k disjoint paths.

Hajos’ conjecture is false, and it seems that graphs without a subdivision of a big complete graph do not behave as well as those without a minor of a big complete graph.

In fact, the graph minor theorem (a proof of Wagner’s conjecture) is not true if we replace the minor relation by the subdivision relation. I.e, For every infinite sequence G₁,G₂, … of graphs, there exist distinct integers i<j such that G_i is a minor of G_j, but if we replace ”minor” by ”subdivision”, this is no longer true.

This is partially because we do not really know what the graphs without a subdivision of a big complete graph look like.

In this talk, we shall discuss this issue. In particular, assuming some moderate connectivity condition, we can say something, which we will present in this talk.

Topics also include coloring graphs without a subdivision of a large complete graph, and some algorithmic aspects. Some of the results are joint work with Theo Muller.

We first present how to extend Ramanujan’s method in partition congruences and show a congruence relation that the coefficients of the quotient of generating series for partitions and sums of squares satisfy. Then we observe a combinatorial interpretation of the product of them and see whether we could find some arithmetic properties of its coefficients.

In their 1984 book “Algebraic Combinatorics I: Association Schemes”, E. Bannai and T. Ito conjectured that there are only finitely many distance-regular graphs with fixed valency k≥3.

In the series of papers, they showed that their conjecture holds for k=3, 4, and for the class of bipartite distance-regular graphs. J. H. Koolen and V. Moulton also show that there are only finitely many distance-regular graphs with k=5, 6, or 7, and there are only finitely many triangle-free distance-regular graphs with k=8, 9 or 10. In this talk, we show that the Bannai-Ito conjecture holds for any integer k>2 (i.e., for fixed integer k>2, there are only finitely many distance-regular graphs with valency k).

This is a joint work with A. Dubickas, J. H. Koolen and V. Moulton.

Lovász and Plummer conjectured that there exists a fixed positive constant c such that every cubic n-vertex graph with no cutedge has at least 2^cn perfect matchings. Their conjecture has been verified for bipartite graphs by Voorhoeve and planar graphs by Chudnovsky and Seymour. We prove that every claw-free cubic n-vertex graph with no cutedge has more than 2^n/18 perfect matchings, thus verifying the conjecture for claw-free graphs.