Search

We show that the number of linear spaces on a set of $n$ points and the number of rank-3 matroids on a ground set of size $n$ are both of the form $(cn+o(n))^{n^2/6}$, where $c=e^{\sqrt{3}/2-3}(1+\sqrt{3})/2$. This is the final piece of the puzzle for enumerating fixed-rank matroids at this level of accuracy: there are exact formulas for enumeration of rank-1 and rank-2 matroids, and it was recently proved by van der Hofstad, Pendavingh, and van der Pol that for constant $r\ge 4$ there are $(e^{1-r}n+o(n))^{n^{r-1}/r!}$ rank-$r$ matroids on a ground set of size $n$.

We give an online algorithm that with high probability computes a ( e e-1 + o(1)) Δ edge coloring on a graph G with maximum degree Δ = ω (log n) under online edge arrivals against oblivious adversaries, making first progress on the conjecture of Bar-Noy, Motwani, and Naor in this general setting. Our algorithm is based on reducing to a matching problem on locally treelike graphs, and then applying a tree recurrence based approach for arguing correlation decay. [ABSTRACT FROM AUTHOR]

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]

An n-vertex graph is called C-Ramsey if it has no clique or independent set of size C log2 n (i.e., if it has near-optimal Ramsey behavior). In this paper, we study edge statistics in Ramsey graphs, in particular obtaining very precise control of the distribution of the number of edges in a random vertex subset of a C-Ramsey graph. This brings together two ongoing lines of research: the study of 'random-like' properties of Ramsey graphs and the study of small-ball probability for low-degree polynomials of independent random variables. The proof proceeds via an 'additive structure' dichotomy on the degree sequence and involves a wide range of different tools from Fourier analysis, random matrix theory, the theory of Boolean functions, probabilistic combinatorics and low-rank approximation. In particular, a key ingredient is a new sharpened version of the quadratic Carbery-Wright theorem on small-ball probability for polynomials of Gaussians, which we believe is of independent interest. One of the consequences of our result is the resolution of an old conjecture of Erdős and McKay, for which Erdős reiterated in several of his open problem collections and for which he offered one of his notorious monetary prizes. [ABSTRACT FROM AUTHOR]

Motivated by problems from compressed sensing, we determine the threshold behaviour of a random $n\times d \pm 1$ matrix $M_{n,d}$ with respect to the property 'every $s$ columns are linearly independent'. In particular, we show that for every $0\lt \delta \lt 1$ and $s=(1-\delta)n$ , if $d\leq n^{1+1/2(1-\delta)-o(1)}$ then with high probability every $s$ columns of $M_{n,d}$ are linearly independent, and if $d\geq n^{1+1/2(1-\delta)+o(1)}$ then with high probability there are some $s$ linearly dependent columns. [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]

Define a permutation σ to be coprime if gcd(m,σ(m))=1$\gcd (m,\sigma (m)) = 1$ for m∈[n]$m\in [n]$. In this note, proving a recent conjecture of Pomerance, we prove that the number of coprime permutations on [n] is n!·(c+o(1))n$n!\cdot (c+o(1))^n$ where c=∏pprime(p−1)2(1−1/p)p·(p−2)(1−2/p).\begin{equation*} c = \prod _{p\text{ prime }}\frac{(p-1)^{2(1-1/p)}}{p\cdot (p-2)^{(1-2/p)}}. \end{equation*}The techniques involve entropy maximization for the upper bound, and a mixture of number‐theoretic bounds, permanent estimates, and the absorbing method for the lower bound. [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]

In this note, we study large deviations of the number N$\mathbf {N}$ of intercalates (2×2$2\times 2$ combinatorial subsquares which are themselves Latin squares) in a random n×n$n\,{\times}\, n$ Latin square. In particular, for constant δ>0$\delta >0$ we prove that exp(−O(n2logn))⩽Pr(N⩽(1−δ)n2/4)⩽exp(−Ω(n2))$\exp (-O(n^{2}\log n))\leqslant \Pr (\mathbf {N}\leqslant (1-\delta)n^{2}/4)\leqslant \exp (-\Omega (n^{2}))$ and exp(−O(n4/3(logn)))⩽Pr(N⩾(1+δ)n2/4)⩽exp(−Ω(n4/3(logn)2/3))$\exp (-O(n^{4/3}(\log n)))\leqslant \Pr (\mathbf {N}\geqslant (1+\delta)n^{2}/4)\leqslant \exp (-\Omega (n^{4/3}(\log n)^{2/3}))$. As a consequence, we deduce that a typical order‐n$n$ Latin square has (1+o(1))n2/4$(1+o(1))n^{2}/4$ intercalates, matching a lower bound due to Kwan and Sudakov and resolving an old conjecture of McKay and Wanless. [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]

Does every |$n$| -vertex Cayley graph have an orthonormal eigenbasis all of whose coordinates are |$O(1/\sqrt{n})$| ? While the answer is yes for abelian groups, we show that it is no in general. On the other hand, we show that every |$n$| -vertex Cayley graph (and more generally, vertex-transitive graph) has an orthonormal basis whose coordinates are all |$O(\sqrt{\log n / n})$|⁠ , and that this bound is nearly best possible. Our investigation is motivated by a question of Assaf Naor, who proved that random abelian Cayley graphs are small-set expanders, extending a classic result of Alon–Roichman. His proof relies on the existence of a bounded eigenbasis for abelian Cayley graphs, which we now know cannot hold for general groups. On the other hand, we navigate around this obstruction and extend Naor's result to nonabelian groups. [ABSTRACT FROM AUTHOR]

