A note on the minimum size of Turán systems
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_ | 1866910809873973248 |
|---|---|
| author | Liu, Xizhi Pikhurko, Oleg |
| author_facet | Liu, Xizhi Pikhurko, Oleg |
| contents | For positive integers $n \ge s > r$, a \emph{Turán $(n,s,r)$-system} is an $n$-vertex $r$-graph in which every set of $s$ vertices contains at least one edge. Let $T(n,s,r)$ denote the the minimum size of a Turán $(n,s,r)$-system.
Upper bounds on $T(n,s,r)$ were established by Sidorenko~\cite{Sid97} for the case $s-r = Ω(r/\ln r)$ (based on a construction of Frankl--Rödl~\cite{FR85}) and by a number of authors in the case $s-r = O(1)$. In this note, we establish upper bounds in the remaining range $O(1)<s-r = O(r/\ln r)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_15457 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A note on the minimum size of Turán systems Liu, Xizhi Pikhurko, Oleg Combinatorics For positive integers $n \ge s > r$, a \emph{Turán $(n,s,r)$-system} is an $n$-vertex $r$-graph in which every set of $s$ vertices contains at least one edge. Let $T(n,s,r)$ denote the the minimum size of a Turán $(n,s,r)$-system. Upper bounds on $T(n,s,r)$ were established by Sidorenko~\cite{Sid97} for the case $s-r = Ω(r/\ln r)$ (based on a construction of Frankl--Rödl~\cite{FR85}) and by a number of authors in the case $s-r = O(1)$. In this note, we establish upper bounds in the remaining range $O(1)<s-r = O(r/\ln r)$. |
| title | A note on the minimum size of Turán systems |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2501.15457 |