KAIST Discrete Math Seminar

A set A of integers is a Sidon set if all the sums a₁+a₂, with a₁≤a₂ and a₁, a₂∈A, are distinct. In the 1940s, Chowla, Erdős and Turán showed that the maximum possible size of a Sidon set contained in [n]={0,1,…,n-1} is √n (1+o(1)). We study Sidon sets contained in sparse random sets of integers, replacing the ‘dense environment’ [n] by a sparse, random subset R of [n].

Let R=[n]_m be a uniformly chosen, random m-element subset of [n]. Let F([n]_m)=max {|S| : S⊆[n]_m Sidon}. An abridged version of our results states as follows. Fix a constant 0≤a≤1 and suppose m=m(n)=(1+o(1))n^a. Then there is a constant b=b(a) for which F([n]_m)=n^b+o(1) almost surely. The function b=b(a) is a continuous, piecewise linear function of a, not differentiable at two points: a=1/3 and a=2/3; between those two points, the function b=b(a) is constant. This is joint work with Yoshiharu Kohayakawa and Vojtech Rödl.

We show that an n-vertex hypergraph with no r-regular subgraph has at most 2^n-1+r-2 edges. We conjecture that if n>r, then every n-vertex hypergraph with no r-regular subgraph having the maximum number of edges contains a full star, meaning 2^n-1 distinct edges containing a single vertex. We prove this conjecture for n≥425. This is joint work with Alexandr V. Kostochka.

Petersen proved that every cubic graph without cut-edges has a perfect matching, but some graphs with cut-edges have no perfect matching. The smallest cubic graph with no perfect matching belongs to a general family applicable to many problems on connected d-regular graphs with n vertices. These include the smallest matching number for such graphs and a relationship between the eigenvalues and the matching number. In addition to these results, we present new results involving this family and the Chinese Postman Problem and a relationship between eigenvalues and edge-connectivity in regular graphs.
This is partly joint work with Sebastian M. Cioaba and Doulgas B. West.

List of speakers</p>

• 11AM-12PM Maria Chudnovsky (Columbia University, USA) : Coloring some perfect graphs
• 2PM-3PM Ken-ichi Kawarabayashi (NII, Japan) : A separator theorem in minor-closed class of graphs
• 4PM-5PM Bojan Mohar (SFU, Canada) : On the chromatic number of digraphs
• 5PM-6PM Paul Seymour (Princeton University, USA) : Colouring Tournaments

A graph G is called perfect if for every induced subgraph H of G, the chromatic number and the clique number of H are equal. After the recent proof of the Strong Perfect Graph Theorem, and the discovery of a polynomial-time recognition algorithm, the central remaining open question about perfect graphs is finding a combinatorial polynomial-time coloring algorithm. (There is a polynomial-time algorithm known, using the ellipsoid method). Recently, we were able to find such an algorithm for a certain class of perfect graphs, that includes all perfect graphs admitting no balanced skew-partition. The algorithm is based on finding special “extremal” decompositions in such graphs; we also use the idea of “trigraphs”.
This is joint work with Nicolas Trotignon, Theophile Trunck and Kristina Vuskovic.

It is shown that for each t, there is a separator of size in any n-vertex graph G with no K_t-minor.
This settles a conjecture of Alon, Seymour and Thomas (J. Amer. Math. Soc., 1990 and STOC’90), and generalizes a result of Djidjev (1981), and Gilbert, Hutchinson and Tarjan (J. Algorithm, 1984), independently, who proved that every graph with n vertices and genus g has a separator of order , because K_t has genus Ω(t²).
Joint work with Bruce Reed.

Several reasons will be presented why the natural extension of the notion of undirected graph colorings is to partition the vertex set of a digraph into acyclic sets. Additionally, some recent results in this area, the proofs of which use probabilistic techniques, will be outlined.

A tournament is a digraph obtained from a complete graph by directing its edges, and colouring a tournament means partitioning its vertex set into acyclic subsets (acyclic means the subdigraph induced on the subset has no directed cycles). This concept is quite like that for graph-colouring, but different. For instance, there are some tournaments H such that every tournament not containing H as a subdigraph has bounded chromatic number. We call them heroes; for example, all tournaments with at most four vertices are heroes.
It turns out to be a fun problem to figure out exactly which tournaments are heroes. We have recently managed to do this, in joint work with Berger, Choromanski, Chudnovsky, Fox, Loebl, Scott and Thomassé, and this talk is about the solution.

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.