Kruskal-Katona's function and a variation of cross-intersecting antichains

Abstract: We prove some properties of the Kruskal-Katona function, and apply to the following variation of cross-intersecting antichains. Let

n g e 4

be an even integer and

m a t h s c r A

and

m a t h s c r B

be two cross-intersecting antichains of

m a t h b b N_{n}

with at most

k

disjoint pairs, i.e. for all

A_{i} i n m a t h s c r A

,

B_{j} i n m a t h s c r B

,

A_{i} c a p B_{j} = e m p t y s e t

only if

i = j l e k

. We prove a best possible upper bound on

| m a t h s c r A | + | m a t h s c r B |

. Furthermore, we show that the extremal families contain only

f r a c n 2

and

(f r a c n 2 + 1)

-sets.

This page was built for publication: Kruskal-Katona's function and a variation of cross-intersecting antichains