KAIST Discrete Math Seminar

Hadwiger’s conjecture is a well known open problem in graph theory. It states that every graph with chromatic number k, contains a certain structure, called a “clique minor” of size k. An interesting special case of the conjecture, that is still wide open, is when the graph G does not contain three pairwise non-adjacent vertices. In this case, it should be true that G contains a clique minor of size t where . This remains open, but Jonah Blasiak proved it in the subcase when |V(G)| is even and the vertex set of G is the union of three cliques. Here we prove a strengthening of Blasiak’s result: that the conjecture holds if some clique in G contains at least |V(G)|/4 vertices.

This is a consequence of a result about packing “seagulls”. A seagull in G is an induced three-vertex path. It is not known in general how to decide in polynomial time whether a graph contains k pairwise disjoint seagulls; but we answer this for graphs with no stable sets of size three.

This is joint work with Paul Seymour.

This is a joint work with Cai-Heng Li. Let denote the set of positive integers n such that each transitive action of degree n is multiplicity-free, and denote the set of such that n=pq for some primes p, q with </center> and where its proof owes much to classification of finite simple groups.

The Cycle Double Cover Problem in Graph Theory suggests that all 2-connected graphs share a certain property with 2-connected planar maps. Such a map clearly contains a collection of cycles, indeed the boundary cycles of its faces, such that each edge belongs to exactly
two of them. The generalization of this property to nonplanar graphs remains one of the central open problems in Graph Theory.

We investigate this problem by generalizing a suitable variation of the statement of another almost obvious property of planar maps, namely the Jordan Curve Theorem. The generalization suggests a new conjecture which is much stronger than the Cycle Double Cover Conjecture. In fact it would imply a very strong form of the Cycle Double Cover Conjecture, suggesting that every cycle in a 2-connected graph appears in at least one cycle double cover of the graph.

We prove the stronger conjecture in a few important special cases.

The Markov Chain Monte Carlo (MCMC) method is a widely-used algorithmic approach for randomly sampling from and estimating the cardinality of large sets. In this talk I will give an introduction to the MCMC approach. Then I will explain a more sophisticated variant that gives a polynomial-time algorithm to approximate the permanent of a non-negative matrix. In graph-theoretic terminology, the permanent corresponds to the number of perfect matchings of a bipartite graph.

In recent years Constraint Satisfaction Problems (CSPs) have gained popularity among graph theorists due to the fact that they can be viewed as a generalisation of graph homomorphism problems. An important conjecture in the field is the CSP Dichotomy Classification Conjecture. Much of the recent progress towards a solution to this conjecture has come from the field universal algebra, and the statement of the Classification Conjecture requires a fair bit of algebraic language. </p>

We talk about a recent graph theoretic construction, called the fibre construction, which can be used to get some of the important results achieved with universal algebra. This construction provides combinatorial version of the Classification Conjecture, and allows one to easily address restricted versions of the Conjecture. Further it leads to results unexpected by the universal algebra community.

Much of the material covered is joint work with Jaroslav Nešetřil and László Zádori.</div>