Approximate counting and sampling via local central limit theorems

We give an FPTAS for computing the number of matchings of size $k$ in a graph $G$ of maximum degree $Delta$ on $n$ vertices, for all $k le (1-delta)m^*(G)$, where $delta>0$ is fixed and $m^*(G)$ is the matching number of $G$, and an FPTAS for the number of independent sets of size $k le (1-delta) alpha_c(Delta) n$, where $alpha_c(Delta)$ is the NP-hardness threshold for this problem. We also provide quasi-linear time randomized algorithms to approximately sample from the uniform distribution on matchings of size $k leq (1-delta)m^*(G)$ and independent sets of size $k leq (1-delta)alpha_c(Delta)n$. Our results are based on a new framework for exploiting local central limit theorems as an algorithmic tool. We use a combination of Fourier inversion, probabilistic estimates, and the deterministic approximation of partition functions at complex activities to extract approximations of the coefficients of the partition function. For our results for independent sets, we prove a new local central limit theorem for the hard-core model that applies to all fugacities below $lambda_c(Delta)$, the uniqueness threshold on the infinite $Delta$-regular tree.

Non-classical polynomials and the inverse theorem

In this note we characterize when non-classical polynomials are necessary in the inverse theorem for the Gowers $U^k$-norm. We give a brief deduction of the fact that a bounded function on $mathbb F_p^n$ with large $U^k$-norm must correlate with a classical polynomial when $kleq p+1$. To the best of our knowledge, this result is new for $k=p+1$ (when $p>2$). We then prove that non-classical polynomials are necessary in the inverse theorem for the Gowers $U^k$-norm over $mathbb F_p^n$ for all $kgeq p+2$, completely characterizing when classical polynomials suffice.

Large deviations in random Latin squares

In this note, we study large deviations of the number $mathbf{N}$ of intercalates ($2times2$ combinatorial subsquares which are themselves Latin squares) in a random $ntimes n$ Latin square. In particular, for constant $delta>0$ we prove that $Pr(mathbf{N}le(1-delta)n^{2}/4)leexp(-Omega(n^{2}))$ and $Pr(mathbf{N}ge(1+delta)n^{2}/4)leexp(-Omega(n^{4/3}(log n)^{2/3}))$, both of which are sharp up to logarithmic factors in their exponents. As a consequence, we deduce that a typical order-$n$ Latin square has $(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.

Singularity of the k-core of a random graph

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 $kge 3$ and $lambda > 0$, an ErdH os--Renyi random graph $Gsimmathbb{G}(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.

Random symmetric matrices: rank distribution and irreducibility of the characteristic polynomial

Conditional on the extended Riemann hypothesis, we show that with high probability, the characteristic polynomial of a random symmetric ${pm 1}$-matrix is irreducible. This addresses a question raised by Eberhard in recent work. The main innovation in our work is establishing sharp estimates regarding the rank distribution of symmetric random ${pm 1}$-matrices over $mathbb{F}_p$ for primes $2 < p leq exp(O(n^{1/4}))$. Previously, such estimates were available only for $p = o(n^{1/8})$. At the heart of our proof is a way to combine multiple inverse Littlewood--Offord-type results to control the contribution to singularity-type events of vectors in $mathbb{F}_p^{n}$ with anticoncentration at least $1/p + Omega(1/p^2)$. Previously, inverse Littlewood--Offord-type results only allowed control over vectors with anticoncentration at least $C/p$ for some large constant $C > 1$.

Majority Dynamics: The Power of One

Consider $n=ell+m$ individuals, where $ellle m$, with $ell$ individuals holding an opinion $A$ and $m$ holding an opinion $B$. Suppose that the individuals communicate via an undirected network $G$, and in each time step, each individual updates her opinion according to a majority rule (that is, according to the opinion of the majority of the individuals she can communicate with in the network). This simple and well studied process is known as majority dynamics in social networks. Here we consider the case where $G$ is a random network, sampled from the binomial model $mathbb{G}(n,p)$, where $(log n)^{-1/16}le ple 1-(log n)^{-1/16}$. We show that for $n=ell+m$ with $Delta=m-ellle(log n)^{1/4}$, the above process terminates whp after three steps when a consensus is reached. Furthermore, we calculate the (asymptotically) correct probability for opinion $B$ to win and show it is [Phibigg(frac{pDeltasqrt{2}}{sqrt{pi p(1-p)}}bigg) + O(n^{-c}),] where $Phi$ is the Gaussian CDF. This answers two conjectures of Tran and Vu and also a question raised by Berkowitz and Devlin. The proof technique involves iterated degree revelation and analysis of the resulting degree-constrained random graph models via graph enumeration techniques of McKay and Wormald as well as Canfield, Greenhill, and McKay.

A Gaussian fixed point random walk

In this note, we design a discrete random walk on the real line which takes steps $0, pm 1$ (and one with steps in ${pm 1, 2}$) where at least $96%$ of the signs are $pm 1$ in expectation, and which has $mathcal{N}(0,1)$ as a stationary distribution. As an immediate corollary, we obtain an online version of Banaszczyks discrepancy result for partial colorings and $pm 1, 2$ signings. Additionally, we recover linear time algorithms for logarithmic bounds for the Koml{o}s conjecture in an oblivious online setting.

Rank deficiency of random matrices

Let $M_n$ be a random $ntimes n$ matrix with i.i.d. $text{Bernoulli}(1/2)$ entries. We show that for fixed $kge 1$, [lim_{nto infty}frac{1}{n}log_2mathbb{P}[text{corank }M_nge k] = -k.]

Popular differences for matrix patterns

The following combinatorial conjecture arises naturally from recent ergodic-theoretic work of Ackelsberg, Bergelson, and Best. Let $M_1$, $M_2$ be $ktimes k$ integer matrices, $G$ be a finite abelian group of order $N$, and $Asubseteq G^k$ with $|A|gealpha 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^ksetminus{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 $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 an additional spectral condition.

Anticoncentration versus the number of subset sums

Let $vec{w} = (w_1,dots, w_n) in mathbb{R}^{n}$. We show that for any $n^{-2}leepsilonle 1$, if [#{vec{xi} in {0,1}^{n}: langle vec{xi}, vec{w} rangle = tau} ge 2^{-epsilon n}cdot 2^{n}] for some $tau in mathbb{R}$, then [#{langle vec{xi}, vec{w} rangle : vec{xi} in {0,1}^{n}} le 2^{O(sqrt{epsilon}n)}.] This exponentially improves the $epsilon$ dependence in a recent result of Nederlof, Pawlewicz, Swennenhuis, and Wk{e}grzycki and leads to a similar improvement in the parameterized (by the number of bins) runtime of bin packing.