Search

Given a connected graph $H$ which is not a star, we show that the number of copies of $H$ in a dense uniformly random regular graph is asymptotically Gaussian, which was not known even for $H$ being a triangle. This addresses a question of McKay from the 2010 International Congress of Mathematicians. In fact, we prove that the behavior of the variance of the number of copies of $H$ depends in a delicate manner on the occurrence and number of cycles of $3,4,5$ edges as well as paths of $3$ edges in $H$. More generally, we provide control of the asymptotic distribution of certain statistics of bounded degree which are invariant under vertex permutations, including moments of the spectrum of a random regular graph. Our techniques are based on combining complex-analytic methods due to McKay and Wormald used to enumerate regular graphs with the notion of graph factors developed by Janson in the context of studying subgraph counts in $\mathbb {G}(n,p)$. [ABSTRACT FROM AUTHOR]

Let |$A$| be the adjacency matrix of a uniformly random |$d$| -regular digraph on |$n$| vertices, and suppose that |$\min (d,n-d)\ge \lambda n$|⁠. We show that for any |$\kappa \geq 0$|⁠ , $$\begin{align*} &\mathbb{P}[s_n(A)\le\kappa]\le C_\lambda\kappa\sqrt{n}+2e^{-c_\lambda n}.\end{align*}$$ Up to the constants |$C_\lambda , c_\lambda> 0$|⁠ , our bound matches optimal bounds for |$n\times n$| random matrices, each of whose entries is an i.i.d |$\operatorname{Ber}(d/n)$| random variable. The special case |$\kappa = 0$| of our result confirms a conjecture of Cook regarding the probability of singularity of dense random regular digraphs. [ABSTRACT FROM AUTHOR]

Let A be an n\times n random matrix whose entries are i.i.d. with mean 0 and variance 1. We present a deterministic polynomial time algorithm which, with probability at least 1-2\exp (-\Omega (\epsilon n)) in the choice of A, finds an \epsilon n \times \epsilon n sub-matrix such that zeroing it out results in \widetilde {A} with \[ \lVert \widetilde {A}\rVert = O(\sqrt {n/\epsilon }). \] Our result is optimal up to a constant factor and improves previous results of Rebrova and Vershynin, and Rebrova. We also prove an analogous result for A a symmetric n\times n random matrix whose upper-diagonal entries are i.i.d. with mean 0 and variance 1. [ABSTRACT FROM AUTHOR]

We show that for an $n\times n$ random symmetric matrix $A_n$ , whose entries on and above the diagonal are independent copies of a sub-Gaussian random variable $\xi$ with mean 0 and variance 1, \begin{equation*}\mathbb{P}[s_n(A_n) \le \epsilon/\sqrt{n}] \le O_{\xi}(\epsilon^{1/8} + \exp(\!-\Omega_{\xi}(n^{1/2}))) \quad \text{for all } \epsilon \ge 0.\end{equation*} This improves a result of Vershynin, who obtained such a bound with $n^{1/2}$ replaced by $n^{c}$ for a small constant c, and $1/8$ replaced by $(1/8) - \eta$ (with implicit constants also depending on $\eta > 0$). Furthermore, when $\xi$ is a Rademacher random variable, we prove that \begin{equation*}\mathbb{P}[s_n(A_n) \le \epsilon/\sqrt{n}] \le O(\epsilon^{1/8} + \exp(\!-\Omega((\!\log{n})^{1/4}n^{1/2}))) \quad \text{for all } \epsilon \ge 0.\end{equation*} The special case $\epsilon = 0$ improves a recent result of Campos, Mattos, Morris, and Morrison, which showed that $\mathbb{P}[s_n(A_n) = 0] \le O(\exp(\!-\Omega(n^{1/2}))).$ Notably, in a departure from the previous two best bounds on the probability of singularity of symmetric matrices, which had relied on somewhat specialized and involved combinatorial techniques, our methods fall squarely within the broad geometric framework pioneered by Rudelson and Vershynin, and suggest the possibility of a principled geometric approach to the study of the singular spectrum of symmetric random matrices. The main innovations in our work are new notions of arithmetic structure – the Median Regularized Least Common Denominator (MRLCD) and the Median Threshold, which are natural refinements of the Regularized Least Common Denominator (RLCD)introduced by Vershynin, and should be more generally useful in contexts where one needs to combine anticoncentration information of different parts of a vector. [ABSTRACT FROM AUTHOR]

We introduce a general framework for studying anticoncentration and local limit theorems for random variables, including graph statistics. Our methods involve an interplay between Fourier analysis, decoupling, hypercontractivity of Boolean functions, and transference between 'fixed‐size' and 'independent' models. We also adapt a notion of 'graph factors' due to Janson. As a consequence, we derive a local central limit theorem for connected subgraph counts in the Erdős–Renyi random graph G(n,p)$G(n,p)$, building on work of Gilmer and Kopparty and of Berkowitz. These results improve an anticoncentration result of Fox, Kwan, and Sauermann and partially answer a question of Fox, Kwan, and Sauermann. We also derive a local central limit theorem for induced subgraph counts, as long as p$p$ is bounded away from a set of 'problematic' densities, partially answering a question of Fox, Kwan, and Sauermann. We then prove these restrictions are necessary by exhibiting a disconnected graph for which anticoncentration for subgraph counts at the optimal scale fails for all constant p$p$, and finding a graph H$H$ for which anticoncentration for induced subgraph counts fails in G(n,1/2)$G(n,1/2)$. These counterexamples resolve anticoncentration conjectures of Fox, Kwan, and Sauermann in the negative. Finally, we also examine the behavior of counts of k$k$‐term arithmetic progressions in subsets of Z/nZ$\mathbb {Z}/n\mathbb {Z}$ and deduce a local limit theorem wherein the behavior is Gaussian at a global scale but has nontrivial local oscillations (according to a Ramanujan theta function). These results improve on results of and answer questions of the authors and Berkowitz, and answer a question of Fox, Kwan, and Sauermann. [ABSTRACT FROM AUTHOR]

Bollobás and Riordan, in their paper 'Metrics for sparse graphs', proposed a number of provocative conjectures extending central results of quasirandom graphs and graph limits to sparse graphs. We refute these conjectures by exhibiting a sequence of graphs with convergent normalized subgraph densities (and pseudorandom C4-counts), but with no limit expressible as a kernel. [ABSTRACT FROM AUTHOR]