Search

Let $M$ be an $n\times n$ matrix with iid subgaussian entries with mean $0$ and variance $1$ and let $\sigma_n(M)$ denote the least singular value of $M$. We prove that \[\mathbb{P}\big( \sigma_{n}(M) \leq \varepsilon n^{-1/2} \big) = (1+o(1)) \varepsilon + e^{-\Omega(n)}\] for all $0 \leq \varepsilon \ll 1$. This resolves, up to a $1+o(1)$ factor, a seminal conjecture of Spielman and Teng., Comment: 27 pages

We present an explicit subset $A\subseteq \mathbb{N} = \{0,1,\ldots\}$ such that $A + A = \mathbb{N}$ and for all $\varepsilon > 0$, \[\lim_{N\to \infty}\frac{\big|\big\{(n_1,n_2): n_1 + n_2 = N, (n_1,n_2)\in A^2\big\}\big|}{N^{\varepsilon}} = 0.\] This answers a question of Erd\H{o}s., Comment: 5 pages

We prove that a subset $A\subseteq [1, N]$ with \[\sum_{n\in A}\frac{1}{n} \ge (\log N)^{4/5 + o(1)}\] contains a subset $B$ such that \[\sum_{n\in B} \frac{1}{n} = 1.\] Our techniques refine those of Croot and of Bloom. Using our refinements, we additionally consider a number of questions regarding unit fractions due to Erd\H{o}s and Graham., Comment: 22 pages

We prove quasipolynomial bounds on the inverse theorem for the Gowers $U^{s+1}[N]$-norm. The proof is modeled after work of Green, Tao, and Ziegler and uses as a crucial input recent work of the first author regarding the equidistribution of nilsequences. In a companion paper, this result will be used to improve the bounds on Szemer\'{e}di's theorem., Comment: 100 pages

Let $r_k(N)$ denote the size of the largest subset of $[N] = \{1,\ldots,N\}$ with no $k$-term arithmetic progression. We show that for $k\ge 5$, there exists $c_k>0$ such that \[r_k(N)\ll N\exp(-(\log\log N)^{c_k}).\] Our proof is a consequence of recent quasipolynomial bounds on the inverse theorem for the Gowers $U^k$-norm as well as the density increment strategy of Heath-Brown and Szemer\'{e}di as reformulated by Green and Tao., Comment: 13 pages

In 1981, Karp and Sipser proved a law of large numbers for the matching number of a sparse Erd\H{o}s-R\'enyi random graph, in an influential paper pioneering the so-called differential equation method for analysis of random graph processes. Strengthening this classical result, and answering a question of Aronson, Frieze and Pittel, we prove a central limit theorem in the same setting: the fluctuations in the matching number of a sparse random graph are asymptotically Gaussian. Our new contribution is to prove this central limit theorem in the subcritical and critical regimes, according to a celebrated algorithmic phase transition first observed by Karp and Sipser. Indeed, in the supercritical regime, a central limit theorem has recently been proved in the PhD thesis of Krea\v{c}i\'c, using a stochastic generalisation of the differential equation method (comparing the so-called Karp-Sipser process to a system of stochastic differential equations). Our proof builds on these methods, and introduces new techniques to handle certain degeneracies present in the subcritical and critical cases. Curiously, our new techniques lead to a non-constructive result: we are able to characterise the fluctuations of the matching number around its mean, despite these fluctuations being much smaller than the error terms in our best estimates of the mean. We also prove a central limit theorem for the rank of the adjacency matrix of a sparse random graph.

