Constructions of Turán systems that are tight up to a multiplicative constant
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916599368253440 |
|---|---|
| author | Pikhurko, Oleg |
| author_facet | Pikhurko, Oleg |
| contents | For positive integers $n\ge s> r$, the Turán function $T(n,s,r)$ is the smallest size of an r-graph with n vertices such that every set of s vertices contains at least one edge. Also, define the Turán density $t(s,r)$ as the limit of $T(n,s,r)/ {n\choose r}$ as $n\to\infty$. The question of estimating these parameters received a lot of attention after it was first raised by Turán in 1941. A trivial lower bound is $t(s,r)\ge 1/{s\choose s-r}$. In the early 1990s, de Caen conjectured that $r\cdot t(r+1,r)\to\infty$ as $r\to\infty$ and offered 500 Canadian dollars for resolving this question.
We disprove this conjecture by showing more strongly that for every integer $R\ge1$ there is $μ_R$ (in fact, $μ_R$ can be taken to grow as $(1+o(1))\, R\ln R$) such that $t(r+R,r)\le (μ_R+o(1))/ {r+R\choose R}$ as $r\to\infty$, that is, the trivial lower bound is tight for every $R$ up to a multiplicative constant $μ_R$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_07443 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Constructions of Turán systems that are tight up to a multiplicative constant Pikhurko, Oleg Combinatorics For positive integers $n\ge s> r$, the Turán function $T(n,s,r)$ is the smallest size of an r-graph with n vertices such that every set of s vertices contains at least one edge. Also, define the Turán density $t(s,r)$ as the limit of $T(n,s,r)/ {n\choose r}$ as $n\to\infty$. The question of estimating these parameters received a lot of attention after it was first raised by Turán in 1941. A trivial lower bound is $t(s,r)\ge 1/{s\choose s-r}$. In the early 1990s, de Caen conjectured that $r\cdot t(r+1,r)\to\infty$ as $r\to\infty$ and offered 500 Canadian dollars for resolving this question. We disprove this conjecture by showing more strongly that for every integer $R\ge1$ there is $μ_R$ (in fact, $μ_R$ can be taken to grow as $(1+o(1))\, R\ln R$) such that $t(r+R,r)\le (μ_R+o(1))/ {r+R\choose R}$ as $r\to\infty$, that is, the trivial lower bound is tight for every $R$ up to a multiplicative constant $μ_R$. |
| title | Constructions of Turán systems that are tight up to a multiplicative constant |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2406.07443 |