pith. sign in

arxiv: 2605.00622 · v1 · submitted 2026-05-01 · 🧮 math.CO · gr-qc· math-ph· math.MP

Sizes of witnesses in Covtree

Jette Gutzeit , Kimia Shaban , Karen Yeats , Stav Zalel This is my paper

Pith reviewed 2026-05-09 18:54 UTC · model grok-4.3

classification 🧮 math.CO gr-qcmath-phmath.MP
keywords posetsdownsetswitnessesminimal witnessesexchange graphsize boundscombinatorics
0
0 comments X

The pith

Minimal witnesses for k unlabelled posets of size n have size at most nk minus n, and no bound of the form n plus k plus constant holds.

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

The paper examines the sizes of minimal witnesses Q for a collection of k unlabelled posets each having n elements. A poset Q witnesses the collection when its downsets of size exactly n match the given k posets exactly, and it is minimal when no proper downset of Q already witnesses the same collection. The authors introduce the exchange graph of downsets to prove that every minimal witness satisfies an upper bound of nk minus n. They also show that the size cannot be bounded above by any expression of the form n plus k plus a fixed constant c, and they give a tighter construction achieving size at most three-halves times n plus three-halves when k equals 3.

Core claim

Given any set Γ of k unlabelled posets each of size n, a poset Q is a witness to Γ when the downsets of Q that contain precisely n elements are exactly the members of Γ. Q is minimal when it contains no proper downset that is itself a witness to Γ. The paper proves that every minimal witness Q has |Q| at most nk minus n. It further shows there is no constant c such that |Q| is at most n plus k plus c for every collection, and that when k equals 3 there exists at least one minimal witness satisfying |Q| at most (3/2)(n plus 1). The proofs rely on the newly defined exchange graph of downsets.

What carries the argument

The exchange graph of downsets, a graph with vertices corresponding to the size-n downsets and edges representing exchanges that preserve the collection Γ; the graph is used to track the additional elements required when moving between downsets while maintaining minimality.

Load-bearing premise

The definitions of witness and minimal witness using exactly the n-element downsets are taken as given, and the exchange graph is assumed to encode all relations among those downsets that are needed to derive the size bounds.

What would settle it

An explicit collection of k posets of size n whose every minimal witness has strictly more than nk minus n elements would disprove the claimed upper bound.

Figures

Figures reproduced from arXiv: 2605.00622 by Jette Gutzeit, Karen Yeats, Kimia Shaban, Stav Zalel.

Figure 1
Figure 1. Figure 1: The tree of labelled possibilities of sequential growth and the result once the nodes are identified up to isomorphism. Covtree. One of us, with other coauthors, introduced covtree [21] in order to have a growth model that is covariant at every step while retaining a tree structure. The nodes at level n of covtree are sets of the form Γn = {P1, . . . , Pk}, where each of the Pi is an unlabelled poset of si… view at source ↗
Figure 2
Figure 2. Figure 2: The first three levels of covtree. Taken from [21]. Given a node, it is very easy to construct its path down to the root of covtree by the above algorithm. The converse is far from true: in general, it is very difficult to generate the nodes above a given node. It is not easy to recognize when a set of posets is a node of covtree and there is no known growth rule to generate the children of a node. Doing s… view at source ↗
Figure 3
Figure 3. Figure 3: A poset of type W with 24 elements. The elements by which the components differ from each other are shown in blue. Proposition 3.6. Let P denote a poset of type W of size 2n − 2 with at most n − 1 minimal elements. Then dn(P) = 1 + ⌊ n 2 ⌋. Proof. Let us denote the two disjoint Newtonian parts of the poset by w1 and w2. Downsets of size n are obtained by taking a downset of size n − 1 − l from w1 and a dow… view at source ↗
Figure 4
Figure 4. Figure 4: A poset with few downsets of size 3ℓ relative to its size. Lemma 3.17. d3ℓ(Hℓ) = ℓ + 2. Proof. Note that if a downset contains the maximal element of some Λi then it contains the entire Λi . In particular, if a downset of size 3ℓ of Hℓ contains the maximal element of the Λ3(ℓ−1) then since |Λ3(ℓ−1))| = 3ℓ − 2, this downset must be Λ3(ℓ−1) along with 2 incomparable elements. The remaining downsets of size 3… view at source ↗
Figure 5
Figure 5. Figure 5: Exchange graph for the poset on the left with the la￾belling as given. This example will be useful for illustrating how short paths sometimes need special consideration, cf. Remark 4.7. a b c d e f g h a b c e h a b e h d a b c d e a b c d a b c d f g c d f g b c d f g a view at source ↗
Figure 6
Figure 6. Figure 6: Exchange graph G5 for the poset on the left with the labelling as given. The bolded path in the exchange graph gives a minimal A−B −· · ·−B −C path as discussed later in this section, cf. setup to Lemma 4.6 view at source ↗
Figure 5
Figure 5. Figure 5: The path from the poset on a, c, e to the poset on a, c, d to the poset on a, c, b is a minimal path of the form discussed immediately before Lemma 4.6, however, the union of the anchor copies is not the union of the path because it does not include d. The problem here is that the anchor copies are adjacent. The only way this can happen without contradicting minimality is if there is a triangle in the exch… view at source ↗
read the original abstract

