[PDF] A maximizing characteristic for critical configurations of chip-firing

View - Download A maximizing characteristic for critical configurations of chip-firing

Previous PDF

Next PDF

A maximizing characteristic for critical congurations of chip-ring games on digraphs

Hoang Thach NGUYEN

, Thi Thu Huong TRANy

November 10, 2018

Abstract

Avalet al.proved in [2] that starting from a critical conguration of a chip- ring game on an undirected graph, one can never achieve a stable conguration by reverse ring any non-empty subsets of its vertices. In this paper, we generalize the result to digraphs with a global sink where reverse ring subsets of vertices is replaced with reverse ring multi-subsets of vertices. Consequently, a combinatorial proof for the duality between critical congurations and superstable congurations on digraphs is given. Finally, by introducing the concept of energy vector assigned to each conguration, we show that critical and superstable congurations are the unique ones with the greatest and smallest (w.r.t. the containment order), respectively, energy vectors in each of their equivalence classes. Keywords|critical congurations, superstable congurations, duality, chip-ring games, energy vector optimizer.

1 Introduction

Originally developped in the early nineties of the last centuries in the context of self- organized criticality [ 9 ] and as a \balancing game" on graphs [ 6 7 ], chip-ring games (CFG) have become an attractive mathematical model in combinatorics [ 5 13 14 16 In recent years, new connections have been found between CFG and the Riemann-Roch theory on graphs [ 1 4 ] and potential theory on graphs [ 3 10 ]. This manuscript contributes some new results to the latter category and at the same time provides a combinatorial insight on existing results. We consider a CFG on a digraphGwith a global sink. A conguration is a distribution of chips on the non-sink vertices. A transition, called a ring, consists in choosing a vertex and sending one of its chips along each out-going arc to its neighbors. A ring is legal if the chosen vertex has at least as many chips as its out-going arcs. Suppose we restrict the game to non-negative congurations and legal rings. Then, a stable conguration is Institute of Mathematics, 18 Hoang Quoc Viet street, Cau Giay district, Hanoi, Vietnam, Email: nhthach@math.ac.vn yVietnamese-German University, Le Lai street, Hoa Phu ward, Thu Dau Mot City, Binh Duong, Viet- nam, Email:huong.ttt@vgu.edu.vn and ttthuong@math.ac.vn

1arXiv:1711.10805v1 [math.CO] 29 Nov 2017

a conguration in which all the non-sink vertices cannot re. A critical conguration is a stable conguration which is \attainable" from a conguration with many chips. The detailed descriptions of the model will be given in Section 2 . Further discussions on critical congurations can be found in [ 11 In order to investigate the critical congurations, we introduce the notion ofG-strongly positive scripts. TheG-strongly positive scripts are closely related to Speer's algorithm [19] (indeed, the minimumG-strongly positive script coincides with the output of Speer's algorithm) and are equivalent to Perkinsonet al.'s \burning congurations" [15]. The key observation is that reverse-ring aG-strongly positive script \increases" the congurations. Thus, by repeatedly reverse-ring aG-strongly positive script then stabilizing, we obtain an \increasing" sequence of stable congurations. Since there are only nitely many stable congurations in each equivalence class, this process must eventually stop at a xed point, which is the critical conguration. Our contribution in this paper is threefold. First, we show that for CFG on digraphs with a global sink, among all the stable congurations of each equivalence class, the critical conguration has the maximum weight (Theorem 5 ). This has been proved in 16 ] for Eulerian digraphs, but the question remained open for digraphs with a global sink. Secondly, we give an extension of Avalet al.[2]'s result from undirected graphs to digraphs with a global sink. Namely, one cannot obtain a stable conguration from a critical one by reverse-ring a non-empty multi-subset of vertices (Theorem 6 ). Using this result, we revisit the duality between critical congurations and superstable congurations (Theorem 9 ). It should be noted that the duality is well-known in the literature: the result for Eulerian digraphs was given by Holroydet al.[11], for strongly connected digraphs by

