Sandwiching random graphs: universality between random graph models

DOI10.1016/j.aim.2003.10.007zbMath1050.05111OpenAlexW2082971831MaRDI QIDQ1886582

Jeong Han Kim, Van H. Vu

Publication date: 18 November 2004

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.aim.2003.10.007

zbMATH Keywords

UniversalityRandom graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Random vibrations in dynamical problems in solid mechanics (74H50)

Related Items (22)

Sandwiching biregular random graphs ⋮ Rainbow Connection of Random Regular Graphs ⋮ Embedding the Erdős-Rényi hypergraph into the random regular hypergraph and Hamiltonicity ⋮ The thresholds for diameter 2 in random Cayley graphs ⋮ A sequential algorithm for generating random graphs ⋮ Small subgraphs of random regular graphs ⋮ The number of perfect matchings, and the nesting properties, of random regular graphs ⋮ On some Multicolor Ramsey Properties of Random Graphs ⋮ Large population limits of Markov processes on random networks ⋮ Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph ⋮ On the restricted size Ramsey number for a pair of cycles ⋮ The average distance and the diameter of dense random regular graphs ⋮ Loose Hamilton Cycles in Regular Hypergraphs ⋮ Preferential attachment without vertex growth: emergence of the giant component ⋮ Local resilience of graphs ⋮ Meyniel's conjecture holds for random graphs ⋮ Local Resilience and Hamiltonicity Maker–Breaker Games in Random Regular Graphs ⋮ On the global strong resilience of fault Hamiltonian graphs ⋮ Edge Correlations in Random Regular Hypergraphs and Applications to Subgraph Testing ⋮ Dirac’s theorem for random regular graphs ⋮ Random regular graphs of non-constant degree: concentration of the chromatic number ⋮ Sandwiching dense random regular graphs between binomial random graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding Hamilton cycles in sparse random graphs
• The asymptotic connectivity of labelled regular graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• The asymptotic number of labeled graphs with given degree sequences
• Turán's extremal problem in random graphs: Forbidding even cycles
• Turán's extremal problem in random graphs: Forbidding odd cycles
• Random regular graphs of high degree
• Random Regular Graphs of Non-Constant Degree: Independence and Chromatic Number
• Random Regular Graphs of Non-Constant Degree: Connectivity and Hamiltonicity
• Local resilience of graphs
• Almost all regular graphs are hamiltonian
• Perfect matchings in random uniform hypergraphs
• Concentration of non‐Lipschitz functions and applications
• Generating Random Regular Graphs Quickly
• On the asymmetry of random regular graphs and random graphs
• Generating random regular graphs
• The chromatic number of random graphs
• The chromatic number of random graphs
• Concentration of multivariate polynomials and its applications

This page was built for publication: Sandwiching random graphs: universality between random graph models