Search

Let $\epsilon_1, \dotsc, \epsilon_n$ be i.i.d. Rademacher random variables taking values $\pm 1$ with probability $1/2$ each. Given an integer vector $\boldsymbol{a} = (a_1, \dotsc, a_n)$, its concentration probability is the quantity $\rho(\boldsymbol{a}):=\sup_{x\in \mathbb{Z}}\Pr(\epsilon_1 a_1+\dots+\epsilon_n a_n = x)$. The Littlewood-Offord problem asks for bounds on $\rho(\boldsymbol{a})$ under various hypotheses on $\boldsymbol{a}$, whereas the inverse Littlewood-Offord problem, posed by Tao and Vu, asks for a characterization of all vectors $\boldsymbol{a}$ for which $\rho(\boldsymbol{a})$ is large. In this paper, we study the associated counting problem: How many integer vectors $\boldsymbol{a}$ belonging to a specified set have large $\rho(\boldsymbol{a})$? The motivation for our study is that in typical applications, the inverse Littlewood-Offord theorems are only used to obtain such counting estimates. Using a more direct approach, we obtain significantly better bounds for this problem than those obtained using the inverse Littlewood--Offord theorems of Tao and Vu and of Nguyen and Vu. Moreover, we develop a framework for deriving upper bounds on the probability of singularity of random discrete matrices that utilizes our counting result. To illustrate the methods, we present the first `exponential-type' (i.e., $\exp(-n^c)$ for some positive constant $c$) upper bounds on the singularity probability for the following two models: (i) adjacency matrices of dense signed random regular digraphs, for which the previous best known bound is $O(n^{-1/4})$ due to Cook; and (ii) dense row-regular $\{0,1\}$-matrices, for which the previous best known bound is $O_{C}(n^{-C})$ for any constant $C>0$ due to Nguyen.

A central problem in extremal graph theory is to estimate, for a given graph $H$, the number of $H$-free graphs on a given set of $n$ vertices. In the case when $H$ is not bipartite, fairly precise estimates on this number are known. In particular, thirty years ago, Erd\H{o}s, Frankl, and R\"odl proved that there are $2^{(1+o(1))\text{ex}(n,H)}$ such graphs. In the bipartite case, however, nontrivial bounds have been proven only for relatively few special graphs $H$. We make a first attempt at addressing this enumeration problem for a general bipartite graph $H$. We show that an upper bound of $2^{O(\text{ex}(n,H))}$ on the number of $H$-free graphs with $n$ vertices follows merely from a rather natural assumption on the growth rate of $n \mapsto \text{ex}(n,H)$; an analogous statement remains true when $H$ is a uniform hypergraph. Subsequently, we derive several new results, along with most previously known estimates, as simple corollaries of our theorem. At the heart of our proof lies a general supersaturation statement that extends the seminal work of Erd\H{o}s and Simonovits. The bounds on the number of $H$-free hypergraphs are derived from it using the method of hypergraph containers.

Given a hypergraph $\Gamma=(\Omega,\mathcal{X})$ and a sequence $\mathbf{p} = (p_\omega)_{\omega\in \Omega}$ of values in $(0,1)$, let $\Omega_{\mathbf{p}}$ be the random subset of $\Omega$ obtained by keeping every vertex $\omega$ independently with probability $p_\omega$. We investigate the general question of deriving fine (asymptotic) estimates for the probability that $\Omega_{\mathbf{p}}$ is an independent set in $\Gamma$, which is an omnipresent problem in probabilistic combinatorics. Our main result provides a sequence of upper and lower bounds on this probability, each of which can be evaluated explicitly in terms of the joint cumulants of small sets of edge indicator random variables. Under certain natural conditions, these upper and lower bounds coincide asymptotically, thus giving the precise asymptotics of the probability in question. We demonstrate the applicability of our results with two concrete examples: subgraph containment in random (hyper)graphs and arithmetic progressions in random subsets of the integers., Comment: 28 pages

The K{\L}R conjecture of Kohayakawa, {\L}uczak, and R\"odl is a statement that allows one to prove that asymptotically almost surely all subgraphs of the random graph G_{n,p}, for sufficiently large p : = p(n), satisfy an embedding lemma which complements the sparse regularity lemma of Kohayakawa and R\"odl. We prove a variant of this conjecture which is sufficient for most known applications to random graphs. In particular, our result implies a number of recent probabilistic versions, due to Conlon, Gowers, and Schacht, of classical extremal combinatorial theorems. We also discuss several further applications., Comment: 33 pages

A setAof positive integers is aBh-setif all the sums of the forma1+ . . . +ah, witha1,. . .,ah∈Aanda1⩽ . . . ⩽ah, are distinct. We provide asymptotic bounds for the number ofBh-sets of a given cardinality contained in the interval [n] = {1,. . .,n}. As a consequence of our results, we address a problem of Cameron and Erdős (1990) in the context ofBh-sets. We also use these results to estimate the maximum size of aBh-sets contained in a typical (random) subset of [n] with a given cardinality.

In this survey we describe a recently-developed technique for bounding the number (and controlling the typical structure) of finite objects with forbidden substructures. This technique exploits a subtle clustering phenomenon exhibited by the independent sets of uniform hypergraphs whose edges are sufficiently evenly distributed; more precisely, it provides a relatively small family of 'containers' for the independent sets, each of which contains few edges. We attempt to convey to the reader a general high-level overview of the method, focusing on a small number of illustrative applications in areas such as extremal graph theory, Ramsey theory, additive combinatorics, and discrete geometry, and avoiding technical details as much as possible., Comment: 29 pages

A well-known theorem of Sperner describes the largest collections of subsets of an $n$-element set none of which contains another set from the collection. Generalising this result, Erd\H{o}s characterised the largest families of subsets of an $n$-element set that do not contain a chain of sets $A_1 \subset \dotsc \subset A_k$ of an arbitrary length $k$. The extremal families contain all subsets whose cardinalities belong to an interval of length $k-1$ centred at $n/2$. In a far-reaching extension of Sperner's theorem, Kleitman determined the smallest number of chains of length two that have to appear in a collection of a given number $a$ of subsets of an $n$-element set. For every $a$, this minimum is achieved by the collection comprising $a$ sets whose cardinalities are as close to $n/2+1/4$ as possible. We show that the same is true about chains of an arbitrary length $k$, for all $a$ and $n$, confirming the prediction Kleitman made fifty years ago. We also characterise all families of $a$ subsets with the smallest number of chains of length $k$ for all $a$ for which this smallest number is positive. Our argument is inspired by an elegant probabilistic lemma from a recent paper of Noel, Scott, and Sudakov, which in turn can be traced back to Lubell's proof of Sperner's theorem., Comment: 13 pages

We characterize the structure of maximum-size sum-free subsets of a random subset of an abelian group G. In particular, we determine the threshold above which, with high probability as |G| → ∞, each such subset is contained in some maximum-size sum-free subset of G, whenever q divides |G| for some (fixed) prime q with q ≡ 2 (mod 3). Moreover, in the special case G = ℤ2n , we determine the sharp threshold for the above property. The proof uses recent ‘transference’ theorems of Conlon and Gowers, together with stability theorems for sum-free sets of abelian groups.

In this paper we study sum-free sets of order m in finite abelian groups. We prove a general theorem about independent sets in 3-uniform hypergraphs, which allows us to deduce structural results in the sparse setting from stability results in the dense setting. As a consequence, we determine the typical structure and asymptotic number of sum-free sets of order m in abelian groups G whose order n is divisible by a prime q with q ≡ 2 (mod 3), for every m ⩾ \(C(q)\sqrt {n\log n} \), thus extending and refining a theorem of Green and Ruzsa. In particular, we prove that almost all sumfree subsets of size m are contained in a maximum-size sum-free subset of G. We also give a completely self-contained proof of this statement for abelian groups of even order, which uses spectral methods and a new bound on the number of independent sets of a fixed size in an (n, d, λ)-graph.

In this paper we study sum-free subsets of the set $\{1,...,n\}$, that is, subsets of the first $n$ positive integers which contain no solution to the equation $x + y = z$. Cameron and Erd\H{o}s conjectured in 1990 that the number of such sets is $O(2^{n/2})$. This conjecture was confirmed by Green and, independently, by Sapozhenko. Here we prove a refined version of their theorem, by showing that the number of sum-free subsets of $[n]$ of size $m$ is $2^{O(n/m)} {\lceil n/2 \rceil \choose m}$, for every $1 \le m \le \lceil n/2 \rceil$. For $m \ge \sqrt{n}$, this result is sharp up to the constant implicit in the $O(\cdot)$. Our proof uses a general bound on the number of independent sets of size $m$ in 3-uniform hypergraphs, proved recently by the authors, and new bounds on the number of integer partitions with small sumset., Comment: 32 pages

In this paper we extend a classical theorem of Corrádi and Hajnal into the setting of sparse random graphs. We show that ifp(n) ≫ (logn/n)1/2, then asymptotically almost surely every subgraph ofG(n,p) with minimum degree at least (2/3 +o(1))npcontains a triangle packing that covers all but at mostO(p−2) vertices. Moreover, the assumption onpis optimal up to the (logn)1/2factor and the presence of the set ofO(p−2) uncovered vertices is indispensable. The main ingredient in the proof, which might be of independent interest, is an embedding theorem which says that if one imposes certain natural regularity conditions on all three pairs in a balanced 3-partite graph, then this graph contains a perfect triangle packing.

An n-vertex graph G is c-Ramsey if it contains neither a complete nor an empty induced subgraph of size greater than c log n. Erdős, Faudree and Sós conjectured that every c-Ramsey graph with n vertices contains Ω(n5/2) induced subgraphs, any two of which differ either in the number of vertices or in the number of edges, i.e., the number of distinct pairs (|V(H)|, |E(H)|), as H ranges over all induced subgraphs of G, is Ω(n5/2). We prove an Ω(n2.3693) lower bound.

In this paper, we address the problem of packing large trees in $G_{n,p}$. In particular, we prove the following result. Suppose that $T_1, \dotsc, T_N$ are $n$-vertex trees, each of which has maximum degree at most $(np)^{1/6} / (\log n)^6$. Then with high probability, one can find edge-disjoint copies of all the $T_i$ in the random graph $G_{n,p}$, provided that $p \geq (\log n)^{36}/n$ and $N \le (1-\varepsilon)np/2$ for a positive constant $\varepsilon$. Moreover, if each $T_i$ has at most $(1-\alpha)n$ vertices, for some positive $\alpha$, then the same result holds under the much weaker assumptions that $p \geq (\log n)^2/(cn)$ and $\Delta(T_i) \leq c np / \log n$ for some~$c$ that depends only on $\alpha$ and $\varepsilon$. Our assumptions on maximum degrees of the trees are significantly weaker than those in all previously known approximate packing results.

A set of elements of a finite abelian group is called sum-free if it contains no Schur triple, i.e., no triple of elements $x,y,z$ with $x+y=z$. The study of how large the largest sum-free subset of a given abelian group is had started more than thirty years before it was finally resolved by Green and Ruzsa a decade ago. We address the following more general question. Suppose that a set $A$ of elements of an abelian group $G$ has cardinality $a$. How many Schur triples must $A$ contain? Moreover, which sets of $a$ elements of $G$ have the smallest number of Schur triples? In this paper, we answer these questions for various groups $G$ and ranges of $a$., Comment: 20 pages; corrected the erroneous equality in (1) in the statement of Theorem 1.3

Nous etudions la structure de phase, en grande dimension, d’un modele de spheres dures sur le reseau $\mathbb{Z}^{d}$. Nous prouvons que le modele presente plusieurs mesures lorsque le parametre de densite depasse $Cd^{-1/3}(\log d)^{2}$, ameliorant ainsi la borne de $Cd^{-1/4}(\log d)^{3/4}$ obtenue par Galvin et Kahn. Notre approche repose sur l’etude de certaines classes d’ensembles separateurs dans $\mathbb{Z}^{d}$, constituees d’ensembles impaires, qui delimitent la frontiere entre differentes phases du modele de spheres dures. Nous faisons une analyse combinatoire precise de la structure de ces ensembles separateurs et obtenons une forme quantitative de la concentration des differentes formes possibles prises par ces ensembles lorsque la dimension $d$ tend vers l’infini. Cette analyse repose sur des methodes obtenues auparavant par le premier auteur, tout en les ameliorant.

Given a class of graphs F, we say that a graph G is universal for F, or F-universal, if every H in F is contained in G as a subgraph. The construction of sparse universal graphs for various families F has received a considerable amount of attention. One is particularly interested in tight F-universal graphs, i.e., graphs whose number of vertices is equal to the largest number of vertices in a graph from F. Arguably, the most studied case is that when F is some class of trees. Given integers n and \Delta, we denote by T(n,\Delta) the class of all n-vertex trees with maximum degree at most \Delta. In this work, we show that every n-vertex graph satisfying certain natural expansion properties is T(n,\Delta)-universal or, in other words, contains every spanning tree of maximum degree at most \Delta. Our methods also apply to the case when \Delta is some function of n. The result has a few very interesting implications. Most importantly, we obtain that the random graph G(n,p) is asymptotically almost surely (a.a.s.) universal for the class of all bounded degree spanning (i.e., n-vertex) trees provided that p \geq c n^{-1/3} \log^2n where c > 0 is a constant. Moreover, a corresponding result holds for the random regular graph of degree pn. In fact, we show that if \Delta satisfies \log n \leq \Delta \leq n^{1/3}, then the random graph G(n,p) with p \geq c \Delta n^{-1/3} \log n and the random r-regular n-vertex graph with r \geq c\Delta n^{2/3} \log n are a.a.s. T(n,\Delta)-universal. Another interesting consequence is the existence of locally sparse n-vertex T(n,\Delta)-universal graphs. For constant \Delta, we show that one can (randomly) construct n-vertex T(n,\Delta)-universal graphs with clique number at most five. Finally, we show robustness of random graphs with respect to being universal for T(n,\Delta) in the context of the Maker-Breaker tree-universality game., Comment: 25 pages

A grounded M-Lipschitz function on a rooted d-ary tree is an integer-valued map on the vertices that changes by at most along edges and attains the value zero on the leaves. We study the behavior of such functions, specifically, their typical value at the root v_0 of the tree. We prove that the probability that the value of a uniformly chosen random function at v_0 is more than M+t is doubly-exponentially small in t. We also show a similar bound for continuous (real-valued) grounded Lipschitz functions., Comment: 8 pages

Many important theorems in combinatorics, such as Szemer\'edi's theorem on arithmetic progressions and the Erd\H{o}s-Stone Theorem in extremal graph theory, can be phrased as statements about independent sets in uniform hypergraphs. In recent years, an important trend in the area has been to extend such classical results to the so-called sparse random setting. This line of research culminated recently in the breakthroughs of Conlon and Gowers and of Schacht, who developed general tools for solving problems of this type. In this paper, we provide a third, completely different approach to proving extremal and structural results in sparse random sets. We give a structural characterization of the independent sets in a large class of uniform hypergraphs by showing that every independent set is almost contained in one of a small number of relatively sparse sets. We then derive many interesting results as fairly straightforward consequences of this abstract theorem. In particular, we prove the well-known conjecture of Kohayakawa, \L uczak and R\"odl, a probabilistic embedding lemma for sparse graphs. We also give alternative proofs of many of the results of Conlon and Gowers and Schacht, and obtain their natural counting versions, which in some cases are considerably stronger. We moreover prove a sparse version of the Erd\H{o}s-Frankl-R\"odl Theorem on the number of H-free graphs and extend a result of R\"odl and Ruci\'nski on Ramsey properties in sparse random graphs to the general, non-symmetric setting. We remark that similar results have been discovered independently by Saxton and Thomason, and that, in parallel to this work, Conlon, Gowers, Samotij and Schacht have proved a sparse analogue of the counting lemma for subgraphs of the random graph G(n,p), which may be viewed as a version of the K\L R conjecture that is stronger in some ways and weaker in others., Comment: 42 pages, in this version we prove a slightly stronger variant of our main theorem

Two years ago, Conlon and Gowers, and Schacht proved general theorems that allow one to transfer a large class of extremal combinatorial results from the deterministic to the probabilistic setting. Even though the two papers solve the same set of long-standing open problems in probabilistic combinatorics, the methods used in them vary significantly and therefore yield results that are not comparable in certain aspects. The theorem of Schacht can be applied in a more general setting and yields stronger probability estimates, whereas the one of Conlon and Gowers also implies random versions of some structural statements such as the famous stability theorem of Erdos and Simonovits. In this paper, we bridge the gap between these two transference theorems. Building on the approach of Schacht, we prove a general theorem that allows one to transfer deterministic stability results to the probabilistic setting that is somewhat more general and stronger than the one obtained by Conlon and Gowers. We then use this theorem to derive several new results, among them a random version of the Erdos-Simonovits stability theorem for arbitrary graphs. The main new idea, a refined approach to multiple exposure when considering subsets of binomial random sets, may be of independent interest., Comment: 19 pages; slightly simplified proof of the main theorem; fixed a few typos

For fixed graphs F1,…,Fr, we prove an upper bound on the threshold function for the property that G(n, p) → (F1,…,Fr). This establishes the 1-statement of a conjecture of Kohayakawa and Kreuter.