Let $r_5(N)$ be the largest cardinality of a set in $\{1,\ldots,N\}$ which does not contain $5$ elements in arithmetic progression. Then there exists a constant $c\in (0,1)$ such that \[r_5(N)\ll \frac{N}{\exp((\log\log N)^{c})}.\] Our work is a consequence of recent improved bounds on the $U^4$-inverse theorem of the first author and the fact that $3$-step nilsequences may be approximated by locally cubic functions on shifted Bohr sets. This combined with the density increment strategy of Heath-Brown and Szemer{\'e}di, codified by Green and Tao, gives the desired result., Comment: 35 pages, comments welcome!

Let $A$ be an $n\times n$ matrix with iid entries where $A_{ij} \sim \mathrm{Ber}(p)$ is a Bernoulli random variable with parameter $p = d/n$. We show that the empirical measure of the eigenvalues converges, in probability, to a deterministic distribution as $n \rightarrow \infty$. This essentially resolves a long line of work to determine the spectral laws of iid matrices and is the first known example for non-Hermitian random matrices at this level of sparsity., Comment: 44 pages

Let $A_n$ be an $n\times n$ matrix with iid entries distributed as Bernoulli random variables with parameter $p = p_n$. Rudelson and Tikhomirov, in a beautiful and celebrated paper, show that the distribution of eigenvalues of $A_n \cdot (pn)^{-1/2}$ is approximately uniform on the unit disk as $n\rightarrow \infty$ as long as $pn \rightarrow \infty$, which is the natural necessary condition. In this paper we give a much simpler proof of this result, in its full generality, using a perspective we developed in our recent proof of the existence of the limiting spectral law when $pn$ is bounded. One feature of our proof is that it avoids the use of $\epsilon$-nets entirely and, instead, proceeds by studying the evolution of the singular values of the shifted matrices $A_n-zI$ as we incrementally expose the randomness in the matrix., Comment: 20 pages

Let $S$ be a subset of $\{1,\ldots,N\}$ avoiding the nontrivial progressions $x, x+y^2-1, x+ 2(y^2-1)$. We prove that $|S|\ll N/\log_m{N}$, where $\log_m $ is the $m$-fold iterated logarithm and $m\in\mathbf{N}$ is an absolute constant. This answers a question of Green., Comment: 47 pages

We prove that there exists a constant $\gamma_{\mathrm{crit}}\approx .17566$ such that if $G\sim \mathbb{G}(n,1/2)$ then for any $\varepsilon > 0$ with high probability $G$ has a equipartition such that each vertex has $(\gamma_{\mathrm{crit}}-\varepsilon)\sqrt{n}$ more neighbors in its own part than in the other part and with high probability no such partition exists for a separation of $(\gamma_{\mathrm{crit}}+\varepsilon)\sqrt{n}$. The proof involves a number of tools ranging from isoperimetric results on vertex-transitive sets of graphs coming from Boolean functions, switchings, degree enumeration formulas, and the second moment method. Our results substantially strengthen recent work of Ferber, Kwan, Narayanan, and the last two authors on a conjecture of F\"uredi from 1988 and in particular prove the existence of fully-friendly bisections in $\mathbb{G}(n,1/2)$, Comment: 51 pages

Two landmark results in combinatorial random matrix theory, due to Koml\'os and Costello-Tao-Vu, show that discrete random matrices and symmetric discrete random matrices are typically nonsingular. In particular, in the language of graph theory, when $p$ is a fixed constant, the biadjacency matrix of a random Erd\H{o}s-R\'enyi bipartite graph $\mathbb{G}(n,n,p)$ and the adjacency matrix of an Erd\H{o}s-R\'enyi random graph $\mathbb{G}(n,p)$ are both nonsingular with high probability. However, very sparse random graphs (i.e., where $p$ is allowed to decay rapidly with $n$) are typically singular, due to the presence of "local" dependencies such as isolated vertices and pairs of degree-1 vertices with the same neighbour. In this paper we give a combinatorial description of the rank of a sparse random graph $\mathbb{G}(n,n,c/n)$ or $\mathbb{G}(n,c/n)$ in terms of such local dependencies, for all constants $c\ne e$ (and we present some evidence that the situation is very different for $c=e$). This gives an essentially complete answer to a question raised by Vu at the 2014 International Congress of Mathematicians. As applications of our main theorem and its proof, we also determine the asymptotic singularity probability of the 2-core of a sparse random graph, we show that the rank of a sparse random graph is extremely well-approximated by its matching number, and we deduce a central limit theorem for the rank of $\mathbb{G}(n,c/n)$.

Answering a pair of questions of Conrey, Gabbard, Grant, Liu, and Morrison, we prove that a triplet of dice drawn from the multiset model are intransitive with probability $1/4+o(1)$ and the probability a random pair of dice tie tends toward $\alpha n^{-1}$ for an explicitly defined constant $\alpha$. This extends and sharpens the recent results of Polymath regarding the balanced sequence model. We further show the distribution of larger tournaments converges to a universal tournamenton in both models. This limit naturally arises from the discrete spectrum of a certain skew-symmetric operator (given by the kernel in the title acting on $L^2([-1,1])$). The limit exhibits a degree of symmetry and can be used to prove that, for instance, the limiting probability that $A_i$ beats $A_{i+1}$ for $1\le i\le 4$ and that $A_5$ beats $A_1$ is $1/32+o(1)$. Furthermore, the limiting tournamenton has range contained in the discrete set $\{0,1\}$. This proves that the associated tournamenton is non-quasirandom in a dramatic fashion, vastly extending work of Cornacchia and H\k{a}z{\l}a regarding the continuous analogue of the balanced sequence model. The proof is based on a reduction to conditional central limit theorems (related to work of Polymath), the use of a "Poissonization" style method to reduce to computations with independent random variables, and the systematic use of switching-based arguments to extract cancellation in Fourier estimates when establishing local limit-type estimates., Comment: 37 pages

We derive an explicit distribution for the threshold sequence of the symmetric binary perceptron with Gaussian disorder, proving that the critical window is of constant width., Comment: 20 pages

We prove the existence of subspace designs with any given parameters, provided that the dimension of the underlying space is sufficiently large in terms of the other parameters of the design and satisfies the obvious necessary divisibility conditions. This settles an open problem from the 1970s. Moreover, we also obtain an approximate formula for the number of such designs., Comment: 61 pages

Consider a host hypergraph $G$ which contains a spanning structure due to minimum degree considerations. We collect three results proving that if the edges of $G$ are sampled at the appropriate rate then the spanning structure still appears with high probability in the sampled hypergraph. We prove such results for perfect matchings in hypergraphs above Dirac thresholds, for $K_r$-factors in graphs satisfying the Hajnal--Szemer\'edi minimum degree condition, and for bounded-degree spanning trees. In each case our proof is based on constructing a spread measure and then applying recent results on the (fractional) Kahn--Kalai conjecture connecting the existence of such measures with probabilistic thresholds. For our second result we give a shorter and more general proof of a recent theorem of Allen, B\"ottcher, Corsten, Davies, Jenssen, Morris, Roberts, and Skokan which handles the $r=3$ case with different techniques. In particular, we answer a question of theirs with regards to the number of $K_r$-factors in graphs satisfying the Hajnal--Szemer\'edi minimum degree condition., Comment: 41 pages. Corrected an error in the proof of Theorem 1.5 and improved exposition

Given 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 length $3,4,5$ as well as paths of length $3$ 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)$.

