Percolation with small clusters on random graphs

DOI10.1007/S00373-015-1628-0zbMATH Open1338.05125arXiv1402.7242OpenAlexW2158541808MaRDI QIDQ293653FDOQ293653

Authors: Mustazee Rahman 

Publication date: 9 June 2016

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

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.

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

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

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)

Cites Work

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

Cited In (5)

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

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)