### The size of crossings in antichains

- Series
- Research Horizons Seminar
- Time
- Wednesday, September 8, 2010 - 12:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 171 (NOTICE THE CHANGE OF ROOM)
- Speaker
- Tom Trotter – School of Mathematics - Georgia Institute of Technology

**Please Note:** 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.