From: Robin Chapman <rjc@maths.ex.ac.uk>
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 <delval@ai.ii.uam.es> 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 <yerman@hiwaay.net>
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