A new approach to an old problem of Erdős and Moser

DOI10.1016/J.JCTA.2012.01.003MaRDI QIDQ412182zbMATH OpenOpenAlexFDO

Authors Hoi Nguyen

Publication date 4 May 2012

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.0755

zbMATH Keywords

concentration probabilitysharp concentrationErdős-Moser problem

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Sums of independent random variables; random walks (60G50) Probability measures on groups or semigroups, Fourier transforms, factorization (60B15) Arithmetic combinatorics; higher degree uniformity (11B30)

Abstract: Let $et{a}_i,i=1,\mathrm{...},n$ be iid Bernoulli random variables, taking values $pm1$ with probability 1/2. Given a multiset $V$ of $n$ elements $v_1,\mathrm{...},v_n$ of an additive group $G$, we define the emph{concentration probability} of $V$ as ${\displaystyle }$ ho(V) := sup_{vin G} P(eta_1 v_1 + ... eta_n v_n =v). ${\displaystyle }$ An old result of Erdos and Moser asserts that if $v_i$ are distinct real numbers then $ho(V)$ is $O(n^{-3/2}logn)$. This bound was then refined by Sarkozy and Szemeredi to $O(n^{-3/2})$, which is sharp up to a constant factor. The ultimate result dues to Stanley who used tools from algebraic geometry to give a complete description for sets having optimal concentration probability; the result now becomes classic in algebraic combinatorics. In this paper, we will prove that the optimal sets from Stanley's work are stable. More importantly, our result gives an almost complete description for sets having large concentration probability.

Recommendations

• A sharp inverse Littlewood-Offord theorem
• Optimal inverse Littlewood-Offord theorems
• Erdős-Littlewood-Offord problem with arbitrary probabilities
• On the Littlewood‐Offord problem for arbitrary distributions
• scientific article; zbMATH DE number 813707

Cites work

• scientific article; zbMATH DE number 3099315 (Why is no real title available?)
• Additive combinatorics
• Freiman's theorem for solvable groups
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• Long arithmetic progressions in sumsets: Thresholds and bounds
• On a lemma of Littlewood and Offord
• On a lemma of Littlewood and Offord on the distributions of linear combinations of vectors
• On the singularity probability of random Bernoulli matrices
• Optimal inverse Littlewood-Offord theorems
• SETS WITH SMALL SUMSET AND RECTIFICATION
• Solution of Two Difficult Combinatorial Problems with Linear Algebra
• Weyl Groups, the Hard Lefschetz Theorem, and the Sperner Property
• Über ein Problem von Erdös und Moser

Cited in

(3)

• scientific article; zbMATH DE number 7662446 (Why is no real title available?)
• scientific article; zbMATH DE number 4179418 (Why is no real title available?)
• Majorization and Rényi entropy inequalities via Sperner theory

This page was built for publication: A new approach to an old problem of Erdős and Moser

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q412182)