Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Perfect Matchings in Random Sparsifications of Dirac Hypergraphs

  • Original Paper
  • Published:
Combinatorica Aims and scope Submit manuscript

Abstract

For all integers \(n \ge k > d \ge 1\), let \(m_{d}(k,n)\) be the minimum integer \(D \ge 0\) such that every k-uniform n-vertex hypergraph \({\mathcal {H}}\) with minimum d-degree \(\delta _{d}({\mathcal {H}})\) at least D has an optimal matching. For every fixed integer \(k \ge 3\), we show that for \(n \in k \mathbb {N}\) and \(p = \Omega (n^{-k+1} \log n)\), if \({\mathcal {H}}\) is an n-vertex k-uniform hypergraph with \(\delta _{k-1}({\mathcal {H}}) \ge m_{k-1}(k,n)\), then a.a.s. its p-random subhypergraph \({\mathcal {H}}_p\) contains a perfect matching. Moreover, for every fixed integer \(d < k\) and \(\gamma > 0\), we show that the same conclusion holds if \({\mathcal {H}}\) is an n-vertex k-uniform hypergraph with \(\delta _d({\mathcal {H}}) \ge m_{d}(k,n) + \gamma \left( {\begin{array}{c}n - d\\ k - d\end{array}}\right) \). Both of these results strengthen Johansson, Kahn, and Vu’s seminal solution to Shamir’s problem and can be viewed as “robust” versions of hypergraph Dirac-type results. In addition, we also show that in both cases above, \({\mathcal {H}}\) has at least \(\exp ((1-1/k)n \log n - \Theta (n))\) many perfect matchings, which is best possible up to an \(\exp (\Theta (n))\) factor.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Data availability

Not applicable.

