Algebraic and Analytic Methods in Combinatorics: Non-averaging sets
Presenter
March 18, 2025
Keywords:
- extremal combinatorics
- extremal graph theory
- probabilistic combinatorics
- discrete geometry
- additive combinatorics
- combinatorial geometry
- incidence geometry
- arithmetic progressions
- Discrete analysis
MSC:
- 05C25 - Graphs and abstract algebra (groups rings fields
- etc.) [See also 20F65]
- 05C35 - Extremal problems in graph theory [See also 90C35]
- 05C50 - Graphs and linear algebra (matrices eigenvalues etc.)
- 05D40 - Probabilistic methods in extremal combinatorics including polynomial methods (combinatorial Nullstellensatz etc.)
- 52C35 - Arrangements of points flats hyperplanes (aspects of discrete geometry) [See also 14N20 32S22]
Abstract
A set of integers A is non-averaging if no element of A is an average of two or more other elements of A. We show that the largest non-averaging subset in [n] has size n^{1/4+o(1)}, resolving a problem of Erdos and Straus. Our proof combines convex geometric arguments with a structure theorem for subset sums. Joint work with Huy Pham.