暑期研習生班專題演講

主講者: 陳宏賓博士(中研院數學所)
講題: On the Largest Size of Families of Sets with a Forbidden Poset
時間: 2013-08-08 (Thu.)  14:00 - 16:00
地點:
Abstract: The problem of determining the largest size of $P$-free families of subsets of $[n]$, denoted by La$(n,P)$, can be traced back to Sperner's Theorem in 1928. He proved that the largest size of $P_2$-free (antichain) families is the largest binomial coefficients of $n$. Let $\Sigma(n,k)$ be the sum of the $k$ middle binomial coefficients of $n$. Sperner's Theorem assures that La$(n,P_2)=\Sigma(n,1)$. Erd$\H{o}$s in 1945 further extended it to $\mbox{La}(n,P_k)=\Sigma(n,k-1)$ where $P_k$ denotes a chain of size $k$. Erd$\H{o}$s' result implies a general bound that for any finite poset $P$,$\label{erdos}\mbox{La}(n,P)\leq \Sigma(n,|P|-1)$,(1),as any poset $P$ is a subposet of a chain of length $|P|$. Little has been known for 65 years about upper bounds on $\la(n,P)$ for general $P$. Surprisingly, Burcsi and Nagy in 2012 gave a nice result improving $(\ref{erdos})$ that for any poset $P$,$\label{BN}\d \mbox{La}(n,P)\leq \left[\frac{1}{2}(|P|+h(P))-1\right]{n\choose \lfloor\frac{n}{2}\rfloor}$,(2), where $h(P)$ denotes the height of $P$, i.e., the largest size of chains in $P$. In this talk, I will improve (2) by showing $\label{CL}\d \mbox{La}(n,P)\leq \left[\frac{1}{m+1}\left(|P|+\frac{1}{2}(m^2+3m-2)(h(P)-1)-1\right)\right]{n\choose \lfloor\frac{n}{2}\rfloor}$,(3),for any integer $m\geq 1$. Note that when $m=1$, (3)=(2).
  || Close window ||