A note on the Erdős-Hajnal hypergraph Ramsey problem
| Autor: | Dhruv Mubayi, Andrew Suk, Emily Zhu |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Zdroj: | Proceedings of the American Mathematical Society. 150:3675-3685 |
| ISSN: | 1088-6826 0002-9939 |
| DOI: | 10.1090/proc/15839 |
| Popis: | We show that there is an absolute constant c > 0 c>0 such that the following holds. For every n > 1 n > 1 , there is a 5-uniform hypergraph on at least 2 2 c n 1 / 4 2^{2^{cn^{1/4}}} vertices with independence number at most n n , where every set of 6 vertices induces at most 3 edges. The double exponential growth rate for the number of vertices is sharp. By applying a stepping-up lemma established by the first two authors, analogous sharp results are proved for k k -uniform hypergraphs. This answers the penultimate open case of a conjecture in Ramsey theory posed by Erdős and Hajnal in 1972. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|