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

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]