Document Open Access Logo

Vanishing of Cohomology Groups of Random Simplicial Complexes (Keynote Speakers)

Authors Oliver Cooley, Nicola Del Giudice, Mihyun Kang, Philipp Sprüssel

PDF

File

Thumbnail PDF
PDF
LIPIcs.AofA.2018.7.pdf
  • Filesize: 447 kB
  • 14 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Random graphs
  • Mathematics of computing → Hypergraphs
Keywords
  • Random hypergraphs
  • random simplicial complexes
  • sharp threshold
  • hitting time
  • connectedness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We consider k-dimensional random simplicial complexes that are generated from the binomial random (k+1)-uniform hypergraph by taking the downward-closure, where k >= 2. For each 1 <= j <= k-1, we determine when all cohomology groups with coefficients in F_2 from dimension one up to j vanish and the zero-th cohomology group is isomorphic to F_2. This property is not monotone, but nevertheless we show that it has a single sharp threshold. Moreover, we prove a hitting time result, relating the vanishing of these cohomology groups to the disappearance of the last minimal obstruction. Furthermore, we study the asymptotic distribution of the dimension of the j-th cohomology group inside the critical window. As a corollary, we deduce a hitting time result for a different model of random simplicial complexes introduced in [Linial and Meshulam, Combinatorica, 2006], a result which has only been known for dimension two [Kahle and Pittel, Random Structures Algorithms, 2016].

Cite As Get BibTex

Oliver Cooley, Nicola Del Giudice, Mihyun Kang, and Philipp Sprüssel. Vanishing of Cohomology Groups of Random Simplicial Complexes (Keynote Speakers). In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.AofA.2018.7

Author Details

Oliver Cooley
  • Institute of Discrete Mathematics, Graz University of Technology, Steyrergasse 30, 8010 Graz, Austria
Nicola Del Giudice
  • Institute of Discrete Mathematics, Graz University of Technology, Steyrergasse 30, 8010 Graz, Austria
Mihyun Kang
  • Institute of Discrete Mathematics, Graz University of Technology, Steyrergasse 30, 8010 Graz, Austria
Philipp Sprüssel
  • Institute of Discrete Mathematics, Graz University of Technology, Steyrergasse 30, 8010 Graz, Austria

Funding

Supported by Austrian Science Fund (FWF): P27290 and W1230 II

References

  1. L. Aronshtam and N. Linial. When does the top homology of a random simplicial complex vanish? Random Structures Algorithms, 46(1):26-35, 2015. URL: http://dx.doi.org/10.1002/rsa.20495.
  2. L. Aronshtam, N. Linial, T. Łuczak, and R. Meshulam. Collapsibility and vanishing of top homology in random simplicial complexes. Discrete Comput. Geom., 49(2):317-334, 2013. URL: http://dx.doi.org/10.1007/s00454-012-9483-8.
  3. E. Babson, C. Hoffman, and M. Kahle. The fundamental group of random 2-complexes. J. Amer. Math. Soc., 24(1):1-28, 2011. URL: http://dx.doi.org/10.1090/S0894-0347-2010-00677-7.
  4. M. Behrisch, A. Coja-Oghlan, and M. Kang. The order of the giant component of random hypergraphs. Random Structures Algorithms, 36(2):149-184, 2010. URL: http://dx.doi.org/10.1002/rsa.20282.
  5. B. Bollobás and O. Riordan. Asymptotic normality of the size of the giant component in a random hypergraph. Random Structures Algorithms, 41(4):441-450, 2012. URL: http://dx.doi.org/10.1002/rsa.20456.
  6. B. Bollobás and O. Riordan. Exploring hypergraphs with martingales. Random Structures Algorithms, 50(3):325-352, 2017. URL: http://dx.doi.org/10.1002/rsa.20678.
  7. B. Bollobás and A. Thomason. Random graphs of small order. In Random graphs '83 (Poznań, 1983), volume 118 of North-Holland Math. Stud., pages 47-97. North-Holland, Amsterdam, 1985. Google Scholar
  8. O. Cooley, M. Kang, and C. Koch. Threshold and hitting time for high-order connectedness in random hypergraphs. Electron. J. Combin., 23(2):Paper 2.48, 14, 2016. Google Scholar
  9. O. Cooley, M. Kang, and C. Koch. The size of the giant high-order component in random hypergraphs. Random Structures &Algorithms, 2018. URL: http://dx.doi.org/10.1002/rsa.20761.
  10. O. Cooley, M. Kang, and Y. Person. Largest components in random hypergraphs. arXiv:1412.6366, dec Manuscript, 2014. URL: http://arxiv.org/abs/1412.6366.
  11. R. W. R. Darling and J. R. Norris. Structure of large random hypergraphs. Ann. Appl. Probab., 15(1A):125-152, 2005. URL: http://dx.doi.org/10.1214/105051604000000567.
  12. P. Erdős and A. Rényi. On random graphs. I. Publ. Math. Debrecen, 6:290-297, 1959. Google Scholar
  13. A. Frieze and M. Karoński. Introduction to random graphs. Cambridge University Press, Cambridge, 2016. Google Scholar
  14. C. Hoffman, M. Kahle, and E. Paquette. The threshold for integer homology in random d-complexes. Discrete Comput. Geom., 57(4):810-823, 2017. URL: http://dx.doi.org/10.1007/s00454-017-9863-1.
  15. M. Kahle and B. Pittel. Inside the critical window for cohomology of random k-complexes. Random Structures Algorithms, 48(1):102-124, 2016. URL: http://dx.doi.org/10.1002/rsa.20577.
  16. M. Karoński and T. Łuczak. Random hypergraphs. In Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), volume 2 of Bolyai Soc. Math. Stud., pages 283-293. János Bolyai Math. Soc., Budapest, 1996. Google Scholar
  17. N. Linial and R. Meshulam. Homological connectivity of random 2-complexes. Combinatorica, 26(4):475-487, 2006. URL: http://dx.doi.org/10.1007/s00493-006-0027-9.
  18. N. Linial and Y. Peled. On the phase transition in random simplicial complexes. Ann. of Math. (2), 184(3):745-773, 2016. URL: http://dx.doi.org/10.4007/annals.2016.184.3.3.
  19. T. Łuczak and Y. Peled. Integral homology of random simplicial complexes. Discrete Comput. Geom., 59(1):131-142, 2018. URL: http://dx.doi.org/10.1007/s00454-017-9938-z.
  20. R. Meshulam and N. Wallach. Homological connectivity of random k-dimensional complexes. Random Structures Algorithms, 34(3):408-417, 2009. URL: http://dx.doi.org/10.1002/rsa.20238.
  21. J. Munkres. Elements of algebraic topology. Addison-Wesley Publishing Company, Menlo Park, CA, 1984. Google Scholar
  22. D. Poole. On the strength of connectedness of a random hypergraph. Electron. J. Combin., 22(1):Paper 1.69, 16, 2015. Google Scholar
  23. J. Schmidt-Pruzan and E. Shamir. Component structure in the evolution of random hypergraphs. Combinatorica, 5(1):81-94, 1985. URL: http://dx.doi.org/10.1007/BF02579445.
  24. V. E. Stepanov. The probability of the connectedness of a random graph G_m (t). Teor. Verojatnost. i Primenen, 15:58-68, 1970. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact