Groupe

GT

Seminars are given every Friday from 2:00 to 3:00 (usually in room 178, but not for the time being). You are welcome 10 minutes earlier for tea, coffee and cake.

In order to receive the announcements, just send an email to sympa@diff.u-bordeaux.fr with subject "subscribe labri.go-gt Cookie Monster", where Cookie is your first name and Monster your last name.

See the agenda of the seminars: webmel.u-bordeaux.fr/service/user/bf-labri.go@u-bordeaux.fr/gt.html https://webmel.u-bordeaux.fr/home/bf-labri.ca@u-bordeaux.fr/gt.go.html; to add it to yours webmel.u-bordeaux.fr/service/user/bf-labri.go@u-bordeaux.fr/gt.ics https://webmel.u-bordeaux.fr/home/bf-labri.ca@u-bordeaux.fr/gt.go.ics , or flash the following QRCode:

Next talks:

The online talks are available here : https://webconf.u-bordeaux.fr/b/mar-ef4-zed.

Vendredi 3 Mai à 14h - Paul Seymour
Recent progress on the Erdos-Hajnal conjecture
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).

Jobs

Group

GT Graphs and Optimization

History

 Previous Years

edit SideBar

Blix theme adapted by David Gilbert, powered by PmWiki