Graph Theory and Combinatorics Seminar
- Event Type
- Seminar/Symposium
- Sponsor
- Department of Mathematics
- Location
- Gregory Hall 327
- Date
- Aug 27, 2024 1:00 pm
- Speaker
- Matija Bucić (Princeton)
- Contact
- Peter Bradshaw
- pb38@illinois.edu
- Views
- 55
- Originating Calendar
- Combinatorics Research Area Calendar
Speaker: Matija Bucić (Princeton)
Title: Equivalence between Erdős-Hajnal and polynomial Rödl and Nikiforov conjectures
Abstract: It is well-known that polynomial versions of theorems of Rödl and Nikiforov, as conjectured by Fox and Sudakov and Nguyen, Scott and Seymour imply the classical Erdős-Hajnal conjecture. We prove that these three conjectures are in fact equivalent, extending several previous particular results in this direction by Fox, Nguyen, Scott and Seymour; Nguyen, Scott and Seymour and Gishboliner and Shapira.
Joint work with Fox and Pham.