Turán problems for star-path forests in hypergraphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910945824997376 |
|---|---|
| author | Zhou, Junpeng Yuan, Xiying |
| author_facet | Zhou, Junpeng Yuan, Xiying |
| contents | An $r$-uniform hypergraph ($r$-graph for short) is linear if any two edges intersect at most one vertex. Let $\mathcal{F}$ be a given family of $r$-graphs. An $r$-graph $H$ is called $\mathcal{F}$-free if $H$ does not contain any member of $\mathcal{F}$ as a subgraph. The Turán number of $\mathcal{F}$ is the maximum number of edges in any $\mathcal{F}$-free $r$-graph on $n$ vertices, and the linear Turán number of $\mathcal{F}$ is defined as the Turán number of $\mathcal{F}$ in linear host hypergraphs. An $r$-uniform linear path $P^r_\ell$ of length $\ell$ is an $r$-graph with edges $e_1,\dots,e_\ell$ such that $|V(e_i)\cap V(e_j)|=1$ if $|i-j|=1$, and $V(e_i)\cap V(e_j)=\emptyset$ for $i\neq j$ otherwise. Gyárfás et al. [\textit{European J. Combin.} (2022) 103435] obtained an upper bound for the linear Turán number of $P_\ell^3$. In this paper, an upper bound for the linear Turán number of $P_\ell^r$ is obtained, which generalizes the known result of $P_\ell^3$ to any $P_\ell^r$. Furthermore, some results for the linear Turán number and Turán number of several linear star-path forests are obtained. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_06637 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Turán problems for star-path forests in hypergraphs Zhou, Junpeng Yuan, Xiying Combinatorics An $r$-uniform hypergraph ($r$-graph for short) is linear if any two edges intersect at most one vertex. Let $\mathcal{F}$ be a given family of $r$-graphs. An $r$-graph $H$ is called $\mathcal{F}$-free if $H$ does not contain any member of $\mathcal{F}$ as a subgraph. The Turán number of $\mathcal{F}$ is the maximum number of edges in any $\mathcal{F}$-free $r$-graph on $n$ vertices, and the linear Turán number of $\mathcal{F}$ is defined as the Turán number of $\mathcal{F}$ in linear host hypergraphs. An $r$-uniform linear path $P^r_\ell$ of length $\ell$ is an $r$-graph with edges $e_1,\dots,e_\ell$ such that $|V(e_i)\cap V(e_j)|=1$ if $|i-j|=1$, and $V(e_i)\cap V(e_j)=\emptyset$ for $i\neq j$ otherwise. Gyárfás et al. [\textit{European J. Combin.} (2022) 103435] obtained an upper bound for the linear Turán number of $P_\ell^3$. In this paper, an upper bound for the linear Turán number of $P_\ell^r$ is obtained, which generalizes the known result of $P_\ell^3$ to any $P_\ell^r$. Furthermore, some results for the linear Turán number and Turán number of several linear star-path forests are obtained. |
| title | Turán problems for star-path forests in hypergraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2403.06637 |