Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 30 min ago
PreprintarXiv licencearXiv

The Kelly--Trotter conjecture and dimension of poset products

  • Zhaochen Dong
  • Kaiyun Wang
Open at sourcePDFDOICite

Abstract

We study the order dimension of Cartesian products of finite posets. Kelly and Trotter conjectured in 1982 that dim(P× Q)≥dim P+dim Q−2 for all finite posets P and Q. For m≥3, let Rm 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(Rm× Rm)≤(1+2/(log2 6))dim Rm+C. Since 1+2/log2 6<2, this disproves the Kelly--Trotter conjecture and shows that 2dim Rm−2−dim(Rm× Rm) can grow linearly with dim Rm. For every integer d≥8, we construct an incidence poset Qd such that dim Qd=d and Qd has the (3,d)-covering property. Consequently, dim(P× Qd)≤dim P+d−3 for every poset P with dim P≥3. Thus, for every integer d≥8, the poset Qd 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× Cr)≤ s for every finite chain C with at least two elements.

Related

  1. Alternating Hamilton Paths and Cycles in Poset Products
    Yuxian Dong, Jianxi Mao
    arXivPreprintCC0Full textCombinatorics & discrete mathematicsarXiv
  2. Poset dimension and maximum comparability degree
    Carla Groenland, Richard Montgomery, Rajko Nenadov +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Pólya’s conjecture for thin products
    Xiang He, Zuoqin Wang
    International Mathematics Research NoticesPeer-reviewedLicence not statedFull text12 citedMathematical physicsOpenAlex
  4. Dimension of the Green measure of skew products with dominant exponent in the fibers
    Clara Genes
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsDynamical systemsarXiv
  5. Bounded VC-dimension implies the Erdős--Rado sunflower conjecture
    Gennian Ge, Jian Wang, Zixiang Xu +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{dong2026kellytrotter,
  title = {{The Kelly--Trotter conjecture and dimension of poset products}},
  author = {Zhaochen Dong and Kaiyun Wang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.31441},
  eprint = {2609.31441},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.31441},
}
RIS
TY  - UNPB
TI  - The Kelly--Trotter conjecture and dimension of poset products
AU  - Zhaochen Dong
AU  - Kaiyun Wang
PY  - 2026
DA  - 2026/09/25
PB  - arXiv
DO  - 10.48550/arxiv.2609.31441
UR  - https://arxiv.org/abs/2609.31441
AB  - We study the order dimension of Cartesian products of finite posets. Kelly and Trotter conjectured in 1982 that dim(P× Q)≥dim P+dim Q−2 for all finite posets P and Q. For m≥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× R_m)≤(1+2/(log_2 6))dim R_m+C. Since 1+2/log_2 6<2, this disproves the Kelly--Trotter conjecture and shows that 2dim R_m−2−dim(R_m× R_m) can grow linearly with dim R_m. For every integer d≥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× Q_d)≤dim P+d−3 for every poset P with dim P≥3. Thus, for every integer d≥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× C^r)≤ s for every finite chain C with at least two elements.
ER  -