Random Subgraphs in Sparse Graphs

DOI10.1137/140976340MaRDI QIDQ3455246zbMATH OpenOpenAlexFDO

Authors Felix Joos

Publication date 4 December 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Cartesian powerconnectivityrandom graphs

Mathematics Subject Classification ID

Connectivity (05C40) Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We investigate the threshold probability for connectivity of sparse graphs under weak assumptions. As a corollary this completely solve the problem for Cartesian powers of arbitrary graphs. In detail, let $G$ be a connected graph on $k$ vertices, $G^n$ the $n$-th Cartesian power of $G$, $alph{a}_i$ be the number of vertices of degree $i$ of $G$, $lambda$ be a positive real number, and $G_p^n$ be the graph obtained from $G^n$ by deleting every edge independently with probability $1-p$. If $su{m}_{i}alph{a}_i(1-p{)}^i=lambd{a}^{frac1n}$, then $li{m}_{nightarrowinfty}mathbbP[G_p^{n}misconnected]=exp(-lambda)$. This result extends known results for regular graphs. The main result implies that the threshold probability does not depend on the graph structure of $G$ itself, but only on the degree sequence of the graph.

Recommendations

• Subgraphs of Random Graphs
• Random graphs and their subgraphs
• Spanning subgraphs of random graphs
• Spanning Subgraphs of Random Graphs
• Largest sparse subgraphs of random graphs
• Largest sparse subgraphs of random graphs
• scientific article; zbMATH DE number 3943865
• Distributions of sparse spanning subgraphs in random graphs
• scientific article; zbMATH DE number 3869382
• On Subgraph Sizes in Random Graphs

Cites work

• Edge isoperimetric inequalities for product graphs
• Evolution of the n-cube
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3752885 (Why is no real title available?)
• scientific article; zbMATH DE number 48363 (Why is no real title available?)
• scientific article; zbMATH DE number 3586242 (Why is no real title available?)
• scientific article; zbMATH DE number 3303834 (Why is no real title available?)
• Hypercube percolation
• Random graphs.
• Random subgraphs in Cartesian powers of regular graphs
• Random subgraphs of certain graph powers
• The Evolution of the Cube
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(17)

• Spanning subgraphs of random graphs
• Sparse quasi-random graphs
• A note on log-concave random graphs
• Connectivity threshold for random subgraphs of the Hamming graph
• Connectivity of random cubic sum graphs
• Local connectivity of a random graph
• scientific article; zbMATH DE number 3869382 (Why is no real title available?)
• Subgraphs of Random Graphs
• scientific article; zbMATH DE number 4110728 (Why is no real title available?)
• On the Thickness of Sparse Random Graphs
• Bisecting sparse random graphs
• On local weak limit and subgraph counts for sparse random graphs
• Subgraphs of random match-graphs
• The giant component after percolation of product graphs
• Weakly saturated subgraphs of random graphs
• Connectivity of Poissonian inhomogeneous random multigraphs
• Minimum degree k and k-connectedness usually arrive together

This page was built for publication: Random Subgraphs in Sparse Graphs

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