The Ungar games. (English) Zbl 07857943
From the structures of a finite lattice they developed a 2-players combinatorial game defining an Ungar move. They proved results for characterizing issues on the principal order ideals, characterized the winner strategies, among other theoretical results. The computational complexity of these games are also given.
Reviewer: Carlos Narciso Bouza Herrera (Habana)
MSC:
| 91A05 | 2-person games |
| 91A46 | Combinatorial games |
| 05A05 | Permutations, words, matrices |
| 05A15 | Exact enumeration problems, generating functions |
| 05A16 | Asymptotic enumeration |
| 05A17 | Combinatorial aspects of partitions of integers |
| 06B05 | Structure theory of lattices |
| 06A07 | Combinatorics of partially ordered sets |
Online Encyclopedia of Integer Sequences:
a(n) is the number of permutations of [1..n] that avoid the consecutive pattern 1324 (equally, the permutations that avoid 4231).References:
| [1] | Gale, D., A curious Nim-type game, Amer. Math. Monthly, 81, 876-879, 1974 · Zbl 0295.90045 · doi:10.1080/00029890.1974.11993683 |
| [2] | Zeilberger, D., Three-rowed CHOMP, Adv. Appl. Math., 26, 168-179, 2001 · Zbl 0977.91008 · doi:10.1006/aama.2000.0714 |
| [3] | Scott, PR, On the sets of directions determined by \(n\) points, Amer. Math. Monthly, 77, 502-505, 1970 · Zbl 0192.57603 · doi:10.1080/00029890.1970.11992527 |
| [4] | Ungar, P., \(2N\) noncollinear points determine at least \(2N\) directions, J. Combin. Theory Ser. A, 33, 343-347, 1982 · Zbl 0496.05001 · doi:10.1016/0097-3165(82)90045-0 |
| [5] | Goodman, JE; Pollack, R., A combinatorial perspective on some problems in geometry, Congr. Numer., 32, 383-394, 1981 · Zbl 0495.05012 |
| [6] | Defant, C.; Li, R., Ungarian Markov chains, Electron. J. Probab., 28, 1-39, 2023 · Zbl 07790304 · doi:10.1214/23-EJP1056 |
| [7] | Aigner, M.; Ziegler, GM, Proofs from the book, 2014, Germany: Springer-Verlag, Germany · Zbl 1294.01001 · doi:10.1007/978-3-662-44205-0 |
| [8] | Asinowski, A., Banderier, C., Hackl, B.: Flip-sort and combinatorial aspects of pop-stack sorting. Discrete Math. Theor. Comput. Sci., 22 (2021) · Zbl 1532.68013 |
| [9] | Asinowski, A.; Banderier, C.; Billey, S.; Hackl, B.; Linusson, S., Pop-stack sorting and its image: permutations with overlapping runs, Acta. Math. Univ. Comenian., 88, 395-402, 2019 |
| [10] | Claesson, A.; Guðmundsson, BÁ, Enumerating permutations sortable by \(k\) passes through a pop-stack, Adv. Appl. Math., 108, 79-96, 2019 · Zbl 1415.05012 · doi:10.1016/j.aam.2019.04.002 |
| [11] | Claesson, A.; Guðmundsson, BÁ; Pantone, J., Counting pop-stacked permutations in polynomial time, Exp. Math., 32, 1, 97-104, 2021 · Zbl 1519.05013 · doi:10.1080/10586458.2021.1926001 |
| [12] | Lichev, L.: Lower bound on the running time of pop-stack sorting on a random permutation. arXiv:2212.09316 [v1] |
| [13] | Pudwell, L.; Smith, R., Two-stack-sorting with pop stacks, Australas. J. Combin., 74, 179-195, 2019 · Zbl 1419.05010 |
| [14] | Choi, Y.; Sun, N., The image of the Pop operator on various lattices, Adv. Appl. Math., 154, 2024 · Zbl 07789128 · doi:10.1016/j.aam.2023.102649 |
| [15] | Defant, C.: Pop-stack-sorting for Coxeter groups. Comb. Theory, 2 (2022) · Zbl 1498.05286 |
| [16] | Defant, C.: Meeting covered elements in \(\nu \)-Tamari lattices. Adv. Appl. Math., 134 (2022) · Zbl 07461716 |
| [17] | Defant, C., Williams, N.: Semidistrim lattices. Forum Math. Sigma, 11 (2023) · Zbl 07699404 |
| [18] | Hong, L., The pop-stack-sorting operator on Tamari lattices, Adv. Appl. Math., 139, 2022 · Zbl 07540628 · doi:10.1016/j.aam.2022.102362 |
| [19] | Sapounakis, A., Tasoulas, I., Tsikouras, P.: On the dominance partial ordering on Dyck paths. J. Integer Seq., 9 (2006) · Zbl 1104.05003 |
| [20] | Tamari, D., The algebra of bracketings and their enumeration, Nieuw Archief voor Wiskunde, 10, 131-146, 1962 · Zbl 0109.24502 |
| [21] | Müller-Hoissen, F., Pallo, J. M., Stasheff, J.: Associahedra, Tamari lattices and related structures: Tamari memorial festschrift, vol. 299 of Progress in Mathematics. Birkhäuser (2012) · Zbl 1253.00013 |
| [22] | Stanley, RP, Enumerative combinatorics, 2012, Cambridge: Cambridge University Press, Cambridge · Zbl 1247.05003 |
| [23] | OEIS Foundation Inc. Entry A113228 in The On-Line Encyclopedia of Integer Sequences, http://oeis.org/A113228 (2023) |
| [24] | Flajolet, P.; Sedgewick, R., Analytic combinatorics, 2009, Cambridge: Cambridge University Press, Cambridge · Zbl 1165.05001 · doi:10.1017/CBO9780511801655 |
| [25] | Reading, N., Cambrian lattices, Adv. Math., 205, 313-353, 2006 · Zbl 1106.20033 · doi:10.1016/j.aim.2005.07.010 |
| [26] | Fomin, SV, Generalized Robinson-Schensted-Knuth correspondence, J. Soviet Math., 41, 979-991, 1988 · Zbl 0698.05003 · doi:10.1007/BF01247093 |
| [27] | Stanley, RP, Differential posets, J. Amer. Math. Soc., 1, 919-961, 1988 · Zbl 0658.05006 · doi:10.1090/S0894-0347-1988-0941434-9 |
| [28] | Barrington, D.; Immerman, N.; Straubing, H., On uniformity within \({ N}{ C}^1\), J. Comput. System Sci., 41, 274-306, 1990 · Zbl 0719.68023 · doi:10.1016/0022-0000(90)90022-D |
| [29] | Kalinich, AO, Flipping the winner of a poset game, Inform. Process. Lett., 112, 86-89, 2012 · Zbl 1233.68146 · doi:10.1016/j.ipl.2011.09.016 |
| [30] | Schaefer, TJ, On the complexity of some two-person perfect-information games, J. Comput. System Sci., 16, 185-225, 1978 · Zbl 0383.90112 · doi:10.1016/0022-0000(78)90045-4 |
| [31] | Grier, D.: Deciding the winner of an arbitrary finite poset game is PSPACE-complete. Automata, Languages, and Programming: 40th International Colloquium, ICALP Proceedings 497-503 (2013) · Zbl 1336.68097 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
