The Mathematics of Chip-Firing

Caroline J. Klivans

• Publisher: Chapman and Hall/CRC
• Year: 2018
• ISBN:
  9781351801003
• Edition: 1
• Topic: Computer Science
• Subtopic: Operating Systems
• Index: Computer Science

The Mathematics of Chip-firing is a solid introduction and overview of the growing field of chip-firing. It offers an appreciation for the richness and diversity of the subject. Chip-firing refers to a discrete dynamical system — a commodity is exchanged between sites of a network according to very simple local rules. Although governed by local rules, the long-term global behavior of the system reveals fascinating properties.

The Fundamental properties of chip-firing are covered from a variety of perspectives. This gives the reader both a broad context of the field and concrete entry points from different backgrounds.

Broken into two sections, the first examines the fundamentals of chip-firing, while the second half presents more general frameworks for chip-firing. Instructors and students will discover that this book provides a comprehensive background to approaching original sources.

Features:

• Provides a broad introduction for researchers interested in the subject of chip-firing

• 
  
  

• The text includes historical and current perspectives

• 
  
  

• Exercises included at the end of each chapter

• 
  
  

About the Author:

Caroline J. Klivans received a BA degree in mathematics from Cornell University and a PhD in applied mathematics from MIT. Currently, she is an Associate Professor in the Division of Applied Mathematics at Brown University. She is also an Associate Director of ICERM (Institute for Computational and Experimental Research in Mathematics). Before coming to Brown she held positions at MSRI, Cornell and the University of Chicago. Her research is in algebraic, geometric and topological combinatorics.

Part I

Fundamentals

Chapter 1

Introduction

1.1 A brief introduction

We start with a brief introduction to the basic dynamics of the chip-firing process in order to give a sense of the fundamental action. The overarching idea to keep in mind is: simple local rules leading to complex global behavior.

Consider the 4 × 4 grid to the left. The grid can be thought of as an abstract graphical network or as the discretization of a planar surface. Four sites are populated with an initial nonzero value – one might visualize a stack of chips, grains of sand or an amount of currency.

Two sites connected by an edge are called neighbors. In the chip-firing process, the action of a site will depend on only two things, the value at the site itself and the number of neighbors it has. If the value at a site is at least as large as the number of neighbors it has, it will give one unit of value to each neighbor. This happens regardless of the neighbors’ values.

In our example, the site with value 6 has four neighbors. Because its value is greater than its number of neighbors, the site will disperse some of its value. Dispersion is egalitarian and one unit of value is passed to each neighbor. When a site passes value to its neighbors the site fires.

Below on the left, the site with value 6 fires once. The result is shown on the right. The value of the initial site has decreased by 4 and the value at each neighbor has increased by 1.

The firing of one site may in turn cause other sites to fire. In our example, two sites with four neighbors now have value 4 and will therefore share with their neighbors. Note that in firing, they will each return one unit of value back to the first site that fired.

The result of firing these two sites is the same regardless of which site fires first or if they fire simultaneously. The result is shown above and to the right.

In the resulting configuration, the original site that fired has now regained enough value that it will fire again. Depending on the initial configuration, two sites might pass value back and forth in this manner many times.

Although some value has returned to the original location, we see that overall the configuration is more spread out than in the initial configuration. For example, sites along the top and left boundaries now have non-zero value.

Boundary sites have fewer neighbors and hence a different threshold for firing. In our running example, below and to the left, two boundary sites currently have value 3. These sites have only three neighbors and hence they will fire.

The result of firing both of these locations is that the corner site will have value 2. A value of 2 is enough to allow the corner site to fire.

After firing the corner, the system settles into a configuration where no sites fire. A configuration in which no site can fire is called stable.

Many immediate questions arise in considering this chip-firing process. For example, when two sites can both fire, does it matter in which order they fire? In our example it did not. We will see that the answer is always no. Chip-firing processes satisfy a certain co...