document: the parallel chip - firing game or candy - passing game is a periodic automaton on graphs in which vertices , each of which contains some nonnegative number of chips , `` fire '' exactly one chip to each of their neighbors if possible . 
   formally , let @xmath4 be an undirected graph with vertex set @xmath5 and edge set @xmath6 . define the _ parallel chip - firing game _ on @xmath4 to be an automaton governed by the following rules :    * at the beginning of the game , @xmath7 chips are placed on each vertex @xmath8 in @xmath4 , where @xmath7 is a nonnegative integer . 
   position _ of the parallel chip - firing game , denoted by @xmath9 , be the ordered pair @xmath10 containing the graph and the number of chips on each vertex of the graph . * at each _ move _ or _ step _ of the game , if a vertex @xmath8 has at least as many chips as it has neighbors , it will give ( _ fire _ ) exactly one chip to each neighbor . 
   such a vertex is referred to as _ firing _ ; otherwise , it is _ non - firing_. all vertices fire simultaneously ( in parallel ) . 
   we employ the notation of levine @xcite . 
   let @xmath11 denote the step operator ; that is , @xmath12 is the position resulting after one step is performed on @xmath9 . 
   let @xmath13 , and @xmath14 . 
   we refer to @xmath15 as the position occurring _ 
   after @xmath16 steps_. for simplicity , we limit our discussion to connected graphs 
   .    as the number of chips and number of vertices are both finite , there are a finite number of positions in this game . 
   additionally , since each position completely determines the next position , it follows that for each initial position @xmath9 , there exist some positive integers @xmath17 such that for large enough @xmath18 , @xmath19 . 
   we refer to the minimal such @xmath17 as the _ period _ @xmath20 of @xmath9 , and we refer to the set @xmath21 as one period of @xmath9 . also , we call the minimal such @xmath18 the _ transient length 
   _ @xmath22 of @xmath9 . 
   the parallel chip - firing game was introduced by bitar and goles @xcite in 1992 as a special case of the general chip - firing game posited by bjrner , lovsz , and shor @xcite in 1991 . 
   they @xcite showed that the period of any position on a tree graph is 1 or 2 . in 2008 , 
   kominers and kominers @xcite further showed that all connected graphs satisfying @xmath23 have period 1 ; they further established a polynomial bound for the transient length of positions on such graphs . 
   their result @xcite that the set of all `` abundant '' vertices @xmath24 with @xmath25 stabilizes is particularly useful in simplifying the game . 
   it was conjectured by bitar @xcite that @xmath26 for all games on all graphs @xmath4 . however , kiwi et . 
   @xcite constructed a graph on which there existed a position whose period was at least @xmath27 , disproving the conjecture . 
   still , it is thought that excluding particular graphs constructed to force long periods , most graphs still have periods that are at most @xmath28 . in 2008 , levine @xcite proved this for the complete graph @xmath1 . 
   the parallel chip - firing game is a special case of the more general chip - firing game , in which at each step , a vertex is chosen to fire . 
   the general chip - firing game , in turn , is an example of an _ abelian sandpile _ @xcite , and has been shown to have deep connections in number theory , algebra , and combinatorics , ranging from elliptic curves @xcite to the critical group of a graph @xcite to the tutte polynomial @xcite . 
   bitar and goles @xcite observed that the parallel chip - firing game has `` nontrivial computing capabilities , '' being able to simulate the and , not , and or gates of a classical computer ; later , goles and margenstern @xcite showed that it can simulate any two - register machine , and therefore solve any theoretically solvable computational problem . 
   finally , the parallel chip - firing game can be used to simulate a pile of particles that falls whenever there are too many particles stacked at any point ; this important problem in statistical physics is often referred to as the _ deterministic fixed - energy sandpile _ @xcite . 
   the fixed - energy sandpile , in turn , is a subset of the more general study of the so - called _ spatially extended dynamical systems _ 
   , which occur frequently in the physical sciences and even economics @xcite . 
   such systems demonstrate the phenomenon of _ self - organized criticality _ , tending towards a `` critical state '' in which slight perturbations in initial position cause large , avalanche - like disturbances . 
   self - organized critical models such as the abelian sandpile tend to display properties of real - life systems , such as @xmath29 noise , fractal patterns , and power law distribution @xcite . 
   finally , the parallel chip - firing game is an example of a cellular automaton , the study of which have implications from biology to social science .      in section 2 
   , we establish some lemmas about parallel chip - firing games on general simple connected graphs . we bound the number of chips on any single vertex in games with nontrivial period , define the notion of a complement position @xmath30 of @xmath9 and show that it has the same behavior as @xmath9 , and find a necessary and sufficient condition for a period to occur . 
   then , in section 3 , we find , with proof , every possible period for the complete bipartite graph @xmath31 . 
   we do so by first showing the only possible periods are of length @xmath32 or @xmath33 for @xmath34 , and then constructing games with such periods , proving our main result . finally , in section 4 , we construct positions on the complete @xmath2-partite graph @xmath35 with period @xmath17 for all @xmath36 . 
   consider a simple connected graph @xmath4 . for each vertex @xmath8 in @xmath4 
   , let @xmath37 denote the number of firing neighbors @xmath38 of @xmath8 ; that is , the number of vertices @xmath38 neighboring @xmath8 satisfying @xmath39 . 
   a step of the parallel chip - firing game on @xmath4 is then defined as follows :    @xmath40    define a _ terminating _ position to be a position in which no vertices fire after finitely many moves . 
   we begin our investigation by proving some lemmas limiting the number of chips on each vertex in a game with nontrivial period ( period greater than 1 ) . 
   [ lem:2n-1 ] for sufficiently large @xmath18 , @xmath41 for all @xmath42 in all games with nontrivial period on a connected graph @xmath4 . 
   kominers and kominers @xcite showed that if a vertex @xmath42 satisfies @xmath43 , then @xmath44 . 
   they then showed that if , after sufficiently many steps @xmath18 , there still exists a vertex @xmath8 with @xmath45 , then all vertices must be firing from that step onward . since the period of a position is 1 if and only if either all or no vertices in @xmath4 are firing @xcite , @xmath46 is true for any game on @xmath4 with nontrivial period and sufficiently large @xmath18 . 
   we further bound the number of chips on each vertex by generalizing a result of levine @xcite :    [ lem : confined ] consider a vertex @xmath8 in position @xmath9 such that @xmath47 . 
   then @xmath48    either @xmath49 or not . 
   we consider the cases individually .    if @xmath50 , then @xmath51 
   . so @xmath52    if instead @xmath53 , then @xmath54 . hence @xmath55 
   @xmath56    if a vertex @xmath8 satisfies @xmath57 , we call it _ confined_. 
   furthermore , call a position confined if all vertices in the position are confined . 
   note that for confined @xmath8 , @xmath58 lemmas  [ lem:2n-1 ] and  [ lem : confined ] imply that if @xmath59 , then @xmath60 is confined if @xmath61 , where @xmath22 is the transient length of @xmath9 ; that is , once the game reaches a position which repeats periodically , all subsequent positions are confined . 
   we generally limit our discussion to confined positions to exclude positions with trivial periods . 
   next , we define @xmath62 to be the indicator function of whether a vertex @xmath8 fires at step @xmath18 . 
   we prove a lemma about positions that are equivalent , or have the same behavior , when acted upon by the step operator @xmath11 . 
   [ lem : complement ] let the _ complement _ @xmath30 of a confined position @xmath9 be the position that results after replacing the @xmath7 chips on each vertex @xmath63 with @xmath64 chips 
   . then @xmath65 . 
   we begin by noticing that since @xmath9 is confined , each vertex @xmath8 has at most @xmath66 chips , so each vertex in @xmath30 has a nonnegative number of chips . 
   observe that a vertex @xmath8 fires in @xmath30 exactly when it did not fire in @xmath9 . 
   hence , @xmath67 , and all but @xmath37 neighbors will fire in @xmath68 . 
   so @xmath69    this lemma means we may treat @xmath9 and @xmath30 as equivalent positions , as at any point during their firing , we may transform one into the other . 
   this implies the following corollary :    for all positions @xmath9 on @xmath4 , @xmath70 . 
   next , we prove a proposition that characterizes a period of the game on any connected graph @xmath4 . for each position @xmath9 and 
   vertex @xmath63 , let @xmath71 be the number of times @xmath8 fires in the first @xmath18 steps .    [ prop : alleq ] the position @xmath9 on @xmath4 satisfies @xmath72 if and only if each vertex has fired the same number of times within those @xmath18 steps ; that is , iff for all vertices @xmath73 , @xmath74    if equation holds , then by equation , @xmath75 for all @xmath8 , so @xmath72 . 
   conversely , if @xmath72 , consider the vertex @xmath76 such that @xmath77 is maximal . then , since @xmath78 for all vertices @xmath38 neighboring @xmath8 , @xmath79 but as @xmath80 , we see that @xmath81 must hold for all @xmath38 neighboring @xmath8 . 
   since the graph is connected , we continue inductively through the entire graph to obtain equation . 
   recall that a complete bipartite graph @xmath82 may be partitioned into two subsets of vertices , @xmath83 and @xmath84 , such that no edges exist among vertices in the same set , but every vertex in @xmath83 is connected to every vertex in @xmath84 . 
   we refer to the sets @xmath85 as the _ sides _ of @xmath4 . 
   define @xmath86 and @xmath87 . 
   as stated above , bitar and goles @xcite showed that if no vertices or all vertices are firing , the period is 1 . 
   we consider only games whose period is greater than 1 ; that is , at least one vertex is firing every turn , and not all vertices fire every turn . 
   let @xmath88 and @xmath89 denote the number of vertices in @xmath83 and @xmath84 , respectively , that fire in @xmath9 . 
   then , @xmath90 if @xmath91 , and @xmath92 if @xmath93 . 
   notice that @xmath89 is the number of vertices in @xmath84 with at least @xmath94 chips , and @xmath88 is the number of vertices in @xmath83 with at least @xmath95 chips . 
   let @xmath96 be the number of times any of the vertices in @xmath83 have fired in the first @xmath18 steps starting from , and including , @xmath15 , and define @xmath97 similarly . 
   define @xmath98 and @xmath99 .    without loss of generality , 
   we prove facts about the vertices in @xmath83 , which also hold for vertices in @xmath84 . in the first @xmath18 steps , a vertex @xmath8 in @xmath83 fires a total of @xmath100 chips and receives @xmath101 chips . 
   hence ,    @xmath102    next , we prove a lemma that bounds the number of times a vertex has fired once the position is confined . 
   [ lem : diff1 ] let @xmath103 . 
   if @xmath9 is confined , and @xmath104 , then for all @xmath105 , @xmath106    we prove this by induction on @xmath18 . 
   the base case , @xmath107 , is straightforward : vertices @xmath8 and @xmath38 have each fired either 0 or 1 times . if @xmath8 fires after step @xmath108 , then @xmath109 chips , and @xmath38 also fires . 
   now , assume @xmath110    if @xmath111 , then by equation , @xmath112 @xmath113    thus , if @xmath8 is ready to fire after step @xmath18 , then @xmath38 must be ready to fire also . 
   it follows that @xmath114    otherwise , @xmath115 . 
   then , since @xmath60 is confined from lemma  [ lem : confined ] , by equation , @xmath116 @xmath117 by lemma  [ lem : confined ] , since the degrees of both @xmath8 and @xmath38 are @xmath95 . 
   so , if @xmath38 is ready to fire after step @xmath18 , so is @xmath8 , and equation again holds .    from the above lemma , we can deduce the following :    [ lem : ndiv ] if @xmath9 is confined and @xmath118 , then @xmath119 for all @xmath120 . 
   let @xmath76 be the vertex in @xmath83 with @xmath121 minimal . 
   by lemma  [ lem : diff1 ] , for all @xmath91 , @xmath122 where @xmath123 . if @xmath124 is the number of vertices @xmath125 with @xmath126 , then @xmath127 since @xmath128 , we have @xmath129 . then @xmath130 
   because @xmath131 ; so @xmath132 for all @xmath91 . 
   since @xmath133 , this implies @xmath119 for all @xmath91 .    clearly , if all @xmath94 vertices in @xmath83 have fired the same number of times , then @xmath118 ; 
   so we have found a necessary and sufficient condition for all vertices on the same side to fire the same number of times . 
   but by proposition  [ prop : alleq ] , a period is completed when all @xmath63 have fired the same number of times ; thus , we desire a relation between the sides that forces every vertex on both sides to fire the same number of times . 
   our first step is the following lemma . 
   [ lem : t1 ] if @xmath9 is confined , and @xmath134 for some positive integer @xmath32 , then @xmath135 for all @xmath136 . 
   if @xmath93 is firing , then @xmath137 since @xmath9 is confined and @xmath8 is firing , @xmath138 ; and since @xmath139 is confined by lemma  [ lem : confined ] , we have @xmath140 these two inequalities together imply that , for firing vertices @xmath8 , @xmath141    if @xmath136 is instead non - firing , then @xmath142 chips . 
   @xmath143 is confined by lemma  [ lem : confined ] , so @xmath144 ; since @xmath145 because @xmath8 is non - firing , we then deduce , similarly as above , that @xmath146 for non - firing vertices @xmath8 as well . 
   therefore , for all @xmath136 , we have that @xmath147 so @xmath148 for all @xmath136 . 
   if @xmath149 , then we can compute @xmath150 ; hence @xmath8 does not fire after step @xmath18 , and @xmath151 . 
   if instead @xmath152 , then @xmath153 , so @xmath8 fires after step @xmath18 , and @xmath154 , and we are done . 
   note that applying this lemma to @xmath15 also means @xmath155 . 
   next , recalling the definition of @xmath156 in equation , we define @xmath157 for nonnegative integers @xmath16 and positive integers @xmath18 . 
   note that by definition , @xmath158 applying lemmas  [ lem : ndiv ] and  [ lem : t1 ] to the position @xmath15 , we find that if @xmath159 , then @xmath160 for all vertices @xmath91 and all vertices @xmath161 . 
   now , we give a sufficient condition for a period of a position on @xmath31 to occur . 
   [ lem : periodt ] if @xmath9 is confined , and for some @xmath162 and @xmath163 , @xmath159 and @xmath164 for all @xmath91 , then @xmath165 if @xmath18 is chosen to be as small as possible .    by lemma 
   [ lem : ndiv ] applied to @xmath166 , since @xmath159 , @xmath167 for all @xmath91 . if for some @xmath162 , @xmath164 for all @xmath91 , then @xmath168 for all @xmath91 . 
   but by equation  , @xmath169 for all @xmath91 , @xmath161 . 
   hence , @xmath170 for all vertices @xmath171 , which by proposition  [ prop : alleq ] applied to @xmath172 implies @xmath173 , or @xmath174 . 
   but @xmath18 is taken to be as small as possible , so @xmath165 .    using this fact , we limit which periods are possible for games on @xmath31 . 
   [ prop : t2 t ] if @xmath9 is confined and @xmath134 , then @xmath165 or @xmath175 .    by iteratively applying lemma  [ lem : t1 ] @xmath176 times , along with lemma  [ lem : ndiv ] , we find that @xmath177 for all vertices @xmath91 and nonnegative even integers @xmath16 . 
   expanding the sums @xmath178 and @xmath179 in terms of @xmath180 , we obtain @xmath181 for all nonnegative even integers @xmath16 and vertices @xmath91 .    if @xmath164 for all @xmath91 and some @xmath182 , then the period is @xmath18 by lemma  [ lem : periodt ] . otherwise , let @xmath183 be the set of vertices @xmath184 satisfying @xmath185 for all @xmath186 . 
   the range of @xmath187 is @xmath188 , so this condition is equivalent to @xmath189 for all @xmath186 . 
   we show that the period of @xmath9 is then @xmath190 .    * case 1 . 
   * @xmath18 is odd . 
   consider some nonnegative integer @xmath191 , and let @xmath192 . 
   if @xmath191 is even , let @xmath193 ; otherwise , let @xmath194 . if @xmath195 then @xmath196 and @xmath197 . 
   but by equation , @xmath198 contradicting the assumption that @xmath185 for all @xmath186 .    hence , @xmath199 for all nonnegative @xmath191 . 
   this implies @xmath200 for all @xmath201 ; hence @xmath202 for all @xmath192 . 
   since @xmath203 for other vertices @xmath204 , by lemma  [ lem : periodt ] , @xmath175 .    * case 2 . 
   * @xmath18 is even . 
   let @xmath192 . by equation , @xmath205    but by equation , @xmath206 for all @xmath192 . 
   then as above , @xmath175 by lemma  [ lem : periodt ] . 
   more specifically , the following corollary holds :    [ cor : lea ] let @xmath9 be a position on @xmath31 . if @xmath20 is odd , @xmath207 ; and if @xmath20 is even , @xmath208 .    without loss of generality , 
   let @xmath209 . if @xmath210 , @xmath211 . otherwise , @xmath59 . 
   since @xmath212 , we may replace @xmath9 by @xmath213 and assume @xmath9 is confined by lemma  [ lem : confined ] .    by the pigeonhole principle , there must exist steps @xmath214 with @xmath215 . 
   but then @xmath216 , so by proposition  [ prop : t2 t ] applied to @xmath217 , @xmath218 or @xmath33 , where @xmath219 hence , if @xmath20 is odd , @xmath211 , and if @xmath20 is even , @xmath220 . 
   finally , we characterize all possible periods for @xmath9 . 
   [ prop : existpos ] there exist positions @xmath9 on @xmath82 with period @xmath32 and @xmath33 for all @xmath221 .    without loss of generality , 
   let @xmath209 . 
   let @xmath222 be the vertices in @xmath83 , and @xmath223 be the vertices in @xmath84 . 
   let @xmath32 be a positive integer such that @xmath224 . 
   we represent each position @xmath9 on @xmath4 by two vectors @xmath225 @xmath226    consider the following position @xmath227 , which we claim has period @xmath32 : @xmath228 @xmath229 @xmath230 and @xmath231 fire , so @xmath232 is represented by @xmath233 @xmath234 we can see that the vertices @xmath235 with @xmath236 satisfy @xmath237 for @xmath238 . 
   so , @xmath239 follows upon applying proposition  [ prop : alleq ] , noting that after @xmath32 steps , each vertex has fired exactly once . 
   hence , @xmath227 has period @xmath32 . 
   next , consider the following position @xmath240 , which we claim has period @xmath33 : @xmath241 @xmath242 note that , if at any point @xmath243 , then @xmath244 , because @xmath245 and @xmath246 have the same neighbors . 
   so , @xmath247 is represented by @xmath248 @xmath249 and @xmath250 is represented by @xmath251 @xmath234 we can see that for @xmath252 , the vertex in @xmath4 that fires ( has @xmath95 chips if it is in @xmath83 , or @xmath94 chips if it is in @xmath84 ) in position @xmath253 is @xmath254    so , after @xmath33 steps , every vertex will have fired once , and by proposition  [ prop : alleq ] , @xmath255 . 
   it remains to construct initial positions with period 1 or 2 . 
   the trivial game with no chips on any vertex has period 1 , while the initial position where each vertex in @xmath83 has @xmath95 chips , and each vertex in @xmath84 has 0 chips , can be easily checked to have period 2 . 
   thus , all periods @xmath256 , and @xmath257 , are achievable .    combining our results 
   , we obtain our main theorem . 
   a nonnegative integer @xmath17 is a possible period of a position @xmath9 of the parallel chip - firing game on @xmath31 if and only if @xmath258    by corollary  [ cor : lea ] , no period lengths may lie outside the sets in ; and in proposition  [ prop : existpos ] , we have constructed positions with all such periods . 
   we again use the vector notation from above to represent the positions of a parallel chip - firing game on the complete @xmath2-partite graph @xmath259 formed by joining the anticliques @xmath260 ; let the vertices in @xmath261 be @xmath262 for each @xmath263 . without loss of generality , we will assume @xmath264 . 
   as above , we represent a position on @xmath4 by the set of vectors @xmath265    below is a representation of a position which has period @xmath266 for all @xmath267 and @xmath268 . 
   note that a vertex in @xmath269 fires when it has at least @xmath270 chips ; here @xmath271 is the degree of any vertex in @xmath269 .    for our construction , we let @xmath272    we now show that this position indeed has period @xmath266 . 
   let @xmath273 be the set of all firing vertices in @xmath274 . 
   it can be checked that    @xmath275 @xmath276 for @xmath277 ; and @xmath278 for @xmath279 , encompassing steps @xmath280 through @xmath281 ; @xmath282 for @xmath283 ; and    @xmath284 for @xmath285 . 
   ( in fact , each vertex @xmath63 fires exactly when it contains @xmath286 chips . ) 
   the latter two categories describe which vertices fire during steps @xmath287 through @xmath288 . 
   but after this @xmath289 step , every vertex in @xmath4 has fired exactly once ; the last to fire is @xmath290 . 
   hence , @xmath291 by proposition  [ prop : alleq ] , and the period is @xmath292 as desired . 
   this means all periods from @xmath293 to @xmath294 are achievable , as @xmath295 ranges from @xmath108 to @xmath296 and @xmath32 ranges from @xmath293 to @xmath297 . as an example , consider the following position on the graph @xmath298 with period @xmath299 : @xmath300    for this position , @xmath301 , and its predicted period length is @xmath302 as desired . 
   for several graphs , a proof of bitar s conjecture that @xmath26 for all parallel chip - firing games on those graphs would be interesting ; we proved the conjecture for the complete bipartite graph . though we have constructed many periods of games on complete @xmath2-partite graphs in section 4 , there exist periods longer than those detailed . 
   for example , take the following position on @xmath303 , which has period 5 : @xmath304 though positions with these larger periods are more difficult to characterize generally , bitar s conjecture still appears to be true for complete @xmath2-partite graphs . 
   moreover , bounding the periods of positions on vertex - regular graphs and more general bipartite graphs are directions for further research . by doubling the length of each cycle in the graph used in the counterexample by kiwi et . 
   @xcite , we find a counterexample on a graph containing only even cycles , that is , for the general bipartite graph . 
   we would also like to determine which periods less than the bound are possible . 
   levine @xcite related period lengths of games on the complete graph to the _ activity _ , defined as @xmath305 . 
   on the other hand , we believe that period lengths are related to lengths of subcycles ( closed paths ) of the graph @xmath4 ; in particular , we conjecture that any period length of a game on @xmath4 is either a divisor of the order of some subcycle of @xmath4 , or perhaps the least common multiple of the orders of some disjoint subcycles of @xmath4 . 
   this agrees with known results for the tree graph @xcite , complete graph @xcite , and now the complete bipartite graph . 
   our numerical experiments have also verified this conjecture for cycle graphs and complete @xmath32-partite graphs ; in fact , my correspondence with zhai @xcite has produced a proof of this conjecture for the cycle graph . 
   another interesting direction to pursue is observing the implications of `` reducing '' the parallel chip - firing game by removing as many chips as possible from each vertex without affecting their firing pattern ( without changing @xmath156 for all @xmath42 and @xmath306 ) . 
   this reduction may simplify some games into being more approachable by induction .    besides studying period lengths of parallel chip - firing games , an examination of the transient length of games on certain graphs would be useful in modeling real - world phenomena . 
   studying transient positions would also help uncover what attributes determine whether a position is within a period or not , and bounding the transient length would make for more efficient computation of the period length of games on complex graphs . 
   chip - firing games on lattices and tori have been used as cellular automaton models of the deterministic fixed - energy sandpile ( see @xcite ) . 
   since most studies of sandpiles have been concerned with asymptotic measures such as the `` activity , '' bounding the period length of such models could serve as a measure of the fidelity of the model to the real world . 
   the author would like to thank my mentor , yan zhang of the massachusetts institute of technology , for his teaching , guidance , and support , the center for excellence in education and the research science institute for sponsoring my research , and dr . 
   john rickert for tips on writing and lecturing . 
   the author would also like to thank dr . 
   lionel levine , scott kominers , paul kominers , daniel vitek , brian hamrick , dr .  dan teague , patrick tenorio , alex zhai , and dr . 
   ming ya jiang for valuable pointers and advice on this problem and this paper .
summary: the parallel chip - firing game is a periodic automaton on graphs in which vertices `` fire '' chips to their neighbors . in 1989 , bitar conjectured that the period of a parallel chip - firing game with @xmath0 vertices is at most @xmath0 . 
   though this conjecture was disproven in 1994 by kiwi et . 
   al . 
   , it has been proven for particular classes of graphs , specifically trees ( bitar and goles , 1992 ) and the complete graph @xmath1 ( levine , 2008 ) . 
   we prove bitar s conjecture for complete bipartite graphs and characterize completely all possible periods for positions of the parallel chip - firing game on such graphs . 
   furthermore , we extend our construction of all possible periods for games on the bipartite graph to games on complete @xmath2-partite graphs , @xmath3 , and prove some pertinent lemmas about games on general simple connected graphs .    tian - yi jiang