DIMACS Discrete Mathematics/Theory of Computing Seminar


Representation of Integers as a subset sum


Gyula Karloyi
Institute for Advanced Study


Seminar Room 431, CoRE Building,
Busch Campus, Rutgers University.


4:30 PM
Tuesday, April 16, 1996


Let $f(n,m)$ denote the maximum cardinality of a subset $A$ of the set of the first $n$ positive integers such that there is no $B\subset A$ the sum of whose elements is $m$. For every positive integer $s$, we determine the precise value of $f(n,m)$ in the range $c_1(s)n Earlier results by Alon, Lipkin, and Alon--Freiman utilized the analytic circle method. Our proof is completely elementary, apart from the application of a generalization of the Erd\H os--Heilbronn conjecture that was proved recently by Dias da Silva--Hamidoune, and also by Alon--Nathanson--Ruzsa, using algebraic tools.

Our first result, combined with other combinatorial ideas, allows us to confirm the following conjecture of Lev. Let $1\le a_1<\ldots

Document last modified on April 12, 1996