Intersecting hypergraphs with large cover number
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908318389239808 |
|---|---|
| author | Bucić, Matija Jain, Vanshika Sivashankar, Varun |
| author_facet | Bucić, Matija Jain, Vanshika Sivashankar, Varun |
| contents | In their famous 1974 paper introducing the local lemma, Erdős and Lovász posed a question-later referred by Erdős as one of his three favorite open problems: What is the minimum number of edges in an $r$-uniform, intersecting hypergraph with cover number $r$? This question was solved up to a constant factor in Kahn's remarkable 1994 paper. More recently, motivated by applications to Bollobás' ''power of many colours'' problem, Alon, Bucić, Christoph, and Krivelevich introduced a natural generalization by imposing a space constraint that limits the hypergraph to use only $n$ vertices. In this note we settle this question asymptotically, up to a logarithmic factor in $n/r$ in the exponent, for the entire range. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_14918 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Intersecting hypergraphs with large cover number Bucić, Matija Jain, Vanshika Sivashankar, Varun Combinatorics 05D05 In their famous 1974 paper introducing the local lemma, Erdős and Lovász posed a question-later referred by Erdős as one of his three favorite open problems: What is the minimum number of edges in an $r$-uniform, intersecting hypergraph with cover number $r$? This question was solved up to a constant factor in Kahn's remarkable 1994 paper. More recently, motivated by applications to Bollobás' ''power of many colours'' problem, Alon, Bucić, Christoph, and Krivelevich introduced a natural generalization by imposing a space constraint that limits the hypergraph to use only $n$ vertices. In this note we settle this question asymptotically, up to a logarithmic factor in $n/r$ in the exponent, for the entire range. |
| title | Intersecting hypergraphs with large cover number |
| topic | Combinatorics 05D05 |
| url | https://arxiv.org/abs/2503.14918 |