***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: János Pach (Rényi Institute, Budapest and MIPT, Moscow)

Thursday 12th November, 3:00 via Zoom.

Title: On the Erdos-Hajnal conjecture for ordered graphs


An ordered graph is a graph with a linear ordering on its vertex
set. We prove that for every positive integer k, there exists a constant
c=c(k)>0 such that any ordered graph G on n vertices with the
property that neither G nor its complement contains an induced monotone
path of size k, has either a clique or an independent set of size at
least n^c. This strengthens a theorem of Bousquet, Lagoutte, and
Thomasse, who proved the analogous statement for unordered graphs. Joint
work with Istvan Tomon.


		----------------------------------

Next week: no talk.

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)