NetNews Usenet Archive 1992 #23/NN_1992_23.iso/spool/sci/math/13316

Internet Message Format | 1992-10-16 | 3.7 KB

Path: sparky!uunet!mcsun!uknet!pavo.csi.cam.ac.uk!gjm11
From: [e-mail] (G.J. McCaughan)
Newsgroups: sci.math
Subject: Re: Combinatorics Problem (probably easy)
Message-ID: <[e-mail]>
Date: 16 Oct 92 16:23:18 GMT
References: <[e-mail]>
Sender: [e-mail] (USENET news)
Organization: U of Cambridge, England
Lines: 62
Nntp-Posting-Host: bootes.cus.cam.ac.uk

In article <[e-mail]> [e-mail] (Chongguang Xu) writes:

> I have a conjecture about a combinatorics question which I have been
> unable to prove.  I'm hoping someone on the net knows the answer or
> can give me a reference.
>
> Given a set S of k elements, let A be the largest family of subsets of S
> such that for every two elements a and b of A, b is not a substet of a.
> My conjecture is that the cardinality of A is C(k, [k/2]), where C(p,q)
> is the binomial coefficient, and [c] is the floor of c.  I can prove that
> the cardinality of A is at least that big, but I can't prove it can't
> be bigger.

Your conjecture is true, and is in fact a well known theorem!
There are at least two substantially different ways to prove it; here is
a nice short one.

Consider maximal nested chains of subsets of S; in other words, we start with
the empty set and throw in one element at a time until we have all of S.
Obviously there are exactly k! such chains.
We ask now: How many chains does a particular set lie in? Well, a set X (with
r elements, say) lies in a given chain if the first r elements added in making
the chain are the elements of X, in some order; and then, of course, the k-r
elements remaining are added after this.
So X lies in r!(k-r)! maximal chains.
Now let A be a family of subsets of S such that none is contained in any other.
Then if X,Y are in A there is no maximal chain going through both of them, for
that would imply one a subset of the other. So if we write M(X) for the set of
all maximal chains including X, all the M(X) with X in A are disjoint.
But M(X) has r!(k-r)! elements, so the sum over all X of r!(k-r)! is at most
k!, so the sum over all X of r!(k-r)!/k! is at most 1. But this is the sum
of the reciprocals of (k choose r), and (k choose r) is maximal when r is
k/2 (give or take 1/2, when k is odd). We are done!

Here is (a sketch of) another proof, which gives a bit more insight into why
the result is true.

First, some definitions:
An "r-set" is a set with r elements, contained in S.
Given a collection X of r-sets, its "s-shadow" is the collection of s-sets
which either contain (if r<s) or are contained in (if r>s)  sets of X.
In particular, the "upper shadow" of X is its (r+1)-shadow and its "lower
shadow" is its (r-1)-shadow.

Now, we can prove that (size of X)/(k choose r) is at most
(size of s-shadow of X)/(k choose s). We do this by successively taking
upper or lower shadows (depending on whether r<s or r>s); then at each
stage most of the factors in the binomial coefficients cancel and we are
left with a straightforward inequality which we prove by considering how
many r-sets have a given shadow, and how many sets are in the shadow of
a given r-set. (There is some abuse of notation here. Never mind.)

Now just take lots of upper and lower shadows successively, noting that
because of the no-subsets condition we never get unexpected overlaps, sort of.
Do it in such a way as to move everything in to s=k/2 (or floor(k/2) if k is
odd). We're done.

Filling in the details here really isn't very tricky, by the way.

--
Gareth McCaughan     Dept. of Pure Mathematics & Mathematical Statistics,
[e-mail]  Cambridge University, England.    [Research student]