2014/12/12 Fri 10:30AM-12PM, 1:30PM-3PM

E6-1, Room 1501

Seminar series on discrete mathematics @ Dept. of Mathematical Sciences, KAIST.

Theory of excluding induced subgraphs

Paul Seymour Department of Mathematics, Princeton University, Princeton, NJ, USA

Maria Chudnovsky, Columbia University, New York, NY, USA

2014/12/11 Thu 10:30AM-12PM, 1:30PM-3PM

2014/12/12 Fri 10:30AM-12PM, 1:30PM-3PM

E6-1, Room 1501

2014/12/12 Fri 10:30AM-12PM, 1:30PM-3PM

E6-1, Room 1501

This will be a series of four lectures, beginning with a general introduction to the area of induced subgraphs, and later focusing on several recent results. We will examine the structure of graphs that do not contain certain induced subgraphs, and in particular study relations between the clique number, stability number and chromatic number of these graphs. Later topics will include the strong perfect graph theorem, and recent progress on the Erdos-Hajnal conjecture, and on various conjectures of Gyárfás.

KAIST Graph Theory Day 2012

2012/12/13 Thursday (Room: 3433, Building E6-1)

List of speakers

- 11AM-12PM Tomáš Kaiser (University of West Bohemia, Czech Republic) : Applications of the matroid-complex intersection theorem
- 1:30PM-2:30PM Paul Seymour (Princeton University, USA) : Graphs, Tournaments, Colouring and Containment
- 2:45PM-3:45PM Maria Chudnovsky (Columbia University, USA) : Excluding paths and antipaths
- 4:30PM-5:30PM Daniel Kráľ (University of Warwick, UK) : Quasirandomness and property testing of permutations
**(Colloquium)**

Applications of the matroid-complex intersection theorems

Tomáš Kaiser

