# DIMACS Discrete Mathematics Seminar

## Title:

On the Conway-Guy Sequence

## Speaker:

- Tom Bohman
- Rutgers University

## Place:

- CoRE Building Room 431
- Busch Campus, Rutgers University

## Time:

- 4:30 PM
- Tuesday, March 28, 1995

## Abstract:

A set S of positive integers has distinct subset sums if for any
distinct subsets I and J of S the sum of the elements in I does not
equal the sum of the elements in J. For example, the sets {1,2,4,8}
and {3,5,6,7} have distinct subset sums. How small can the largest
element of such a set be? In other words, what is
f(n)=min{max S :|S|=n and S has distinct subset sums}?

Erdos conjectures that f(n) > c2^n for some constant c. In 1967
Conway and Guy constructed an interesting sequence of sets of
integers. They conjectured not only that these sets have distinct
subset sums but also that they are the best possible (with respect to
the largest element). I will show a technique for proving that sets of
integers have distinct subset sums. This technique can be used to
show that the sets from the Conway-Guy sequence (as well as some other
interesting sets) have distinct subset sums. The Conway-Guy sequence
now gives the best known upper bound on f(n).

Document last modified on March 27, 1995