The Kelly--Trotter conjecture and dimension of poset products

Zhaochen Dong; Kaiyun Wang

En palabras de los autores

We study the order dimension of Cartesian products of finite posets. Kelly and Trotter conjectured in 1982 that $dim (P \times Q) \geq dim P + dim Q - 2$ for all finite posets $P$ and $Q$ . For $m \geq 3$ , 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}) \leq (1 + \frac{2}{l o g _{2} 6}) dim R_{m} + C$ . Since $1 + 2/ lo g_{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 \geq 8$ , 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}) \leq dim P + d - 3$ for every poset $P$ with $dim P \geq 3$ . Thus, for every integer $d \geq 8$ , 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}) \leq s$ for every finite chain $C$ with at least two elements.

Resultado principalEl resumen no menciona limitaciones.

The Kelly--Trotter conjecture and dimension of poset products

En palabras de los autores

Más de Combinatoria y matemática discreta ese día

Breaking the Infinite Barrier in the 31​--32​ Conjecture

Proof of the Kahn Saks Conjecture

Greedy queens and the golden ratio

2-colouring shift-chains

Discounted Hitting Domination on Graphs with Submodularity, Complexity and Exact Algorithms

Breaking the Infinite Barrier in the $\frac{1}{3}$ -- $\frac{2}{3}$ Conjecture