Sandwiching random graphs: universality between random graph models

DOI10.1016/j.aim.2003.10.007zbMath1050.05111MaRDI 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

Universality; Random graphs

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

60C05: Combinatorial probability

74H50: Random vibrations in dynamical problems in solid mechanics

Related Items

Edge Correlations in Random Regular Hypergraphs and Applications to Subgraph Testing, On some Multicolor Ramsey Properties of Random Graphs, Loose Hamilton Cycles in Regular Hypergraphs, Embedding the Erdős-Rényi hypergraph into the random regular hypergraph and Hamiltonicity, A sequential algorithm for generating random graphs, Small subgraphs of random regular graphs, Random regular graphs of non-constant degree: concentration of the chromatic number, Meyniel's conjecture holds for random graphs, The thresholds for diameter 2 in random Cayley graphs, Local Resilience and Hamiltonicity Maker–Breaker Games in Random Regular Graphs, Rainbow Connection of Random Regular Graphs, Local resilience of 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