The Ungar Games

MaRDI QIDQ6508809arXivFDO

Authors Colin Defant, Noah Kravitz, Nathan Williams

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)

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.

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)