Poisson Cloning Model for Random Graphs

MaRDI QIDQ5491016zbMATH OpenFDO

Authors Jeong Han Kim

Publication date 26 September 2006

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

zbMATH Keywords

giant component, core, Poisson distribution

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: In the random graph $G(n,p)$ with $pn$ bounded, the degrees of the vertices are almost i.i.d Poisson random variables with mean $gl:=p(n-1)$. Motivated by this fact, we introduce the Poisson cloning model $G_{PC}(n,p)$ for random graphs in which the degrees are i.i.d Poisson random variables with mean $gl$. Then, we first establish a theorem that shows the new model is equivalent to the classical model $G(n,p)$ in an asymptotic sense. Next, we introduce a useful algorithm, called the cut-off line algorithm, to generate the random graph $G_{PC}(n,p)$. The Poisson cloning model $G_{PC}(n,p)$ equipped with the cut-off line algorithm enables us to very precisely analyze the sizes of the largest component and the $t$-core of $G(n,p)$. This new approach to the problems yields not only elegant proofs but also improved bounds that are essentially best possible. We also consider the Poisson cloning models for random hypergraphs and random $k$-SAT problems. Then, the $t$-core problem for random hypergraphs and the pure literal algorithm for random $k$-SAT problems are analyzed.

Recommendations

• Computing and Combinatorics
• Sparse random graphs with clustering
• The random-cluster model on the complete graph
• The Structure of a Random Graph at the Point of the Phase Transition
• High density asymptotics of the Poisson random connection model

Cited in

(22)

• Loose cores and cycles in random hypergraphs
• Survival and extinction of epidemics on random graphs with general degree
• Core forging and local limit theorems for the \(k\)-core of random graphs
• On the threshold for k-regular subgraphs of random graphs
• Anatomy of the giant component: the strictly supercritical regime
• On the phase transition in random simplicial complexes
• A simple solution to the k‐core problem
• Upper-bounding the k-colorability threshold by counting covers
• Mixing time of near-critical random graphs
• Computing and Combinatorics
• Critical value asymptotics for the contact process on random graphs
• Phase transitions in graphs on orientable surfaces
• The satisfiability threshold for k-XORSAT
• The stripping process can be slow. II
• Singularity of the \(k\)-core of a random graph
• Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics
• Subcritical epidemics on random graphs
• The k-XORSAT threshold revisited (extended abstract)
• On the robustness of random k-cores
• Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
• The asymptotic k-SAT threshold
• Asymptotic normality of the \(k\)-core in random graphs

This page was built for publication: Poisson Cloning Model for Random Graphs

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