Over the past 10 years, there has been considerable interest in exploring questions connecting dimension for posets with graph theoretic properties of their cover graphs and order diagrams, especially with the concepts of planarity and treewidth. Joret and Micek conjectured that if P is a poset with a planar cover graph, then the dimension of P is bounded in terms of the number of minimal elements of P and the treewidth of the cover graph of P. We settle this conjecture in the affirmative. To this end, we strengthen a recent breakthrough result  by Blake et al. (<CitationRef CitationID="CR15">2022</CitationRef>), who proved that for each poset P admitting a planar cover graph and a unique minimal element we have <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11083_2025_9695_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="154" /> </InlineMediaObject> <EquationSource Format="TEX">$\dim (P) \leqslant 2 \operatorname {se}(P) + 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>dim</mo> <mo stretchy="false">(</mo> <mi>P</mi> <mo stretchy="false">)</mo> <mo>⩽</mo> <mn>2</mn> <mo>se</mo> <mo stretchy="false">(</mo> <mi>P</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11083_2025_9695_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="54" /> </InlineMediaObject> <EquationSource Format="TEX">$\dim (P)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>dim</mo> <mo stretchy="false">(</mo> <mi>P</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> stands for the dimension of P and <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11083_2025_9695_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">$\operatorname {se}(P)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>se</mo> <mo stretchy="false">(</mo> <mi>P</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> stands for the maximum order of a standard example contained in P. We prove that <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11083_2025_9695_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="179" /> </InlineMediaObject> <EquationSource Format="TEX">$\dim (P) \leqslant 2 \operatorname {wheel}(P) + 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>dim</mo> <mo stretchy="false">(</mo> <mi>P</mi> <mo stretchy="false">)</mo> <mo>⩽</mo> <mn>2</mn> <mo>wheel</mo> <mo stretchy="false">(</mo> <mi>P</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11083_2025_9695_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="66" /> </InlineMediaObject> <EquationSource Format="TEX">$\operatorname {wheel}(P)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>wheel</mo> <mo stretchy="false">(</mo> <mi>P</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> stands for the maximum order of a wheel contained in P.

Forcing the Wheel

期刊论文
发表日期：

2025年1月18日

查看全文

Jędrzej Hodor,
William T. Trotter

摘要

Over the past 10 years, there has been considerable interest in exploring questions connecting dimension for posets with graph theoretic properties of their cover graphs and order diagrams, especially with the concepts of planarity and treewidth. Joret and Micek conjectured that if P is a poset with a planar cover graph, then the dimension of P is bounded in terms of the number of minimal elements of P and the treewidth of the cover graph of P. We settle this conjecture in the affirmative. To this end, we strengthen a recent breakthrough result by Blake et al. (2022), who proved that for each poset P admitting a planar cover graph and a unique minimal element we have $\dim (P) \leqslant 2 \operatorname {se}(P) + 2$ $dim (P) ⩽ 2 se (P) + 2$ , where $\dim (P)$ $dim (P)$ stands for the dimension of P and $\operatorname {se}(P)$ $se (P)$ stands for the maximum order of a standard example contained in P. We prove that $\dim (P) \leqslant 2 \operatorname {wheel}(P) + 2$ $dim (P) ⩽ 2 wheel (P) + 2$ , where $\operatorname {wheel}(P)$ $wheel (P)$ stands for the maximum order of a wheel contained in P.