IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Packing posets in a family of subsets

  • Oct. 28, 2013
  • 3:15 p.m.
  • LeConte 312

Abstract

Abstract: For a poset $P$, we are interested in maximizing the size of a family $F$ of subsets of $[n]$, where each connected component of $F$ is a copy of $P$. For instance, Sperner showed that when $P$ is one element, $\binom{n}{\lfloor n/2\rfloor}$ is the maximum number of copies of $P$ and that this is only achieve by taking subsets of a middle size. Griggs, Stahl, and Trotter have shown that when $P$ is a chain on $k$ elements, $\frac{1}{2^{k-1}}\binom{n}{\lfloor n/2\rfloor}$ is asymptotically the maximum number of copies of $P$ as $n$ goes to infinity. For the general poset $P$ and as $n$ goes to infinity, we prove that the maximum number of unrelated copies of $P$ is asymptotic to a constant times $\binom{n}{\lfloor n/2\rfloor}$. Moreover, the constant has the form $\frac{1}{c(P)}$, where $c(P)$ is the size of the smallest convex closure over all embeddings of $P$ into the Boolean lattice.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC