Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-26T03:28:39.783Z Has data issue: false hasContentIssue false
  • English
  • Français

Combinatorial anti-concentration inequalities, with applications

Part of: Graph theory Extremal combinatorics Combinatorial probability

Published online by Cambridge University Press:  30 June 2021

JACOB FOX ,
MATTHEW KWAN  and
LISA SAUERMANN
JACOB FOX
Affiliation:
Department of Mathematics, Stanford University, 450 Jane Stanford Way, Building 380, Stanford, CA 94305-2125, U.S.A. e-mails: [email protected], [email protected], [email protected]
MATTHEW KWAN
Affiliation:
Department of Mathematics, Stanford University, 450 Jane Stanford Way, Building 380, Stanford, CA 94305-2125, U.S.A. e-mails: [email protected], [email protected], [email protected]
LISA SAUERMANN
Affiliation:
Department of Mathematics, Stanford University, 450 Jane Stanford Way, Building 380, Stanford, CA 94305-2125, U.S.A. e-mails: [email protected], [email protected], [email protected]
Get access Rights & Permissions [Opens in a new window]

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.

MSC classification

Primary: 05D40: Probabilistic methods 60C05: Combinatorial probability 05C80: Random graphs
Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 171 , Issue 2 , September 2021 , pp. 227 - 248
Copyright
© The Author(s), 2021. Published by Cambridge University Press on behalf of Cambridge Philosophical Society

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

Research supported by a Packard Fellowship and by NSF Award DMS-1855635.

‡

Research supported in part by SNSF project 178493.

References

REFERENCES

