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
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:
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.
- the player who wins the ordinary Nim game must still play to
- each player endeavours to obtain as many candies as possible.
- 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
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
- 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
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 nk, of vertices of degree k is of the form nk ~ 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 nk 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
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
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 robbers 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,
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 K3, 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
K3, 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
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
- 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.