Metraipolis › archive › dc_fe599448ce37
The Computational Complexity of the Ungar Games on Distributive Lattices — arXiv:2610.11017
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.11017
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-09T06:29:00.560Z
- SHA-256 of the archived text
d31e5cd615b60fb398d9176c11be1fb10d48787399127a7be559277e83e5a9f6- Stable URL of this page
https://metraipolis.com/documento/dc_fe599448ce37
How to cite
The Computational Complexity of the Ungar Games on Distributive Lattices — arXiv:2610.11017 — arXiv (en), https://arxiv.org/abs/2610.11017 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fe599448ce37 (Metraipolis archive dc_fe599448ce37, sha256 d31e5cd615b60fb398d9176c11be1fb10d48787399127a7be559277e83e5a9f6)
BibTeX
@misc{dcfe599448ce37,
title = {The Computational Complexity of the Ungar Games on Distributive Lattices — arXiv:2610.11017},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.11017},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fe599448ce37; sha256 d31e5cd615b60fb398d9176c11be1fb10d48787399127a7be559277e83e5a9f6},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.11017. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The Ungar game, introduced by Defant et al., is a combinatorial game played on a finite lattice, which originates from a geometric transformation introduced by Ungar to resolve Scott's slope problem. When played on a distributive lattice $L$, the Ungar game reduces to repeatedly choosing and removing a non-empty set of maximal elements from a finite poset $P$, where $L$ is represented as the lattice $J(P)$ of the order ideals of $P$ by Birkhoff's representation theorem. Defant et al. raised the open question of whether determining the outcome of the Ungar game on $J(P)$ is PSPACE-complete with respect to $|P|$. In this paper, we settle this open question in the affirmative. More precisely, we prove that the problem is PSPACE-complete even when restricted to posets $P$ with maximum chain length $l(P) \le 3$ such that the underlying graph of the Hasse diagram of $P$ is bipartite, where the length of a chain is defined as the number of elements in the chain minus one. Furthermore, we show that the problem is NP-complete for $l(P) \le 2$, whereas the case $l(P) \le 1$ is known to belong to LOGSPACE. Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno). Categorie arXiv: Combinatorics (math.CO). Pagina del lavoro: https://arxiv.org/abs/2610.11017 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-09T05:53:57.118Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).