Sergey Kitaev

Counting (2+2)-free posets by indistinguishable elements and a
conjecture of Jovovic

Abstract: An unlabeled poset is said to be (2+2)-free if it does not
contain an induced subposet that is isomorphic to 2+2, the union of
two disjoint 2-element chains. We derive the generating function for
the number of (2+2)-free posets with respect to the number of
indistinguishable elements (elements with the same up- and down-sets)
and another statistic. Moreover, we show that (2+2)-free posets with
at most k indistinguishable elements are in bijection with upper
triangular matrices of non-negative integers not exceeding k such that
each row and column contains a nonzero entry. In particular,
(2+2)-free posets on n elements with no indistinguishable elements
correspond to upper triangular binary matrices where each row and
column contains a nonzero entry, and whose sum of entries is n. We not
only derive a formula counting such matrices which confirms a
conjecture of Jovovic, but also generalize the formula to count upper
triangular matrices of non-negative integers not exceeding k (thus
enumerating the corresponding (2+2)-free posets too).

 

This is joint work with Mark Dukes, Jeff Remmel, and Einar Steingrimsson.