Given a set $\Gamma$ of $k$ unlabelled posets, each of size $n$, we say that a poset $Q$ is a \emph{witness} to $\Gamma$ if $\Gamma$ is the set of downsets of size $n$ of $Q$. We say that $Q$ is a \emph{minimal witness} if it does not contain a proper downset that is itself a witness to $\Gamma$. Motivated by the causal set approach to quantum gravity, we study the upper bound on the size of minimal witnesses as a function of $n$ and $k$. We show that there is no linear upper bound of the form $n+k+c$ for any constant $c$. We introduce the \emph{exchange graph of downsets} as a new tool to study this scenario, and use it to show that all minimal witnesses $Q$ satisfy the bound $|Q|\leq nk-n$, and that when $k=3$ there is at least one minimal witness $Q$ that satisfies the bound $|Q|\leq \frac{3}{2}(n+1)$.

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 / 2 minor

Summary. The manuscript defines a witness Q to a set Γ of k unlabelled posets each of size n as a poset whose downsets of size n are exactly the members of Γ. A minimal witness is one containing no proper downset that is itself a witness. The authors prove there is no linear upper bound of the form n+k+c on the size of minimal witnesses for any constant c. They introduce the exchange graph of downsets and use it to prove that every minimal witness Q satisfies |Q| ≤ nk − n. For the special case k=3 they exhibit at least one minimal witness satisfying the sharper bound |Q| ≤ (3/2)(n+1).

Significance. If the stated bounds hold, the work supplies concrete combinatorial limits on the size of minimal posets realizing prescribed collections of n-element downsets, directly relevant to the causal-set program in quantum gravity. The exchange graph is a new, parameter-free tool that tracks downset exchanges preserving Γ and yields the general upper bound without circularity or fitted constants. Credit is given for the explicit constructions demonstrating the absence of any linear bound and for the direct combinatorial arguments establishing both the general nk−n bound and the k=3 sharpening.

minor comments (2)
  1. The definitions of witness and minimal witness are introduced clearly in the abstract and presumably early in the text, but an explicit small-scale example (e.g., n=2, k=2) illustrating both a witness and a minimal witness would improve readability for readers new to the setting.
  2. The k=3 bound |Q| ≤ (3/2)(n+1) is stated without an immediate comparison to the general nk−n bound; adding one sentence in the relevant theorem statement or discussion would clarify how the sharpening is obtained.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and accurate summary of the manuscript, as well as for recommending minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation relies on standard definitions of witnesses and minimal witnesses for unlabelled posets, followed by explicit constructions disproving linear bounds and the introduction of the exchange graph of downsets to prove the nk-n upper bound (with k=3 sharpening). These steps are direct combinatorial arguments internal to the paper; no self-definitional loops, fitted inputs renamed as predictions, or load-bearing self-citations appear. The exchange graph is defined and applied within the manuscript without reduction to prior author work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on classical order theory with no free parameters or invented physical entities; the exchange graph is a new analytical construction rather than a postulated object.

