University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Special Seminar - Paul SeymourExport this event to calendar

Tuesday, April 3, 2018 — 10:00 AM EDT

Title: Erdos-Hajnal meets Gyarfas-Sumner

Speaker: Paul Seymour
Affiliation: Princeton
Room: QNC 1501

Abstract:

The Gyarfas-Sumner conjecture says that every graph with huge (enough) chromatic number and bounded clique number contains any given forest as an induced subgraph. (And non-forests do not have this property.) The Erdos-Hajnal conjecture says that for every graph H, all graphs not containing H as an induced subgraph have a clique or stable set of polynomial size.  Both conjectures are well-known, and impossibly difficult.

This talk is about a much nicer problem vaguely related to both of these, the following.  Say an n-vertex graph is ʿʿc-coherentʾʾ if every vertex has degree <cn, and every two disjoint vertex subsets of size at least cn have an edge between them. Which graphs H have the property that all c-coherent graphs contain H if c is small enough?

The answer turns out to be forests (like the Gyarfas-Sumner conjecture, only this time we can prove it); proved in joint work with Maria Chudnovsky, Alex Scott, and Sophie Spirkl a few weeks ago.  This extends some previous theorems (Bousquet, Lagoutte, and Thomasse proved it for paths; and Liebenau, Pilipczuk, Spirkl and I proved it for subdivided caterpillars). All three proofs are quite pretty and I will sketch them if there is time.

The connection with Erdos-Hajnal is, it implies that for every forest H, all graphs that contain neither H nor its complement have two linear sets of vertices that either have no edges between or are complete to each other; and this implies that all such graphs have a polynomial-sized clique or stable set. We also have some results (the four of us with Jacob Fox) about what you can say when you exclude H and its complement, and neither of them is a forest. (You can still get two sets that are complete or anticomplete, but not such big ones.)

Location 
QNC - Quantum Nano Centre
1501
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
  1. 2020 (94)
    1. November (1)
    2. October (3)
    3. September (12)
    4. August (11)
    5. July (17)
    6. June (11)
    7. May (6)
    8. March (11)
    9. February (11)
    10. January (11)
  2. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  3. 2018 (136)
  4. 2017 (103)
  5. 2016 (137)
  6. 2015 (136)
  7. 2014 (88)
  8. 2013 (48)
  9. 2012 (39)
  10. 2011 (36)
  11. 2010 (40)
  12. 2009 (40)
  13. 2008 (39)
  14. 2007 (15)