DIMACS Discrete Mathematics/Theory of Computing Seminar

Title:

Representation of Integers as a subset sum

Speaker:

Gyula Karloyi

Institute for Advanced Study

Place:

Seminar Room 431, CoRE Building,

Busch Campus, Rutgers University.

Time:

4:30 PM

Tuesday, April 16, 1996

Abstract:

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