Alon, N.. Combinatorial Nullstellensatz. Combin. Probab. Comput. 8 (1999), no. 1-2, 7–29, Recent trends in combinatorics (Mátraháza, 1995).CrossRefGoogle Scholar
Alon, N., Hefetz, D., Krivelevich, M. and Tyomkyn, M.. Edge-statistics on large graphs. Combin. Probab. Comput. 29 (2020), no. 2, 163–189.CrossRefGoogle Scholar
Barbour, A. D., Karoński, M. and Ruciński, A.. A central limit theorem for decomposable random variables with applications to random graphs. J. Combin. Theory Ser. B 47 (1989), no. 2, 125–145.CrossRefGoogle Scholar
Berkowitz, R.. A quantitative local limit theorem for triangles in random graphs. arXiv preprint arXiv:1610.01281 (2016).Google Scholar
Berkowitz, R.. A local limit theorem for cliques in G(n,p). arXiv preprint arXiv:1811.03527 (2018).Google Scholar
Bollobás, B.. Random graphs, second ed. Camb. Stud. Adv. Math., vol. 73. (Cambridge University Press, Cambridge, 2001).Google Scholar
Bollobás, B., Pebody, L. and Riordan, O.. Contraction-deletion invariants for graphs. J. Combin. Theory Ser. B 80 (2000), no. 2, 320–345.CrossRefGoogle Scholar
Costello, K. P., Tao, T. and Vu, V.. Random symmetric matrices are almost surely nonsingular. Duke Math. J. 135 (2006), no. 2, 395–413.CrossRefGoogle Scholar
de Mier, A. and Noy, M.. On graphs determined by their Tutte polynomials. Graphs Combin. 20 (2004), no. 1, 105–119.CrossRefGoogle Scholar
Dunbar, S. R.. Topics in probability theory and stochastic processes: The moderate deviations result, 2012, URL: https://www.math.unl.edu/⁓sdunbar1/ProbabilityTheory/Lessons/BernoulliTrials/ModerateDeviations/moderatedeviations.pdf. Last visited on 2018/12/03.Google Scholar
Erdös, P.. On a lemma of Littlewood and Offord. Bull. Amer. Math. Soc. 51 (1945), 898–902.CrossRefGoogle Scholar
Feige, U.. On sums of independent random variables with unbounded variance and estimating the average degree in a graph. SIAM J. Comput. 35 (2006), no. 4, 964–984.CrossRefGoogle Scholar
Filmus, Y., Kindler, G., Mossel, E. and Wimmer, K.. Invariance principle on the slice. 31st Conference on Computational Complexity, LIPIcs. Leibniz Int. Proc. Inform., vol. 50, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016, Art. No. 15, 10 pages.Google Scholar
Filmus, Y. and Mossel, E., Harmonicity and invariance on slices of the Boolean cube. 31st Conference on Computational Complexity, LIPIcs. Leibniz Int. Proc. Inform., vol. 50, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016, Art. No. 16, 13 pages.Google Scholar
Fox, J., Kwan, M. and Sauermann, L.. Anticoncentration for subgraph counts in random graphs. arXiv preprint arXiv:1905.12749 (2019).Google Scholar
Fox, J., Kwan, M. and Sudakov, B.. Acyclic subgraphs of tournaments with high chromatic number, arXiv preprint arXiv:1912.07722 (2019).Google Scholar
Fox, J. and Sauermann, L.. A completion of the proof of the edge-statistics conjecture, Advances in Combinatorics 2020:4.Google Scholar
Gilmer, J. and Kopparty, S.. A local central limit theorem for triangles in a random graph. Random Structures Algorithms 48 (2016), no. 4, 732–750.Google Scholar
Janson, S., Łuczak, T. and Ruciński, A.. Random graphs. (Cambridge University Press, 2000).Google Scholar
Kallenberg, O.. Foundations of modern probability. Prob. Appli. (Springer-Verlag, New York, 1997).Google Scholar
Kim, J. H. and Vu, V. H.. Concentration of multivariate polynomials and its applications. Combinatorica 20 (2000), no. 3, 417–434.CrossRefGoogle Scholar
Kwan, M., Sudakov, B. and Tran, T.. Anticoncentration for subgraph statistics. J. London Math. Soc. 99, no. 3 (2019), 757–777.CrossRefGoogle Scholar
Littlewood, J. E. and Offord, A. C.. On the number of real roots of a random algebraic equation. III. Rec. Math. [Mat. Sbornik] N.S. 12(54) (1943), 277–286.Google Scholar
Loebl, M., Matoušek, J. and Pangrác, O.. Triangles in random graphs. Discrete Math. 289 (2004), no. 1-3, 181–185.CrossRefGoogle Scholar
Martinsson, A., Mousset, F., Noever, A. and Trujić, M.. The edge-statistics conjecture for ℓ ≪ k 6/5 . Israel J. Math. 234 (2019), no. 2, 677–690.CrossRefGoogle Scholar
McDiarmid, C.. Concentration. Probabilistic methods for algorithmic discrete mathematics. Algorithms Combin. vol. 16, (Springer, Berlin, 1998), pp. 195–248.Google Scholar
Meka, R., Nguyen, O. and Vu, V.. Anti-concentration for polynomials of independent random variables. Theory Comput. 12 (2016), Paper No. 11, 16 pages.Google Scholar
Nguyen, H. H. and Vu, V. H.. Small ball probability, inverse theorems, and applications. Erdös centennial, Bolyai Soc. Math. Stud., vol. 25, János Bolyai Math. Soc. (Budapest, 2013), pp. 409–463.Google Scholar
Rosiński, J. and Samorodnitsky, G.. Symmetrization and concentration inequalities for multilinear forms with applications to zero-one laws for Lévy chaos. Ann. Probab. 24 (1996), no. 1, 422–437.CrossRefGoogle Scholar
Razborov, A. and Viola, E.. Real advantage, ACM Trans. Comput. Theory 5 (2013), no. 4, Art. 17, 8 pages.Google Scholar
Tao, T. and Vu, V.. From the Littlewood-Offord problem to the circular law: universality of the spectral distribution of random matrices. Bull. Amer. Math. Soc. (N.S.) 46 (2009), no. 3, 377–396.CrossRefGoogle Scholar
Tao, T. and Vu, V. H.. Inverse Littlewood-Offord theorems and the condition number of random discrete matrices. Ann. of Math. (2) 169 (2009), no. 2, 595–632.CrossRefGoogle Scholar
Vu, V.. Anti-concentration inequalities for polynomials. A journey through discrete mathematics (Springer, Cham, 2017), pp. 801–810.Google Scholar
Watson, G. N.. A Treatise on the Theory of Bessel Functions (Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1995). Reprint of the second (1944) edition.Google Scholar