Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics

Lincoln Lu

University of South Carolina

On crown-free families of subsets

Abstract:

Given a poset $P$, we are interested in determining the maximum size (denoted by $La(n,P)$) of any family of subsets of an $n$-set avoiding all extensions of $P$ as subposets. The starting point of this kind of problem is Sperner's Theorem from 1928, which can be restated as $La(n, P_2)= {n\choose \lfloor \frac{n}{2} \rfloor}$. Here $P_2$ is the chain of $2$ elements. These problems were studied by Erd\H{o}s, Katona, and others. In 2008, Griggs and Lu conjectured the limit $\pi(P):=\lim_{n\to\infty} \frac{La(n,P)} {{n\choose \lfloor \frac{n}{2} \rfloor}}$ exists and is an integer. For poset $P$ define $e(P)$ to be the maximum $k$ such that for all $n$, the union of the $k$ middle levels of subsets in the $n$-set contains no extension of $P$ as a subposet. Saks and Winkler observed $\pi(P)=e(P)$ in all known examples where $\pi(P)$ is determined. Bukh proved this conjecture holds for any tree poset $P$ (meaning its Hasse diagram is a tree). For $t\geq 2$, let crown $\O_{2t}$ be a poset of height $2$, whose Hasse diagram is cycle $C_{2t}$. De Bonis-Katona-Swanepoel proved $La(n,O_{4})= {n\choose \lfloor \frac{n}{2} \rfloor} + {n\choose \lceil \frac{n}{2} \rceil}$. Griggs and Lu proved the conjecture holds for crown $\O_{2t}$ with even $t\geq 3$. In this talk, we will prove that the conjecture holds for crown $\O_{2t}$ with odd $t\geq 7$.

Host: Fan Chung Graham

January 8, 2013

1:00 PM

AP&M 7321

****************************