Hostname: page-component-848d4c4894-xfwgj Total loading time: 0 Render date: 2024-06-25T07:20:43.087Z Has data issue: false hasContentIssue false
  • English
  • Français

Counting spanning subgraphs in dense hypergraphs

Part of: Graph theory Extremal combinatorics

Published online by Cambridge University Press:  30 May 2024

Richard Montgomery  and
Matías Pavez-Signé
Richard Montgomery
Affiliation:
Mathematics Institute, Zeeman Building, University of Warwick, Coventry, UK
Matías Pavez-Signé*
Affiliation:
Center for Mathematical Modeling (CNRS IRL2807), University of Chile, Santiago, Chile
*
Corresponding author: Matías Pavez-Signé; Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We give a simple method to estimate the number of distinct copies of some classes of spanning subgraphs in hypergraphs with a high minimum degree. In particular, for each $k\geq 2$ and $1\leq \ell \leq k-1$, we show that every $k$-graph on $n$ vertices with minimum codegree at least

\begin{equation*} \left \{\begin {array}{l@{\quad}l} \left (\dfrac {1}{2}+o(1)\right )n & \text { if }(k-\ell )\mid k,\\[5pt] \left (\dfrac {1}{\lceil \frac {k}{k-\ell }\rceil (k-\ell )}+o(1)\right )n & \text { if }(k-\ell )\nmid k, \end {array} \right . \end{equation*}
contains $\exp\!(n\log n-\Theta (n))$ Hamilton $\ell$-cycles as long as $(k-\ell )\mid n$. When $(k-\ell )\mid k$, this gives a simple proof of a result of Glock, Gould, Joos, Kühn, and Osthus, while when $(k-\ell )\nmid k$, this gives a weaker count than that given by Ferber, Hardiman, and Mond, or when $\ell \lt k/2$, by Ferber, Krivelevich, and Sudakov, but one that holds for an asymptotically optimal minimum codegree bound.

Keywords

Degree conditionsspanning subgraphshypergraphs

MSC classification

Primary: 05C35: Extremal problems
Secondary: 05C65: Hypergraphs 05D40: Probabilistic methods
Type
Paper
Information
Combinatorics, Probability and Computing , First View , pp. 1 - 13
Check for updates
Copyright
© The Author(s), 2024. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Allen, P., Böttcher, J., Corsten, J., Davies, E., Jenssen, M., Morris, P., Roberts, B. and Skokan, J. (2022) A robust Corrádi–Hajnal theorem. arXiv preprint arXiv: 2209.01116.Google Scholar
Barber, B., Kühn, D., Lo, A. and Osthus, D. (2016) Edge-decompositions of graphs with high minimum degree. Adv Math 288 337–385.CrossRefGoogle Scholar
Bedenknecht, W. and Reiher, C. (2020) Squares of Hamiltonian cycles in 3-uniform hypergraphs. Rand Struct Algor 56(2) 339–372.CrossRefGoogle Scholar
Bolobás, B. (1995) Extremal graph theory. In:Handbook of combinatorics, pp.1231–1292.Google Scholar
Bondy, J. A. (1995) Basic graph theory: paths and circuits. In Handbook of combinatorics, pp. 3–110.Google Scholar
Böttcher, J., Schacht, M. and Taraz, A. (2009) Proof of the bandwidth conjecture of Bollobás and Komlós. Math Ann 343(1) 175–205.CrossRefGoogle Scholar
Csaba, B., Levitt, I., Nagy-György, J. and Szemeredi, E. (2010) Tight bounds for embedding bounded degree trees, In:Fete of Combinatorics and Computer Science, Vol.20. Springer, pp. 95–137.CrossRefGoogle Scholar
Cuckler, B. and Kahn, J. (2009) Hamiltonian cycles in Dirac graphs. Combinatorica 29(3) 299–326.CrossRefGoogle Scholar
Daykin, D. E. and Häggkvist, R. (1981) Degrees giving independent edges in a hypergraph. Bull Aust Math Soc 23(1) 103–109.CrossRefGoogle Scholar
Dirac, G. A. (1952) Some theorems on abstract graphs. Proc Lond Math Soc s3-2(1) 69–81.CrossRefGoogle Scholar
Ferber, A., Hardiman, L. and Mond, A. (2023) Counting Hamiltonian cycles in Dirac hypergraphs. Combinatorica 43(4) 665–680.CrossRefGoogle Scholar
Ferber, A., Krivelevich, M. and Sudakov, B. (2016) Counting and packing Hamilton $\ell$ -cycles in dense hypergraphs. J Comb 7(1) 135–157.Google Scholar
Glock, S., Gould, S., Joos, F., Kühn, D. and Osthus, D. (2021) Counting Hamilton cycles in Dirac hypergraphs. Combin Probab Comput 30(4) 631–653.CrossRefGoogle Scholar
Gupta, P., Hamann, F., Müyesser, A., Parczyk, O. and Sgueglia, A. (2023) A general approach to transversal versions of Dirac-type theorems. Bull Lond Math Soc 55(6) 2817–2839.CrossRefGoogle Scholar
Hajnal, A. and Szemerédi, E. (1970) Proof of a conjecture of P. Erdős. Combin Theory Appl 2 601–623.Google Scholar
Janson, S. (1994) The numbers of spanning trees, Hamilton cycles and perfect matchings in a random graph. Combin Probab Comput 3(1) 97–126.CrossRefGoogle Scholar
Janson, S., uczak, T.Ł. and Rucinski, A. (2000) Random graphs. Wiley-Interscience, Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000 CrossRefGoogle Scholar
Kang, D. Y., Kelly, T., Kühn, D., Osthus, D. and Pfenninger, V. (2022) Perfect matchings in random sparsifications of Dirac hypergraphs. arXiv preprint arXiv: 2211.01325, 2022.Google Scholar
Komlós, J., Sárközy, G. N. and Szemerédi, E. (1995) Proof of a packing conjecture of Bollobás. Combin Probab Comput 4(3) 241–255.CrossRefGoogle Scholar
Komlós, J., Sárközy, G. N. and Szemerédi, E. (1998) Proof of the Seymour conjecture for large graphs. Ann Comb 2(1) 43–60.CrossRefGoogle Scholar
Komlós, J., Sárközy, G. N. and Szemerédi, E. (2001) Proof of the Alon-Yuster conjecture. Discret Math 235(1-3) 255–269.CrossRefGoogle Scholar
Komlós, J., Sárközy, G. N. and Szemerédi, E. (2001) Spanning trees in dense graphs. Combin Probab Comput 10(5) 397–416.CrossRefGoogle Scholar
Komlós, J., Sárközy, G. N. and Szemerédi, E. (1998) On the Pósa-Seymour conjecture. J Graph Theory 29(3) 167–176.3.0.CO;2-O>CrossRefGoogle Scholar
Kühn, D., Mycroft, R. and Osthus, D. (2010) Hamilton $\ell$ -cycles in uniform hypergraphs. J Combin Theory Ser A 117(7) 910–927.CrossRefGoogle Scholar
Kühn, D. and Osthus, D. (2009) Embedding large subgraphs into dense graphs. In:London Mathematical Society Lecture Notes, 365, Cambridge University Press.Google Scholar
Kühn, D. and Osthus, D. (2009) The minimum degree threshold for perfect graph packings. Combinatorica 29(1) 65–107.CrossRefGoogle Scholar
Kühn, D. and Osthus, D. (2014) Hamilton cycles in graphs and hypergraphs: An extremal perspective. In: 2014 International Congress of Mathematicians, ICM, pp. 381–406.Google Scholar
McDiarmid, C. (1989) On the method of bounded differences. In: Surveys in Combinatorics, 1989: Invited Papers at the Twelfth British Combinatorial Conference, Cambridge University Press, pp. 148–188.CrossRefGoogle Scholar
Pavez-Signé, M., Sanhueza-Matamala, N. and Stein, M. (2023) Towards a hypergraph version of the Pósa-Seymour conjecture. Adv Comb 2023(3) 29.Google Scholar
Pham, H. T., Sah, A., Sawhney, M. and Simkin, M. (2023) A toolkit for robust thresholds.Google Scholar
Rödl, V., Szemerédi, E. and Ruciński, A. (2008) An approximate Dirac-type theorem for k-uniform hypergraphs. Combinatorica 28(2) 229–260.CrossRefGoogle Scholar
Simonovits, M. and Szemerédi, E. (2019) Embedding graphs into larger graphs: results, methods, and problems. In: Building Bridges II: Mathematics of László Lovász, pp. 445–592.CrossRefGoogle Scholar
Sárközy, G. N., Selkow, S. M. and Szemerédi, E. (2003) On the number of Hamiltonian cycles in Dirac graphs. Discrete Math 265(1) 237–250.CrossRefGoogle Scholar
Zhao, Y. (2016) Recent advances on Dirac-type problems for hypergraphs. In: Recent Trends in Combinatorics, pp. 145–165.CrossRefGoogle Scholar