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 - Sophie SpirklExport this event to calendar

Friday, January 26, 2018 — 9:30 AM EST

Title: Sparse graphs with forbidden induced subgraphs and the Erdos-Hajnal conjecture

Speaker: Sophie Spirkl
Affiliation: Princeton University
Room: MC 5501

Abstract:

A graph G is called H-free if it does not contain H as an induced subgraph, i.e. H cannot be obtained from G by deleting vertices. A famous conjecture due to Erdos and Hajnal states that for every graph H, there is a constant c > 0 such that in every n-vertex H-free graph G, there is a set of nc vertices that are either all pairwise adjacent or all pairwise non-adjacent. This conjecture is open, although it has been proved for some graphs H.

I will give some background on this conjecture and discuss recent results (joint with Anita Liebenau, Marcin Pilipczuk, and Paul Seymour) on a variant this problem. The main tool for these results are sparse graphs, i.e. graphs in which no vertex is adjacent to more than small fraction of the vertices.

Location 
MC - Mathematics & Computer Building
5501
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
30
31
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
1
2
3
  1. 2020 (89)
    1. September (11)
    2. August (11)
    3. July (17)
    4. June (11)
    5. May (6)
    6. March (11)
    7. February (11)
    8. 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 (138)
  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)