3-uniform linear hypergraphs without a long Berge path

EUROCOMB’23

Abstract
Extensions of the Erdős-Gallai theorem for general hypergraphs are well studied. In this work, we prove the extension of the Erdős-Gallai theorem for linear hypergraphs. In particular, we show that the number of hyperedges in an $n$-vertex $3$-uniform linear hypergraph, without a Berge path of length $k$ as a subgraph is at most $\frac{(k-1)}{6}n$ for $k\geq 4$. This is an extended abstract for EUROCOMB23 of the manuscript arXiv:2211.16184.

Pages:
532–538
References

Paul N Balister, E Győri, Jenő Lehel, and Richard H Schelp. Connected graphs without long paths. Discrete Mathematics, 308(19):4487-4494, 2008.
https://doi.org/10.1016/j.disc.2007.08.047

Claude Berge. Graphs and hypergraphs. North-Holland, 1973.

Akbar Davoodi, Ervin Győri, Abhishek Methuku, and Casey Tompkins. An Erdős-Gallai type theorem for uniform hypergraphs. European Journal of Combinatorics, 69:159-162, 2018.
https://doi.org/10.1016/j.ejc.2017.10.006

Zoltán Füredi, Alexandr Kostochka, and Ruth Luo. Avoiding long Berge cycles ii, exact bounds for all n. arXiv preprint arXiv:1807.06119, 2018.
https://doi.org/10.1016/j.jctb.2018.12.001

Zoltán Füredi, Alexandr Kostochka, and Ruth Luo. Avoiding long Berge cycles. Journal of Combinatorial Theory, Series B, 137:55-64, 2019.
https://doi.org/10.1016/j.jctb.2018.12.001

Zoltán Füredi, Alexandr Kostochka, and Ruth Luo. On 2-connected hypergraphs with no long cycles. arXiv preprint arXiv:1901.11159, 2019.
https://doi.org/10.37236/8488

Zoltán Füredi, Alexandr Kostochka, Ruth Luo, and Jacques Verstraëte. Stability in the Erdős-Gallai theorem on cycles and paths, II. Discrete Mathematics, 341(5):1253-1263, 2018.
https://doi.org/10.1016/j.disc.2017.12.018

Zoltán Füredi, Alexandr Kostochka, and Jacques Verstraëte. Stability in the Erdős-Gallai theorems on cycles and paths. Journal of Combinatorial Theory, Series B, 121:197-228, 2016.
https://doi.org/10.1016/j.jctb.2016.06.004

Dániel Gerbner, Dániel Nagy, Balázs Patkós, Nika Salia, and Máté Vizer. Stability of extremal connected hypergraphs avoiding Berge-paths. arXiv preprint arXiv:2008.02780, 2020.
https://doi.org/10.1007/978-3-030-83823-2_19

András Gyárfás, Miklós Ruszinkó, and Gábor N Sárközy. Linear Turán numbers of acyclic triple systems. European Journal of Combinatorics, 99:103435, 2022.
https://doi.org/10.1016/j.ejc.2021.103435

Ervin Győri, Gyula Y Katona, and Nathan Lemons. Hypergraph extensions of the Erdős-Gallai theorem. European Journal of Combinatorics, 58:238-246, 2016.
https://doi.org/10.1016/j.ejc.2016.05.012

Ervin Győri, Nathan Lemons, Nika Salia, and Oscar Zamora. The structure of hypergraphs without long Berge cycles. Journal of Combinatorial Theory, Series B, 2020.
https://doi.org/10.1016/j.jctb.2020.04.007

Ervin Győri, Abhishek Methuku, Nika Salia, Casey Tompkins, and Máté Vizer. On the maximum size of connected hypergraphs without a path of given length. Discrete Mathematics, 341(9):2602-2605, 2018.
https://doi.org/10.1016/j.disc.2018.06.006

Ervin Győri and Nika Salia. Linear three-uniform hypergraphs with no berge path of given length. arXiv preprint arXiv:2211.16184, 2022.

Ervin Győri, Nika Salia, and Oscar Zamora. Connected hypergraphs without long berge-paths. European Journal of Combinatorics, 96:103353, 2021.
https://doi.org/10.1016/j.ejc.2021.103353

GN Kopylov. On maximal paths and cycles in a graph. In Doklady Akademii Nauk, volume 234, pages 19-21. Russian Academy of Sciences, 1977.

Alexandr Kostochka and Ruth Luo. On r-uniform hypergraphs with circumference less than r. Discrete Applied Mathematics, 276:69-91, 2020
https://doi.org/10.1016/j.dam.2019.07.011

Metrics

0

Views

0

PDF views