---

Graphs, Games and the Web / Graphes, jeux et la Toile
(Org: Anthony Bonato, Wilfrid Laurier University, Jeannette Janssen, Dalhousie University, and/et Richard Nowakowski, Dalhousie University)

---

MICHAEL ALBERT, University of Otago, Dunedin, New Zealand
Candy Nim

Nim is often played, when it is played at all, using small candies or chocolates in place of beans. By convention the candies removed by a player during the game become his or her property. So the normal priorities of the game are somewhat altered:

• the player who wins the ordinary Nim game must still play to win, but
  
  
• each player endeavours to obtain as many candies as possible.
  
  

Under these conditions the natural position to consider are ordinary second player wins. For such positions the questions to be asked are: what is the first player's advantage in terms of candies obtained and what should the first player's initial move be? We present the result of initial investigations of this problem. These suggest that even in the first non-trivial family of cases, three heaped candy Nim, the answers to these questions are surprisingly complex.

ELWYN BERLEKAMP, University of California at Berkeley
Quantitative Go, and some other combinatorial games

Combinatorial game theory is concerned with two-person perfect-information games, especially those classes of positions for which winning strategies can be stated explicitly, or at least proved to exist. The powerful mathematical methods (often requiring only paper and pencil, no computers) are most successful when applied to games whose positions often decompose into "sums". The many examples of such games include Nim, Dots and Boxes, Hackenbush (best played with colored chalk and erasures), Domineering (played with dominoes on a checkerboard), Konane (popular in ancient Hawaii), Amazons (invented less than fifteen years ago, but which has attracted a substantial following on the Internet), and Go (a popular Asian board game dating back several thousand years, and which supports nearly 2,000 active professionals today). The theory also applies very well to the fascinating new game called "Clobber", invented in Nova Scotia in the summer of 2001.

In many of these games, a mathematically defined "temperature" provides a numerical measure of the value of the next move. The extension of this notion to loopy positions, such as kos in Go, appeared in "Games of No Chance" in 1996. A subsequent extension, called "Environmental Go", includes a stack of coupons in addition to the Go board. This has led to fruitful collaborations between game theoreticians and professional 9-dan Go players.

For the past four years, we have been developing methods and techniques which allow us to get rigorous analyses of the last 50 to 100 moves of some professional games, and we not infrequently discover fatal mistakes.

We will present a broad introductory overview of this subject, including a fascinating problem in which Go, chess, checkers, and domineering are all played concurrently.

ANTHONY BONATO, Wilfrid Laurier University, Waterloo, Ontario, Canada  N2L 3C5
A unifying model for massive self-organizing networks

The web graph has nodes representing HTML web pages and edges representing the links between web pages. A protein network has nodes representing proteins in a cell, with edges representing interactions between the proteins. Despite their obvious differences, these networks possess many common characteristics. For example, both networks are massive, evolving, and small world. Further, both networks have a power law degree distribution: while most nodes have few links, a few nodes have a large number of links. There has been much recent activity and interest in modelling so-called self-organizing networks like the web graph. Several researchers have proposed stochastic models for self-organizing networks, including the copying model of Kumar et al. for the web graph, and the duplication model of Chung et al. for biological networks. We present a new model of self-organizing networks unifying both the copying and duplication models. We consider the infinite limits of graphs generated by our models, and contrast such limits with the infinite random graph. This is joint work with Jeannette Janssen.

NANCY CLARKE, Acadia University, Wolfville, NS  B4P 2R6
Variations on the Cops and Robber Game

Two versions of the Cops and Robber game are introduced in which the cops play with partial information provided via selected vertices of a graph. The robber has perfect information. When the partial information includes only the robber's position, we give bounds on the amount of information required by a single cop to guarantee the capture of a robber on a tree. When the partial information also includes information about the robber's direction, we give bounds on the amount of information required by a cop to capture a robber on a copwin graph.

COLIN COOPER, King's College, University of London
Random graph models of large networks

The world wide web raises interesting algorithmic questions in information retrieval such as search, classification and ranking of documents.

