KAIST Discrete Math Seminar

We prove that every infinite sequence of skew-symmetric or symmetric matrices M₁, M₂, … over a fixed finite field must have a pair M_i, M_j (i<j) such that that M_i is isomorphic to a principal submatrix of the Schur complement of a nonsingular principal submatrix in M_j, if those matrices have bounded rank-width. This generalizes three theorems on well-quasi-ordering of graphs or matroids admitting good tree-like decompositions; (1) Robertson and Seymour’s theorem for graphs of bounded tree-width, (2) Geelen, Gerards, and Whittle’s theorem for matroids representable over a fixed finite field having bounded branch-width, and (3) Oum’s theorem for graphs of bounded rank-width with respect to pivot-minors.

A non-complete distance-regular graph Γ is called geometric if there exists a set C of Delsarte cliques such that each edge of Γ lies in a unique clique in C. In this talk, we determine the non-complete distance-regular graphs satisfying max{3,8(a₁+1)/3}<k<4a₁+10−6c₂. To prove this result, we first show by considering non-existence of 4-claws that any non-complete distance-regular graph satisfying max{3,8(a₁+1)/3}<k<4a₁+10−6c₂ is a geometric distance-regular graph with smallest eigenvalue −3. Moreover, we classify the geometric distance-regular graphs with smallest eigenvalue −3. As an application, 7 feasible intersection arrays are ruled out.

The H-colouring Dichotomy of Hell and Nesetril, proved in 1990, is one of the most quoted results in the field of Graph Homomorphisms. It says that H-coloring, the problem of deciding if a given graph G admits an homomorphism to the fixed graph H, is NP-complete if H contains an odd cycle, and otherwise polynomial time solvable.
In this talk we present a short new proof of this result, recently published, using a new projective property defined for homomorphisms of powers of a graph G onto a graph H.

A classical theorem of Cedric Smith guarantees the existence of a second Hamilton circuit other than a given one in any hamiltonian cubic graph. It is an open problem in complexity theory whether the corresponding search problem is polynomially solvable. We observe that a search algorithm, implicit in Bill Tutte’s nonconstructive proof of Smith’s theorem, has exponential running time. We also mention two possible candidates for search algorithms with polynomial complexity.

I will talk about recent progress of distance-regular graphs.

A sequence of even length is a repetition if the first half is identical to the second half. A sequence is said to contain a repetition if it has a subsequence which is a repetition. A classical result of Thue says that there is an infinite sequence on 3 symbols which contains no repetition. This result motivated many deep research and challenging problems. One graph concept related to this result is Thue-colouring. A Thue-colouring of a graph G is a mapping which assigns to each vertex of G a colour (a symbol) in such a way that the colour sequence of any path of G contains no repetition. The Thue-chromatic number of a graph is the minimum number of colours needed in a Thue-colouring of G. Thue’s result is equivalent to say that the infinite path has Thue-chromatic number 3. It is also known that the Thue-chromatic number of any tree is at most 4.
Thue-choice number of a graph G is the list version of its Thue-chromatic number, which is the minimum integer k such that if each vertex of G is given k-permissible colours, then there is a Thue-colouring of G using a permissible colour for each vertex. This talk will survey some research related to Thue Theorem and will show that Thue-choice number of paths is at most 4 and Thue choice number of trees are unbounded.