×

Minimum degree of 3-graphs without long linear paths. (English) Zbl 1443.05135

Summary: A well known theorem in graph theory states that every graph \(G\) on \(n\) vertices and minimum degree at least \(d\) contains a path of length at least \(d\), and if \(G\) is connected and \(n \geq 2d + 1\) then \(G\) contains a path of length at least \(2d\) [G. A. Dirac, Proc. Lond. Math. Soc. (3) 2, 69–81 (1952; Zbl 0047.17001)]. In this article, we give an extension of Dirac’s result to hypergraphs. We determine asymptotic lower bounds of the minimum degrees of 3-graphs to guarantee linear paths of specific lengths, and the lower bounds are tight up to an error term depending only on the lengths of the paths.

MSC:

05C65 Hypergraphs
05C38 Paths and cycles
05C07 Vertex degrees
05C35 Extremal problems in graph theory

Citations:

Zbl 0047.17001
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Allen, P.; Böttcher, J.; Cooley, O.; Mycroft, R., Tight cycles and regular slices in dense hypergraphs, J. Combin. Theory Ser. A, 149, 30-100 (2017) · Zbl 1358.05200
[2] Balister, P. N.; Győri, E.; Lehel, J.; Schelp, R. H., Connected graphs without long paths, Discrete Math., 308, 4487-4494 (2008) · Zbl 1159.05029
[3] Bushaw, N.; Kettle, N., Turán number for forests of paths in hypergraphs, SIAM J. Discrete Math., 28, 711-721 (2014) · Zbl 1301.05184
[4] Davoodi, A.; Győri, E.; Methuku, A.; Tompkins, C., An Erdős-Gallai type theorem for uniform hypergraphs, European J. Combin., 69, 159-162 (2018) · Zbl 1376.05099
[5] Dirac, G. A., Some theorems on abstract graphs, Proc. Lond. Math. Soc. (3), 2, 69-81 (1952) · Zbl 0047.17001
[6] Erdős, P.; Gallai, T., On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hung., 10, 337-356 (1959) · Zbl 0090.39401
[7] Faudree, R. J.; Schelp, R. H., Path Ramsey numbers in multicolorings, J. Combin. Theory Ser. B, 19, 150-160 (1975) · Zbl 0286.05111
[8] Furedi, Z.; Jiang, T.; Seiver, R., Exact solution of the hypergraph Turán problem for \(k\)-uniform linear paths, Combinatorica., 34, 299-322 (2014) · Zbl 1324.05192
[9] Győri, E.; Katona, G. Y.; Lemons, N., Hypergraph extensions of the Erdős-Gallai theorem, European J. Combin., 58, 238-246 (2016) · Zbl 1343.05113
[10] Kostochka, A.; Mubayi, D.; Verstraëte, J., Turán problems and shadows I: paths and cycles, J. Combin. Theory Ser. A, 129, 57-79 (2015) · Zbl 1302.05129
[11] Y. Ma, X. Hou, J. Gao, A Dirac-type theorem for uniform hypergraphs, arXiv:2004.05073.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.