Spanning structures and universality in sparse hypergraphs

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 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 it is shown that this holds for 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 with © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 819–844, 2016