Let A$A$ be an n×n$n\times n$ real matrix, and let M$M$ be an n×n$n\times n$ random matrix whose entries are independent and identically distributed sub‐Gaussian random variables with mean 0 and variance 1. We make two contributions to the study of sn(A+M)$s_n(A+M)$, the smallest singular value of A+M$A+M$. (1)We show that for all ε⩾0$\epsilon \geqslant 0$, P[sn(A+M)⩽ε]=O(εn)+2e−Ω(n),\begin{equation*} \mathbb {P}[s_n(A + M) \leqslant \epsilon ] = O(\epsilon \sqrt {n}) + 2e^{-\Omega (n)}, \end{equation*}provided only that A$A$ has Ω(n)$\Omega (n)$ singular values which are O(n)$O(\sqrt {n})$. This extends a well‐known result of Rudelson and Vershynin, which requires all singular values of A$A$ to be O(n)$O(\sqrt {n})$.(2)We show that any bound of the form sup∥A∥⩽nC1P[sn(A+M)⩽n−C3]⩽n−C2\begin{equation*} \sup _{\Vert A\Vert \leqslant n^{C_1}}\mathbb {P}[s_n(A+M)\leqslant n^{-C_3}] \leqslant n^{-C_2} \end{equation*}must have C3=Ω(C1C2)$C_3 = \Omega (C_1 \sqrt {C_2})$. This complements a result of Tao and Vu, who proved such a bound with C3=O(C1C2+C1+1)$C_3 = O(C_1C_2 + C_1 + 1)$, and counters their speculation of possibly taking C3=O(C1+C2)$C_3 = O(C_1 + C_2)$. [ABSTRACT FROM AUTHOR]

The following combinatorial conjecture arises naturally from recent ergodic-theoretic work of Ackelsberg, Bergelson, and Best. Let M_1, M_2 be k\times k integer matrices, G be a finite abelian group of order N, and A\subseteq G^k with |A|\ge \alpha N^k. If M_1, M_2, M_1-M_2, and M_1+M_2 are automorphisms of G^k, is it true that there exists a popular difference d \in G^k\setminus \{0\} such that \[ \#\{x \in G^k: x, x+M_1d, x+M_2d, x+(M_1+M_2)d \in A\} \ge (\alpha ^4-o(1))N^k?\] We show that this conjecture is false in general, but holds for G = \mathbb {F}_p^n with p an odd prime given the additional spectral condition that no pair of eigenvalues of M_1M_2^{-1} (over the algebraic closure \overline {\mathbb {F}}_p) are negatives of each other. In particular, the "rotated squares" pattern does not satisfy this eigenvalue condition, and we give a construction of a set of positive density in (\mathbb {F}_5^n)^2 for which that pattern has no nonzero popular difference. This is in surprising contrast to three-point patterns, which we handle over all compact abelian groups and which do not require additional spectral conditions. [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]

May the triforce be the 3-uniform hypergraph on six vertices with edges {123′, 12′3, 1′23}. We show that the minimum triforce density in a 3-uniform hypergraph of edge density δ is δ4–o(1) but not O(δ4). Let M(δ) be the maximum number such that the following holds: for every ∊ > 0 and G = F2n with n sufficiently large, if A ⊆ G × G with A ≥ δ|G|2, then there exists a nonzero "popular difference" d ∈ G such that the number of "corners" (x, y), (x + d, y), (x, y + d) ∈ A is at least (M(δ)–∊)|G|2. As a corollary via a recent result of Mandache, we conclude that M(δ) = δ4–o(1) and M(δ) = ω(δ4). On the other hand, for 0 < δ < 1/2 and sufficiently large N, there exists A ⊆ [N]3 with |A| ≥ δN3 such that for every d ≠ 0, the number of corners (x, y, z), (x + d, y, z), (x, y + d, z), (x, y, z + d) ∈ A is at most δc log(1/δ)N3. A similar bound holds in higher dimensions, or for any configuration with at least 5 points or affine dimension at least 3. [ABSTRACT FROM AUTHOR]

We examine the quantity S ( G ) = ∑ u v ∈ E ( G ) min ( deg u , deg v ) over sets of graphs with a fixed number of edges. The main result shows the maximum possible value of S ( G ) is achieved by three different classes of constructions, depending on the distance between the number of edges and the nearest triangular number. Furthermore we determine the maximum possible value when the set of graphs is restricted to be bipartite, a forest, or to be planar given sufficiently many edges. The quantity S ( G ) corresponds to the difference between two well studied indices, the irregularity of a graph and the sum of the squares of the degrees in a graph. These are known as the first and third Zagreb indices in the area of mathematical chemistry. [ABSTRACT FROM AUTHOR]

A numerical semigroup S is called cyclotomic if its corresponding numerical semi-group polynomial, PS(x) = (1 - x)∑s∊S xs, is expressible as a product of cyclotomic polynomials. Ciolan, García-Sánchez, and Moree [SIAM J. Discrete Math., 30 (2016), pp. 650-668] conjectured that, for every embedding dimension at least 4, there exists a numerical semigroup which is symmetric but not cyclotomic. We prove this conjecture by giving an infinite class of numerical semigroup families Sn,t, which, for every fixed t, are symmetric but not cyclotomic when n ≥ max (8(t+1)3; 40(t+2)). We also verify through a finite case check that the numerical semigroup families Sn,0 and Sn,1 yield noncyclotomic numerical semigroups for every embedding dimension at least 4. [ABSTRACT FROM AUTHOR]