Tata Institute of Fundamental Research
Polynomial to Exponential Transition in Ramsey Theory
STCS Seminar
Speaker:
Dhruv Mubayi (University of Illinois at Chicago
Chicago, Illinois, U.S.)
Organiser:
Jaikumar Radhakrishnan
Date:
Tuesday, 6 Aug 2019, 11:30 to 12:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: After a brief introduction to classical hypergraph Ramsey numbers, I will focus on the following problem. What is the minimum t such that there exist arbitrarily large k-uniform hypergraphs whose independence number is at most polylogarithmic in the number of vertices and every s vertices span at most t edges? Erdos and Hajnal conjectured (1972) that this minimum can be calculated precisely using a recursive formula and Erdos offered a $500 prize for a proof. For k = 3, this has been settled for many values of s, but it was not known for larger k.
Here we settle the conjecture for all k at least 4. Our method also answers a question of Bhat and Rodl about the maximum upper density of quasirandom hypergraphs.
This is joint work with Alexander Razborov.
| Speaker: | Dhruv Mubayi (University of Illinois at Chicago Chicago, Illinois, U.S.) |
| Organiser: | Jaikumar Radhakrishnan |
| Date: | Tuesday, 6 Aug 2019, 11:30 to 12:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: After a brief introduction to classical hypergraph Ramsey numbers, I will focus on the following problem. What is the minimum t such that there exist arbitrarily large k-uniform hypergraphs whose independence number is at most polylogarithmic in the number of vertices and every s vertices span at most t edges? Erdos and Hajnal conjectured (1972) that this minimum can be calculated precisely using a recursive formula and Erdos offered a $500 prize for a proof. For k = 3, this has been settled for many values of s, but it was not known for larger k.
Here we settle the conjecture for all k at least 4. Our method also answers a question of Bhat and Rodl about the maximum upper density of quasirandom hypergraphs.
This is joint work with Alexander Razborov.
Here we settle the conjecture for all k at least 4. Our method also answers a question of Bhat and Rodl about the maximum upper density of quasirandom hypergraphs.
This is joint work with Alexander Razborov.