Factors in random graphs

DOI10.1002/RSA.20224MaRDI QIDQ3522827zbMATH OpenOpenAlexWikidataFDO

Authors Anders Johansson, Van Vu, J. Kahn

Publication date 4 September 2008

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

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

zbMATH Keywords

entropymartingaleconcentration inequalitiesrandom graphsfactorrandom hypergraphsShamir's problem

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let $H$ be a fixed graph on $v$ vertices. For an $n$-vertex graph $G$ with $n$ divisible by $v$, an $H$-{em factor} of $G$ is a collection of $n/v$ copies of $H$ whose vertex sets partition $V(G)$. In this paper we consider the threshold $t{h}_H(n)$ of the property that an ErdH{o}s-R'enyi random graph (on $n$ points) contains an $H$-factor. Our results determine $t{h}_H(n)$ for all strictly balanced $H$. The method here extends with no difficulty to hypergraphs. As a corollary, we obtain the threshold for a perfect matching in random $k$-uniform hypergraph, solving the well-known "Shamir's problem."

Recommendations

• Random cliques in random graphs and sharp thresholds for F$$ F $$‐factors
• Triangle Factors in Random Graphs
• Threshold Functions for H-factors
• scientific article; zbMATH DE number 3777557
• \(H(n)\)-factors in random graphs

Cites work

• Perfect Matchings in Random r-regular, s-uniform Hypergraphs

Cited in

(83)

• scientific article; zbMATH DE number 3777557 (Why is no real title available?)
• Thresholds versus fractional expectation-thresholds
• Maker-Breaker games on randomly perturbed graphs
• Packing Hamilton cycles in random and pseudo-random hypergraphs
• Spanning structures and universality in sparse hypergraphs
• Multitrees in random graphs
• On the maximum number of Latin transversals
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor
• Dirac-type theorems in random hypergraphs
• Tilings in randomly perturbed dense graphs
• Clique factors in pseudorandom graphs
• Perfect matchings and loose Hamilton cycles in the semirandom hypergraph model
• Universality for graphs of bounded degeneracy
• Cycle factors and renewal theory
• An analogue of the Erdős-Gallai theorem for random graphs
• An improved upper bound on the density of universal random graphs
• The hitting time of clique factors (extended abstract)
• Factors in randomly perturbed hypergraphs
• Threshold Functions for H-factors
• A note on spanning \(K_r\)-cycles in random graphs
• The hitting time of clique factors
• The square of a Hamilton cycle in randomly perturbed graphs
• Co-degrees resilience for perfect matchings in random hypergraphs
• Sharp thresholds for nonlinear Hamiltonian cycles in hypergraphs
• Hypercontractivity for global functions and sharp thresholds
• Minimal H-factors and covers
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• Threshold for Steiner triple systems
• The approximate Loebl-Komlós-Sós conjecture. I: The sparse decomposition
• A proof of the Kahn–Kalai conjecture
• A smoother notion of spread hypergraphs
• Spanning F-cycles in random graphs
• On Komlós' tiling theorem in random graphs
• Optimal spread for spanning subgraphs of Dirac hypergraphs
• On fractional K‐factors of random graphs
• Weak saturation stability
• Spanning trees in random graphs
• Random cliques in random graphs and sharp thresholds for F$$ F $$‐factors
• Cycles and matchings in randomly perturbed digraphs and hypergraphs
• On spanning structures in random hypergraphs
• A robust Corrádi-Hajnal theorem
• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
• Rainbow Hamilton cycles in random graphs
• Vertex-critical graphs far from edge-criticality
• Tight Hamilton cycles in random hypergraphs
• Almost spanning universality in random graphs
• The threshold bias of the clique-factor game
• Triangle resilience of the square of a Hamilton cycle in random graphs
• Maximal planar subgraphs of fixed girth in random graphs
• Powers of Hamilton cycles in pseudorandom graphs
• On the concentration of the chromatic number of random graphs
• Cycles and matchings in randomly perturbed digraphs and hypergraphs
• Increasing the flexibility of the herding attack
• Hitting times for Shamir's problem
• Pseudorandom hypergraph matchings
• Triangles in randomly perturbed graphs
• Tiling multipartite hypergraphs in quasi-random hypergraphs
• Nonvertex-balanced factors in random graphs
• Universality of random graphs and rainbow embedding
• \(H(n)\)-factors in random graphs
• Optimal threshold for a random graph to be 2-universal
• Random triangles in random graphs
• A note on non-isomorphic edge-color classes in random graphs
• Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process
• 2-universality in randomly perturbed graphs
• Almost all Steiner triple systems are almost resolvable
• Rainbow matchings and Hamilton cycles in random graphs
• Searching for (sharp) thresholds in random structures: where are we now?
• Corrádi and Hajnal's theorem for sparse random graphs
• Finding tight Hamilton cycles in random hypergraphs faster
• Perfect fractional matchings in \(k\)-out hypergraphs
• The triangle-free process and the Ramsey number \(R(3,k)\)
• Cycle Saturation in Random Graphs
• Hamilton -cycles in randomly perturbed hypergraphs
• On the chromatic number in the stochastic block model
• Random perturbation of sparse graphs
• On offset Hamilton cycles in random hypergraphs
• Embedding spanning bounded degree subgraphs in randomly perturbed graphs
• Color-bias perfect matchings in hypergraphs
• Asymptotics for Shamir's problem
• FF‐factors in Quasi‐random Hypergraphs
• Efficient algorithms for three‐dimensional axial and planar random assignment problems

This page was built for publication: Factors in random graphs

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