Spanning structures and universality in sparse hypergraphs

DOI10.1002/RSA.20690MaRDI QIDQ2953700zbMATH OpenOpenAlexFDO

Authors Yury Person, O. Parczyk

Publication date 5 January 2017

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.02243

zbMATH Keywords

random hypergraphsspanning structuresthresholdsuniversality

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: In this paper the problem of finding various spanning structures in random hypergraphs is studied. We notice that a general result of Riordan [Spanning subgraphs of random graphs, Combinatorics, Probability & Computing 9 (2000), no. 2, 125-148] can be adapted from random graphs to random $r$-uniform hypergaphs and provide sufficient conditions when a random $r$-uniform hypergraph $mathcal{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 $Delta$? For $mathcal{H}^{(r)}(n,p)$ it is shown that this holds for $p=omegaleft((lnn/n{)}^{1/Delta}ight)$ a.a.s. by combining approaches taken by Dellamonica, Kohayakawa, R"odl and Ruci'nski [An improved upper bound on the density of universal random graphs, Random Structures Algorithms 46 (2015), no. 2, 274-299] and of Ferber, Nenadov and Peter [Universality of random graphs and rainbow embedding, Random Structures Algorithms, to appear]. 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"odl, Ruci'nski and Szemer'edi and Alon and Capalbo yield constructions of universal hypergraphs that are sparser than the random hypergraph $mathcal{H}^{(r)}(n,p)$ with $p=omegaleft((lnn/n{)}^{1/Delta}ight)$.

Recommendations

• On spanning structures in random hypergraphs
• Spanning universality in random graphs
• Almost-spanning universality in random graphs
• Spanning trees in random regular uniform hypergraphs
• Almost-spanning universality in random graphs (extended abstract)

Cites work

• Almost-spanning universality in random graphs
• An improved upper bound on the density of universal random graphs
• Approximate counting of regular hypergraphs
• Closing gaps in problems related to Hamilton cycles in random graphs and hypergraphs
• Cycle factors and renewal theory
• Embedding nearly-spanning bounded degree trees
• Embedding spanning trees in random graphs
• Expanders Are Universal for the Class of All Spanning Trees
• Factors in random graphs
• Hamiltonian circuits in random graphs
• Introduction to Random Graphs
• Isometric embeddings into cube-hypergraphs
• Loose Hamilton cycles in random 3-uniform hypergraphs
• Loose Hamilton cycles in random uniform hypergraphs
• On Pósa's conjecture for random graphs
• On the existence of a factor of degree one of a connected random graph
• Sharp threshold for the appearance of certain spanning trees in random graphs
• Spanning Subgraphs of Random Graphs
• Spanning subgraphs of random graphs
• Sparse universal graphs for bounded‐degree graphs
• The threshold for combs in random graphs
• Threshold functions
• Thresholds and Expectation Thresholds
• Tight Hamilton cycles in random hypergraphs
• Tight Hamilton cycles in random uniform hypergraphs
• Universality of random graphs
• Universality of random graphs and rainbow embedding
• Universality of Random Graphs for Graphs of Maximum Degree Two

Cited in

(16)

• On rainbow Hamilton cycles in random hypergraphs
• Embedding spanning bounded degree subgraphs in randomly perturbed graphs
• On offset Hamilton cycles in random hypergraphs
• Phase transition in cohomology groups of non-uniform random simplicial complexes
• Saturation number of Berge stars in random hypergraphs
• L_p regular sparse hypergraphs
• On spanning structures in random hypergraphs
• Hamiltonian Berge cycles in random hypergraphs
• Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs
• Powers of tight Hamilton cycles in randomly perturbed hypergraphs
• Spanning trees in random regular uniform hypergraphs
• On powers of tight Hamilton cycles in randomly perturbed hypergraphs
• Hamilton cycles in the line graph of a random hypergraph
• Spanning F-cycles in random graphs
• The threshold for powers of tight Hamilton cycles in random hypergraphs
• On universal hypergraphs

This page was built for publication: Spanning structures and universality in sparse hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2953700)