[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 ] .