Seminars & Colloquia Calendar
Ramsey's Theorem in the countable and the approximate Erd?s-Hajnal property
Leonardo Coregliano (IAS)
Location: Hill Center 705
Date & time: Monday, 21 March 2022 at 2:00PM - 3:00PM
Abstract: The celebrated Erd?s-Hajnal Conjecture says that in any proper hereditary class of finite graphs we are guaranteed to have a clique or anti-clique of size \(n^c\), which is a much better bound than the logarithmic size that is provided by Ramsey's Theorem in general. On the other hand, in uncountable cardinalities, the model-theoretic property of stability guarantees a uniform set much larger than the bound provided by the Erd?s-Rado Theorem in general. However, in the case of countable structures balanced between these two, all structures seem to behave in the same way since the infinite version of Ramsey's Theorem already yields a uniform set of the maximum possible cardinality.
By instead considering a different notion of large sets, namely, that of positive upper density and ignoring negligible errors, we show that the same phenomenon happens in the countable: a countable graph has a large almost clique or a large almost anti-clique if and only if it has a large almost stable set. Similarly, in the countable we can consider a variant Erd?s-Hajnal property: we say that a hereditary class of finite graphs \(C\) has the approximate Erd?s-Hajnal property (AEHP) if every countable graph whose finite induced subgraphs are all in \(C\) must contain a large almost clique or a large almost anti-clique. Surprisingly, AEHP has a simple characterization as precisely those classes that avoid some recursive blow-up of the 4-cycle.
In this talk, I will explain how these problems are reduced to problems for limits of dense graph sequences (graphons) and show how the corresponding graphon problems have very clean combinatorial proofs. No background knowledge in model theory or in the theory of graphons will be required.
This talk is based on joint work with Maryanthe Malliaris.
Chiara Damiolini, Ian Coley and Franco Rota -Charles Weibel Organizer's Page
Wujun Zhang Organizer's webpage
Ziming Shi, Sagun Chanillo, Xiaojun Huang, Chi Li, Jian Song Seminar website Old seminar website
Swastik Kopparty, Sepehr Assadi Seminar webpage
Jeffry Kahn, Bhargav Narayanan, Jinyoung Park Organizer's webpage
Brooke Ogrodnik, Website
Robert Dougherty-Bliss and Doron Zeilberger --> homepage
Paul Feehan, Daniel Ketover, Natasa Sesum Organizer's webpage
Lev Borisov, Emanuel Diaconescu, Angela Gibney, Nicolas Tarasca, and Chris Woodward Organizer's webpage
Jason Saied Seminar webpage
Brian Pinsky, Rashmika Goswami website
Quentin Dubroff Organizer's webpage
James Holland; Organizer website
Edna Jones Organizer's webpage
Brooke Ogrodnik website
Yanyan Li, Zheng-Chao Han, Jian Song, Natasa Sesum Organizer's Webpage
Organizer: Luochen Zhao
Yanyan Li, Zheng-Chao Han, Natasa Sesum, Jian Song Organizer's Page
Lisa Carbone, Yi-Zhi Huang, James Lepowsky, Siddhartha Sahi Organizer's webpage
Simon Thomas website
Kasper Larsen, Daniel Ocone and Kim Weston Organizer's page
Joel Lebowitz, Michael Kiessling
Yanyan Li, Haim Brezis Organizer's Webpage
Stephen D. Miller, John C. Miller, Alex V. Kontorovich, Alex Walker seminar website
Stephen D. Miller
Brooke Ogrodnik, Website
Organizers: Yanyan Li, Z.C. Han, Jian Song, Natasa Sesum
Yael Davidov Seminar webpage
Kristen Hendricks, Xiaochun Rong, Hongbin Sun, Chenxi Wu Organizer's page
Fioralba Cakoni Seminar webpage
Ebru Toprak, Organizer
- Show events from all categories
Special Note to All Travelers
Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.
Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.