Spanning structures and universality in sparse hypergraphs1. Issue 4 (11th October 2016)

• Record Type: Journal Article
• Authors: Parczyk, Olaf; Person, Yury
• Is Part Of: Random structures & algorithms. Volume 49:Issue 4(2016)
• Page Start: 819
• Page End: 844
• Publication Date: 2016-10-11
• Subjects: random hypergraphs -- spanning structures -- thresholds -- universality; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20690
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: In this paper the problem of finding various spanning structures in random hypergraphs is studied. We notice that a general result of Riordan [Combin Probab Comput 9 (2000), 125–148] can be adapted from random graphs to random r ‐uniform hypergraphs and provide sufficient conditions when a random r ‐uniform hypergraph H ( r ) ( n, p ) contains a given spanning structure a.a.s. We also discuss several spanning structures such as cube‐hypergraphs, lattices, spheres, and Hamilton cycles in hypergraphs. Moreover, we study universality, i.e. when does an r ‐uniform hypergraph contain any hypergraph on n vertices and with maximum vertex degree bounded by Δ? For H ( r ) ( n, p ) it is shown that this holds for p ≫ ( ln n / n ) 1 / Δ a.a.s. by combining approaches taken by Dellamonica, Kohayakawa, Rödl and Ruciński [Random Struct Algorithms 46 (2015), 274–299] and of Ferber, Nenadov and Peter [Random Struct Algorithms 48 (2016), 546–564] and of Kim and Lee [SIAM J Discrete Math 28 (2014), 1467–1478]. Furthermore it is shown that the random graph G ( n, p ) for appropriate p and explicit constructions of universal graphs due to Alon, Capalbo, Kohayakawa, Rödl, Ruciński and Szemerédi [Lecture Notes in Comput. Sci., Vol. 2129, Springer, Berlin, 2001, pp. 170–180] and Alon and Capalbo [Random Struct Algorithms 31 (2007), 123–133; Proceedings of the 9th Annual ACM‐SIAM Symposium Society of Industrial and Applied Mathematics, 2008, pp. 373–378] yield constructions of universal hypergraphs that are sparser than the random hypergraph H ( r ) ( n, p ) with p ≫ ( ln n / n ) 1 / Δ © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 819–844, 2016