Jim Boyce

Hi,

Any collection of 10 cards contains a Superset, and there is a
collection of 9 cards that does not have a Superset.

A superset is a collection of 4 cards that are left if you take two Sets
that share a common card and remove that common card. (I will give
another characterization later.) This gives a trivial upper bound, that
14 cards must contain a Superset. Each pair of cards (there are 91
pairs) defines a third card that completes its Set. there are only 81
cards, so there are pairs that share the same "completer". The pairs do
not overlap, beacuse then they would be identical. So two paris witht e
same "completer" form a Superset.

The second characterization of a Superset requires some more machinery.
Put some reasonable coordinate systems on the cards, so that you can
take the difference between two cards to get a direction (and
distance). Suppose you have two (disjoint) pairs of cards and their
differences are the same. Then these four cards form a parallelogram.
There are also a Superset. The diagonals of a parallelogram intersect
at another card.

There are 40 (unsigned) directions for lines. With 10 cards, there are
45 pairs of cards. Each pair of cards has a difference which is one of
those 40 directions. If there are 2 disjoint pairs with the same
difference, then we have a Superset. We see that there are pairs with
the same difference. If they overlap, then they are a Set, and that
direction is used 3 times. If the 10 cards consists of 3 Sets and
another card, then the 3 sets account for 3 directions 3 times each, and
there are still 36 pairs which might be distributed over the remaining
37 directions without overlap.

However, it turns out that while you can find 3 Sets that do not contain
a Superset, there is no room for the 10th card.

Here is a diagram of a 9-card collection with no Superset:

xxx ooo ooo
ooo ooo ooo
ooo ooo ooo

xoo ooo ooo
xoo ooo ooo
xoo ooo ooo

ooo xoo ooo
ooo oxo ooo
ooo oox ooo

-jim

----------------------------------------

Dear Ed,

I'm writing to you about SET. In the January 2000
installment of my Mindsharpener column for Optima, the
newsletter of the Mathematical Programming Society, I
described how integer programming can be used to find
a largest `Set'less collection of SET cards. The idea
of formulating the problem as an integer program (IP)
is due to Mohan Rajagopolan, who was at the time a
student at Oberlin College (he is now a Ph.D. student
at Cornell). Some crucial ideas that led to the
solution of Mohan's IP were contributed by me (Bob Bosch),
Oliver Schirokauer (also a member of Oberlin's Math Dept.)
and Carl Cotner (of Penn State). I believe that our
integer-programming based proof was the first published
proof that the maximum number is 20. (The SET site
presents a collection of 20, but does not present a
complete proof; it does provide a link to David Van Brink's
site, which contains what may be the beginnings of a valid
proof.) My Optima article is available online at
http://www.ise.ufl.edu/~optima/ (see Optima 63, pages 2-3).

Also, about a year ago, Mohan e-mailed me to tell me
that Joseph S. Miller, a graduate student at Cornell,
had found a nice combinatorial proof.

Best regards,

Bob