Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.00622 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918477367869440 |
|---|---|
| author | Gutzeit, Jette Shaban, Kimia Yeats, Karen Zalel, Stav |
| author_facet | Gutzeit, Jette Shaban, Kimia Yeats, Karen Zalel, Stav |
| contents | Given a set $Γ$ of $k$ unlabelled posets, each of size $n$, we say that a poset $Q$ is a \emph{witness} to $Γ$ if $Γ$ 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 $Γ$. 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)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_00622 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Sizes of witnesses in Covtree Gutzeit, Jette Shaban, Kimia Yeats, Karen Zalel, Stav Combinatorics General Relativity and Quantum Cosmology Mathematical Physics Given a set $Γ$ of $k$ unlabelled posets, each of size $n$, we say that a poset $Q$ is a \emph{witness} to $Γ$ if $Γ$ 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 $Γ$. 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)$. |
| title | Sizes of witnesses in Covtree |
| topic | Combinatorics General Relativity and Quantum Cosmology Mathematical Physics |
| url | https://arxiv.org/abs/2605.00622 |