On tree census and the giant component in sparse random graphs

DOI10.1002/rsa.3240010306zbMath0747.05080OpenAlexW2005394933MaRDI QIDQ3970912

Boris G. Pittel

Publication date: 25 June 1992

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

Full work available at URL: https://doi.org/10.1002/rsa.3240010306

zbMATH Keywords

treeindependencerandom sequencegiant componentsparse random graphcoagulation process

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80)

Related Items (40)

Size of the largest cluster under zero-range invariant measures ⋮ The critical mean-field Chayes–Machta dynamics ⋮ Phase transition phenomena in random discrete structures ⋮ Cycles in a random graph near the critical point ⋮ Components of Random Forests ⋮ On the Thickness of Sparse Random Graphs ⋮ The random-cluster model on the complete graph ⋮ On a greedy 2-matching algorithm and Hamilton cycles in random graphs with minimum degree at least three ⋮ Corrigendum to: ``On the limiting distribution of the metric dimension for random forests ⋮ Distributed algorithms for random graphs ⋮ Finding paths in sparse random graphs requires many queries ⋮ A large‐deviations principle for all the cluster sizes of a sparse Erdős–Rényi graph ⋮ Local Limit Theorems for the Giant Component of Random Hypergraphs ⋮ On the number of isolated vertices in a growing random graph ⋮ Cutting Edges at Random in Large Recursive Trees ⋮ Asymptotic normality in random graphs with given vertex degrees ⋮ Unnamed Item ⋮ Asymptotic normality of the \(k\)-core in random graphs ⋮ Monotonicity, asymptotic normality and vertex degrees in random graphs ⋮ A moment-generating formula for Erdős-Rényi component sizes ⋮ Counting connected graphs inside-out ⋮ Between 2- and 3-colorability ⋮ Stochastic processes in random graphs ⋮ The order of the giant component of random hypergraphs ⋮ A phase transition in the random transposition random walk ⋮ Central limit theorem for statistics of subcritical configuration models ⋮ A new approach to the giant component problem ⋮ The peculiar phase structure of random graph bisection ⋮ A power law of order 1/4 for critical mean-field Swendsen-Wang dynamics ⋮ Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs ⋮ The solution space geometry of random linear equations ⋮ Asymptotic normality of the size of the giant component via a random walk ⋮ First Passage Percolation on the Erdős–Rényi Random Graph ⋮ Coalescent random forests ⋮ Limit theory of combinatorial optimization for random geometric graphs ⋮ Normal convergence problem? Two moments and a recurrence may be the clues ⋮ Tree and forest weights and their application to nonuniform random graphs ⋮ On the largest component of the random graph at a nearcritical stage ⋮ On the normality of giant components ⋮ On the Rigidity of Sparse Random Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• When are small subgraphs of a random graph normally distributed?
• Maximal induces trees in sparse random graphs
• The longest path in a random graph
• Poisson approximation for dependent trials
• Random tree-type partitions as a model for acyclic polymerization: Holtsmark (3/2-stable) distribution of the supercritical gel
• Large induced trees in sparse random graphs
• On the probable behaviour of some algorithms for finding the stability number of a graph
• Solutions and critical times for the monodisperse coagulation equation when a_ij=A + B(i + j) + Cij
• A branching-process solution of the polydisperse coagulation equation
• On a Daley-Kendall model of random rumours
• A Random Graph With a Subcritical Number of Edges
• Poisson convergence and random graphs
• Poisson approximation for some statistics based on exchangeable trials
• On a functional central limit theorem for Markov population processes
• The principle of the diffusion of arbitrary constants

This page was built for publication: On tree census and the giant component in sparse random graphs