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

DOI10.1007/S00493-012-2716-XzbMATH Open1289.05453arXiv1002.5028OpenAlexW1988956155WikidataQ123122306 ScholiaQ123122306MaRDI QIDQ2392038FDOQ2392038

Authors: Terence Tao, Van Vu 

Publication date: 6 August 2013

Published in: Combinatorica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Estimates for the concentration function of combinatorial number theory and probability
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• Title not available (Why is that?)
• Solution of the Littlewood-Offord problem in high dimensions
• Some new results on the Littlewood-Offord problem
• 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 a lemma of Littlewood and Offord
• Title not available (Why is that?)
• On the tightest packing of sums of vectors
• Stronger form of an M-part Sperner theorem
• A Sperner-type 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
• On the number of Hadamard matrices via anti-concentration
• Non-abelian Littlewood-Offord inequalities
• 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
• Fooling Polytopes
• A non-uniform Littlewood-Offord inequality
• Inverse Littlewood-Offord problems for quasi-norms

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)