Positive codegree Andrásfai--Erdős--Sós theorem for the generalized triangle
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917834493263872 |
|---|---|
| author | Liu, Xizhi Ren, Sijie Wang, Jian |
| author_facet | Liu, Xizhi Ren, Sijie Wang, Jian |
| contents | The celebrated Andrásfai--Erdős--Sós Theorem from 1974 shows that every $n$-vertex triangle-free graph with minimum degree greater than $2n/5$ must be bipartite.
We establish a positive codegree extension of this result for the $r$-uniform generalized triangle $\mathrm{T}_{r} = \left\{\{1,\ldots, r-1,r\}, \{1,\ldots, r-1,r+1\},\{r,r+1, \ldots, 2r-1\}\right\}$$\colon$ For every $n \ge (r-1)(2r+1)/2$, if $\mathcal{H}$ is an $n$-vertex $\mathrm{T}_{r}$-free $r$-uniform hypergraph in which each $(r-1)$-tuple of vertices is contained in either zero edges or more than $2n/(2r+1)$ edges of $\mathcal{H}$, then $\mathcal{H}$ is $r$-partite. This result provides the first tight positive codegree Andr{á}sfai--Erdős--Sós type theorem for hypergraphs. It also immediately implies that the positive codegree Turán number of $\mathrm{T}_{r}$ is $\lfloor n/r \rfloor$ for all $r$. Additionally, for $r=3$, our result answers one of the questions posed by Hou et al.~\cite{HLYZZ22} in a strong form. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_07090 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Positive codegree Andrásfai--Erdős--Sós theorem for the generalized triangle Liu, Xizhi Ren, Sijie Wang, Jian Combinatorics The celebrated Andrásfai--Erdős--Sós Theorem from 1974 shows that every $n$-vertex triangle-free graph with minimum degree greater than $2n/5$ must be bipartite. We establish a positive codegree extension of this result for the $r$-uniform generalized triangle $\mathrm{T}_{r} = \left\{\{1,\ldots, r-1,r\}, \{1,\ldots, r-1,r+1\},\{r,r+1, \ldots, 2r-1\}\right\}$$\colon$ For every $n \ge (r-1)(2r+1)/2$, if $\mathcal{H}$ is an $n$-vertex $\mathrm{T}_{r}$-free $r$-uniform hypergraph in which each $(r-1)$-tuple of vertices is contained in either zero edges or more than $2n/(2r+1)$ edges of $\mathcal{H}$, then $\mathcal{H}$ is $r$-partite. This result provides the first tight positive codegree Andr{á}sfai--Erdős--Sós type theorem for hypergraphs. It also immediately implies that the positive codegree Turán number of $\mathrm{T}_{r}$ is $\lfloor n/r \rfloor$ for all $r$. Additionally, for $r=3$, our result answers one of the questions posed by Hou et al.~\cite{HLYZZ22} in a strong form. |
| title | Positive codegree Andrásfai--Erdős--Sós theorem for the generalized triangle |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2411.07090 |