BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
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.
Define a permutation σ to be coprime if gcd(m,σ(m))=1 for m∈[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 where c=∏p prime p⋅(p−2)(1−2/p)(p−1)2(1−1/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.
Let X be a random vector valued in Rm such that ∥X∥2≤1 almost surely. For every k≥3, we show that there exists a sigma algebra F generated by a partition of Rm into k sets such that ∥Cov(X)−Cov(E[X∣F])∥F≲logk1. 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 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∈{±1}m/m almost surely.
A celebrated theorem of Spencer states that for every set system S1,…,Sm⊆[n], there is a coloring of the ground set with {±1} with discrepancy O(nlog(m/n+2)). We provide an algorithm to find such a coloring in near input-sparsity time O~(n+∑i=1m∣Si∣). 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.
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×2 Latin subsquare) is at least (e−9/4n−o(n))n2. Equivalently, P[N=0]≥e−n2/4−o(n2)=e−(1+o(1))EN, where 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<δ≤1 we have P[N≤(1−δ)EN]=exp(−Θ(n2)) and for any constant δ>0 we have P[N≥(1+δ)EN]=exp(−Θ(n4/3logn)). 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×2 submatrices with the same arrangement of symbols) is of order n4, 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.
We prove that with high probability G(3)(n,n−1+o(1)) contains a spanning Steiner triple system for n≡1,3(mod6), 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.
The following combinatorial conjecture arises naturally from recent ergodic-theoretic work of Ackelsberg, Bergelson, and Best. Let M1, M2 be k×k integer matrices, G be a finite abelian group of order N, and A⊆Gk with ∣A∣≥αNk. If M1, M2, M1−M2, and M1+M2 are automorphisms of Gk, is it true that there exists a popular difference d∈Gk∖{0} such that #{x∈Gk:x,x+M1d,x+M2d,x+(M1+M2)d∈A}≥(α4−o(1))Nk. We show that this conjecture is false in general, but holds for G=Fpn with p an odd prime given the additional spectral condition that no pair of eigenvalues of M1M2−1 (over Fp) 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 (F5n)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.
Let Mn be a random n×n matrix with i.i.d. Bernoulli(1/2) entries. We show that for fixed k≥1, limn→∞n1log2P[corank Mn≥k]=−k.
We show that for every 1≤k≤d/(logd)C, every finite transitive set of unit vectors in Rd lies within distance O(1/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.
Let H be a graph allowing loops as well as vertex and edge weights. We prove that, for every triangle-free graph G without isolated vertices, the weighted number of graph homomorphisms hom(G,H) satisfies the inequality hom(G,H)≤∏uv∈E(G)hom(Kdu,dv,H)1/(dudv), where du denotes the degree of vertex u in G. In particular, one has hom(G,H)1/∣E(G)∣≤hom(Kd,d,H)1/d2 for every d-regular triangle-free G. The triangle-free hypothesis on G is best possible. More generally, we prove a graphical Brascamp-Lieb type inequality, where every edge of G is assigned some two-variable function. These inequalities imply tight upper bounds on the partition function of various statistical models such as the Ising and Potts models, which includes independent sets and graph colorings. For graph colorings, corresponding to H=Kq, we show that the triangle-free hypothesis on G may be dropped; this is also valid if some of the vertices of Kq are looped. A corollary is that among d-regular graphs, G=Kd,d maximizes the quantity cq(G)1/∣V(G)∣ for every q and d, where cq(G) counts proper q-colorings of G. Finally, we show that if the edge-weight matrix of H is positive semidefinite, then hom(G,H)≤∏v∈V(G)hom(Kdv+1,H)1/(dv+1). This implies that among d-regular graphs, G=Kd+1 maximizes hom(G,H)1/∣V(G)∣. For 2-spin Ising models, our results give a complete characterization of extremal graphs: complete bipartite graphs maximize the partition function of 2-spin antiferromagnetic models and cliques maximize the partition function of ferromagnetic models. These results settle a number of conjectures by Galvin-Tetali, Galvin, and Cohen-Csikvári-Perkins-Tetali, and provide an alternate proof to a conjecture by Kahn.
We improve the upper bound for diagonal Ramsey numbers to R(k+1,k+1)≤exp(−c(logk)2)(k2k) for k≥3. To do so, we build on a quasirandomness and induction framework for Ramsey numbers introduced by Thomason and extended by Conlon, demonstrating optimal "effective quasirandomness" results about convergence of graphs. This optimality represents a natural barrier to improvement.
We prove that for all fixed p>2, the translative packing density of unit ℓp-balls in Rn is at most 2(γp+o(1))n with γp<−1/p. This is the first exponential improvement in high dimensions since van der Corput and Schaake (1936).
In this work, we analyze dimension reduction algorithms based on the Kac walk and discrete variants. (1) For n points in Rd, we design an optimal Johnson-Lindenstrauss (JL) transform based on the Kac walk which can be applied to any vector in time O(dlogd) for essentially the same restriction on n as in the best-known transforms due to Ailon and Liberty [SODA, 2008], and Bamberger and Krahmer [arXiv, 2017]. Our algorithm is memory-optimal, and outperforms existing algorithms in regimes when n is sufficiently large and the distortion parameter is sufficiently small. In particular, this confirms a conjecture of Ailon and Chazelle [STOC, 2006] in a stronger form. (2) The same construction gives a simple transform with optimal Restricted Isometry Property (RIP) which can be applied in time O(dlogd) for essentially the same range of sparsity as in the best-known such transform due to Ailon and Rauhut [Discrete Comput. Geom., 2014]. (3) We show that by fixing the angle in the Kac walk to be π/4 throughout, one obtains optimal JL and RIP transforms with almost the same running time, thereby confirming -- up to a loglogd factor -- a conjecture of Avron, Maymounkov, and Toledo [SIAM J. Sci. Comput., 2010]. Our moment-based analysis of this modification of the Kac walk may also be of independent interest.
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), building on work of Gilmer and Kopparty and of Berkowitz. These results improve an anticoncentration result of Fox, Kwan, and Sauermann and partially answers a question of Fox, Kwan, and Sauermann. We also derive a local limit central limit theorem for induced subgraph counts, as long as 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, and finding a graph H for which anticoncentration for induced subgraph counts fails in 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-term arithmetic progressions in subsets of Z/nZ 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.
We examine the behavior of the number of k-term arithmetic progressions in a random subset of Z/nZ. We prove that if a set is chosen by including each element of Z/nZ independently with constant probability p, then the resulting distribution of k-term arithmetic progressions in that set, while obeying a central limit theorem, does not obey a local central limit theorem. The methods involve decomposing the random variable into homogeneous degree d polynomials with respect to the Walsh/Fourier basis. Proving a suitable multivariate central limit theorem for each component of the expansion gives the desired result.
We show that every matrix A∈Rn×n is at least δ∥A∥-close to a real matrix A+E∈Rn×n whose eigenvectors have condition number at most O~n(δ−1). In fact, we prove that, with high probability, taking E to be a sufficiently small multiple of an i.i.d. real sub-Gaussian matrix of bounded density suffices. This essentially confirms a speculation of Davies, and of Banks, Kulkarni, Mukherjee, and Srivastava, who recently proved such a result for i.i.d. complex Gaussian matrices. Along the way, we also prove non-asymptotic estimates on the minimum possible distance between any two eigenvalues of a random matrix whose entries have arbitrary means; this part of our paper may be of independent interest.
Let A be an n×n real matrix, and let M be an n×n random matrix whose entries are i.i.d sub-Gaussian random variables with mean 0 and variance 1. We make two contributions to the study of sn(A+M), the smallest singular value of A+M. (1) We show that for all ε≥0, P[sn(A+M)≤ε]=O(εn)+2e−Ω(n), provided only that A has Ω(n) singular values which are O(n). This extends a well-known result of Rudelson and Vershynin, which requires all singular values of A to be O(n). (2) We show that any bound of the form sup∥A∥≤nC1P[sn(A+M)≤n−C3]≤n−C2 must have C3=Ω(C1C2). This complements a result of Tao and Vu, who proved such a bound with C3=O(C1C2+C1+1), and counters their speculation of possibly taking C3=O(C1+C2).
We present a randomized algorithm which takes as input an undirected graph G on n vertices with maximum degree Δ, and a number of colors k≥(8/3+oΔ(1))Δ, and returns -- in expected time O~(nΔ2logk) -- a proper k-coloring of G distributed perfectly uniformly on the set of all proper k-colorings of G. Notably, our sampler breaks the barrier at k=3Δ encountered in recent work of Bhandari and Chakraborty [STOC 2020]. We also sketch how to modify our methods to relax the restriction on k to k≥(8/3−ε0)Δ for an absolute constant ε0>0. As in the work of Bhandari and Chakraborty, and the pioneering work of Huber [STOC 1998], our sampler is based on Coupling from the Past [Propp&Wilson, Random Struct. Algorithms, 1995] and the bounding chain method [Huber, STOC 1998; Häggström&Nelander, Scand. J. Statist., 1999]. Our innovations include a novel bounding chain routine inspired by Jerrum's analysis of the Glauber dynamics [Random Struct. Algorithms, 1995], as well as a preconditioning routine for bounding chains which uses the algorithmic Lovász Local Lemma [Moser&Tardos, J.ACM, 2010].
A k-universal permutation, or k-superpermutation, is a permutation that contains all permutations of length k as patterns. The problem of finding the minimum length of a k-superpermutation has recently received significant attention in the field of permutation patterns. One can ask analogous questions for other classes of objects. In this paper, we study k-supertrees. For each d≥2, we focus on two types of rooted plane trees called d-ary plane trees and [d]-trees. Motivated by recent developments in the literature, we consider "contiguous" and "noncontiguous" notions of pattern containment for each type of tree. We obtain both upper and lower bounds on the minimum possible size of a k-supertree in three cases; in the fourth, we determine the minimum size exactly. One of our lower bounds makes use of a recent result of Albert, Engen, Pantone, and Vatter on k-universal layered permutations.
Let A be the adjacency matrix of a uniformly random d-regular digraph on n vertices, and suppose that min(d,n−d)≥λn. We show that for any κ≥0, P[sn(A)≤κ]≤Cλκn+2e−cλn. Up to the constants Cλ,cλ>0, our bound matches optimal bounds for n×n random matrices, each of whose entries is an i.i.d Ber(d/n) random variable. The special case κ=0 of our result confirms a conjecture of Cook regarding the probability of singularity of dense random regular digraphs.
Fix a non-CM elliptic curve E/Q, and let aE(p)=p+1−#E(Fp) denote the trace of Frobenius at p. The Sato-Tate conjecture gives the limiting distribution μST of aE(p)/(2p) within [−1,1]. We establish bounded gaps for primes in the context of this distribution. More precisely, given an interval I⊆[−1,1], let pI,n denote the nth prime such that aE(p)/(2p)∈I. We show liminfn→∞(pI,n+m−pI,n)<∞ for all m≥1 for "most" intervals, and in particular, for all I with μST(I)≥0.36. Furthermore, we prove a common generalization of our bounded gap result with the Green-Tao theorem. To obtain these results, we demonstrate a Bombieri-Vinogradov type theorem for Sato-Tate primes.
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 δclog(1/δ)N3. A similar bound holds in higher dimensions, or for any configuration with at least 5 points or affine dimension at least 3.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.