It is observed empirically that the world wide web and many other large networks have degree sequences which exhibit a power law. Thus the proportion n_k, of vertices of degree k is of the form n_k ~ Ck^-x when k is large. Here x > 0 constant is the parameter of the power law. This polynomial decrease is in contrast to classical Erdös-Rényi random graphs where n_k drops off exponentially fast above the expected degree.

We discuss two classes of random graphs, the fixed degree sequence and discrete dynamic (web graph or scale free graph) models. These are intended to model the world wide web and related structures. We describe results obtained for these models.

For web graphs we give more detail on the degree sequence and vertex degree distribution in the Undirected model, including the case with vertex deletions and the Directed Hub-Authority model.

ERIC DUCHENE, UJF/INPG - Grenoble
A new deletion game on graphs : "Le Picarète"

Time spent on chairs of halls often seems too long ... the following game could help students killing it: find a sheet of squared paper and define a grid on it (the game zone) by darkening some segments (generally we draw a rectangular outline, and may darken several segments inside). Then two players will darken alternatively one segment of the grid. Each player gets one point when darkening the fourth side of a square. The game ends when all the segments have been darkened, the winner being the player with the most points.

Our talk will deal with a generalization of this game: two players remove alternatively an edge of a given graph, one player getting one point each time the deletion of an edge lets one vertex alone (so that you can get at best two points by edge deleted). When no edges remain, the player who has got the maximum number of points is declared the winner.

Our study does not consist in finding the Grundy's function of this game (for a change!), but trying to make an estimate of the value of an initial game configuration, i.e. the difference between the maxima numbers of points feasible by both players. First of all, we describe a classification of connected graphs according to the parity of their numbers of edges, vertices and pendent edges. From this first classification, as a game configuration could be considered as a set of connected graphs, we define a new classification about configurations themselves. A game configuration will be coded on three bits, each bit representing the parity of a specific set of "odd connected components" (components heaving an odd number of edges). Hence we define eight types of configurations, and for each one, we make an estimate of its value, function of the types of connected graphs that compose it. This estimate consists in finding an upper or lower bound of the value, that often let us decide which configurations are winning or losing, and find a strategy that leads to victory (or to the most respectable defeat...).

SHANNON FITZPATRICK, University of Prince Edward Island, Charlottetown, PE C1A 4P3
Cops, Robbers and Isometric Paths

An isometric path is merely any shortest path between two vertices. Aigner & Fromme observed that, in the game of "Cops and Robber", a single cop moving on an isometric path P can, after a finite number of moves, capture the robber immediately should the robber move onto P. Therefore, given a set of isometric paths that cover the vertices of a graph, assigning a single cop to each path easily results in the robber’s capture.

In this talk, I will discuss the problem of determining the minimum number of isometric paths required to cover the vertices of a graph. For graphs such as trees, grid graphs, and certain classes of hypercubes, this number has been determined exactly. I will also introduce new results for the fractional analogue of this problem.

MATT HARREN, UC Berkeley / 577 Soda Hall #1776 / Berkeley, CA 94720-1776, USA
Federations in Go Endgames

Combinatorial game theory relies on our ability to decompose games into sums of smaller, independent games. But what if the subgames are not truly independent, and there are a few certain combinations of moves that will allow one subgame to affect another?

This talk looks at the independence problem of Go endgames. We describe an extension to AnalGo, a software tool that assists with the analysis of endgames, that can reason about Go subgames that are "mostly" independent but may interact under some circumstances. The new extension allows users to declare federations of subgames which may affect each other. In these federations, users specify conditions under which subgames interact, and the effects that these interactions could have. Federations simplify analysis because the subgames can be dealt with independently by the user, and the software will account for any overlap.

JEANNETTE JANSSEN, Dalhousie

FRANçOIS LAVIOLETTE, Université Laval
Cop-win graphs and bridge graphs

We will explore the strong link between cop-win graphs and bridge graphs. In particular we will show that they can be characterized by very similar construction procedures. We will also construct finite cop-win graphs that have a very small diameter but in which the robber is able to "survive" for a very long time.

