Turán results for posets and their alternating cycles

Abstract

For a partially ordered set $\mathbb{P}=(X,\le )$ there exist hypergraphs where the vertices are the set of ordered tuples of either all incomparable elements of $\mathbb{P}$ or all the critical pairs of $\mathbb{P}$, and the edges are formed by the duals of either all the alternating cycles of $\mathbb{P}$ or all the strict alternating cycles of $\mathbb{P}$. The weak chromatic numbers of these hypergraphs are all equal to the order dimension of $\mathbb{P}$. Here are established upper bounds on the number of strict alternating cycles a poset $\mathbb{P}=(X,\le )$ can have in terms of $n=|X|$, the cardinality of the groundset of $\mathbb{P}$, and the width $w$ of $\mathbb{P}$. These bounds also apply to the number of hyperedges of the associated hypergraph ${\mathcal{H}}^s(\mathbb{P})$, with incomparable pairs as vertices and strict alternating cycles dual to its hyperedges.

26 pages, 5 figures, one table