The size of crossings in antichains

Research Horizons Seminar
Wednesday, September 8, 2010 - 12:00
1 hour (actually 50 minutes)
School of Mathematics - Georgia Institute of Technology

Hosted by: Yao Li and Ricardo Restrepo

Combinatorial mathematics exhibits a number of elegant, simply stated problems that turn out to be surprisingly challenging. In this talk, I report on a problem of this type on which I have been working with Noah Streib, Stephen Young and Ruidong Wang from Georgia Tech, as well as Piotr Micek, Bartek Walczak and Tomek Krawczyk, all computer scientists from Poland. Given positive integers  $k$ and $w$, what is the largest integer   $t = f(k,w)$  for which there exists a family $\mathcal{F}$ of $t$ vectors in $N^{w}$ so that: \begin{enumerate} \item  Any two vectors in the family $\mathcal{F}$ are incomparable in the product ordering; and \item  There do not exist two vectors $A$ and $B$ in the family for which there are distinct  $i$ and $j$  so that  $a_i\ge  k +b_i$  and $b_j \ge k + a_j$. \end{enumerate}  The Polish group posed the problem to us at the SIAM Discrete Mathematics held in Austin, Texas, this summer.  They were able to establish the following bounds: \[   k^{w-1} \le  t  \le  k^w \] We were able to show that the lower bound is essentially correct by showing that there is a constant  $c_w$   so that  $t  \l c_w k^{w-1}$. But recent work suggests that the lower bound might actually be tight.