k-regular subgraphs near the k-core threshold of a random graph

DOI10.1016/J.JCTB.2019.10.001MaRDI QIDQ1985447zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 7 April 2020

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

random graphs\(k\)-regular subgraph

Mathematics Subject Classification ID

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

Abstract: We prove that $G_{n,p=c/n}$ whp has a $k$-regular subgraph if $c$ is at least $e^{-Theta(k)}$ above the threshold for the appearance of a subgraph with minimum degree at least $k$; i.e. an non-empty $k$-core. In particular, this pins down the threshold for the appearance of a $k$-regular subgraph to a window of size $e^{-Theta(k)}$.

Recommendations

• On the threshold for k-regular subgraphs of random graphs
• (k+1)-Cores Have k-Factors
• Regular subgraphs of random graphs
• The property of having a \(k\)-regular subgraph has a sharp threshold
• The first \(k\)-regular subgraph is large

Cites work

• scientific article; zbMATH DE number 3906527 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1405894 (Why is no real title available?)
• (k+1)-Cores Have k-Factors
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Cores in random hypergraphs and Boolean formulas
• Critical subgraphs of a random graph
• Encores on cores
• On the robustness of random k-cores
• On the threshold for k-regular subgraphs of random graphs
• Regular subgraphs of random graphs
• Sudden emergence of a giant k-core in a random graph
• The Factors of Graphs
• The asymptotic number of labeled graphs with given degree sequences
• The first \(k\)-regular subgraph is large
• The mixing time of the giant component of a random graph
• The property of having a \(k\)-regular subgraph has a sharp threshold

Cited in

(7)

• The first \(k\)-regular subgraph is large
• A novel giant-subgraph phase-transition in sparse random \(k\)-partite graphs
• On the threshold for k-regular subgraphs of random graphs
• The property of having a \(k\)-regular subgraph has a sharp threshold
• Regular subgraphs of random graphs
• Regular subgraphs of dense graphs
• Threshold functions for small subgraphs in simple graphs and multigraphs

This page was built for publication: \(k\)-regular subgraphs near the \(k\)-core threshold of a random graph

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