• ### Keeping Your Distance is Hard(1605.06801)

Feb. 8, 2019 math.CO, cs.CC
We study the computational complexity of distance games, a class of combinatorial games played on graphs. A move consists of colouring an uncoloured vertex subject to it not being at certain distances determined by two sets, D and S. D is the set of forbidden distances for colouring vertices in different colors, while S is the set of forbidden distances for the same colour. The last player to move wins. Well-known examples of distance games are Node-Kayles, Snort, and Col, whose complexities were shown to be PSPACE-hard. We show that many more distance games are also PSPACE-hard.
• ### A mis\ere play $\star$-operator(1608.06996)

Aug. 25, 2016 math.CO
We study the $\star$-operator (Larsson et al. 2011) of impartial vector subtraction games (Golomb 1965). Here we extend the notion to the mis\ere-play convention, and prove convergence and other properties; notably more structure is obtained under mis\`ere-play as compared with the normal-play convention (Larsson 2012).
• ### Building Nim(1502.04068)

Aug. 27, 2015 math.CO, cs.DM
The game of nim, with its simple rules, its elegant solution and its historical importance is the quintessence of a combinatorial game, which is why it led to so many generalizations and modifications. We present a modification with a new spin: building nim. With given finite numbers of tokens and stacks, this two-player game is played in two stages (thus belonging to the same family of games as e.g. nine-men's morris): first building, where players alternate to put one token on one of the, initially empty, stacks until all tokens have been used. Then, the players play nim. Of course, because the solution for the game of nim is known, the goal of the player who starts nim play is a placement of the tokens so that the Nim-sum of the stack heights at the end of building is different from 0. This game is trivial if the total number of tokens is odd as the Nim-sum could never be 0, or if both the number of tokens and the number of stacks are even, since a simple mimicking strategy results in a Nim-sum of 0 after each of the second player's moves. We present the solution for this game for some non-trivial cases and state a general conjecture.
• ### Circular Nim Games(1211.0091)

Nov. 1, 2012 math.CO
A circular Nim game is a two player impartial combinatorial game consisting of n stacks of tokens placed in a circle. A move consists of choosing k consecutive stacks, and taking at least one token from one or more of the k stacks. The last player able to make a move wins. We prove results on the structure of the losing positions for small n and k and pose some open questions for further investigations.
• ### Avoiding substrings in compositons(0903.5135)

June 23, 2009 math.CO
A classical result by Guibas and Odlyzko obtained in 1981 gives the generating function for the number of strings that avoid a given set of substrings with the property that no substring is contained in any of the others. In this paper, we give an analogue of this result for the enumeration of compositions that avoid a given set of prohibited substrings, subject to the compositions' length (number of parts) and weight. We also give examples of families of strings to be avoided that allow for an explicit formula for the generating function. Our results extend recent results by Myers on avoidance of strings in compositions subject to weight, but not length.
• ### Partially ordered patterns and compositions(math/0610030)

Oct. 1, 2006 math.CO
A partially ordered (generalized) pattern (POP) is a generalized pattern some of whose letters are incomparable, an extension of generalized permutation patterns introduced by Babson and Steingrimsson. POPs were introduced in the symmetric group by Kitaev [Partially ordered generalized patterns, Discrete Math. 298 (2005), 212-229; Introduction to partially ordered patterns, Discrete Appl. Math., to appear], and studied in the set of $k$-ary words by Kitaev and Mansour [Partially ordered generalized patterns and $k$-ary words, Annals of Combinatorics 7 (2003) 191-200]. Moreover, Kitaev et al. [S. Kitaev, T. McAllister and K. Petersen, Enumerating segmented patterns in compositions and encoding with restricted permutations, preprint] introduced segmented POPs in compositions. In this paper, we study avoidance of POPs in compositions and generalize results for avoidance of POPs in permutations and words. Specifically, we obtain results for the generating functions for the number of compositions that avoid shuffle patterns and multi-patterns. In addition, we give the generating function for the distribution of the maximum number of non-overlapping occurrences of a segmented POP $\tau$ (that is allowed to have repeated letters) among the compositions of $n$ with $m$ parts in a given set, provided we know the generating function for the number of compositions of $n$ with $m$ parts in the given set that avoid $\tau$. This result is a $q$-analogue of the main result in [S. Kitaev, T. Mansour, Partially ordered generalized patterns and $k$-ary words, Annals of Combinatorics 7 (2003) 191-200].
• ### Counting rises, levels, and drops in compositions(math/0310197)

Oct. 14, 2003 math.CO
A composition of $n\in\NN$ is an ordered collection of one or more positive integers whose sum is $n$. The number of summands is called the number of parts of the composition. A palindromic composition of $n$ is a composition of $n$ in which the summands are the same in the given or in reverse order. In this paper we study the generating function for the number of compositions (respectively palindromic compositions) of $n$ with $m$ parts in a given set $A\subseteq\NN$ with respect to the number of rises, levels, and drops. As a consequence, we derive all the previously known results for this kind of problem, as well as many new results.