From: Robin Chapman Subject: Re: Counting "unsubsumed" subsets Date: Mon, 13 Dec 1999 21:02:51 GMT Newsgroups: comp.theory,sci.math.symbolic To: delval@ai.ii.uam.es Keywords: Sperner's theorem on maximum number of incomparable subsets In article <385543A7.3CC767D7@ai.ii.uam.es>, Alvaro del Val wrote: > The following problem arises in a complexity analysis of > certain forms of logical resolution. I want to filter out > "subsumed clauses" from the analysis. The underlying technical > problem looks like one of those "someone must have solved it > before". Here it is: > > Let R be any family of subsets of a set S. > If there are no sets T and U in R such that (T subset U) > then R is an *acceptable* set of subsets of S. > > Question: What is the size of the largest acceptable R, as a function of > the number n > of elements of S? > > Conjecture: ( n ) > (n/2) > meaning combinations of n/2 elements of the n-sized universe. > (Intuitively, if R is acceptable then it is picking a "single slice" > of the poset lattice of subsets of S, with set containment as partial > order. That is, T in R implies nothing below or above T in this lattice > is > also in R. The conjecture means roughly that picking the middle of the > lattice we obtain a "maximal slice") This is Sperner's theorem. To be precise the maximum number of incomparable subsets of {1,2,...,n} is (n choose n/2) when n is even, and (n choose (n-1)/2) when n is odd. The only maximal collections are those of the (n/2)-element subsets when n is even, and of the (n-1)/2-element subsets and the (n+1)/-element subsets when n is odd. Here's a simple proof due to Lubell, Yamamoto and Meshalkin (all sp.?). Let A be a collection of incomparable subsets of {1,2,...,n} having a_j j-element sets. Consider the n! orderings c_1, ..., c_n of 1, 2, ..., n. At most one set in A can occur as {c_1, c_2, ..., c_j} in this ordering. Each j-element set occurs in this way in j!(n-j)! orderings. Hence the sum of a_j j!(n-j)! is at most n! or the sum of a_j/(n choose j) is at most 1 (this is th LYM inequality). Since the largest of the (n choose j) is (n choose n/2) or (n choose (n-1)/2) according to the parity of n, the sum of the a_j is at most this quantity. For more details see Bollobas: Combinatorics, CUP or Anderson: Combinatorics of Finite Sets, OUP. -- Robin Chapman http://www.maths.ex.ac.uk/~rjc/rjc.html "`Well, I'd already done a PhD in X-Files Theory at UCLA, ...'" Greg Egan, _Teranesia_ Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: Grange Gorman Subject: Re: Counting "unsubsumed" subsets Date: Fri, 17 Dec 1999 01:03:27 -0600 Newsgroups: comp.theory,sci.math.symbolic Alvaro del Val wrote: [original article quoted again --djr] Your conjecture is correct. It is called Sperner's Lemma. A very short proof due to Lubell can be found by counting permutations that contain the sets as a prefix... Let A be your collection of sets. Then SUM |S|! (n-|S|)! <= n! S in A giving SUM 1/C(n,|S|) <= 1 S in A Now C(n,|S|) is at most C(n,n/2) Therefore |A| <= C(n,n/2) QED In the words of Paul Erdos, this proof is in the book. NG