Number of chains in posets of width 2 (YEAR)

Originators: Vaclav Linek    (presented by Douglas West - REGS 2011)

Definitions: The width of a poset P is the maximum size of an antichain in P (a set of pairwise incomparable elements). A chain is a set of elements of which no two are incomparable (a totally ordered set). By Dilworth's Theorem, a poset of width w has a partition into w chains.

Question 1: Is it true for every positive integer k that there is a poset of width 2 in which the number of chains is exactly k? Is it true for sufficiently large k?

Comments: The empty set of elements in a poset is counted as a chain. Thus for posets of width 1 (which are chains), the only values achievable are powers of 2. On the other hand, in an antichain of size k-1, all chains have size at most 1, and the number of chains is k. The problem becomes nontrivial when the width is restricted, and the case of width 2 is open. Students in REGS have constructed posets of width 2 with all numbers of chains up to 852, except for 499.

Under an appropriate transformation, the number of chains in a poset becomes the number of independent sets in a corresponding graph. Linek asked another question about that situation.

Question 2: Is it true that for every sufficiently large integer k, there is a tree in which the number of independent sets is exactly k?