An $n$-vertex graph is called $C$-Ramsey if it has no clique or independent set of size $C\log_2 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 probabilities 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. One of the consequences of our result is the resolution of an old conjecture of Erd\H{o}s and McKay, for which Erd\H{o}s offered one of his notorious monetary prizes.

We investigate which finite Cayley graphs admit a quantum ergodic eigenbasis, proving that this holds for any Cayley graph on a group of size $n$ for which the sum of the dimensions of its irreducible representations is $o(n)$, yet there exist Cayley graphs that do not have any quantum ergodic eigenbasis., Comment: 8 pages

A celebrated theorem of Spencer states that for every set system $S_1,\dots, S_m \subseteq [n]$, there is a coloring of the ground set with $\{\pm 1\}$ with discrepancy $O(\sqrt{n\log(m/n+2)})$. We provide an algorithm to find such a coloring in near input-sparsity time $\tilde{O}(n+\sum_{i=1}^{m}|S_i|)$. A key ingredient in our work, which may be of independent interest, is a novel width reduction technique for solving linear programs, not of covering/packing type, in near input-sparsity time using the multiplicative weights update method., Comment: 18 pages; comments welcome

Let $X$ be a random vector valued in $\mathbb{R}^{m}$ such that $\|X\|_{2} \le 1$ almost surely. For every $k\ge 3$, we show that there exists a sigma algebra $\mathcal{F}$ generated by a partition of $\mathbb{R}^{m}$ into $k$ sets such that \[\|\operatorname{Cov}(X) - \operatorname{Cov}(\mathbb{E}[X\mid\mathcal{F}]) \|_{\mathrm{F}} \lesssim \frac{1}{\sqrt{\log{k}}}.\] This is optimal up to the implicit constant and improves on a previous bound due to Boedihardjo, Strohmer, and Vershynin. Our proof provides an efficient algorithm for constructing $\mathcal{F}$ and leads to improved accuracy guarantees for $k$-anonymous or differentially private synthetic data. We also establish a connection between the above problem of minimizing the covariance loss and the pinning lemma from statistical physics, providing an alternate (and much simpler) algorithmic proof in the important case when $X \in \{\pm 1\}^m/\sqrt{m}$ almost surely., Comment: 9 pages; comments welcome