Finite bridge graphs are always cop-win, but it is not the case in general. Indeed, in the infinite case, even chordal graphs of diameter 2 may not be cop-win. Since this may seem counterintuitive, we will introduce a new family of graphs, the weakly-cop-win graphs. These graphs have the nice property that in the finite case, they are exactly the cop-win graphs, and that every bridge graph (finite or infinite) is weakly-cop-win. We will also show that the family of infinite bridge graphs possess a nice compactness property.

LIONEL LEVINE, 824 Evans Hall, Dept. of Mathematics, University of California, Berkeley, CA 94720
Fractal sequences and Restricted Nim

The Grundy number of an impartial game G is the size of the unique Nim heap equal to G. We introduce a new variant of Nim, Restricted Nim, which restricts the number of stones a player may remove from a heap in terms of the size of the heap. Certain classes of Restricted Nim are found to produce sequences of Grundy numbers with a self-similar fractal structure. Extending work of C. Kimberling, we obtain new characterizations of these "fractal sequences" and give a bijection between these sequences and certain upper-triangular arrays. As a special case we obtain the game of Serial Nim, in which the Nim heaps are ordered from left to right, and players can move only in the leftmost nonempty heap.

XIANGWEN LI, University of Regina, Regina, SK
Pursuit-Evasion in graphs without a K_{3, 3}-minor

The Pursuit-Evasion search model has been extensively studied for many years. This model was first introduced by Nowakowski and Winkler, and by Quilliot independently. Aigner and Fromme proved the classical theorem that the search number for every planar graph is at most 3. In this paper, we improved this result by proving that if G has no K_{3, 3}-minor, then the search number for G is at most 3. We also show the upper bound is best possible.

HONGYU LIU, Dalhousie

PAUL OTTAWAY, Dalhousie University, Halifax, NS B3H 4R2
Even-Odd Games

This talk will examine a recursively defined set of game values that naturally arise in certain games. In one such game played on a graph, players alternately remove vertices according to restrictions based on their degree. We show that one variation leads to even-odd games where neither fractions or infinitesimals (besides 0 and *) can occur.

DAVID PIKE, Memorial University of Newfoundland, St. John's, Newfoundland
Iterated 2-Cycle Contractions and Strong Connectivity in Random Directed Graphs

Given a directed graph, consider the effect of the following algorithm: find a directed 2-cycle u « v, contract this cycle so that u and v coalesce into a single new vertex, and then iterate this procedure until no directed 2-cycles remain. The property of there being a single vertex at the end of this procedure is compared with the property of being strongly connected. We focus our work on random directed graphs, although our underlying motivation relates to the Web Graph. This work is joint with Alasdair Graham.

AARON SIEGEL, University of California, Berkeley, CA
Calculating values of loopy games

Computer calculations involving traditional games-those without repeated positions-are relatively straightforward, as most of the algorithms can be specified by a simple recursion. However, there are a number of interesting games that allow some degree of repetition, including Go and Fox and Geese, and extending the algorithms to accommodate such loopy games introduces significant complications. Since the game graphs of loopy games may contain cycles, infinite play sequences are theoretically possible, and these must be modeled computationally. I will introduce one software program, Combinatorial Game Suite, which can handle certain types of loopy games. I will discuss how the loopy games algorithms differ from those for traditional games, and how they were applied to calculate game-theoretic values of positions in Fox and Geese.

DAVID WOLFE, Gustavus Adolphus College, St Peter, MN 56082
Partisan Subtraction Games

Since Bouton's paper of 1902, the game of Nim has provided a foundation to the theory of nonpartisan games. Yet partisan variants of Nim have remained mostly a mystery.

Fraenkel and Kotzig introduced partisan subtraction games which are played with a pile of n beans (or multiple piles of varied sizes). Each of two players, Left and Right, has a predefined subtraction set of positive integers. Players take turns removing any number of beans in his/her subtraction set. A player who cannot move loses. We present a variety of known results and possible extensions.

Joint work with Dan Calistrate, Richard Nowakowski, and Michael Albert.