Combinatorics Seminar
Ben Fish
UIC
Excluding Diamonds in Linear Lattices
Abstract: Four distinct elements a,b,c, and d of a poset form a diamond if
a < b < d and a < c < d. A subset of a poset is diamond-free if no
four elements of the subset form a diamond. Finding the largest size of a diamond-free subset in a poset is difficult - even in the Boolean lattices, it remains an open problem. In this talk, we will instead consider the problem of finding the largest size of a diamond-free subset in the linear lattices. A linear lattice is the poset of subspaces of a finite dimensional vector space over a finite field of order q. We conjecture that the size of the largest diamond-free subset of a linear lattice is equal to the sum of the largest two rank numbers of the lattice. In this talk, I will demonstrate that the size of a diamond-free subset of a linear lattice can be no more than 2 + 1/(q+1) times the width of the lattice, which as q tends to infinity, approaches the fraction predicted by our conjecture. In addition, for linear lattices of dimension no more than 5, I will demonstrate that the size of the largest diamond-free subset is equal to the sum of the largest two rank numbers of the lattice, i.e. the above conjecture holds.
Wednesday April 9, 2014 at 3:00 PM in SEO 427