Posts Tagged ‘MariaChudnovsky’

Paul Seymour and Maria Chudnovsky, Theory of excluding induced subgraphs [KAIST CMC Annual Distinguished Lecture]

Friday, December 5th, 2014
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
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

Thursday, November 29th, 2012
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.

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.

KAIST Graph Theory Day 2011

Sunday, April 3rd, 2011
KAIST Graph Theory Day 2011
2011/5/10 Tuesday (Room: 1501, Building E6-1)

Poster (KAIST Graph Theory Day)

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.

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 Kt-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 Kt has genus Ω(t2).
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.

Maria Chudnovsky, Packing seagulls in graphs with no stable set of size three

Monday, April 13th, 2009
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
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.