The Matroid intersection theorem of Edmonds gives a formula for the maximum size of a common independent set in two matroids on the same ground set. Aharoni and Berger generalized this theorem to the `topological’ setting where one of the matroids is replaced by an arbitrary simplicial complex. I will present two applications of this result to graph-theoretical problems. The first application is related to the existence of spanning 2-walks in tough graphs, the other one is more recent and gives a bound on the fractional arboricity of a graph G ensuring that G can be covered by k forests and a matching. In both cases, slightly better results can be obtained by other methods, but there seems to be room for improvement on the topological side as well.

Graphs, tournaments, colouring and containment

Paul Seymour

Some tournaments H are *heroes*; they have the property that all tournaments not containing H as a subtournament have bounded chromatic number (colouring a tournament means partitioning its vertex-set into transitive subsets). In joint work with eight authors, we found all heroes explicitly. That was great fun, and it would be nice to find an analogue for graphs instead of tournaments.

The problem is too trivial for graphs, if we only exclude one graph H; but it becomes fun again if we exclude a finite set of graphs. The Gyarfas-Sumner conjecture says that if we exclude a forest and a clique then chromatic number is bounded. So what other combinations of excluded subgraphs will give bounded chromatic (or cochromatic) number? It turns out (assuming the Gyarfas-Sumner conjecture) that for any finite set S of graphs, the graphs not containing any member of S all have bounded cochromatic number if and only if S contains a complete multipartite graph, the complement of a complete multipartite graph, a forest, and the complement of a forest.

Proving this led us to the following: for every complete multipartite graph H, and every disjoint union of cliques J, there is a number n with the following property. For every graph G, if G contains neither of H,J as an induced subgraph, then V(G) can be partitioned into two sets such that the first contains no n-vertex clique and the second no n-vertex stable set.

In turn, this led us (with Alex Scott) to the following stronger result. Let H be the disjoint union of H_1,H_2, and let J be obtained from the disjoint union of J_1,J_2 by making every vertex of J_1 adjacent to every vertex of J_2. Then there is a number n such that for every graph G containing neither of H,J as an induced subgraph, V(G) can be partitioned into n sets such that for each of them, say X, one of H_1,H_2,J_1,J_2 is not contained in G|X.

How about a tournament analogue of this? It exists, and the same (short) proof works; and this leads to a short proof of the most difficult result of the heroes paper that we started with.

There are a number of other related results and open questions. Joint work with Maria Chudnovsky.

The problem is too trivial for graphs, if we only exclude one graph H; but it becomes fun again if we exclude a finite set of graphs. The Gyarfas-Sumner conjecture says that if we exclude a forest and a clique then chromatic number is bounded. So what other combinations of excluded subgraphs will give bounded chromatic (or cochromatic) number? It turns out (assuming the Gyarfas-Sumner conjecture) that for any finite set S of graphs, the graphs not containing any member of S all have bounded cochromatic number if and only if S contains a complete multipartite graph, the complement of a complete multipartite graph, a forest, and the complement of a forest.

Proving this led us to the following: for every complete multipartite graph H, and every disjoint union of cliques J, there is a number n with the following property. For every graph G, if G contains neither of H,J as an induced subgraph, then V(G) can be partitioned into two sets such that the first contains no n-vertex clique and the second no n-vertex stable set.

In turn, this led us (with Alex Scott) to the following stronger result. Let H be the disjoint union of H_1,H_2, and let J be obtained from the disjoint union of J_1,J_2 by making every vertex of J_1 adjacent to every vertex of J_2. Then there is a number n such that for every graph G containing neither of H,J as an induced subgraph, V(G) can be partitioned into n sets such that for each of them, say X, one of H_1,H_2,J_1,J_2 is not contained in G|X.

How about a tournament analogue of this? It exists, and the same (short) proof works; and this leads to a short proof of the most difficult result of the heroes paper that we started with.

There are a number of other related results and open questions. Joint work with Maria Chudnovsky.

Excluding paths and antipaths

Maria Chudnovsky

The Erdos-Hajnal conjecture states that for every graph H, there exists a constant delta(H)>0, such that every n-vertex graph with no induced subgraph isomorphic to H contains a clique or a stable set of size at least n^delta(H). This conjecture is still open. We consider a variant of the conjecture, where instead of excluding a single graph H as an induced subgraph, a family of graphs is excluded. We prove this modified conjecture for the case when the five-edge path and its complement are excluded. Our second result is an asymmetric version of this: we prove that for every graph G such that G contains no induced six-edge path, and the complement of G contains no induced four-edge path, G contains a polynomial-size clique or stable set. This is joint work with Paul Seymour.

Quasirandomness and property testing of permutations

Daniel Kráľ

A systematic study of large combinatorial objects has recently led to discovering many connections between discrete mathematics and analysis. In this talk, we explore the analytic view of large permutations. We associate every sequence of permutations with a measure on a unit square and show the following: if the density of every 4-element subpermutations in a permutation p is 1/4!+o(1), then the density of every k-element subpermutation is 1/k!+o(1). This solves a question of Graham whether quasirandomness of a permutation is captured by densities of its 4-element subpermutations. At the end of the talk, we present a result related to an area of computer science called property testing. A property tester is an algorithm which determines (with a small error probability) properties of a large input object based on a small sample of it. Specifically, we prove a conjecture of Hoppen, Kohayakawa, Moreira and Sampaio asserting that hereditary properties of permutations are testatble with respect to the so-called Kendal’s tau distance.

The results in this talk were obtained jointly with Tereza Klimosova or Oleg Pikhurko.

The results in this talk were obtained jointly with Tereza Klimosova or Oleg Pikhurko.

KAIST Graph Theory Day 2011

2011/5/10 Tuesday (Room: 1501, Building E6-1)

Poster (KAIST Graph Theory Day)

Registration

List of speakers

- 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

Coloring some perfect graphs

Maria Chudnovsky

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.

This is joint work with Nicolas Trotignon, Theophile Trunck and Kristina Vuskovic.

A separator theorem in minor-closed class of graphs

Ken-ichi Kawarabayashi

It is shown that for each t, there is a separator of size \(O(t \sqrt{n})\) 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 \(O(\sqrt{gn})\), because K_{t} has genus Ω(t^{2}).

Joint work with Bruce Reed.

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 \(O(\sqrt{gn})\), because K

Joint work with Bruce Reed.

On the chromatic number of digraphs

Bojan Mohar

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.

Colouring Tournaments

Paul Seymour

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.

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.

Packing seagulls in graphs with no stable set of size three

Maria Chudnovsky

Department of Industrial Engineering and Operations Research & Department of Mathematics, Columbia University, New York, USA

Department of Industrial Engineering and Operations Research & Department of Mathematics, Columbia University, New York, USA

2009/5/21 Thursday 2PM-3PM

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 \(t = \lceil |V(G)|/2 \rceil\). 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.