Singularity of the k-core of a random graph

DOI10.1215/00127094-2022-0060zbMATH Open1514.05142arXiv2106.05719MaRDI QIDQ6046464FDOQ6046464

Authors: Asaf Ferber, Matthew Kwan, Ashwin Sah, Mehtaab Sawhney 

Publication date: 11 May 2023

Published in: Duke Mathematical Journal (Search for Journal in Brave)

Abstract: Very sparse random graphs are known to typically be singular (i.e., have singular adjacency matrix), due to the presence of "low-degree dependencies such as isolated vertices and pairs of degree-1 vertices with the same neighbourhood. We prove that these kinds of dependencies are in some sense the only causes of singularity: for constants $kge3$ and $lambda>0$, an ErdH os--R'enyi random graph $GsimmathbbG(n,lambda/n)$ with $n$ vertices and edge probability $lambda/n$ typically has the property that its $k$-core (its largest subgraph with minimum degree at least $k$) is nonsingular. This resolves a conjecture of Vu from the 2014 International Congress of Mathematicians, and adds to a short list of known nonsingularity theorems for "extremely sparse random matrices with density $O(1/n)$. A key aspect of our proof is a technique to extract high-degree vertices and use them to "boost the rank, starting from approximate rank bounds obtainable from (non-quantitative) spectral convergence machinery due to Bordenave, Lelarge and Salez.

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

Recommendations

• Sudden emergence of a giant \(k\)-core in a random graph
• The rank of random graphs
• Singularity of sparse random matrices: simple proofs
• Asymptotic normality of the \(k\)-core in random graphs
• On the singularity of random combinatorial matrices

zbMATH Keywords

singularityrandom matricesrandom graphs

Mathematics Subject Classification ID

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

Cites Work

• Recurrence of distributional limits of finite planar graphs
• Title not available (Why is that?)
• Sudden emergence of a giant \(k\)-core in a random graph
• Title not available (Why is that?)
• Differential equation approximations for Markov chains
• Log-concave probability and its applications
• Title not available (Why is that?)
• Random symmetric matrices are almost surely nonsingular.
• A simple solution to the k‐core problem
• Title not available (Why is that?)
• Asymptotic normality of the \(k\)-core in random graphs
• Adjacency matrices of random digraphs: singularity and anti-concentration
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• How does the core sit inside the mantle?
• Cores in random hypergraphs and Boolean formulas
• Thek-Core and Branching Processes
• Poisson Cloning Model for Random Graphs
• Encores on cores
• The rank of diluted random graphs
• Almost all cubic graphs are Hamiltonian
• Karp-Sipser on random graphs with a fixed degree sequence
• The rank of random graphs
• Singularity of random symmetric matrices -- simple proof
• Title not available (Why is that?)
• The correct exponent for the Gotsman-Linial conjecture
• On the singularity of adjacency matrices for random regular digraphs
• Cores of random graphs are born Hamiltonian
• Fixed energy universality of Dyson Brownian motion
• The smallest singular value of a shifted $d$-regular random square matrix
• The distribution of sandpile groups of random regular graphs
• On the almost eigenvectors of random regular graphs
• Hitting Time Theorems for Random Matrices
• Singularity of random Bernoulli matrices
• Sharp transition of the invertibility of the adjacency matrices of sparse random graphs
• The circular law for random regular digraphs
• On the rank of random sparse matrices
• The rank of sparse random matrices
• Structure of eigenvectors of random regular digraphs
• Singularity of sparse random matrices: simple proofs
• Anti-concentration for polynomials of independent random variables
• Recent progress in combinatorial random matrix theory
• Anticoncentration for subgraph statistics
• Invertibility of adjacency matrices for random \(d\)-regular graphs
• Core forging and local limit theorems for the \(k\)-core of random graphs
• An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs

Cited In (4)

• A note on the singularity probability of random directed \(d\)-regular graphs
• On the rank, kernel, and core of sparse random graphs
• Maximal core size in singular graphs
• Birth of a giant \((k_{1},k_{2})\)-core in the random digraph

This page was built for publication: Singularity of the \(k\)-core of a random graph

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