The Turán number of Berge matchings
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912844913573888 |
|---|---|
| author | Wang, Yichen Yang, Zixuan Zhao, Xiamiao Bai, Yuhang Zhou, Junpeng |
| author_facet | Wang, Yichen Yang, Zixuan Zhao, Xiamiao Bai, Yuhang Zhou, Junpeng |
| contents | Given a graph $F$, an $r$-uniform hypergraph $\mathcal{H}$ is a {\em Berge-$F$} if there is a bijection $ϕ:E(F)\to E(\mathcal{H})$ such that $e\subseteq ϕ(e)$ for each $e\in E(F)$. Given a family $\mathcal{F}$ of $r$-uniform hypergraphs, an $r$-uniform hypergraph is $\mathcal{F}$-free if it does not contain any member of $\mathcal{F}$ as a subhypergraph. The Turán number of $\mathcal{F}$ is the maximum number of hyperedges in an $\mathcal{F}$-free $r$-graph on $n$ vertices. Let $M_{s+1}$ denote a matching of size $s+1$, i.e., the graph consisting of $s+1$ independent edges. Khormali and Palmer [\textit{European J. Combin.} 102 (2022) 103506] completely determined the Turán number of Berge matchings for sufficiently large $n$. Subsequently, Kang, Ni, and Shan [\textit{Discrete Math.} 345 (2022) 112901] determined the exact value of the Turán number of Berge-$M_{s+1}$ for all $n$ when $r \le s-1$ or $r \ge 2s+2$. In this paper, we settle the final open case $s \le r \le 2s+1$, thereby completing the determination of the Turán number of Berge matchings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_05422 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Turán number of Berge matchings Wang, Yichen Yang, Zixuan Zhao, Xiamiao Bai, Yuhang Zhou, Junpeng Combinatorics Given a graph $F$, an $r$-uniform hypergraph $\mathcal{H}$ is a {\em Berge-$F$} if there is a bijection $ϕ:E(F)\to E(\mathcal{H})$ such that $e\subseteq ϕ(e)$ for each $e\in E(F)$. Given a family $\mathcal{F}$ of $r$-uniform hypergraphs, an $r$-uniform hypergraph is $\mathcal{F}$-free if it does not contain any member of $\mathcal{F}$ as a subhypergraph. The Turán number of $\mathcal{F}$ is the maximum number of hyperedges in an $\mathcal{F}$-free $r$-graph on $n$ vertices. Let $M_{s+1}$ denote a matching of size $s+1$, i.e., the graph consisting of $s+1$ independent edges. Khormali and Palmer [\textit{European J. Combin.} 102 (2022) 103506] completely determined the Turán number of Berge matchings for sufficiently large $n$. Subsequently, Kang, Ni, and Shan [\textit{Discrete Math.} 345 (2022) 112901] determined the exact value of the Turán number of Berge-$M_{s+1}$ for all $n$ when $r \le s-1$ or $r \ge 2s+2$. In this paper, we settle the final open case $s \le r \le 2s+1$, thereby completing the determination of the Turán number of Berge matchings. |
| title | The Turán number of Berge matchings |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2510.05422 |