Originators: H. Snevily (presented by D.B. West - REGS 2009)
Definitions: We study subsets of an n-element set; let [n]={1,...,n}. A family is a set of subsets of [n]. An ideal is a family F that is closed under taking subsets; that is, if A∈F and B⊆A, then B∈F. A star is a family that has a common element. An intersecting family is a family whose members pairwise intersect. A family has the star property if some maximum-sized intersecting family in it is a star. (Note that every star is an intersecting family, but not every intersecting family is a star.)
Conjecture 1: (Chvátal [C]) Every ideal has the star property.
Background: The family of all subsets of [n] satisfies the conjecture, since its maximal stars have size 2n-1 and no intersecting family contains a set and its complement. Conjecture 1 has been proved for ideals satisfying various conditions on the set of maximal members. For example, several earlier results are subsumed by the result of Snevily [S]: If I is an ideal, and x is an element of [n] such that A-a+x∈I whenever A∈I and a∈A, then the star of members containing x is a largest intersecting family in I. Snevily suggests several questions to cast additional light on the star property. For a set B⊆[n] and a family F, the translate of F by B, written F(B), is {A⊕B: A∈F}, where ⊕ denotes symmetric difference. Note that F(∅)=F. Also, the translate of an ideal need not be an ideal; if I={∅,1,2,3,23}, then I(3)={3,13,23,∅,2} (for clarity, we list the members of a family without brackets and internal commas). B. Reiniger (REGS) observed that the translate of any ideal by any singleton set has the star property.
Question 2: (Snevily) Which are the families F such that neither F(∅) nor F([n]) has the star property?
Comments: The first question asks for a weaker version of Chvátal's Conjecture, since I=I(∅). In general, F(∅) and F([n]) are F itself and the family of complements of members of F. If at least one of these always has the star property, then the Erdős-Ko-Rado Theorem [EKR] follows.
Given F, one can ask what properties H(F) must have, where H(F)={B⊆[n]: F(B) has the star property}. Question 2 asks whether H(I) is nonempty when I is an ideal. Unfortunately, it need not hold that H(I) is an ideal whenever I is an ideal, even when I is required to contain all singletons. For example, with n=4, let I consist of all subsets of [3] plus all sets of size at most 2 containing the element 4. Now I(123) does not have the star property but I(1234) does.
Question 3: (Snevily) A family is star-perfect if every translate has the star property. Which families (or which ideals) are star-perfect? If a family F is star-perfect, must it also be true that the family of subsets of [n] not in F is star-perfect?
Comments: Let F be complement-partitionable if it can be partitioned into pairs of complementary sets. Since each complementary pair contributes at most once to an intersecting family, and for any element of [n] one member of the pair contains it, every complement-partitionable family has the star property. Also, every translate of a complement-partitionable family is complement-partitionable, since translating by an element just moves the element from one member of a complementary pair to the other. Hence "complement-partitionable" is a sufficient condition for F to be star-perfect. The complement of a complement-partitionable family is also complement-partitionable.
Trivially, families of size 1 are star-perfect, since translation does not change the size of a family (this is one motivation for using the term "translate"). Similarly, families of size 2 are star-perfect. Another example of a star-perfect family is the ideal of all sets omitting the element 1. Translation by a set not containing 1 does not change the family, and translation by a set containing 1 turns it into a star. Is I star-perfect when I is the ideal consisting of all sets of size at most k, where k<n/2?
Question 4: (Snevily) Which families (or which ideals) have the fewest translates satisfying the star property? Do at least half the translates always have the star property? Letting ^ denote the set complementation operator, is it always true that I(B) or I(B^) has the star property when I is an ideal?
Comments: Paul Wenger showed that the translate of an ideal I by a set B is an ideal if and only if B is contained in every maximal element of I.
Finally, we remark that Snevily showed that if I is an ideal, then every translate of I by a nonempty set B contains a star at least as large as the largest intersecting family in I. The reason is the theorem of Berge [B], which showed that every ideal I can be partitioned into pairs of disjoint sets (with ∅ left over when |I| is odd). This is a weaker condition than complement-partitionable. We conclude that the maximum intersecting family in I has size at most |I|/2, and every element lies in at most half of the members of I, but then in every translation I(B), the elements of B occur in at least half of the members.
References:
[B] Berge, C.; A theorem related to the Chvátal conjecture. Proceedings
of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975),
pp. 35-40. Congressus Numerantium, No. XV, Utilitas Math., Winnipeg, Man., 1976.
[C] Chvátal, V.; Intersecting families of edges in hypergraphs having the
hereditary property. Hypergraph Seminar (Proc. First Working Sem., Ohio State
Univ., Columbus, Ohio, 1972; dedicated to Arnold Ross), pp. 61--66. Lecture
Notes in Math., Vol. 411, Springer, Berlin, 1974.
[EKR] Erdős, P.; Ko, Chao; Rado, R.
Intersection theorems for systems of finite sets.
Quart. J. Math. Oxford Ser. (2) 12 1961 313-320.
[S] Snevily, Hunter; A new result on Chvátal's conjecture.
J. Combin. Theory Ser. A 61 (1992), no. 1, 137--141.