The phase transition in random graphs: A simple proof
From MaRDI portal
Publication:2852544
DOI10.1002/rsa.20470zbMath1272.05181arXiv1201.6529OpenAlexW2110089205MaRDI QIDQ2852544
Michael Krivelevich, Benjamin Sudakov
Publication date: 9 October 2013
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1201.6529
Related Items (37)
Large complete minors in random subgraphs ⋮ Short proofs for long induced paths ⋮ An elementary approach to component sizes in critical random graphs ⋮ Incremental algorithm for maintaining a DFS tree for undirected graphs ⋮ Smoothed Analysis on Connected Graphs ⋮ Finding paths in sparse random graphs requires many queries ⋮ The largest hole in sparse random graphs ⋮ Finding Hamilton cycles in random graphs with few queries ⋮ Long paths and cycles in random subgraphs of \(\mathcal{H}\)-free graphs ⋮ Site percolation on pseudo‐random graphs ⋮ Depth-first search performance in a random digraph with geometric outdegree distribution ⋮ Heavy and light paths and Hamilton cycles ⋮ How to build a pillar: a proof of Thomassen's conjecture ⋮ Improved baselines for causal structure learning on interventional data ⋮ Unnamed Item ⋮ The phase transition in site percolation on pseudo-random graphs ⋮ Manipulative Waiters with Probabilistic Intuition ⋮ The Threshold Probability for Long Cycles ⋮ Strict convexity of the free energy of the canonical ensemble under decay of correlations ⋮ On percolation and ‐hardness ⋮ Client-waiter games on complete and random graphs ⋮ Ramsey Goodness of Clique Versus Paths in Random Graphs ⋮ Paths and cycles in random subgraphs of graphs with large minimum degree ⋮ Longest Paths in Random Hypergraphs ⋮ On topological minors in random simplicial complexes ⋮ Infinite and Giant Components in the Layers Percolation Model ⋮ Largest Components in Random Hypergraphs ⋮ On giant components and treewidth in the layers model ⋮ Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs ⋮ Long paths and cycles in random subgraphs of graphs with large minimum degree ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier ⋮ Decay of correlations and uniqueness of the Infinite-Volume Gibbs measure of the Canonical ensemble of 1d-lattice systems ⋮ On the performance of the depth first search algorithm in supercritical random graphs ⋮ Sandwiching dense random regular graphs between binomial random graphs ⋮ The Phase Transition in Multitype Binomial Random Graphs ⋮ Expansion in supercritical random subgraphs of the hypercube and its consequences ⋮ Critical percolation on random regular graphs
Cites Work
- The longest path in a random graph
- Percolation beyond \(\mathbb{Z}^ d\), many questions and a few answers
- Biased positional games on matroids
- Biased positional games and the phase transition
- Long cycles in subgraphs of (pseudo)random directed graphs
- The transitive closure of a random digraph
- The emergence of a giant component in random subgraphs of pseudo-random graphs
This page was built for publication: The phase transition in random graphs: A simple proof
