An Erdős--Trotter problem on antichains with multiplicity $r$ on each occurring level
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912977114890240 |
|---|---|
| author | He, Yixin Tang, Quanyu |
| author_facet | He, Yixin Tang, Quanyu |
| contents | Fix an integer $r\ge2$. For each $n$ we consider families $\mathcal F\subseteq 2^{[n]}$ that form an antichain and have the property that, for every $t$, if there exists $A\in\mathcal F$ with $|A|=t$ then there exist at least $r$ members of $\mathcal F$ of size $t$. A problem of Erdős and Trotter asserts that, for each fixed $r$, there exists a threshold $n_0(r)$ such that whenever $n>n_0(r)$ one can achieve $n-3$ distinct set sizes in such a family, and asks for estimates on $n_0(r)$. We compute that $n_0(2)=3$ and $n_0(3)=8$. For all $r\ge4$ we prove matching linear bounds up to lower-order terms, namely $$ 2r+2 \le n_0(r) \le 2r+2\log_2 r + O(\log_2\log_2 r). $$ In particular, $n_0(r) = 2r + o(r)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_09803 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An Erdős--Trotter problem on antichains with multiplicity $r$ on each occurring level He, Yixin Tang, Quanyu Combinatorics 05D05, 06A07 Fix an integer $r\ge2$. For each $n$ we consider families $\mathcal F\subseteq 2^{[n]}$ that form an antichain and have the property that, for every $t$, if there exists $A\in\mathcal F$ with $|A|=t$ then there exist at least $r$ members of $\mathcal F$ of size $t$. A problem of Erdős and Trotter asserts that, for each fixed $r$, there exists a threshold $n_0(r)$ such that whenever $n>n_0(r)$ one can achieve $n-3$ distinct set sizes in such a family, and asks for estimates on $n_0(r)$. We compute that $n_0(2)=3$ and $n_0(3)=8$. For all $r\ge4$ we prove matching linear bounds up to lower-order terms, namely $$ 2r+2 \le n_0(r) \le 2r+2\log_2 r + O(\log_2\log_2 r). $$ In particular, $n_0(r) = 2r + o(r)$. |
| title | An Erdős--Trotter problem on antichains with multiplicity $r$ on each occurring level |
| topic | Combinatorics 05D05, 06A07 |
| url | https://arxiv.org/abs/2602.09803 |