printable pdf
比利时vs摩洛哥足彩 ,
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

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