14:00
15:00

[gt.go] - "Recent progress on the Erdos-Hajnal conjecture" by Paul Seymour

/Exposé /Talk/

The EH-conjecture says that for every hereditary class of graphs (except the class of all graphs), there exists c>0 such that every graph G in the class has a clique or stable set of size at least |G|^c. ("Hereditary'' means closed under taking induced subgraphs.) A graph H has the "EH-property'' if the class of graphs not containing H as an induced subgraph satisfies the conjecture.

In joint work with Alex Scott and my student Tung Nguyen, we have made some good progress recently:

(1) It was known that to prove the conjecture, it was enough to prove that prime graphs have the EH-property ("prime'' means not made by substitution from smaller graphs), but only three nontrivial prime graphs were known to have the EH-property. Now we have infinitely many.

(2) In particular, it was not known that the five-vertex path has the EH-property (that was the smallest open case), but we proved that.

(3) We don't know that the 100-vertex path has the EH-property, but it nearly does: there exists c>0 such that every graph |G| not containing a 100-vertex path as an induced subgraph has either a clique of size 2^(log |G|)^{1-o(1)}, or a stable set of size |G|^c.

(4) We proved a conjecture of Fox, Pach and Suk, that for all d>0, the class of all graphs with VC-dimension at most d satisfies the conjecture.

The most difficult of these is (2), and the easiest is (4), and we will sketch a proof of (4).

[Paul Seymour ] (Professor at Princeton University )
[ https://web.math.princeton.edu/~pds/ | https://web.math.princeton.edu/~pds/ ]

Remarks / Remarques

Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .

LaBRI/178 et https://webconf.u-bordeaux.fr/b/mar-ef4-zed