Combining the theorems of Turán and de Bruijn-Erd\H os
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913583440330752 |
|---|---|
| author | Chakravarty, Sayok Mubayi, Dhruv |
| author_facet | Chakravarty, Sayok Mubayi, Dhruv |
| contents | Fix an integer $s \ge 2$. Let $\mathcal{P}$ be a set of $n$ points and let $\mathcal{L}$ be a set of lines in a linear space such that no line in $\mathcal{L}$ contains more than $(n-1)/(s-1)$ points of $\mathcal{P}$. Suppose that for every $s$-set $S$ in $\mathcal{P}$, there is a pair of points in $S$ that lies in a line from $\mathcal{L}$. We prove that $|\mathcal{L}| \ge (n-1)/(s-1)+s-1$ for $n$ large, and this is sharp when $n-1$ is a multiple of $s-1$. This generalizes the de Bruijn-Erd\H os theorem which is the case $s=2$. Our result is proved in the more general setting of linear hypergraphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_14634 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Combining the theorems of Turán and de Bruijn-Erd\H os Chakravarty, Sayok Mubayi, Dhruv Combinatorics 05B05, 05B25, 05D05 Fix an integer $s \ge 2$. Let $\mathcal{P}$ be a set of $n$ points and let $\mathcal{L}$ be a set of lines in a linear space such that no line in $\mathcal{L}$ contains more than $(n-1)/(s-1)$ points of $\mathcal{P}$. Suppose that for every $s$-set $S$ in $\mathcal{P}$, there is a pair of points in $S$ that lies in a line from $\mathcal{L}$. We prove that $|\mathcal{L}| \ge (n-1)/(s-1)+s-1$ for $n$ large, and this is sharp when $n-1$ is a multiple of $s-1$. This generalizes the de Bruijn-Erd\H os theorem which is the case $s=2$. Our result is proved in the more general setting of linear hypergraphs. |
| title | Combining the theorems of Turán and de Bruijn-Erd\H os |
| topic | Combinatorics 05B05, 05B25, 05D05 |
| url | https://arxiv.org/abs/2411.14634 |