BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:b22a350c-3cec-4ebb-b8f6-58ff354fdf1e
X-WR-CALNAME:[gt.go] - 'Recent progress on the Erdos-Hajnal conjecture' by 
 Paul Seymour
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20260329T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20231029T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20241027T030000
RDATE:20251026T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20240331T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20250330T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:b22a350c-3cec-4ebb-b8f6-58ff354fdf1e
DTSTAMP:20260528T173023Z
CLASS:PUBLIC
DESCRIPTION:/Exposé /Talk/ \n\nThe EH-conjecture says that for every heredi
 tary class of graphs (except the class of all graphs)\, there exists c>0 s
 uch 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 a
 s an induced subgraph satisfies the conjecture. \n\nIn joint work with Ale
 x Scott and my student Tung Nguyen\, we have made some good progress recen
 tly: \n\n(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 s
 ubstitution from smaller graphs)\, but only three nontrivial prime graphs 
 were known to have the EH-property. Now we have infinitely many. \n\n(2) I
 n particular\, it was not known that the five-vertex path has the EH-prope
 rty (that was the smallest open case)\, but we proved that. \n\n(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 pa
 th as an induced subgraph has either a clique of size 2^(log |G|)^{1-o(1)}
 \, or a stable set of size |G|^c. \n\n(4) We proved a conjecture of Fox\, 
 Pach and Suk\, that for all d>0\, the class of all graphs with VC-dimensio
 n at most d satisfies the conjecture. \n\nThe most difficult of these is (
 2)\, and the easiest is (4)\, and we will sketch a proof of (4). \n\n\n[Pa
 ul Seymour ] (Professor at Princeton University ) \n[ https://web.math.pri
 nceton.edu/~pds/ | https://web.math.princeton.edu/~pds/ ] \n\n\nRemarks / 
 Remarques \n\nFind all the information of the working group on this [ http
 s://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web 
 page ] . \nRetrouvez toutes les informations du GT sur cette [ https://gra
 phesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .
DTSTART;TZID=Europe/Paris:20240503T140000
DTEND;TZID=Europe/Paris:20240503T150000
LOCATION:LaBRI/178 et https://webconf.u-bordeaux.fr/b/mar-ef4-zed
SEQUENCE:0
SUMMARY:[gt.go] - 'Recent progress on the Erdos-Hajnal conjecture' by Paul 
 Seymour
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