We prove that with high probability $\mathbb{G}^{(3)}(n,n^{-1+o(1)})$ contains a spanning Steiner triple system for $n\equiv 1,3\pmod{6}$, establishing the exponent for the threshold probability for existence of a Steiner triple system. We also prove the analogous theorem for Latin squares. Our result follows from a novel bootstrapping scheme that utilizes iterative absorption as well as the connection between thresholds and fractional expectation-thresholds established by Frankston, Kahn, Narayanan, and Park., Comment: Improved exposition. Results unchanged. 23 pages, 1 figure

Define a permutation $\sigma$ to be coprime if $\gcd(m,\sigma(m)) = 1$ for $m\in[n]$. In this note, proving a recent conjecture of Pomerance, we prove that the number of coprime permutations on $[n]$ is $n!\cdot (c+o(1))^n$ where \[c = \prod_{p\text{ prime }}\frac{(p-1)^{2(1-1/p)}}{p\cdot (p-2)^{(1-2/p)}}.\] 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., Comment: 11 pages; simplified proof with improved quantitative aspects

Motivated by problems from compressed sensing, we determine the threshold behavior 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<\delta <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.

We prove several results about substructures in Latin squares. First, we explain how to adapt our recent work on high-girth Steiner triple systems to the setting of Latin squares, resolving a conjecture of Linial that there exist Latin squares with arbitrarily high girth. As a consequence, we see that the number of order-$n$ Latin squares with no intercalate (i.e., no $2\times2$ Latin subsquare) is at least $(e^{-9/4}n-o(n))^{n^{2}}$. Equivalently, $\mathbb{P}\left[\mathbf{N}=0\right]\ge e^{-n^{2}/4-o(n^{2})}=e^{-(1+o(1))\mathbb{E}\mathbf{N}}$, where $\mathbf{N}$ is the number of intercalates in a uniformly random order-$n$ Latin square. In fact, extending recent work of Kwan, Sah, and Sawhney, we resolve the general large-deviation problem for intercalates in random Latin squares, up to constant factors in the exponent: for any constant $0<\delta\le1$ we have $\mathbb{P}[\mathbf{N}\le(1-\delta)\mathbb{E}\mathbf{N}]=\exp(-\Theta(n^{2}))$ and for any constant $\delta>0$ we have $\mathbb{P}[\mathbf{N}\ge(1+\delta)\mathbb{E}\mathbf{N}]=\exp(-\Theta(n^{4/3}\log n))$. Finally, as an application of some new general tools for studying substructures in random Latin squares, we show that in almost all order-$n$ Latin squares, the number of cuboctahedra (i.e., the number of pairs of possibly degenerate $2\times2$ submatrices with the same arrangement of symbols) is of order $n^{4}$, which is the minimum possible. As observed by Gowers and Long, this number can be interpreted as measuring ``how associative'' the quasigroup associated with the Latin square is., Comment: 32 pages, 1 figure. Corrected typos and improved terminology

We prove a 1973 conjecture due to Erd\H{o}s on the existence of Steiner triple systems with arbitrarily high girth., Comment: Added details to some proofs. Final version, to appear in Annals of Mathematics

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: the numbers of rank-1 and rank-2 matroids on a ground set of size $n$ have exact representations in terms of well-known combinatorial functions, 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$. In our proof, we introduce a new approach for bounding the number of clique decompositions of a complete graph, using quasirandomness instead of the so-called entropy method that is common in this area.