Asadi and Backman [

1 ], for digraphs with a global sink by Perkinsonet al.[15]. There are remarkable dierences between the techniques used in those proofs. For the case of digraphs with a global sink, Perkinsonet al.used advanced algebra techniques such as the coordinate ring and Grobner bases, while Asadi and Backman's proof is a combinatorial one. Our proof is combinatorial and is independent from Asadi and Backman's proof. A notable dierence is that the attainability in their proof requires that the ring/reverse- ring sequences to be legal, while the legality restriction is not imposed in our proof. Lastly, we give an energy maximizing (resp. minimizing) characteristic for critical (resp. superstable) congurations (Theorem 8 and Corollar y 11 ). Unlike previous studies on

CFG and potential theory [

3 10 ] where energies are dened as norms, in this paper, the energies are dened as vectors and are compared using the containment order. This order is not unfamiliar in the CFG literature: its restriction on the set of accessible congurations (given an initial conguration) coincides with the accessibility order, which has been extensively investigated in connection with lattice structures [ 8 12

The manuscript is organized as follows. Section

2 giv esa brief summary of relev ant denitions and fundamental results on CFG and critical congurations. Section 3 presen ts some properties and the maximizing characterization of critical congurations. Section 4 discusses the duality and the minimizing characterization of superstable congurations. 2

2 Preliminaries

Unless stated otherwise, the vectors in this paper are row vectors. Letabe a vector in Z n. We denote byaithei-th component ofa. We say that a vector is non-negative (resp. positive) if all of its components are non-negative (resp. positive). The zero vector is denoted by 0

00 and the all-one vector by 111.

Thesupportofais dened by supp(a) =fijai6= 0g. Theweightofaisw(a) =Pn i=1ai. For a matrixM, letMidenote thei-th row vector ofMandMijthe entry at rowi and columnjofM. Thecontainment orderonZnis dened by:ab()aibifor alli= 1;2;;n. Let us now give some basic notions of chip-ring games on digraphs with a global sink. LetG= (V;E) be a directed multigraph without loops, withn+ 1 vertices,i.e. V=f1;2;;n+ 1g. Theout-going degree(resp.in-going degree) of a vertexiis denoted byd+i(resp.di). The number of edges going fromitojis denoted byei;j. Asource component(resp.sink component) ofGis a strongly connected component without in-going (resp. out-going) edge from other strongly connected components. A vertexsofVis asinkiffsgis a sink component. It is aglobal sinkif it is a sink and for every other vertexi, there exists a directed path fromitos. Note that a global sink is unique if it exists. In the rest of the paper, we suppose thatGhas a global sink at the vertexn+ 1. The graphGcan be represented by itsLaplacian matrixe2Z(n+1)(n+1)whose entries are dened as follows: e ij=( d+iifi=j ; ei;jifi6=j : Thereduced Laplacian matrix is the matrix obtained frome by removing the row and the column corresponding to the sink. The Laplacian and reduced Laplacian matrices play an important role in the study of combinatorial properties of graphs and of chip-ring games on graphs (dened hereafter) as well, see [ 6 7 ] and the references therein. We recall here two useful properties for the Laplacian and the reduced Laplacian of digraphs with a global sink. i)

The k ernelof

e is spanned by a non-negative vectorvsuch thatvn+1>0. Conse- quently, the rank ofe isn. ii) The matrix is non-singular. Moreo ver,all the en triesof

1are non-negative.

The rst property is a particular case of [

6 , Proposition 3.1]. The non-singularity is a corollary of the rst property. The non-negativity of

1is a property of non-singular

