Percolation with small clusters on random graphs

DOI10.1007/S00373-015-1628-0MaRDI QIDQ293653zbMATH OpenOpenAlexFDO

Authors Mustazee Rahman

Publication date 9 June 2016

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

independent setpercolationrandom graphsregular graphinduced forest

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30)

Abstract: Consider the problem of determining the maximal induced subgraph in a random $d$-regular graph such that its components remain bounded as the size of the graph becomes arbitrarily large. We show, for asymptotically large $d$, that any such induced subgraph has size density at most $2(logd)/d$ with high probability. A matching lower bound is known for independent sets. We also prove the analogous result for sparse ErdH{o}s-R'{e}nyi graphs.

Recommendations

• Critical percolation on random regular graphs
• Maximum independent sets on random regular graphs
• The largest hole in sparse random graphs
• Induced subgraphs in sparse random graphs with given degree sequences
• Regular induced subgraphs of a random graph

Cites work

• scientific article; zbMATH DE number 4049676 (Why is no real title available?)
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Decycling numbers of random regular graphs
• Fragmentability of graphs
• Induced Forests in Regular Graphs with Large Girth
• Invariant Gaussian processes and independent sets on regular graphs of large girth
• On the independence and chromatic numbers of random regular graphs
• On the independence number of random graphs
• Random graphs.
• The Independence Ratio of Regular Graphs
• The asymptotic number of labeled graphs with given degree sequences

Cited in

(5)

• Percolation on Sparse Random Graphs with Given Degree Sequence
• Critical percolation on random regular graphs
• Interference percolation
• Factor of iid percolation on trees
• Critical percolation on random regular graphs

This page was built for publication: Percolation with small clusters on random graphs

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