Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2308.06070 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916543889145856 |
|---|---|
| author | Łuczak, Tomasz Polcyn, Joanna Reiher, Christian |
| author_facet | Łuczak, Tomasz Polcyn, Joanna Reiher, Christian |
| contents | Let $\mathrm{ex}(n,s)$ denote the maximum number of edges in a triangle-free graph on $n$ vertices which contains no independent sets larger than $s$. The behaviour of $\mathrm{ex}(n,s)$ was first studied by Andrásfai, who conjectured that for $s>n/3$ this function is determined by appropriately chosen blow-ups of so called Andrásfai graphs. Moreover, he proved $\mathrm{ex}(n, s)=n^2-4ns+5s^2$ for $s/n\in [2/5, 1/2]$ and in earlier work we obtained $\mathrm{ex}(n, s)=3n^2-15ns+20s^2$ for $s/n\in [3/8, 2/5]$. Here we make the next step in the quest to settle Andrásfai's conjecture by proving $\mathrm{ex}(n, s)=6n^2-32ns+44s^2$ for $s/n\in [4/11, 3/8]$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_06070 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The next case of Andrásfai's conjecture Łuczak, Tomasz Polcyn, Joanna Reiher, Christian Combinatorics 05C35, 05C69 Let $\mathrm{ex}(n,s)$ denote the maximum number of edges in a triangle-free graph on $n$ vertices which contains no independent sets larger than $s$. The behaviour of $\mathrm{ex}(n,s)$ was first studied by Andrásfai, who conjectured that for $s>n/3$ this function is determined by appropriately chosen blow-ups of so called Andrásfai graphs. Moreover, he proved $\mathrm{ex}(n, s)=n^2-4ns+5s^2$ for $s/n\in [2/5, 1/2]$ and in earlier work we obtained $\mathrm{ex}(n, s)=3n^2-15ns+20s^2$ for $s/n\in [3/8, 2/5]$. Here we make the next step in the quest to settle Andrásfai's conjecture by proving $\mathrm{ex}(n, s)=6n^2-32ns+44s^2$ for $s/n\in [4/11, 3/8]$. |
| title | The next case of Andrásfai's conjecture |
| topic | Combinatorics 05C35, 05C69 |
| url | https://arxiv.org/abs/2308.06070 |