Antichains and the LYM inequality

**hairymclairy** · May 7th 2012, 01:46 PM

Hello,

Can anyone help me understand how to derive the local LYM inequality from the LYM inequality?

Thanks in advance.

**Plato** · May 7th 2012, 02:21 PM

Originally Posted by hairymclairy

Can anyone help me understand how to derive the local LYM inequality from the LYM inequality?

I think that you need to supply several definitions.

**hairymclairy** · May 8th 2012, 01:01 AM

They're fairly standard theorems, I thought they'd be well-known as they trivially imply Sperner's theorem/lemma about the maximal size of an antichain.

The LYM inequality states that given an antichain $\mathscr{A}$ on [n], let $a_k=\left|\mathscr{A}\cap{[n]\choose k}\right|$ i.e the number of sets of size $k$ in $A.$ Then
$\sum_{k=0}^n\frac{a_k}{{n\choose k}}\leqslant 1$ .

Now the local LYM inequality states that if $A\subseteq{[n] \choose r}$ then $\frac{|\partial A|}{{n \choose r-1}}\geqslant\frac{|A|}{{n\choose r}}$ , where $\partial A$ is the lower shadow of the antichain $A$ , in symbols $\partial A=\{B\in{[n]\choose r-1}:B\subseteq A'\in A\}$ .

In the above notation, $[n]=\{1,2,3,...,n\}$ . Each implies the other, but I'm struggling to show properly that the first inequality implies the second.

**hairymclairy** · May 8th 2012, 05:57 AM

I've solved this now.

Thanks anyway.

Thread: Antichains and the LYM inequality

LinkBack

Thread Tools

Display

Antichains and the LYM inequality

Re: Antichains and the LYM inequality

Re: Antichains and the LYM inequality

Re: Antichains and the LYM inequality

Similar Math Help Forum Discussions

Maximal Antichains

Inequality with x in the denominator (rational inequality)

Proving the triangle inequality using the Cauchy-Schwartzs inequality

inequality

Inequality

Search Tags