pith. sign in

arxiv: 2606.24877 · v1 · pith:MGG5JJ6Vnew · submitted 2026-06-23 · 🧮 math.CO

Tur\'{a}n results for posets and their alternating cycles

Geir Agnarsson , John B. Kent This is my paper

Pith reviewed 2026-06-25 22:33 UTC · model grok-4.3

classification 🧮 math.CO
keywords posetsorder dimensionalternating cycleshypergraphsweak chromatic numbercritical pairsTurán bounds
0
0 comments X

The pith

Weak chromatic numbers of hypergraphs from a poset's alternating cycles equal its order dimension.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines four hypergraphs on a poset P whose vertices are either the ordered tuples of incomparable elements or the critical pairs, with hyperedges given by the duals of all alternating cycles or all strict alternating cycles. It proves that the weak chromatic number of each such hypergraph equals the order dimension of P. The work further establishes upper bounds on the total number of strict alternating cycles that any poset on n elements of width w can contain, and shows these bounds carry over to the number of hyperedges in the hypergraph whose vertices are the incomparable pairs. A reader would care because order dimension measures the minimum number of linear extensions needed to realize the partial order, and the results supply both an exact hypergraph-coloring characterization and quantitative limits on the cycle structures that appear in posets.

Core claim

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

What carries the argument

Hypergraphs whose vertices are incomparable pairs or critical pairs and whose edges are the duals of alternating cycles or strict alternating cycles; their weak chromatic number equals order dimension.

If this is right

  • Order dimension equals the weak chromatic number in each of the four hypergraph constructions from alternating cycles.
  • The number of strict alternating cycles is bounded above by a function of the poset size n and width w.
  • The hypergraph H^s(P) has at most as many hyperedges as the maximum number of strict alternating cycles permitted by n and w.
  • Turán-type extremal results on cycle counts hold uniformly for all posets of given size and width.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The equality may permit computing order dimension by reducing it to known algorithms for weak hypergraph coloring on these specific instances.
  • The cycle bounds could be applied to count or enumerate alternating cycles in concrete families such as interval orders or dimension-two posets.
  • The hypergraph models might connect order dimension to other hypergraph parameters such as matching number or clique number in future work.

Load-bearing premise

The hypergraphs are constructed so that their weak chromatic numbers exactly equal the order dimension through the duals of the alternating cycles.

What would settle it

A single poset P for which the weak chromatic number of any one of the four constructed hypergraphs differs from the order dimension of P.

Figures

Figures reproduced from arXiv: 2606.24877 by Geir Agnarsson, John B. Kent.

Figure 1
Figure 1. Figure 1: A poset with critical pairs condition is satisfied and the second is vacuously true. The pair (x1, y1) is critical because the first condition is vacuously true and the second condition is satisfied. The critical pair (x2, y2) satisfies both conditions, and (x4, y4) is trivially a critical pair. Observe that (y4, x4) is also a critical pair, but (y1, x1) is not. In general this relation is not symmetric, i… view at source ↗
Figure 2
Figure 2. Figure 2: Alternating cycle S = [(x1, x2)(x2, x3)(x3, x4)(x4, x5)(x5, x6)(x6, x1)] as a digraph cycle In this way we obtain the following proposition: Proposition 3.2. Let P0 = (X, =) be the trivial poset on |X| = n elements. Then the number of strict alternating cycles on P0 is given by: |ACs (P0)| = Xn k=2  n k  (k − 1)! = n!g(n) where g(n) = nX−2 k=0 1 k! 1 n − k . From Proposition 3.2 it is clear the quantity … view at source ↗
Figure 3
Figure 3. Figure 3: A poset of four disjoint chains: P = C1 ∪ C2 ∪ C3 ∪ C4 Enumerating all the possible strict alternating cycles will require some care notationally. For a ground set X with |X| = n and a positive integer w ∈ N, let ˜n = (n1, . . . , nw) be an ordered w-tuple of positive integers that add up to n, so P i ni = n. For a partition X = X1 ∪ · · · ∪ Xw with |Xi | = ni for each i, denote the poset consisting of w d… view at source ↗
Figure 4
Figure 4. Figure 4: A Tur´an graph on 7 vertices, showing the maximum number of 16 edges among simple graphs on 7 vertices without containing K4 as a subgraph the following definition: 17 [PITH_FULL_IMAGE:figures/full_fig_p017_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Behavior of ( 1+α 2α2 ) α = β behavior in β n that is being masked by the dominance of the factorial term. 23 [PITH_FULL_IMAGE:figures/full_fig_p023_5.png] view at source ↗
read the original abstract

For a partially ordered set ${\mathbb{P}} = (X,\leq)$ 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,\leq)$ 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper associates four hypergraphs with a poset P=(X,≤): vertices are either the set of all incomparable tuples or all critical pairs, while hyperedges are the duals of all alternating cycles or all strict alternating cycles. It claims that the weak chromatic number of each of these hypergraphs equals the order dimension dim(P). It further establishes upper bounds on the number of strict alternating cycles in P in terms of n=|X| and the width w of P; these bounds also apply to the number of hyperedges in the associated hypergraph H^s(P) with incomparable pairs as vertices.

