Réunion d'été SMC 2023

Ottawa, 2 - 5 juin 2023


Théorie des jeux combinatoires
Org: Melissa Huggan (Vancouver Island University), Rebecca Milley (Memorial University), Mehdi Salimi (St. Francis Xavier University) et Alexandra Wesolek (Simon Fraser University)

RYLO ASHMORE, Memorial University of Newfoundland
Herding cats stuck in trees  [PDF]

In the game of Cat Herding on a graph, one player (the herder) will omnipresently delete edges, while the other player (the cat) is on a vertex of the graph, and will move along any path to a new vertex. Eventually, the cat is isolated on a single vertex, and the cat's objective is to delay this event, while the herder tries to hasten it. In an optimally played game, the number of cuts the herder made to isolate the cat is the \emph{cat number} of the graph.

In this talk, we will investigate this graph parameter for both dense and sparse graphs. We will see an argument that the asymptotic behaviour of the cat number of complete graphs is $\frac{n^2}{3}$. We also look at an unexpected connection between cat herding on trees and Fibonacci numbers. In particular, we will see that trees with maximum cat number amongst graphs with $n$ vertices have cat number asymptotically $\log_\phi n$.

ANTHONY BONATO, Toronto Metropolitan University
The Localization Game  [PDF]

The Localization game models an invisible evader on a graph detectable by distance probes. The game and its corresponding optimization parameter, the localization number, have come into a renewed focus in recent years. We give a sample of recent results on the localization number for various graph families, ranging from locally finite graphs, directed graphs, and graphs arising from designs and Latin squares.

ALEX CLOW, Simon Fraser University
An Alternate Construction of Numbers as Games  [PDF]

The standard way to construct numbers in a combinatorial game ruleset is as strings in \textsc{Blue-Red Hackenbush}, which is equivalent to an ordinal sum with positive and negative integer summands. We provide another method of constructing all numbers as an ordinal sum in a natural rule set. Unlike in Hackenbush, our method constructs every $x \geq 0$ with only non-negative integer summands. In doing so we explore some novel results regarding ordinal sums of numbers which have broader implications to games with number valued positions.

\vspace{0.5cm} Joint work with Neil McKay (University of New Brunswick St.John).

Atomic structure and the multiverse  [PDF]

Losing games has proved far more difficult than winning. However, the complexities of misère play are not quite as impenetrable as was once feared decades ago. Recent work has directed attention towards the study of what is called a universe; a set of games exhibiting various closure properties. Dead-ending universes are particularly amenable to analysis, and we present related results on the structure of the monoid of Left dead-ends. We also discuss constructions of the universal closures of some well-known rulesets, including Domineering and Hackenbush.

DANNY DYER, Memorial University of Newfoundland
The cheating robot on graph products  [PDF]

In this talk, we will explore recent results on the cheating robot version of the game of cops and robbers. In this version, the robber may ``cheat'' and move away once a cop has begun their move to capture them. We will investigate some results involving bounds on the cheating robot number of planar graphs and the the cheating robot number of graph products. Joint work with Nancy Clarke and William Kellough.

MELISSA HUGGAN, Vancouver Island University
The damage number of the product of graphs  [PDF]

In adversarial situations on networks, we often concern ourselves with minimizing resources required for neutralizing a threat. Here we consider a different parameter which addresses the situation where an adversary is damaging each unique location they visit. Framed within the context of the game of Cops and Robbers on graphs, the robber tries to maximize the number of unique vertices they visit to maximize the damage to the graph, while the cops aim to minimize the damage by limiting the robber territory. This model was first introduced in 2019 by Cox and Sanaei. We build on their results. We provide a general upper bound for the damage number of the Cartesian product of graphs and consider the damage number of the product of two trees or cycles. We also consider graphs with small damage number along with their products.

This is joint work with Margaret-Ellen Messinger and Amanda Porter.

SVENJA HUNTEMANN, Concordia University of Edmonton
Temperature of Partizan ArcKayles  [PDF]

Partizan ArcKayles is played on any finite graph whose edges have been coloured blue or red. The player called Left removes any blue edge and any incident edges, while the player Right removes any red and incident edges. This game is a generalization of Domineering, which has been conjectured to have a maximum temperature of 2. We will discuss the temperature of Partizan ArcKayles, focusing on trees.

This is joint work with Neil McKay (University of New Brunswick) and Craig Tennenhouse (University of New England).

MARY ROSE JERADE, University of Ottawa
So Long Sucker: 2-player, 2-color case  [PDF]