M-matrix (see, for instance, [

17 18 Achip-ring game(CFG) onG, denoted by CFG(G), is a discrete dynamical system in which: 3 -A chip conguration(congurationfor short) is a vector inZnwhose coordinates represent the numbers of chips at non-sink vertices

1. We will use bold letters such

asaaato denote conguration vectors. The transition so ccuraccording to the ring rule, dened as follows. A vertex is activeif it has at least as many chips as its out-going degree. An active vertex can reby sending one chip along each of its out-going edge to its neighbors. That is, if b bbis the conguration obtained fromaaaby ring an active vertexi, we writeaaai!bbb, then: b j=( a id+iifj=i; a j+ei;jotherwise, or equivalently: b bb=aaai: A (unconstrained)ring sequenceis a sequence of non-sink vertices (s1;s2;;sk) in V. The ring sequence (s1;s2;;sk) is calledlegalfromaaaif there exists a sequence of congurationsaaa=aaa0;aaa1;;aaaksuch thataaar1s r!aaarfor all 1rkandsris active in a aar1. Thering scriptof a legal ring sequence (s1;s2;;sk) is a vector2Nn, where iis the number of occurrences of the vertexiin the sequence (s1;s2;;sk). The ring script provides a direct way to compute the result of a ring sequence: ifbbbis obtained fromaaaby ring sequentiallys1;s2;;skandis the corresponding ring script, then b bb=aaa:(1) When referring to vectors inNnwithout mentioning a ring sequence, we will use the termn-scripts, or simplyscripts. We say that two congurationsaaaandbbbarelinearly equivalent, denoted byaaabbb, if there exists a vector2Znverifying (1). The linear equivalence is an equivalent relation onZn. The quotient groupZn=h1;:::;niis called theSandpile groupofGand is denoted bySP(G). When the context is clear, we refer to elements ofSP(G) simply as equivalent classes. Note thataaabbbdoes not imply thatbbbcan be obtained fromaaaby a legal ring sequence. In fact, even ifbbb=aaa for some non-negative, it is not always the case that there exists a legal ring sequence leading fromaaatobbb. A conguration is said to bestableif it does not have any active vertex. It is known that for each CFG with a global sink and for any non-negative congurationaaa, there exists a unique stable conguration, denoted byaaa, which can be obtained fromaaaby a legal ring sequence. A process of ring fromaaatoaaais called astabilizationofaaa. Note that there may be many legal ring sequences fromaaatoaaa, but they all have the same ring script. In fact, they are the longest legal ring sequences fromaaa. It is straightforward that ifaaa andbbbare non-negative congurations, then (aaa+bbb)= (aaa+bbb)= (aaa+bbb):1 Typically, the congurations must be non-negative. In this paper, we allow the coordinates of a conguration to be negative. 4 Moreover, ifbbbis obtained fromaaaby a legal ring sequence with ring script, then (aaa)=bbb:

We refer the interested reader to [

7 11 12 ] for more details on these results. We end this section with some important properties of critical congurations, also known as recurrent congurations. There are several denitions of critical congurations in the literature. In [ 11 ], it is shown that all those denitions are equivalent for CFG on a digraph with a global sink. We recall here the denition that we consider most useful for our purposes in this paper. Letcccmax= (d+11;d+21;;d+n1) be the maximum stable conguration by the containment order.

Denition 1(Critical conguration).

A non-negative congurationaaais critical if and only if for any congurationbbb, there exists a non-negative congurationcccsuch thataaa= (bbb+ccc). The following lemma presents some known properties of critical congurations. Lemma 1([11]).Consider a CFG on a graphGwith a global sink. i) Each e quivalentclass of SP(G)has exactly one critical conguration. ii) If aaais critical,bbbis stable, andbbbaaa, thenbbbis critical. iii) A non-ne gativec ongurationaaaiscriticalif it is stable and there exists a non-negative congurationcccsuch thataaa= (cccmax+ccc). It is dicult to decide if a conguration is critical or not using the above denitions. However, there exist ecient algorithms to recognize critical congurations, for instance Dhar'sburning algorithmfor undirected graphs [9] and Speer'sscript algorithmfor con- nected digraphs [ 19 ]. In the next section, we give a maximizing characterization for the critical congurations on their equivalent classes.

3 Critical congurations as energy vector maximizers

In this section, we prove that we never reach a stable conguration from a critical one by reverse-ring unconstrainedly any non-empty multi-subsets of vertices (Theorem 6 ). This is an analogue of Avalet al.'s result [2] in the case of digraphs with a global sink. Then, by associating each conguration with an energy vector, we will show that among stable congurations in a same equivalence class, the critical conguration is the unique one with the greatest energy vector by the containment order (Theorem 8 ). An armative answer for a question in [ 16 ] about the maximum weight of critical congurations is also given usingG-strongly positive scripts. Before presenting these results, we rst introduce the concepts ofG-positive scripts andG-strongly positive scripts. 5 Denition 2(G-positive andG-strongly positive scripts).

