The Kelly--Trotter conjecture and dimension of poset products

Source abstract

We study the order dimension of Cartesian products of finite posets. Kelly and Trotter conjectured in 1982 that $\dim(P\times Q)\ge\dim P+\dim Q-2$ for all finite posets $P$ and $Q$. For $m\ge3$, let $R_m$ denote the incidence poset of the complete graph on $m$ vertices. We prove that there is a constant $C$ such that, for all sufficiently large $m$, $\dim(R_m\times R_m)\le\left(1+\frac{2}{\log_2 6}\right)\dim R_m+C$. Since $1+2/\log_2 6<2$, this disproves the Kelly--Trotter conjecture and shows that $2\dim R_m-2-\dim(R_m\times R_m)$ can grow linearly with $\dim R_m$. For every integer $d\ge8$, we construct an incidence poset $Q_d$ such that $\dim Q_d=d$ and $Q_d$ has the $(3,d)$-covering property. Consequently, $\dim(P\times Q_d)\le\dim P+d-3$ for every poset $P$ with $\dim P\ge3$. Thus, for every integer $d\ge8$, the poset $Q_d$ violates the Kelly--Trotter conjecture with every poset of dimension at least $3$. Finally, we prove that a poset $Q$ has an $(r,s)$-covering if and only if $\dim(Q\times C^r)\le s$ for every finite chain $C$ with at least two elements.