axioms (1)
  • standard math Standard definition and properties of partially ordered sets and their downsets hold.
    The entire framework is built on established poset theory.

pith-pipeline@v0.9.0 · 5506 in / 1352 out tokens · 50473 ms · 2026-05-09T18:54:34.209693+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

27 extracted references · 27 canonical work pages

  1. [1]

    Space-Time as a Causal Set

    Luca Bombelli, Joohan Lee, David Meyer, and Rafael Sorkin. Space-Time as a Causal Set. Phys. Rev. Lett., 59:521–524, 1987

    work page 1987

  2. [2]

    The causal set approach to quantum gravity

    Sumati Surya. The causal set approach to quantum gravity. Living Rev. Rel., 22(1):5, 2019

    work page 2019

  3. [3]

    Springer Nature Singapore, Singapore, 2024

    Fay Dowker and Sumati Surya.The Causal Set Approach to the Problem of Quantum Gravity, pages 2989–3002. Springer Nature Singapore, Singapore, 2024

    work page 2024

  4. [4]

    Bombelli and D

    L. Bombelli and D. A. Meyer. The Origin of Lorentzian Geometry. Phys. Lett. A , 141:226– 228, 1989

    work page 1989

  5. [5]

    D. P. Rideout and R. D. Sorkin. A Classical sequential growth dynamics for causal sets. Phys. Rev., D61:024002, 2000

    work page 2000

  6. [6]

    Moment problems and the causal set approach to quantum gravity

    Avner Ash and Patrick McDonald. Moment problems and the causal set approach to quantum gravity. J. Math. Phys. , 44:1666–1678, 2003

    work page 2003

  7. [7]

    Ash and P

    A. Ash and P. McDonald. Random partial orders, posts, and the causal set approach to discrete quantum gravity. J. Math. Phys. , 46:062502, 2005. SIZES OF WITNESSES IN COVTREE 23

    work page 2005

  8. [8]

    Observables in extended percolation models of causal set cosmology

    Fay Dowker and Sumati Surya. Observables in extended percolation models of causal set cosmology. Class. Quant. Grav. , 23:1381–1390, 2006

    work page 2006

  9. [9]

    The mathematics of causal sets , pages 339–365

    Graham Brightwell and Malwina Luczak. The mathematics of causal sets , pages 339–365. Springer International Publishing, Cham, 2016

    work page 2016

  10. [10]

    Order-invariant measures on causal sets

    Graham Brightwell and Malwina Luczak. Order-invariant measures on causal sets. The An- nals of Applied Probability , 21(4):1493–1536, 2011

    work page 2011

  11. [11]

    Order-invariant measures on fixed causal sets.Com- binatorics, Probability and Computing , 21:330–357, 2012

    Graham Brightwell and Malwina Luczak. Order-invariant measures on fixed causal sets.Com- binatorics, Probability and Computing , 21:330–357, 2012

    work page 2012

  12. [12]

    Fay Dowker, Raquel S

    Graham Brightwell, H. Fay Dowker, Raquel S. Garcia, Joe Henson, and Rafael D. Sorkin. ‘Observables’ in causal set cosmology. Phys. Rev., D67:084031, 2003

    work page 2003

  13. [13]

    If time had no beginning: growth dynamics for past-infinite causal sets

    Bruno Valeixo Bento, Fay Dowker, and Stav Zalel. If time had no beginning: growth dynamics for past-infinite causal sets. Class. Quant. Grav. , 39(4):045002, 2022

    work page 2022

  14. [14]

    On extending the Quantum Measure

    Fay Dowker, Steven Johnston, and Sumati Surya. On extending the Quantum Measure. J. Phys., A43:505305, 2010

    work page 2010

  15. [15]

    A Criterion for Covariance in Complex Sequential Growth Models

    Sumati Surya and Stav Zalel. A Criterion for Covariance in Complex Sequential Growth Models. Class. Quant. Grav. , 37(19):195030, 2020

    work page 2020

  16. [16]

    Observables in cyclic growth dynamics

    Fay Dowker and Stav Zalel. Observables in cyclic growth dynamics. 2022

    work page 2022

  17. [17]

    Being and Becoming on the Road to Quantum Gravity; or, the Birth of a Baby Is Not a Baby

    Fay Dowker. Being and Becoming on the Road to Quantum Gravity; or, the Birth of a Baby Is Not a Baby . 4 2020

    work page 2020

  18. [18]

    The birth of spacetime atoms as the passage of time

    Fay Dowker. The birth of spacetime atoms as the passage of time. In Do We Need a Physics of ‘Passage’? Cape Town, South Africa, December 10-14, 2012 , 2014

    work page 2012

  19. [19]

    Hopf algebras from poset growth models

    Karen Yeats and Stav Zalel. Hopf algebras from poset growth models. The Electronic Journal of Combinatorics, 31(3):P3.9, Jul. 2024

    work page 2024

  20. [20]

    Fay Dowker, Raquel S

    Graham Brightwell, H. Fay Dowker, Raquel S. Garcia, Joe Henson, and Rafael D. Sorkin. General covariance and the ’Problem of time’ in a discrete cosmology. In Alternative Natural Philosophy Association Meeting Cambridge, England, August 16-21, 2001 , 2002

    work page 2001

  21. [21]

    A mani- festly covariant framework for causal set dynamics

    Fay Dowker, Nazireen Imambaccus, Amelia Owens, Rafael Sorkin, and Stav Zalel. A mani- festly covariant framework for causal set dynamics. Class. Quant. Grav., 37(8):085003, 2020

    work page 2020

  22. [22]

    The structure of covtree: searching for manifestly covariant causal set dynamics

    Stav Zalel. The structure of covtree: searching for manifestly covariant causal set dynamics. Class. Quant. Grav. , 38(1):015001, 2021

    work page 2021

  23. [23]

    Covariant Growth Dynamics , pages 3231–3266

    Stav Zalel. Covariant Growth Dynamics , pages 3231–3266. Springer Nature Singapore, Sin- gapore, 2024

    work page 2024

  24. [24]

    What Becomes of a Causal Set? Brit

    Christian Wuthrich and Craig Callender. What Becomes of a Causal Set? Brit. J. Phil. Sci. , 68(3):907–925, 2017

    work page 2017

  25. [25]

    Albert and A.M

    M.H. Albert and A.M. Frieze. Random graph orders. Order, 6(1), 1989

    work page 1989

  26. [26]

    Glaser, Denjoe O’Connor, and Sumati Surya

    L. Glaser, Denjoe O’Connor, and Sumati Surya. Finite Size Scaling in 2d Causal Set Quantum Gravity. Class. Quant. Grav. , 35(4):045006, 2018

    work page 2018

  27. [27]

    Combinatorial aspects of Feynman integrals and causal set theory

    Kimia Shaban. Combinatorial aspects of Feynman integrals and causal set theory. Master’s thesis, University of Waterloo, 2025. aDepartment of Mathematics, University of Zurich, Zurich, Switzerland Email address: jette.gutzeit@icloud.com bDepartment of Computer Science, University of Toronto, Toronto, ON, Canada Email address: kimia.shaban@mail.utoronto.ca...

    work page 2025