**Inventory018: Small subsets of {1,2,3,4,5,6,7,8}
**(proposed
by Hans-Dieter Gronau, 4/9/02).

Let X_1,X_2,...,X_m be subsets of N={1,2,...,8} satisfying:

(a) no X_i is a subset of any X_j (Sperner condition) for any i <>
j,

(b) the union of any 3 X_i's is a proper subset of N.

What is the maximum of m ?

Comments: This problem with arbitrary N was considered
by P. Frankl and myself about 20 years ago and was almost completely settled:

max m = {n-1 \choose (n-2)/2} + 1 if n=4,6,7,48 or >=
54 and even or

max m = {n-1 \choose (n-1)/2} if n is odd and <> 7,13,19,25,31,43.

See J. of Combinatorial Theory Ser. A 30 (1981), 298-318.

Actually, in all the undecided cases I can prove:

1) a maximal family contains sets with size <= [(n-1)/2]
only and

2) if there is at least one 1-element set then we get
the size of the family given above if n is even and it's not maximal if
n is odd (n<>7).

The first open case is for N={1,2,...,8}. So, the question
is:

What is the maximal number of 2- and 3-element subsets
of N={1,2,...,8} satisfying (a) and (b) ?

Is it 35 (by choosing all 3-element subsets of N={1,2,...,7})
?

**Discussion.**

**Bibliography.**

**Return to [Polya
Home Page] [Members]
[Problem Center]
[Inventory]
[Reserve Area]**