So Long Sucker is a 1950 strategy board game developed by mathematician John Forbes Nash Jr. and his colleagues. It has a simple layout consisting of 4 players with $k$ chips each of their designated color, and a board consisting of $r$ empty rows. With a clear setup comes intricate rules that allow the game to reflect real life negotiations and conflicts between multiple parties. It is a useful tool to study players’ behaviors in situations that involve individual and group decisions.

The set of rules is very distinctive: players take turns but not in a fixed order, agreements can be made and broken at any time, and a player can win the game even if they are out of chips. One of the main points of interest in studying this game, is to study when a player has a winning strategy.

The game starts off with four players that get eliminated one after the other until only the winner is left. Thus in order to study winning strategies, it is of interest to look at endgame situations; particularly when there are only two players left in the game. During this talk, we will present a particular setup of the game: there are two players, first player Blue and second player Red, and their respective colors left in play. We will show through inductive reasoning, how we are able to characterize Blue's winning strategies.

TRENT MARBACH, Toronto Metropolitan University
The one-visibility localization game  [PDF]

We introduce a variant of the localization game in which the cops only have visibility one, along with the corresponding optimization parameter, the one-visibility localization number $\zeta_1$. This parameter has some surprising connections to the isoperimetric inequalities, and to the reduced visibility cops and robber game. We explore these connections by studying upper and lower bounds for $\zeta_1$ on $k$-ary trees and on Cartesian grids. We will also present the connections we have found to some other graph properties, such as tree-width and domination number.

REBECCA MILLEY, Grenfell Campus, Memorial University of NL
Progress on misère dicots  [PDF]

The algebraic structure of misère-play games, where the last move loses, is much less understood than that of normal-play, where the last move wins. Full misère has less equality and comparability, no nonzero inverses, and a trivial equivalence class for zero; however, restricting to certain subsets of misère games has proven useful for misère analysis. This talk will survey progress in the study of "dicot" games, where at every point, either both players have a legal move or neither does. We review the recent developments of a recursive comparison test, unique canonical forms, and classification of invertible elements, before outlining the next direction of open problems for the dicot universe.

DYLAN PEARSON, Mount Allison University
Slow Localization  [PDF]

A variation of the localization game is studied where the cops are restricted to moving to adjacent vertices on their turn. The distance from each cop to the robber is returned every round with the cops’ goal being to uniquely identify the robber’s location. The minimum number of cops required to locate the robber is called the slow localization number. We compare the slow localization number with the localization number on different graph classes and determine the slow localization number on Cartesian grids, caterpillars, wheels and cocoons.

This is joint work with Danny Dyer and Melissa Huggan.

MEHDI SALIMI, St. Francis Xavier University
The Strategies for Players to Win in Pursuit-Evasion Differential Games with Various Constraints  [PDF]

Pursuit-evasion differential games have garnered substantial scholarly attention, exemplified by significant contributions such as Leon A. Petrosyan's seminal work, "Differential Pursuit Games" (1977).

This study delves into a pursuit-evasion differential game involving an infinite number of pursuers and a lone evader. Notably, the control functions employed by all participants must conform to either geometric or integral constraints. By formulating winning strategies, the pursuers can effectively apprehend the evader by ensuring that at least one pursuer achieves an identical geometric position.

The study presents a comprehensive strategy enabling pursuers to capture the evader successfully. Moreover, the research findings have practical implications across diverse domains, particularly robotics and mobile gaming. The insights from this investigation contribute to the advancement of sophisticated robotic systems and foster the enhancement of interactive experiences within mobile gaming applications.

BRETT STEVENS, Carleton University
Proving simple things about one dimensional snort  [PDF]

Winning Ways volume 1 proposes values, modulo infinitesimal closeness, for one dimensional snort positions when they are cooled by 1. It also claims that these values are themselves infinitesimally close to the overheated values of sums of simple numbers and *s. We set out to articulate proofs of these assertions and further to determine and prove the temperatures and other cooled values of one dimensional snort positions. We were successful at establishing and proving cooled values. Although we believe we know the temperatures of these games, completing the proof has been challenging. I will discuss our successes and challenges as wells as describing a 1-d snort playing bot we have made available on the internet.

THOMAS WOLF, Brock University
Families of P-Positions in Chomp  [PDF]

The main part of the talk describes a method for finding families of P-positions which let to five 2-parameter families describing all P-positions with tiles in two rows and one column. Comments will also be made on a collection of all loosing (P-) positions up to some size, a conjecture about the asymptodic density of P-positions, a computation determining Sprague-Grundy (SG) numbers and a formula for SG numbers for any position with tiles in two rows.

© Société mathématique du Canada : http://www.smc.math.ca/