The Littlewood-Offord problem in high dimensions and a conjecture of Frankl and Füredi

DOI10.1007/S00493-012-2716-XMaRDI QIDQ2392038zbMATH OpenOpenAlexWikidataFDO

Authors Terence Tao, Van Vu

Publication date 6 August 2013

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

concentration inequalityorthonormal basisBernoulli random variablessmall ball probabilityFubini's theoremLittlewood-Offord problem

Mathematics Subject Classification ID

Combinatorial probability (60C05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: We give a new bound on the probability that the random sum $x{i}_1{v}_1+\mathrm{...}+x{i}_n{v}_n$ belongs to a ball of fixed radius, where the $x{i}_i$ are iid Bernoulli random variables and the $v_i$ are vectors in $R^d$. As an application, we prove a conjecture of Frankl and F"uredi (raised in 1988), which can be seen as the high dimensional version of the classical Littlewood-Offord-ErdH os theorem.

Recommendations

• Small ball probability, inverse theorems, and applications
• The Littlewood-Offord problem for Markov chains
• A non-uniform Littlewood-Offord inequality
• A nonuniform Littlewood-Offord inequality for all norms
• On the Littlewood‐Offord problem for arbitrary distributions
• Optimal inverse Littlewood-Offord theorems
• On the Littlewood-Offord problem
• Matching random samples in many dimensions
• A sharp inverse Littlewood-Offord theorem

Cites work

• scientific article; zbMATH DE number 3230288 (Why is no real title available?)
• scientific article; zbMATH DE number 3099315 (Why is no real title available?)
• A Sperner-type theorem
• Estimates for the concentration function of combinatorial number theory and probability
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• On a lemma of Littlewood and Offord
• On a lemma of Littlewood and Offord on the distribution of certain sums
• On a lemma of Littlewood and Offord on the distributions of linear combinations of vectors
• On the tightest packing of sums of vectors
• Solution of the Littlewood-Offord problem in high dimensions
• Some new results on the Littlewood-Offord problem
• Stronger form of an M-part Sperner theorem

Cited in

(14)

• Complex random matrices have no real eigenvalues
• Anti-concentration for subgraph counts in random graphs
• An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs
• Non-abelian Littlewood-Offord inequalities
• On the number of Hadamard matrices via anti-concentration
• The singularity probability of a random symmetric matrix is exponentially small
• Solution of the Littlewood-Offord problem in high dimensions
• Small ball probability, inverse theorems, and applications
• Small ball estimates for quasi-norms
• The Littlewood-Offord problem for Markov chains
• A nonuniform Littlewood-Offord inequality for all norms
• Inverse Littlewood-Offord problems for quasi-norms
• A non-uniform Littlewood-Offord inequality
• Fooling Polytopes

This page was built for publication: The Littlewood-Offord problem in high dimensions and a conjecture of Frankl and Füredi

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