The Ungar Games

arXiv2302.06552MaRDI QIDQ6508809FDOQ6508809

Authors: Colin Defant, Noah Kravitz, Nathan Williams 

Abstract: Let $L$ be a finite lattice. An Ungar move sends an element $xinL$ to the meet of $xcupT$, where $T$ is a subset of the set of elements covered by $x$. We introduce the following Ungar game. Starting at the top element of $L$, two players -- Atniss and Eeta -- take turns making nontrivial Ungar moves; the first player who cannot do so loses the game. Atniss plays first. We say $L$ is an Atniss win (respectively, Eeta win) if Atniss (respectively, Eeta) has a winning strategy in the Ungar game on $L$. We first prove that the number of principal order ideals in the weak order on $S_n$ that are Eeta wins is $O(0.95586^{n}n!)$. We then consider a broad class of intervals in Young's lattice that includes all principal order ideals, and we characterize the Eeta wins in this class; we deduce precise enumerative results concerning order ideals in rectangles and type-$A$ root posets. We also characterize and enumerate principal order ideals in Tamari lattices that are Eeta wins. Finally, we conclude with some open problems and a short discussion of the computational complexity of Ungar games.

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) 2-person games (91A05) Asymptotic enumeration (05A16) Combinatorial aspects of partitions of integers (05A17) Combinatorics of partially ordered sets (06A07) Structure theory of lattices (06B05) Combinatorial games (91A46)

This page was built for publication: The Ungar Games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6508809)