The Computational Complexity of the Ungar Games on Distributive Lattices

@misc{hashimoto2026computational,
  title = {{The Computational Complexity of the Ungar Games on Distributive Lattices}},
  author = {Kengo Hashimoto},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.11017},
  eprint = {2610.11017},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.11017},
}

TY  - UNPB
TI  - The Computational Complexity of the Ungar Games on Distributive Lattices
AU  - Kengo Hashimoto
PY  - 2026
DA  - 2026/10/07
PB  - arXiv
DO  - 10.48550/arxiv.2610.11017
UR  - https://arxiv.org/abs/2610.11017
AB  - 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) ≤ 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) ≤ 2, whereas the case l(P) ≤ 1 is known to belong to LOGSPACE.
ER  -