Significance. If the results hold, the work supplies a direct hypergraph-coloring characterization of order dimension that builds on the Dushnik-Miller realizer and critical-pair theory. The Turán-style bounds on strict alternating cycles constitute new extremal combinatorics for posets and immediately yield edge bounds for one of the hypergraphs. The construction is parameter-free and rests on standard facts about alternating cycles forbidding realizer extensions.

minor comments (3)
  1. [Abstract] Abstract, first paragraph: the four hypergraphs are introduced without explicit notation for the vertex sets (incomparable tuples vs. critical pairs) or edge sets (alternating vs. strict alternating); the manuscript should introduce consistent notation H(P), H^s(P), etc., at the first use.
  2. [Abstract] The bounds are stated to apply to |E(H^s(P))| but the precise functional form (e.g., O(n^2 w) or similar) is not displayed in the abstract; the introduction or theorem statements should state the explicit inequalities.
  3. The manuscript should include a short preliminary section recalling the definitions of critical pairs, alternating cycles, and weak chromatic number to make the hypergraph construction self-contained for readers outside dimension theory.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript and for recommending minor revision. The report contains no specific major comments requiring point-by-point response.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper constructs four hypergraphs whose vertices are incomparable tuples or critical pairs and whose edges are duals of alternating or strict alternating cycles; it states that the weak chromatic numbers of all four equal dim(P). This equality is presented as following directly from the standard Dushnik-Miller characterization of dimension via realizers and the known correspondence between alternating cycles and obstructions to realizer extensions, which are external facts from dimension theory rather than internal definitions or self-citations. The subsequent Turán-style upper bounds on the number of strict alternating cycles (and thus on |E(H^s(P))|) are derived combinatorially from n and the width w of P, with no fitted parameters, no self-citation load-bearing the central claim, and no renaming of known results as new derivations. The derivation chain is therefore self-contained against external benchmarks and exhibits no reduction of outputs to inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard definitions of posets, order dimension, critical pairs, alternating cycles, and weak hypergraph coloring. No free parameters, ad-hoc axioms, or invented entities are indicated in the abstract.

axioms (2)
  • standard math Standard properties of partial orders and the definition of order dimension via realizer size.
    Invoked implicitly when equating chromatic number to dimension.
  • domain assumption Existence and duality properties of alternating cycles in posets.
    Used to form the hyperedges of the constructed hypergraphs.

