An official website of the United States government
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
Abstract We study quantitative relationships between the triangle removal lemma and several of its variants. One such variant, which we call the triangle-free lemma , states that for each $$\epsilon>0$$ there exists M such that every triangle-free graph G has an $$\epsilon$$ -approximate homomorphism to a triangle-free graph F on at most M vertices (here an $$\epsilon$$ -approximate homomorphism is a map $$V(G) \to V(F)$$ where all but at most $$\epsilon \left\lvert{V(G)}\right\rvert^2$$ edges of G are mapped to edges of F ). One consequence of our results is that the least possible M in the triangle-free lemma grows faster than exponential in any polynomial in $$\epsilon^{-1}$$ . We also prove more general results for arbitrary graphs, as well as arithmetic analogues over finite fields, where the bounds are close to optimal.more » « less
-
Abstract We prove several different anti-concentration inequalities for functions of independent Bernoulli-distributed random variables. First, motivated by a conjecture of Alon, Hefetz, Krivelevich and Tyomkyn, we prove some “Poisson-type” anti-concentration theorems that give bounds of the form 1/ e + o (1) for the point probabilities of certain polynomials. Second, we prove an anti-concentration inequality for polynomials with nonnegative coefficients which extends the classical Erdős–Littlewood–Offord theorem and improves a theorem of Meka, Nguyen and Vu for polynomials of this type. As an application, we prove some new anti-concentration bounds for subgraph counts in random graphs.more » « less