Letbe ann-script. We say that:

i)isG-positiveif000; ii)isG-strongly positiveif it isG-positive andsupp() intersects each source com- ponent ofG.

Remarks:

In case that Gn fn+ 1gis strongly connected, the concepts ofG-positiveness and

G-strong positiveness coincide.

A G-strongly positive script isG-positive but the converse is not true. For instance, consider the graph in Figure 1 . The scripts (1;2;4) and (0;0;1) both areG-positive but the former isG-strongly positive while the latter is not. -G-positive andG-strongly positive scripts always exist. Indeed, since the entries of

1are positive rational numbers, one can nd a positive integer vectorusuch

thatu1is also a positive integer vector. Then=u1is aG-strongly positive script. Let be aG-strongly positive script. The support of may not intersect all strongly connected components ofG. For example, consider the graph in Figure1 . The script= (1;2;3) isG-strongly positive and ()(v3) = 0.v 1v 2v

3s63112

Figure 1: A graph with global sinks

The following lemma is a crucial result which shows that for stable congurations, legal ring consumes less time than reverse ring. Lemma 2.Let= (1;:::;n)be ann-script and letaaabe a stable conguration of CFG(G)such thataaa+is non-negative. Letbe the ring script in the stabilizing process ofaaa+. Then. Proof.Letbbb=aaa+. Sinceaaais stable, we have, for alli= 1;2:::;n:

0ai=biiii+X

j6=i jjiCombining this with the fact that ij0 for allj6=iand (2), we have the following evaluation for the number of chips at vertexiafter the ring ofst0: b it0tiiX j6=i t0jjibi(i+ 1)iiX j6=i jji<0;

which contradicts the legality ofs.Note that the proof of Lemma2 do esnot require aaa+ to be non-negative. We keep

this hypothesis, however, for ease of exposition and in fact, it does not aect our other proofs. The next lemma states that reverse-ring aG-positive script followed by the stabiliza- tion does not decrease the weight of a non-negative conguration. Lemma 3.Letbe aG-positive script and letaaa;bbbbe stable congurations such that b bb= (aaa+). Thenw(bbb)w(aaa). Proof.Letbe the ring script of the stabilization ofaaa+. We havebbb=aaa+, and: w(bbb) =bbb111 =aaa111 + ()111 =w(aaa) +X i:(i;n+1)2E(ii)ei;n+1:

By Lemma

2

,iifor alli. Hence,w(bbb)w(aaa).The next proposition shows the recurring nature of critical congurations. This result

was mentioned in [ 15 , Theorem 2.27], but we have not found a proof in the literature. We restate it here with a complete proof. Proposition 4.Letaaabe a stable conguration and letbe aG-strongly positive script. Thenaaais critical if and only if(aaa+)=aaa. Moreover, ifaaais critical then the ring script in the stabilizing process ofaaa+is. Proof.We rst prove that (cccmax+)=cccmax. Since0, (cccmax+)is stable, hence (cccmax+)cccmax. On the other hand, by Lemma3 ,w(cccmax+)w(cccmax).

Hence, (cccmax+)=cccmax.

7 Now letaaabe an arbitrary critical conguration. By Lemma1 , there existsccc0 suchquotesdbs_dbs44.pdfusesText_44

[PDF] comment évaluer par compétences en français

[PDF] les conséquences du développement du chemin de fer au xixème siècle

[PDF] conséquences de l'industrialisation sur le paysage

[PDF] l'industrialisation et ses conséquences

[PDF] industrialisation 4eme

[PDF] grille d'observation comportement agressif

[PDF] evaluation comportement professionnel

[PDF] comment noter un film

[PDF] epreuve dnl physique bac

[PDF] bareme ece chimie

[PDF] grille notation epi

[PDF] grille d'évaluation epi

[PDF] fiche epi élèves

[PDF] epi petit déjeuner

[PDF] evaluation epi collège