Singularity of the k-core of a random graph

DOI10.1215/00127094-2022-0060zbMATH Open1514.05142MaRDI 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)

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

zbMATH Keywords

singularityrandom matricesrandom graphs

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(4)

• A note on the singularity probability of random directed \(d\)-regular graphs
• Maximal core size in singular graphs
• On the rank, kernel, and core of sparse random 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)