pith-pipeline@v0.9.1-grok · 5698 in / 1287 out tokens · 20924 ms · 2026-06-25T22:33:57.921431+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 3 canonical work pages

  1. [1]

    Trotter , Pages =

    William T. Trotter , Pages =. Combinatorics and Partially Ordered Sets: Dimension Theory , Year =

  2. [2]

    doi:10.1016/j.endm.2015.06.108 ,url =

    Tomasz Krawczyk and Bartosz Walczak ,title =. doi:10.1016/j.endm.2015.06.108 ,url =

    work page doi:10.1016/j.endm.2015.06.108 2015

  3. [3]

    SIAM Journal on Algebraic Discrete Methods , volume =

    Yannakakis, Mihalis , title =. SIAM Journal on Algebraic Discrete Methods , volume =. 1982 , doi =

    1982

  4. [4]

    Minors and dimension , volume =

    Walczak, Bartosz , address =. Minors and dimension , volume =. Journal of combinatorial theory. , lccn =

  5. [5]

    A decomposition theorem for partially ordered sets , Volume =

    Robert Palmer Dilworth , Journal =. A decomposition theorem for partially ordered sets , Volume =

  6. [6]

    Graham and Donald E

    Ronald L. Graham and Donald E. Knuth and Oren Patashnik , Pages =. Concrete Mathematics , Year =

  7. [7]

    Ben Dushnik and E. W. Miller , journal =. Partially Ordered Sets , urldate =

  8. [8]

    On the dimension of partially ordered sets , journal =

    David Kelly , abstract =. On the dimension of partially ordered sets , journal =. 1981 , note =. doi:https://doi.org/10.1016/0012-365X(81)90203-X , url =

    work page doi:10.1016/0012-365x(81)90203-x 1981

  9. [9]

    Trotter Jr

    William T. Trotter Jr. and John I. Moore Jr. , abstract =. The dimension of planar posets , journal =. 1977 , issn =. doi:https://doi.org/10.1016/0095-8956(77)90048-X , url =

    work page doi:10.1016/0095-8956(77)90048-x 1977

  10. [10]

    50 Years of Combinatorics, Graph Theory, and Computing , pages=

    Dimension for posets and chromatic number for graphs , author=. 50 Years of Combinatorics, Graph Theory, and Computing , pages=. 2019 , publisher=

    2019

  11. [11]

    Proofs from

    Aigner, Martin and Ziegler, G. Proofs from. 1998 , publisher=

    1998

  12. [12]

    2006 , publisher=

    Graph Theory: Modeling, Applications, and Algorithms , author=. 2006 , publisher=

    2006

  13. [13]

    Journal of Algorithms , volume=

    A poset dimension algorithm , author=. Journal of Algorithms , volume=. 1999 , publisher=

    1999

  14. [14]

    SIAM Journal on Discrete Mathematics , volume=

    Planar posets have dimension at most linear in their height , author=. SIAM Journal on Discrete Mathematics , volume=. 2017 , publisher=

    2017

  15. [15]

    Journal of Combinatorial Theory, Series B , volume=

    Minors and dimension , author=. Journal of Combinatorial Theory, Series B , volume=. 2017 , publisher=

    2017

  16. [16]

    Discrete Mathematics , volume=

    The rank of a distributive lattice , author=. Discrete Mathematics , volume=. 1979 , publisher=

    1979

  17. [17]

    Fundamenta Mathematicae , volume=

    Sur l'extension de l'ordre partiel , author=. Fundamenta Mathematicae , volume=. 1930 , publisher=

    1930

  18. [18]

    Journal of the ACM (JACM) , volume=

    Samplesort: A sampling approach to minimal storage tree sorting , author=. Journal of the ACM (JACM) , volume=. 1970 , publisher=

    1970

  19. [19]

    The American Mathematical Monthly , volume=

    Gamma and factorial in the monthly , author=. The American Mathematical Monthly , volume=. 2018 , publisher=

    2018

  20. [20]

    Discrete Mathematics , volume=

    Some theorems on graphs and posets , author=. Discrete Mathematics , volume=. 1976 , publisher=

    1976