References

  1. Allen, P., Böttcher, J., Corsten, J., Davies, E., Jenssen, M., Morris, P., Roberts, B., Skokan, J.: A robust Corrádi–Hajnal Theorem. arXiv:2209.01116 (2022)

  2. Alon, N., Frankl, P., Huang, H., Rödl, V., Ruciński, A., Sudakov, B.: Large matchings in uniform hypergraphs and the conjecture of Erdős and Samuels. J. Comb. Theory Ser. A 119, 1200–1215 (2012)

    Google Scholar 

  3. Alon, Y., Krivelevich, M.: Hitting time of edge disjoint Hamilton cycles in random subgraph processes on dense base graphs. SIAM J. Discret. Math. 36, 728–754 (2022)

    MathSciNet  Google Scholar 

  4. Alweiss, R., Lovett, S., Wu, K., Zhang, J.: Improved bounds for the sunflower lemma. Ann. Math. 194, 795–815 (2021)

    MathSciNet  Google Scholar 

  5. Barber, B., Glock, S., Kühn, D., Lo, A., Montgomery, R., Osthus, D.: Minimalist designs. Random Struct. Algorithms 57, 47–63 (2020)

    MathSciNet  Google Scholar 

  6. Barber, B., Kühn, D., Lo, A., Osthus, D.: Edge-decompositions of graphs with high minimum degree. Adv. Math. 288, 337–385 (2016)

    MathSciNet  Google Scholar 

  7. Barber, B., Kühn, D., Lo, A., Osthus, D., Taylor, A.: Clique decompositions of multipartite graphs and completion of Latin squares. J. Comb. Theory Ser. A 151, 146–201 (2017)

    MathSciNet  Google Scholar 

  8. Chang, Y., Ge, H., Han, J., Wang, G.: Matching of given sizes in hypergraphs. SIAM J. Discret. Math. 36, 2323–2338 (2022)

    MathSciNet  Google Scholar 

  9. Chung, F.R.K.: Regularity lemmas for hypergraphs and quasi-randomness. Random Struct. Algorithms 2, 241–252 (1991)

    MathSciNet  Google Scholar 

  10. Condon, P., Espuny Díaz, A., Girão, A., Kühn, D., Osthus, D.: Hamiltonicity of random subgraphs of the hypercube. Mem. Am. Math. Soc. (to appear)

  11. Cooper, C., Frieze, A., Molloy, M., Reed, B.: Perfect matchings in random \(r\)-regular, \(s\)-uniform hypergraphs. Comb. Probab. Comput. 5, 1–14 (1996)

    MathSciNet  Google Scholar 

  12. Dirac, G.A.: Some theorems on abstract graphs. Proc. Lond. Math. Soc. (3) 2, 69–81 (1952)

    MathSciNet  Google Scholar 

  13. Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17, 449–467 (1965)

    MathSciNet  Google Scholar 

  14. Erdős, P., Rényi, A.: On the existence of a factor of degree one of a connected random graph. Acta Math. Acad. Sci. Hungar. 17, 359–368 (1966)

    MathSciNet  Google Scholar 

  15. Erdős, P.: On the combinatorial problems which I would most like to see solved. Combinatorica 1, 25–42 (1981)

    MathSciNet  Google Scholar 

  16. Erdős, P., Rado, R.: Intersection theorems for systems of sets. J. Lond. Math. Soc. 1, 85–90 (1960)

    MathSciNet  Google Scholar 

  17. Ferber, A., Hardiman, L., Mond, A.: Counting Hamiltonian cycles in Dirac hypergraphs. arXiv:2110.15475 (2021)

  18. Ferber, A., Krivelevich, M., Sudakov, B.: Counting and packing Hamilton \(\ell \)-cycles in dense hypergraphs. J. Comb. 7, 135–157 (2016)

    MathSciNet  Google Scholar 

  19. Ferber, A., Kwan, M.: Dirac-type theorems in random hypergraphs. J. Comb. Theory Ser. B 155, 318–357 (2022)

    MathSciNet  Google Scholar 

  20. Frankl, P., Rödl, V.: The uniformity lemma for hypergraphs. Graphs Comb. 8, 309–312 (1992)

    MathSciNet  Google Scholar 

  21. Frankl, P., Kupavskii, A.: The Erdős matching conjecture and concentration inequalities. J. Comb. Theory Ser. B 157, 366–400 (2022)

    Google Scholar 

  22. Frankston, K., Kahn, J., Narayanan, B., Park, J.: Thresholds versus fractional expectation-thresholds. Ann. Math. 194, 475–495 (2021)

    MathSciNet  Google Scholar 

  23. Frieze, A., Janson, S.: Perfect matchings in random \(s\)-uniform hypergraphs. Random Struct. Algorithms 7, 41–57 (1995)

    MathSciNet  Google Scholar 

  24. Frieze, A., Kannan, R.: Quick approximation to matrices and applications. Combinatorica 19, 175–220 (1999)

    MathSciNet  Google Scholar 

  25. Gao, W., Han, J.: Minimum codegree threshold for \(C_6^3\)-factors in 3-uniform hypergraphs. Comb. Probab. Comput. 26, 536–559 (2017)

    Google Scholar 

  26. Gao, W., Han, J., Zhao, Y.: Codegree conditions for tiling complete \(k\)-partite \(k\)-graphs and loose cycles. Comb. Probab. Comput. 28, 840–870 (2019)

    MathSciNet  Google Scholar 

  27. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)

    Google Scholar 

  28. Glebov, R., Luria, Z., Simkin, M.: Perfect matchings in random subgraphs of regular bipartite graphs. J. Graph Theory 97, 208–231 (2021)

    MathSciNet  Google Scholar 

  29. Glock, S., Gould, S., Joos, F., Kühn, D., Osthus, D.: Counting Hamilton cycles in Dirac hypergraphs. Comb. Probab. Comput. 30, 631–653 (2021)

    MathSciNet  Google Scholar 

  30. Glock, S., Kühn, D., Lo, A., Montgomery, R., Osthus, D.: On the decomposition threshold of a given graph. J. Comb. Theory Ser. B 139, 47–127 (2019)

    MathSciNet  Google Scholar 

  31. Glock, S., Kühn, D., Lo, A., Osthus, D.: The existence of designs via iterative absorption: hypergraph \(F\)-designs for arbitrary \(F\). Mem. Am. Math. Soc. 284, v+131 (2023)

    MathSciNet  Google Scholar 

  32. Hajnal, A., Szemerédi, E.: Proof of a Conjecture of P. Erdős, Combinatorial Theory and Its Applications, II (Proceedings in Colloqisum, Balatonfüred, North-Holland, Amsterdam, pp. 601–623 (1969)

  33. Hàn, H., Schacht, M.: Dirac-type results for loose Hamilton cycles in uniform hypergraphs. J. Comb. Theory Ser. B 100, 332–346 (2010)

    MathSciNet  Google Scholar 

  34. Hàn, H., Person, Y., Schacht, M.: On perfect matchings in uniform hypergraphs with large minimum vertex degree. SIAM J. Discret. Math. 23, 732–748 (2009)

    MathSciNet  Google Scholar 

  35. Han, J.: Near perfect matchings in \(k\)-uniform hypergraphs. Comb. Probab. Comput. 24, 723–732 (2015)

    MathSciNet  Google Scholar 

  36. Han, J.: Near perfect matchings in \(k\)-uniform hypergraphs II. SIAM J. Discret. Math. 30, 1453–1469 (2016)

    MathSciNet  Google Scholar 

  37. Johansson, A., Kahn, J., Vu, V.: Factors in random graphs. Random Struct. Algorithms 33, 1–28 (2008)

    MathSciNet  Google Scholar 

  38. Johansson, T.: On Hamilton cycles in Erdős-Rényi subgraphs of large graphs. Random Struct. Algorithms 57, 132–149 (2020)

    Google Scholar 

  39. Kahn, J.: Hitting times for Shamir’s problem. Trans. Am. Math. Soc. 375, 627–668 (2022)

    MathSciNet  Google Scholar 

  40. Kahn, J.: Asymptotics for Shamir’s problem. Adv. Math. 422, 109019, 39 (2023)

    MathSciNet  Google Scholar 

  41. Kahn, J., Kalai, G.: Thresholds and expectation thresholds. Comb. Probab. Comput. 16, 495–502 (2007)

    MathSciNet  Google Scholar 

  42. Kang, D.Y., Kelly, T., Kühn, D., Methuku, A., Osthus, D.: Thresholds for Latin squares and Steiner triple systems: bounds within a logarithmic factor. Trans. Am. Math. Soc. 376, 6623–6662 (2023)

    MathSciNet  Google Scholar 

  43. Karp, R.M.: Reducibility Among Combinatorial Problems. Complexity of Computer Computations, pp. 85–103. Springer, Berlin (1972)

    Google Scholar 

  44. Keevash, P., Mycroft, R.: A geometric theory for hypergraph matching. Mem. Am. Math. Soc. 233, vi+95 (2015)

    MathSciNet  Google Scholar 

  45. Khan, I.: Perfect matchings in 3-uniform hypergraphs with large vertex degree. SIAM J. Discret. Math. 27, 1021–1039 (2013)

    MathSciNet  Google Scholar 

  46. Khan, I.: Perfect matchings in 4-uniform hypergraphs. J. Comb. Theory Ser. B 116, 333–366 (2016)

    MathSciNet  Google Scholar 

  47. Kim, J.H., Vu, V.H.: Concentration of multivariate polynomials and its applications. Combinatorica 20, 417–434 (2000)

    MathSciNet  Google Scholar 

  48. Knox, F., Kühn, D., Osthus, D.: Edge-disjoint Hamilton cycles in random graphs. Random Struct. Algorithms 46, 397–445 (2015)

    MathSciNet  Google Scholar 

  49. Komlós, J., Sárközy, G.N., Szemerédi, E.: Proof of a packing conjecture of Bollobás. Comb. Probab. Comput. 4, 241–255 (1995)

    Google Scholar 

  50. Krivelevich, M., Lee, C., Sudakov, B.: Robust Hamiltonicity of Dirac graphs. Trans. Am. Math. Soc. 366, 3095–3130 (2014)

    MathSciNet  Google Scholar 

  51. Krivelevich, M., Lee, C., Sudakov, B.: Long paths and cycles in random subgraphs of graphs with large minimum degree. Random Struct. Algorithms 46, 320–345 (2015)

    MathSciNet  Google Scholar 

  52. Kühn, D., Osthus, D.: Matchings in hypergraphs of large minimum degree. J. Graph Theory 51, 269–280 (2006)

    MathSciNet  Google Scholar 

  53. Kühn, D., Osthus, D.: Embedding Large Subgraphs into Dense Graphs, Surveys in Combinatorics, London Mathematical Society, Lecture Note Series, vol. 365. Cambridge University Press, Cambridge, pp. 137–167 (2009)

  54. Kühn, D., Osthus, D.: Hamilton decompositions of regular expanders: a proof of Kelly’s conjecture for large tournaments. Adv. Math. 237, 62–146 (2013)

    MathSciNet  Google Scholar 

  55. Kühn, D., Osthus, D., Treglown, A.: Matchings in 3-uniform hypergraphs. J. Comb. Theory Ser. B 103, 291–305 (2013)

    MathSciNet  Google Scholar 

  56. Kwan, M., Sah, A., Sawhney, M., Simkin, M.: High-girth Steiner triple systems. arXiv:2201.04554 (2022)

  57. Lu, H., Yu, X., Yuan, X.: Nearly perfect matchings in uniform hypergraphs. SIAM J. Discret. Math. 35, 1022–1049 (2021)

    MathSciNet  Google Scholar 

  58. Park, J., Pham, H.T.: A proof of the Kahn-Kalai conjecture. J. Am. Math. Soc. 37, 235–243 (2024)

    MathSciNet  Google Scholar 

  59. Pham, H.T., Sah, A., Sawhney, M., Simkin, M.: A toolkit for robust thresholds. arXiv:2210.03064 (2022)

  60. Pósa, L.: Hamiltonian circuits in random graphs. Discret. Math. 14, 359–364 (1976)

    MathSciNet  Google Scholar 

  61. Rödl, V., Ruciński, A.: Dirac-Type Questions for Hypergraphs—A Survey (or More Problems for Endre to Solve), An Irregular Mind, Bolyai Society of Mathematical Studies, vol. 21. János Bolyai Mathematical Society, Budapest, pp. 561–590 (2010)

  62. Rödl, V., Ruciński, A., Szemerédi, E.: Perfect matchings in uniform hypergraphs with large minimum degree. Eur. J. Comb. 27, 1333–1349 (2006)

    MathSciNet  Google Scholar 

  63. Rödl, V., Ruciński, A., Szemerédi, E.: Perfect matchings in large uniform hypergraphs with large minimum collective degree. J. Comb. Theory Ser. A 116, 613–636 (2009)

    MathSciNet  Google Scholar 

  64. Rödl, V., Ruciński, A., Schacht, M., Szemerédi, E.: A note on perfect matchings in uniform hypergraphs with large minimum collective degree. Comment. Math. Univ. Carolin. 49, 633–636 (2008)

    MathSciNet  Google Scholar 

  65. Rödl, V., Ruciński, A., Szemerédi, E.: An approximate Dirac-type theorem for \(k\)-uniform hypergraphs. Combinatorica 28, 229–260 (2008)

    MathSciNet  Google Scholar 

  66. Sah, A., Sawhney, M., Simkin, M.: Threshold for Steiner triple systems. Geom. Funct. Anal. 33, 1141–1172 (2023)

    MathSciNet  Google Scholar 

  67. Schmidt, J., Shamir, E.: A threshold for perfect matchings in random \(d\)-pure hypergraphs. Discret. Math. 45, 287–295 (1983)

    MathSciNet  Google Scholar 

  68. Steger, A.: Die Kleitman–Rothschild Methode, Ph.D. thesis, Rheinische Friedrich-Wilhelms-Universität Bonn (1990)

  69. Sudakov, B.: Robustness of Graph Properties, Surveys in Combinatorics, London Mathematical Society, Lecture Note Series, vol. 440. Cambridge University Press, Cambridge, pp. 372–408 (2017)

  70. Talagrand, M.: Are many small sets explicitly small? In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, pp. 13–36 (2010)

  71. Treglown, A., Zhao, Y.: A note on perfect matchings in uniform hypergraphs, Electron. J. Comb. 23, Paper 1.16, 14 (2016)

  72. Zhao, Y.: Recent Advances on Dirac-Type Problems for Hypergraphs, Recent Trends in Combinatorics, IMA Volume in Mathematical Application, vol. 159. Springer, Cham., pp. 145–165 (2016)

Download references

Author information

Authors and Affiliations

  1. Extremal Combinatorics and Probability Group (ECOPRO), Institute for Basic Science (IBS), Daejeon, South Korea

    Dong Yeap Kang

  2. School of Mathematics, Georgia Institute of Technology, Atlanta, GA, 30332, USA

    Tom Kelly

  3. School of Mathematics, University of Birmingham, Edgbaston, Birmingham, B15 2TT, UK

    Daniela Kühn & Deryk Osthus

  4. Institute of Discrete Mathematics, Graz University of Technology, Graz, Austria

    Vincent Pfenninger

Authors
  1. Dong Yeap Kang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tom Kelly
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Daniela Kühn
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Deryk Osthus
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Vincent Pfenninger
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tom Kelly.

Ethics declarations

Conflicts of interest

The authors have no conflictsof interest to declare that are relevant to the content of this paper.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This project has received partial funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement no. 786198, D. Kang, T. Kelly, D. Kühn, D. Osthus, and V. Pfenninger). Dong Yeap Kang was supported by Institute for Basic Science (IBS-R029-Y6).

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kang, D.Y., Kelly, T., Kühn, D. et al. Perfect Matchings in Random Sparsifications of Dirac Hypergraphs. Combinatorica 44, 1233–1266 (2024). https://doi.org/10.1007/s00493-024-00116-0

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00493-024-00116-0

Keywords

Mathematics Subject Classification

Search

Navigation