We give an online algorithm that with high probability computes a $\left(\frac{e}{e-1} + o(1)\right)\Delta$ edge coloring on a graph $G$ with maximum degree $\Delta = \omega(\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 recurrences based approach for arguing correlation decay., Comment: 22 pages, 1 figure

This is a companion note to the paper "Almost all Steiner triple systems have perfect matchings (arXiv:1611.02246). That paper contains several general lemmas about random Steiner triple systems; in this note we record analogues of these lemmas for random Latin squares, which in particular are necessary ingredients for our recent paper "Large deviations in random Latin squares" (arXiv:2106.11932). Most important is a relationship between uniformly random order-$n$ Latin squares and the triangle removal process on the complete tripartite graph $K_{n,n,n}$., Comment: arXiv admin note: text overlap with arXiv:1611.02246

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., Comment: 26 pages; comments welcome!

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 $k\leq 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 $k\geq p+2$, completely characterizing when classical polynomials suffice., Comment: 11 pages

In this note, we study large deviations of the number $\mathbf{N}$ of intercalates ($2\times2$ combinatorial subsquares which are themselves Latin squares) in a random $n\times n$ Latin square. In particular, for constant $\delta>0$ we prove that $\Pr(\mathbf{N}\le(1-\delta)n^{2}/4)\le\exp(-\Omega(n^{2}))$ and $\Pr(\mathbf{N}\ge(1+\delta)n^{2}/4)\le\exp(-\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., Comment: 15 pages

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 $k\ge 3$ and $\lambda > 0$, an Erd\H{o}s--R\'enyi random graph $G\sim\mathbb{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., Comment: 25 pages

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$., Comment: 12 pages; comments welcome!

Consider $n=\ell+m$ individuals, where $\ell\le 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 p\le 1-(\log n)^{-1/16}$. We show that for $n=\ell+m$ with $\Delta=m-\ell\le(\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 \[\Phi\bigg(\frac{p\Delta\sqrt{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., Comment: 30 pages

Resolving a conjecture of F\"uredi from 1988, we prove that with high probability, the random graph $G(n,1/2)$ admits a friendly bisection of its vertex set, i.e., a partition of its vertex set into two parts whose sizes differ by at most one in which $n-o(n)$ vertices have at least as many neighbours in their own part as across. The engine of our proof is a new method to study stochastic processes driven by degree information in random graphs; this involves combining enumeration techniques with an abstract second moment argument., Comment: 21 pages, 3 appendices

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 Banaszczyk's 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., Comment: 8 pages

Let $M_n$ be a random $n\times n$ matrix with i.i.d. $\text{Bernoulli}(1/2)$ entries. We show that for fixed $k\ge 1$, \[\lim_{n\to \infty}\frac{1}{n}\log_2\mathbb{P}[\text{corank }M_n\ge k] = -k.\], Comment: 8 pages; comments welcome!

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 $\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., Comment: 24 pages

We show that for every $1 \le k \le d/(\log d)^C$, every finite transitive set of unit vectors in $\mathbb{R}^d$ lies within distance $O(1/\sqrt{\log (d/k)})$ of some codimension $k$ subspace, and this distance bound is best possible. This extends a result of Ben Green, who proved it for $k=1$., Comment: 17 pages

Let $\vec{w} = (w_1,\dots, w_n) \in \mathbb{R}^{n}$. We show that for any $n^{-2}\le\epsilon\le 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 W\k{e}grzycki and leads to a similar improvement in the parameterized (by the number of bins) runtime of bin packing., Comment: 10 pages; revised version

We prove that every $n$-vertex tournament has at most $n\left(\frac{n-1}{2}\right)^k$ walks of length $k$., Comment: Appendix with alternative entropy proof by Dingding Dong and Tomasz \'Slusarczyk

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 \[\|\widetilde{A}\| = O\left(\sqrt{n/\epsilon}\right).\] 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$., Comment: 13 pages; comments welcome!