Spanning structures and universality in sparse hypergraphs
Spanning structures and universality in sparse hypergraphs
复制标题
DOI：
10.1002/rsa.20690
复制
发表时间：
2015-04
影响因子：
1
通讯作者：
Olaf Parczyk;Y. Person
中科院分区：
文献类型：
--
作者：
Olaf Parczyk;Y. Person
在本文中，研究了在随机超图中找到各种跨度结构的问题。当随机的R-均匀高图H（r）（n，p）包含给定的跨度结构A.A.S.时提供足够的条件多维数据库，晶格，球体和汉密尔顿周期，我们研究普遍性，即何时在N顶点上含有任何n均匀的超图和最大的顶点，p）表明，通过结合Dellamonica，Kohayakawa，Rödl和Ruciński[随机结构算法46（2015），274–299]和Ferber，Nenadov和Peter [随机结构算法48（2016），546–564]和Kim和Lee [Siam J Inveth Math 28（2014），1467-1478]结果表明，由于Alon，Capalbo，Kohayakawa，Rödl，Ruciński和szemerédi，在适当的P和明确图的随机图G（n，p）中Comput。和应用数学，2008年，pp。373–378]比随机超图H（r）（n，p）更稀疏的通用超图的屈服构造p≫（LNN/N）1/δ©2016 Wiley Werdionals，Inc。随机结构。
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≫(lnn/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≫(lnn/n)1/Δ © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 819–844, 2016