A new approach to an old problem of Erdos and Moser

Details A new approach to an old problem of Erdos and Moser A new approach to an old problem of Erdos and Moser

2011-12-04

arxiv.org/abs/1112.0755v1

Mathematics

Combinatorics

Scientific paper

Let $\eta_i, i=1,..., n$ be iid Bernoulli random variables, taking values $\pm 1$ with probability 1/2. Given a multiset $V$ of $n$ elements $v_1, ..., v_n$ of an additive group $G$, we define the \emph{concentration probability} of $V$ as $$\rho(V) := \sup_{v\in G} P(\eta_1 v_1 + ... \eta_n v_n =v). $$ An old result of Erdos and Moser asserts that if $v_i $ are distinct real numbers then $\rho(V)$ is $O(n^{-3/2}\log n)$. 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.

Affiliated with

Also associated with

No associations

Rating

A new approach to an old problem of Erdos and Moser does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A new approach to an old problem of Erdos and Moser, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A new approach to an old problem of Erdos and Moser will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-388435