P Mark Kayll
email: mark.kayll@umontana.edu

Dave Perkins
email: dperkins@luzerne.edu

A chip-firing variation and a new proof of Cayley's Formula

Keywords: chip-firing, burn-off games, relaxed legal configurations, Cayley's Formula

We introduce a variation of chip-firing games on connected graphs. These 'burn-off' games incorporate the loss of energy that may occur in the physical processes that classical chip-firing games have been used to model. For a graph G = (V, E), a configuration of 'chips' on its nodes is a mapping C : V → N. We study the configurations that can arise in the course of iterating a burn-off game. After characterizing the 'relaxed legal' configurations for general graphs, we enumerate the 'legal' ones for complete graphs Kn. The number of relaxed legal configurations on Kn coincides with the number tn+1 of spanning trees of Kn+1. Since our algorithmic, bijective proof of this fact does not invoke Cayley's Formula for tn, our main results yield secondarily a new proof of this formula.

Introduction

Chip-firing games on graphs by now enjoy a rich literature. This is due not only to their surprising array of mathematical connections but also to their utility in modeling certain kinds of physical systems. For the former, we find ties, e.g., to discrepancy theory [START_REF] Spencer | Balancing vectors in the max norm[END_REF], the Tutte polynomial [START_REF] Merino | Chip firing and the Tutte polynomial[END_REF], critical groups of graphs [START_REF] Biggs | Chip-firing and the critical group of a graph[END_REF], G-parking functions [START_REF] Benson | G-parking functions, acyclic orientations and spanning trees[END_REF], and stochastic processes [START_REF] Engel | The probabilistic abacus[END_REF]. For the latter, these games connect to earthquakes [START_REF] Bak | Earthquakes as a self-organized critical phenomenon[END_REF], sandpiles [START_REF] Dhar | Algebraic aspects of abelian sandpile models[END_REF], traffic [START_REF] Nagel | Emergent traffic jams[END_REF], and the brain [START_REF] Stassinopoulos | Democratic reinforcement: A principle for brain function[END_REF].

This article continues the published account of [START_REF] Perkins | Investigations of a chip-firing game[END_REF]-initiated in [START_REF] Kayll | Combinatorial proof of an Abel-type identity[END_REF]-where we study a variant of chip-firing in which all games have finite length. These 'burn-off' games incorporate the loss of energy that may occur in the physical processes that classical chip-firing games have been used to model. Whereas, classically, when a node v 'fires', it sends one chip to each of its neighbors, our game modifies this action by additionally eliminating one chip at v; see Section 1.1 for a precise definition of these games.

It's worth noting the analogy between burn-off games and graph pebbling, sometimes used in modeling the movement of expendable resources. Here, 'pebbles' are placed on the nodes of a graph, then moved around subject to the condition that if v contains (at least) two pebbles, then one of them may be moved to a neighbor of v at a cost of permanently removing another from v; see [START_REF] Hurlbert | A survey of graph pebbling[END_REF] for an early pebbling survey and [START_REF] Hurlbert | The graph pebbling page[END_REF] for a dynamic record of related references. Though we don't make use of the pebbling/burn-off game connection, the recent explosion in pebbling research suggests that our chip-firing approach could also prove to be fruitful.

Björner et al. [START_REF] Björner | Chip-firing games on graphs[END_REF] are generally credited with initiating the study of chip-firing games on general (connected, undirected) graphs, although a subset of these authors in [START_REF] Björner | Chip-firing games on directed graphs[END_REF] points to antecedents in [START_REF] Engel | The probabilistic abacus[END_REF] and [START_REF] Spencer | Balancing vectors in the max norm[END_REF]. It's historically interesting that an early result for general graphs, in [START_REF] Tardos | Polynomial bound for a chip firing game on graphs[END_REF], predates the purported initiator [START_REF] Björner | Chip-firing games on graphs[END_REF]. We offer some of this as evidence that a thorough literature review is beyond our scope and instead point the reader to [START_REF] Merino | The chip-firing game[END_REF] for a chip-firing survey, to [START_REF] Godsil | Algebraic graph theory[END_REF] for a textbook account of the algebraic aspects of chip firing, and to [START_REF] Benson | G-parking functions, acyclic orientations and spanning trees[END_REF] for a few more recent related citations.

This paper is organized as follows. Section 2 presents our results for general graphs, while Section 3 focuses on complete graphs. After characterizing the 'relaxed legal' chip configurations ( §2.1), we give an algorithm to check a configuration for 'legality' ( §2.2) and then prove that the set of 'legal' configurations is up-closed in the poset of all configurations on a fixed graph ( §2.3). In §3.1, we enumerate the 'legal' chip configurations for complete graphs K n . The number of relaxed legal configurations on K n coincides with the number t n+1 of spanning trees of K n+1 . Since our algorithmic, bijective proof of this fact ( §3.2) does not invoke Cayley's Formula for t n , our results in Section 3 yield a new proof of this formula.

We are not the first authors to observe a connection between chip-firing games and spanning tree enumeration. Indeed, Biggs and Winkler [START_REF] Biggs | Chip-firing and the chromatic polynomial[END_REF] present bijections between their set of 'critical' configurations and the set of trees spanning their underlying graph. Benson et al. [START_REF] Benson | G-parking functions, acyclic orientations and spanning trees[END_REF], who "present the[ir] article in an expository self-contained form", provide somewhat of a related mini-survey, including a citation to [START_REF] Biggs | Chip-firing and the chromatic polynomial[END_REF]. (Their scope also includes connections with parking functions and sandpile models.) Even more recently, Baker and Shokrieh [START_REF] Baker | Chip-firing games, potential theory on graphs, and spanning trees[END_REF] further explore these latter connections and obtain a bijective proof of the Matrix-Tree Theorem. We ourselves, in [START_REF] Kayll | Combinatorial proof of an Abel-type identity[END_REF], have even touched on the chip-firing/spanning tree connection. Nevertheless, since burn-off games comprise a non-trivial variation of chip-firing, it seems worthwhile to illuminate this connection in the new context.

Notation and terminology

We generally follow 'standard' graph theory conventions and make attempts to produce a self-contained treatment of our results. For any basics we may have omitted, we point the reader to [START_REF] Bondy | Graph theory[END_REF].

Description of the game

The 'game board' is a connected graph G = (V, E). For each node v ∈ V , we begin with a nonnegative number C(v) of chips on v; the function

C : V → N is a configuration. Each v ∈ V has an associated critical number k v ≥ deg G (v). Every node v for which C(v) ≥ k v is
live and may be 'fired'. Formally, when v fires, C is modified to a configuration C such that

C (u) =    C(v) -deg G (v) if u = v, C(u) + 1 if uv ∈ E(G), C(u) if v = u ∼ v; (1)
loosely speaking, v sends a chip to each of its neighbors. A configuration in which no node is live is relaxed. Starting with a configuration C on G, a chip-firing game is played as follows. If there exists a live node, fire it; this constitutes a turn of the game. The game proceeds in turns, wherein live nodes are successively chosen and fired. If, at any point in this process, no node is live, the game ends, its length being the number of turns taken starting from C until the end. If C is relaxed, the game has length zero; otherwise, the process of passing from C through a C and eventually to a relaxed configuration on G is relaxing C. Björner et al. [START_REF] Björner | Chip-firing games on graphs[END_REF] took each k v to be the minimum natural value deg G (v). They observed that some chip-firing games may be of infinite length. For example, if the total number of chips on G exceeds twice the number of edges, then, by the pigeonhole principle, one can always find at least one live node. This paper also established, among other results, that if the total number of chips on G is less than |E|, then every chip-firing game on G is of finite length.

Another way to ensure finite game lengths is to decrease the total number of chips at each turn. A 'burn-off game' differs from the chip-firing game of [START_REF] Björner | Chip-firing games on graphs[END_REF] in two ways: first, we take each k v , for v ∈ V , to be deg G (v) + 1; second, we modify the firing rule [START_REF] Bak | Earthquakes as a self-organized critical phenomenon[END_REF] to

C (u) =    C(v) -deg G (v) -1 if u = v, C(u) + 1 if uv ∈ E(G), C(u) if v = u ∼ v; (2)
notice that when v is fired, one of its chips effectively vanishes. A burn-off game is a chip-firing game with the adjusted critical numbers and following the modified firing rule [START_REF] Baker | Chip-firing games, potential theory on graphs, and spanning trees[END_REF]. The game just defined is equivalent to the 'dollar game' of Biggs [START_REF] Biggs | Chip-firing and the critical group of a graph[END_REF] in the particular case when his 'government' node is adjacent to every other node in the underlying graph; see also [START_REF] Biggs | Chip-firing and the chromatic polynomial[END_REF]. In our burn-off games, we call a node v supercritical when C(v) takes a value larger than deg G (v).

During a chip-firing or burn-off game, chips from the neighbors of a node v may cause v to become supercritical. If, during one of these games, several nodes simultaneously become live in this fashion, one may wonder how to decide which node to fire next. The paper [START_REF] Björner | Chip-firing games on graphs[END_REF] established that for the chip-firing game described above, this decision has no bearing on the game length or the final chip configuration. Using a similar approach, this paper's second author showed in [START_REF] Perkins | Investigations of a chip-firing game[END_REF] that the analogous result for burn-off games also holds.

Reverse-firing and legal configurations

Our primary purpose is to study the configurations that can arise in the course of iterating a burn-off game, i.e., incrementing C at a chosen node, relaxing the resulting configuration, and repeating these two steps indefinitely. Of course, the set of configurations that arise in this way depends on the initial configuration. Though it may seem natural to begin with the empty configuration, C ≡ 0, this configuration will never recur during a burn-off game sequence because each firing event redistributes chips to the neighbors of the firing node.

Instead, we seek to begin with a configuration typical of those that will be encountered in a long sequence of burn-off games. Here, we follow [START_REF] Bak | Earthquakes as a self-organized critical phenomenon[END_REF], wherein the authors investigated an earthquake model based on chip-firing on a grid.

We define a configuration to be supercritical if every node is supercritical. In the spirit of [START_REF] Bak | Earthquakes as a self-organized critical phenomenon[END_REF], we shall focus on the configurations that can result from relaxing a supercritical configuration. To understand these, it is instructive to consider what happens when a burn-off game is played in reverse.

A reverse-firing game is defined so as to undo the firing rule of the chip-firing game under consideration. Thus, for burn-off games, considering (2), we see that to reverse-fire a node v (each of whose neighbors u of necessity satisfies C (u) ≥ 1) means to modify C to a configuration C such that

C(u) =    C (v) + deg G (v) + 1 if u = v, C (u) -1 if uv ∈ E(G), C (u) if v = u ∼ v. (3)
Informally, starting from C , when a node v reverse-fires, it pulls one chip from each of its neighbors and one out of thin air. Now a configuration C is legal if there exists a reverse-firing sequence starting with C and ending with a supercritical configuration. A legal configuration containing no live nodes is a relaxed legal configuration. Notice that the empty configuration is relaxed but not legal, while the configuration with

C(v) = deg G (v) + 1, for each v ∈ V ,
is legal but not relaxed. We leave it as an (easy) exercise to construct a configuration that is neither legal nor relaxed.

2 Results for general graphs

Characterizing relaxed legal configurations

Our first result characterizes the relaxed legal configurations on general (connected simple) graphs. Its statement uses N G to denote the 'earlier neighbor set'; i.e., given an ordering

(w 1 , w 2 . . . , w n ) of V , we define N G (w i ) := {w h ∈ V : w h w i ∈ E(G) and h < i}. Proposition 2.1 A relaxed configuration C : V → N is legal if and only if it is possible to relabel V as w 1 , w 2 , . . . , w n so that C(w i ) ≥ |N G (w i )| for 1 ≤ i ≤ n. (4)
Proof: Suppose that we have a relaxed legal configuration C. Since C is legal, it can be reverse-fired into a configuration where all nodes are supercritical. Further, since C is relaxed, no node is supercritical. Thus, in any reverse-firing sequence that certifies the legality of C, all nodes must reverse-fire (this being the only way for a node to gain chips during a reverse-firing game). Consider such a reverse-firing sequence.

Listing only the first time each node reverse-fires during the game, suppose that they are reverse-fired in the order w 1 , w 2 , . . . , w n . Any given node w j reverse-fires only after each node w 1 , w 2 , . . . , w j-1 reverse-fires at least once. Each of these nodes which is a neighbor of w j takes a chip from w j when it reverse-fires. Thus, we must have C(w j ) ≥ |N G (w j )|, and (4) follows since j was arbitrary.

To establish the converse, suppose that it is possible to relabel the nodes w 1 , w 2 , . . . , w n so that (4) holds. We claim that reverse-firing the nodes in increasing subscript order results in each node increasing its chip-count by one.

Consider a node w j for some j with 1 ≤ j ≤ n, and define s := |N G (w j )|. Each of the s nodes in N G (w j ) reverse-fires before w j does, and each reverse-firing will pull one chip from w j . This leaves C(w j ) -s ≥ 0 chips on w j . When w j reverse-fires, it pulls a chip from each of its deg(w j ) neighbors and receives one extra chip for the reverse burn-off. Finally, the nodes w j+1 , . . . , w n reverse-fire, and each neighbor of w j in this set (say there are of these) pulls a chip from w j . Therefore, after each node has been reverse-fired once, the number of chips on w j is decreased by s + = deg(w j ) and increased by deg(w j ) + 1 (while never becoming negative), for a net increase of one, as claimed.

Notice that reverse-firing each node once, as described in the preceding paragraph, preserves (4). Thus, this process may be repeated until all nodes become supercritical. That is, if t := max v∈V {deg(v) -by Algorithm 2.2, it must contain at least as many chips as it has neighbors in G * . Thus, the relabeling u n , u n-1 , . . . , u 1 that gives the deletion order also suffices to show that (4) holds for C. Therefore, C is legal. 2

The poset of legal configurations

In the next section, we shall find it useful to consider the set B of all configurations on a fixed graph G as a poset (B, ) whose ordering relates to the numbers of chips on the nodes of G as follows: for P, Q ∈ B and ≤ the usual (total) ordering on N, let

P Q if and only if each v ∈ V (G) satisfies P (v) ≤ Q(v).
Proposition 2.5 If P is a legal configuration, then any Q with P Q is also legal.

Proof: We clearly need only consider those configurations Q with P ≺ Q (i.e., P Q but P = Q). Such a Q has at least as many chips on any given node v as does P , and since P ≺ Q, there exists a node x with P (x) < Q(x). Starting from the configuration P , add one chip to x to create a new configuration P .

Since P is legal, there exists a reverse-firing sequence that results in a supercritical configuration. 'Freeze' the new chip on x, and carry out the same reverse-firing sequence starting with P . The frozen chip will not affect the reverse-firing game, and once P is reverse-fired to a supercritical configuration, the chip may be 'thawed'. The resulting supercritical configuration shows that P is legal.

If P = Q, the assertion is proved; if not, the argument above can be repeated with P in the role of P . 2

Results for complete graphs

After specializing Proposition 2.1 to complete graphs, we enumerate certain legal configurations on these graphs. Then we present a pair of algorithms that give a one-to-one correspondence between relaxed legal configurations on K n and spanning trees of K n+1 . These algorithms provide our new proof of Cayley's Formula (see [START_REF] Cayley | A theorem on trees[END_REF] or, e.g., [START_REF] Bondy | Graph theory[END_REF]).

Enumerating legal configurations

Lemma 3.1 A relaxed configuration C : V → N on K n is legal if and only if it is possible to relabel the nodes w 1 , w 2 , . . . , w n so that

C(w i ) ≥ i -1 for 1 ≤ i ≤ n. (5)
Proof: We simply observe that condition ( 5) is equivalent to condition (4) because in a complete graph, each

w i satisfies |N Kn (w i )| = i -1. 2
The following formulation of Lemma 3.1 is needed in Section 3.2.

Corollary 3.2 A relaxed configuration C : V → N on K n is legal if and only if for each ∈ {1, 2, . . . , n}, at least nnodes contain at least chips.

Now we develop a formula for L(K n ), the number of relaxed legal configurations C on K n . We first count the legal (but not necessarily relaxed) configurations; here our determination includes a parameter to bound the maximum value of C(v) for v ∈ V := V (K n ). For n ≥ 1 and m ≥ n -1, let L n,m be the number of legal configurations satisfying C(v) ≤ m for each v ∈ V . For convenience, we also define L 0,m := 1 for all m ≥ 0. The proof of the next result makes implicit use of Proposition 2.5. Theorem 3.3 For all n ≥ 1 and m ≥ n -1, we have

L n,m = (m -n + 2)(m + 2) (n-1) . (6)
Proof: We proceed by induction on n and m. Since L 0,m := 1, this satisfies [START_REF] Björner | Chip-firing games on directed graphs[END_REF]. For each m ≥ 0, we include in our base case L 1,m , which counts the number of legal configurations on K 1 . By ( 5), the single node must contain at least zero chips. Thus, the number of chips occupying this node lies in the set {0, 1, . . . , m}; so L 1,m = m + 1, which satisfies [START_REF] Björner | Chip-firing games on directed graphs[END_REF]. Finally, we observe that for n ≥ 2, the symbol L n,n-2 enumerates the legal configurations in which all n nodes contain at most n -2 chips; since (5) requires C(w n ) ≥ n -1, we have L n,n-2 = 0 for all n ≥ 2. This satisfies ( 6), and we include it in our base case. Now fix n ≥ 2 and m ≥ n -1, and assume that ( 6) is valid for each L n-k,m-1 with k ∈ {0, 1, . . . , n}. To determine L n,m , we let k ∈ {0, 1, . . . , n} count the number of nodes containing exactly m chips; there are n k ways to choose these k nodes. Consider the configuration on the remaining n -k nodes of K n . Focusing on these nodes, we know from Lemma 2.3 that C| V (K n-k ) must be legal on K n-k , with at most m -1 chips on each node. Since the number of such configurations is L n-k,m-1 , we have

L n,m = n k=0 n k L n-k,m-1 .
Now we apply our inductive hypothesis to simplify the sum:

L n,m = n k=0 n k ((m -1) -(n -k) + 2) ((m -1) + 2) (n-k)-1 = n k=0 n k k n [(m + 1) -(m -n + 1)] + (m -n + 1) (m + 1) n-k-1 = n k=0 k n n k (m + 1) + n -k n n k (m -n + 1) (m + 1) n-k-1 = n k=1 n -1 k -1 (m + 1) n-k + n-1 k=0 n -1 k (m -n + 1)(m + 1) n-k-1 = (m -n + 2) n-1 k=0 n -1 k (m + 1) (n-1)-k = (m -n + 2)((m + 1) + 1) n-1 ;
induction gives the result. 2

Since L(K n ) = L n,n-1 , we obtain the immediate

Corollary 3.4 L(K n ) = (n + 1) n-1 .
This last observation led us to the connection between burn-off games on complete graphs and the enumeration of spanning trees therein.

Connections with spanning trees

A direct proof that the number of relaxed legal configurations on K n coincides with the number of spanning trees of K n+1 , without resort to Cayley's Formula, will yield a proof of the latter.

Theorem 3.5 The number of relaxed legal configurations on K n equals the number of spanning trees of K n+1 .

Proof: We establish algorithmically injections between the set R of relaxed legal configurations on K n and the set S of spanning trees of K n+1 . Define A : R → S via Algorithm 3.6 and B : S → R via Algorithm 3.7 (both below). Regarding these algorithms, score refers to a numeric label assigned to a node. Define F : V (K n ) → N as the function that makes this assignment.

Our first algorithm injectively maps R to S.

Algorithm 3.6

INPUT: a complete graph K n and relaxed legal configuration

C : V (K n ) → N OUTPUT: a spanning tree of K n+1 (1) Let V (K n ) = {v 1 , v 2 , . . . , v n }.
(2) Delete all edges from K n and introduce a new node v 0 .

(

) Let M 0 = (v 0 ) and M 0 = {v 0 }. (4) Let F (v 0 ) = n -1. 3
(5) Let Q 0 = 0 and i = 0.

Until all v k have been included in some sequence M i , do the following:

(6) i ← i + 1. (7) Let Q i = Q i-1 + |M i-1 |. ( 8
) Let M i = (v i1 , v i2 , .
. . , v it ), for some t ≥ 1, be the sequence (in increasing subscript order) of all nodes v for which

C(v) = F (u) for some u ∈ M i-1 . Let M i = {x : x is an entry of M i }. (9) Add an edge from each v k in M i to the node u ∈ M i-1 for which C(v k ) = F (u). ( 10
) For each j = 1, 2, . . . , |M i |, let F (v ij ) = n -Q i -j.
The purpose of the variables Q i is to record the number of nodes that have been included in an earlier M j . In fact,

Q i = i-1 j=0 M j .
Thus, in step [START_REF] Dhar | Algebraic aspects of abelian sandpile models[END_REF], each score is given to exactly one node. Therefore, "the node" selected in step ( 9) is indeed unique.

Proof that A is well-defined: Algorithm 3.6 will fail if, during any iteration, M i is empty, because no further edges can then be added in step [START_REF] Cayley | A theorem on trees[END_REF]. We demonstrate below that no M i is ever empty, but assume for now that this is true. Step (9) adds an edge from each v k ∈ M i to a node that is already part of a single growing component of the subgraph of K n+1 being constructed. The algorithm continues until all nodes of K n+1 are members of some M i , so all nodes of K n+1 are eventually connected to the growing component. Note also that exactly n edges are created by step [START_REF] Cayley | A theorem on trees[END_REF], one for each node except v 0 . A spanning connected subgraph (of an (n + 1)-node graph G) with n edges is necessarily a spanning tree of G; thus, the algorithm certainly constructs a spanning tree of K n+1 .

It remains to prove that no M i is empty. We proceed by induction. It is clear in step (3) that M 0 is not empty; suppose that M i-1 is not empty for some fixed i > 0. (By definition of M i-1 , it is clear that M i-2 is also not empty.) As Algorithm 3.6 proceeds, the scores assigned to the nodes in step [START_REF] Dhar | Algebraic aspects of abelian sandpile models[END_REF] descend from n -1. We must show that at least one value of C(v k ), for 1 ≤ k ≤ n, is large enough to equal the score of one of the nodes in M i-1 . This will guarantee that M i contains at least one element.

When, in step ( 8), the nodes are checked to see if they will be members of M i , the algorithm inspects the scores assigned to the nodes in M i-1 (our induction hypothesis ensures that there are nodes in M i-1 to inspect). These scores were assigned (during the preceding iteration) in the following order:

n -Q i-1 -1, n -Q i-1 -2, . . . , n -Q i-1 -|M i-1 | = n -Q i .
Thus, the lowest score assigned to a node of

M i-1 is n -Q i .
Since C is a legal configuration on K n , we know that for each ∈ {1, 2, . . . , n}, at least nnodes contain at least chips (see Corollary 3.2). Substituting n -Q i for , we see that our legal configuration C is such that at least Q i nodes contain at least n -Q i chips.

Since Q i -1 nodes have been assigned scores (we subtract 1 because v 0 ∈ V (K n )), there is at least one unassigned node v k containing at least n -Q i chips (i.e., C(v k ) ≥ n -Q i ); this number is at least as big as the lowest score found in M i-1 . We also know that C(v k ) is one of the scores assigned to a node in M i-1 , for if C(v k ) exceeded all of those scores, then v k would have already been assigned to an earlier sequence. It follows by induction that no M i is empty and, by our earlier remarks, that A is well-defined.

2

Proof that A is an injection: Let C : V (K n ) → N and C * : V (K n ) → N be two distinct relaxed legal configurations on K n . Let A(C) = T and A(C * ) = T * . We will prove that A is an injection by showing that T and T * must be distinct.

As C = C * , Algorithm 3.6 must encounter C(v i ) = C * (v i ) for some i ∈ {1, 2, . . . , n}. Choose i to index the earliest such encounter; since Algorithm 3.6 assigns the scores in order of decreasing value, i is the index witnessing max{max{C(v j ), C * (v j )} : 1 ≤ j ≤ n and C(v j ) = C * (v j )}. Without loss of generality, we may suppose that C * (v i ) > C(v i ).

We will show that v i has different neighbors in T and T * , so that T = T * . Suppose that as Algorithm 3.6 operates on C, the sequences constructed in step (8) are M 1 , M 2 , . . . , M j , and suppose that as it operates on C * , the corresponding sequences are M * 1 , M * 2 , . . . , M * k . Now suppose that v i ∈ M s (for some s ∈ {1, 2, . . . , j}) and v i ∈ M * t (for some t ∈ {1, 2, . . . , k}). We distinguish two cases. Since C(v i ) and C * (v i ) are the earliest unequal entries considered, we have M s-1 = M * t-1 . Since C(v i ) = C * (v i ), the node v i must be assigned different neighbors, say x, y, from among the nodes of M s-1 and M * t-1 , respectively. Then the edge {v i , x} belongs to E(T ) E(T * ), implying that T = T * . Case 2: s = t. Algorithm 3.6 adds an edge between v i and some node w * in M * t-1 . Since C(v i ) and C * (v i ) are the earliest unequal entries encountered, we know that M t-1 = M * t-1 . But we have assumed that C * (v i ) > C(v i ), so t < s; this implies that M s-1 = M * t-1 . Thus, the edge {v i , w * } belongs to E(T * ) E(T ), again implying that T = T * . 2

Our second algorithm injectively maps S to R.

Algorithm 3.7

INPUT: a spanning tree T of K n+1

OUTPUT: a relaxed legal configuration C :

V (K n ) → N on K n (1) Fix a node v 0 in K n+1 . (2) Label the remaining nodes v 1 , v 2 , . . . , v n . ( 3
) Let N 0 = (v 0 ), N 0 = {v 0 }, and i = 0.
Until all v k have been included in some sequence N i , repeat steps ( 4) and ( 5):

(4) i ← i + 1.

(5) Define N i = (v i1 , v i2 , . . . , v it ), for t ≥ 1, as the sequence (in increasing subscript order) of all unassigned nodes that are neighbors in T of a node in N i-1 . Let N i = {x : x is an entry of N i }.

(6) Define N = (u k ) n+1 k=1 as the concatenation of all the N i 's, in their natural order. (7) For k = 1, 2, . . . , n, set F (u k ) = n -k (note that the (n + 1) st entry is not assigned a score). (8) a. For each i = 1, 2, . . . , n, the node v i is an entry of some N j , and is thus the neighbor in T of some

v k ∈ N j-1 . b. Let C(v i ) = F (v k ).
It's worth noting that in step [START_REF] Biggs | Chip-firing and the critical group of a graph[END_REF] we are performing a breadth-first search (see, e.g., [START_REF] Bondy | Graph theory[END_REF]) from v 0 to determine the N i 's.

Proof that B is well-defined: Step (7) makes it clear that C is relaxed, since the maximum assigned score is n -1. In order to show that C is legal, we demonstrate that for each ∈ {1, 2, . . . , n}, at least nnodes contain at least chips (again, see Corollary 3.2). In step [START_REF] Björner | Chip-firing games on graphs[END_REF], a node v k receives the score after (n -1)other nodes have been assigned scores. As v k has n neighbors in K n+1 , it will have n -((n -1) -) = + 1 unlabeled neighbors in T . These are the only nodes that can be assigned C-values at most F (v k ) = in step (8b). Thus, for ∈ {0, 1, . . . , n -1}, at most + 1 nodes of K n are assigned C-values at most . Complementation and Corollary 3.2 imply that C is indeed legal. 2

Proof that B is an injection: Let T and T * be two distinct spanning trees of K n+1 . Let V (K n+1 ) = {v 0 , v 1 , . . . , v n }. Let B(T ) = C and B(T * ) = C * . We will prove that B is an injection by showing that the configurations C and C * must be distinct. For v ∈ V (T ), let Γ T (v) denote the set of neighbors of v that are assigned the value F (v) in step (8b); in other words, Γ T (v) is the set of nodes adjacent to v, and one edge further from v 0 , in T . Define Γ T * (v) analogously.

Since T = T * , we infer that Γ T (v) = Γ T * (v) for some v ∈ V (K n+1 ). With N i , N * i denoting the sequences constructed by step (5) for T , T * respectively, let r := min{i : there exists v ∈ N i ∩ N * i with Γ T (v) = Γ T * (v)}. Choose any v ∈ N r ∩ N * r with Γ T (v) = Γ T * (v). Step (8b) assigns the value F (v) to all x ∈ Γ T (v) and the value F * (v) to all y ∈ Γ T * (v). By the choice of r (as a minimum), we have F (v) = F * (v); by step [START_REF] Björner | Chip-firing games on graphs[END_REF], we know that this score is assigned exclusively to v. To receive this score in step (8b) (as a chip count), a node must be a member of either Γ T (v) or Γ T * (v). Since Γ T (v) = Γ T * (v), we have C = C * ; thus, B is injective.

2

Now that we have demonstrated injections between the set R of relaxed legal configurations on K n and the set S of spanning trees of K n+1 , we have |R| = |S|, which finally completes the proof of Theorem 3.5.

2

As noted at the start of this section, our results yield a new proof of Cayley's Formula, for combining Theorem 3.5 with Corollary 3.4 gives |S| = |R| = L(K n ) = (n + 1) n-1 . We view this as somewhat of a curiosity because it is certainly not the most efficient published proof of this identity (see, e.g., [START_REF] Moon | Various proofs of Cayley's formula for counting trees[END_REF]). Nevertheless, it ties our results on burn-off games to spanning tree enumeration much as conventional chip-firing games have been likewise linked.

We intend to present further results on burn-off games from [START_REF] Perkins | Investigations of a chip-firing game[END_REF] in a future paper, for which the present article will form a foundation.

Case 1 :

 1 s = t.

Acknowledgements

Our thanks go to the referee for the careful read, for sharing the reference [4], and especially for pointing out the connection between our burn-off game and the Biggs dollar game.

C(v)}, then repeating the process t + 1 times will result in every node v containing at least deg(v) + 1 chips. Therefore, the original configuration was legal. 2

Checking the legality of a configuration

Given a configuration C (not necessarily relaxed) on a graph G, we may check if C is legal using the following algorithm. The proof of its efficacy leans on Proposition 2.1.

Algorithm 2.2

INPUT: a graph G = (V, E) and a chip configuration C : V → N on G

OUTPUT: an answer to the question 'Is C legal?'

(4) Delete v and all incident edges from G * to create a graph G -.

(

In the proof of Proposition 2.4, which asserts that Algorithm 2.2 works correctly, we also need the following lemma. For a configuration C : V (G) → N on G and a subgraph H of G, the notation C| V (H) as usual denotes the configuration restricted to H.

Proof: By Proposition 2.1, the legality of C on G implies that it is possible to relabel the nodes w 1 , . . . , w n so that each w i (considered in G) contains at least as many chips as it has neighbors with smaller subscripts. In H, a node w i may have fewer such neighbors, but it certainly cannot have more. Thus,

Second, we show that if Algorithm 2.2 proceeds until all nodes are deleted, then C is legal. Suppose we relabel the nodes so that the algorithm's deletion order is u n , u n-1 , . . . , u 1 . For n ≥ j ≥ 1, let G * (u j ) be the subgraph of G remaining just before the deletion of u j . For u j to be deleted from G * (u j )


Xin Zhang
email: xinzhang@mail.sdu.edu.cn

Jian-Liang Wu
email: jlwu@sdu.edu.cn

Guizhen Liu
email: gzliu@sdu.edu.cn

New Upper Bounds for the Heights of Some Light Subgraphs in 1-Planar Graphs with High Minimum Degree †

Keywords: 1-planar graphs, light graphs, height

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is shown that each 1-planar graph of minimum degree 6 contains a copy of 4-cycle with all vertices of degree at most 19. In addition, we also show that the complete graph K4 is light in the family of 1-planar graphs of minimum degree 7, with its height at most 11.

Introduction

Throughout this paper, all graphs are finite, simple and undirected. We use V (G), E(G), δ(G) and ∆(G) to denote the vertex set, the edge set, the minimum degree and the maximum degree of a graph G. Let e(G) = |E(G)| and v(G) = |V (G)|. For planar graphs, we use F (G) to denote the face set of G and let f (G) = |F (G)|. A vertex (face) of degree k is called a k-vertex (f ace) and a vertex (face) of degree at least k is called a k + -vertex (f ace). For undefined concepts we refer the reader to [START_REF] Bondy | Graph Theory with Applications[END_REF].

Let G be a family of graphs and let H be a connected graph such that each member of G contains a subgraph isomorphic to H. Denote h(H, G ) and w(H, G ) respectively to be the smallest integers with the property that each graph G ∈ G contains a subgraph K H such that max x∈V (K) {d G (x)} ≤ h(H, G ) and x∈V (K) {d G (x)} ≤ w(H, G ). These two parameters h(H, G ) and w(H, G ) are called the height and the weight of H in the family G . If they are finite, then we say H is light in G , otherwise we say H is heavy in G .

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. The notion of 1-planar was introduced by Ringel [START_REF] Ringel | Ein Sechsfarbenproblem auf der Kugel[END_REF] while studying the simultaneous vertex-face coloring of planar graphs; in the mentioned paper, he proved that each 1-planar graph is 7-colorable. Now this bound was improved to 6 (being sharp) by Borodin [START_REF] Borodin | Solution of Ringel's problems on the vertex-face coloring of plane graphs and on the coloring of 1-planar graphs[END_REF][START_REF] Borodin | A new proof of the 6 color theorem[END_REF]. Borodin et al. [START_REF] Borodin | Acyclic colouring of 1-planar graphs[END_REF] also proved that each 1-planar graph is acyclically 20-colorable. In addition, the list analogue of vertex coloring of 1-planar graphs was investigated in [START_REF] Albertson | Coloring vertices and faces of locally planar graphs[END_REF] by Albertson and Mohar. In [START_REF] Wang | Coupled choosability of plane graphs[END_REF], Wang and Lih proved that each 1-planar graph is list 7-colorable. Recently, Zhang et al. showed that each 1-planar graph G with maximum degree ∆ is ∆-edge colorable if ∆ ≥ 10 [START_REF] Zhang | On edge colorings of 1-planar graphs[END_REF], or ∆ ≥ 9 and G contains no chordal 5-cycles [START_REF] Zhang | On edge colorings of 1-planar graphs without chordal 5-cycles[END_REF], or ∆ ≥ 8 and G contains no chordal 4-cycles [START_REF] Zhang | On edge colorings of 1-planar graphs without adjacent triangles[END_REF], or ∆ ≥ 7 and G contains no 3-cycles [START_REF] Zhang | Edge coloring of triangle-free 1-planar graphs[END_REF]; it is ∆-edge choosable and (∆ + 1)-total choosable if ∆ ≥ 21 [START_REF] Zhang | List edge and list total coloring of 1-planar graphs[END_REF]; it is (∆ + 1)-edge choosable and (∆ + 2)-total choosable if ∆ ≥ 16 [START_REF] Zhang | List edge and list total coloring of 1-planar graphs[END_REF]. The generalization of the total coloring of 1-planar graphs, the so called (p, 1)-total labelling problem, is studied in [START_REF] Zhang | On (p, 1)-total labelling of 1-planar graphs[END_REF].

Although 1-planar graphs is an interesting family, it is still little explored comparing to the family of planar graphs. In general, the family of 1-planar graphs has many fundamental aspects which are different from the planar ones. It is well-known that the planarity test for a graph is polynomial. But for 1-planarity, it is extremely unlucky that its recognizing is NP-complete [START_REF] Korzhik | Minimal obstructions for 1-immersions and hardness of 1-planarrity test[END_REF]. This hardness may come from the fact that the set of 1-planar graphs is not closed under taking minors and thus the 1-planarity cannot be characterized by forbidding some minors.

On the other hand, 1-planar graphs also have some similar local structures as planar graphs. For example, the maximum possible number of edges in a 1-planar graph G is 4v(G) -8 and there are many 1-planar graphs that attain this bound [START_REF] Fabrici | The structure of 1-planar graphs[END_REF]. This implies that the maximum possible minimum degree of a 1-planar graph is 7. Note that every planar graph is 5-degenerate. So each 1-planar graph with minimum degree 6 or 7 cannot be planar. However, such 1-planar graphs may have many nice and similar properties as planar graphs. In particular, we wonder whether a 1-planar graph with minimum degree 6 or 7 has a similar behavior as a planar graph with high minimum degree concerning the local structures.

In the Fifth Workshop of "Graph Embeddings and Maps on Surfaces" held at Tále in the Summer of 2009, Madaras [START_REF] Madaras | On local properties of 1-planar graphs with specified minimum degree and girth[END_REF] reported some new results on the light subgraphs in 1-planar graphs with minimum degree 6 and 7, as well as in 1-planar graphs with minimum degree 5 and girth 4. They (Hudák and Madaras) proved that each 1-planar graph with minimum degree 6 contains a 4-cycle with all vertices of degree at most 71, and this upper bound was later decreased to 47 [START_REF] Hudák | On local properties of 1-planar graphs with high minimum degree[END_REF]. They also proved the existence of a complete graph K 4 with all vertices of degree at most 13 in 1-planar graphs with minimum degree 7 [START_REF] Hudák | On local properties of 1-planar graphs with high minimum degree[END_REF][START_REF] Madaras | On local properties of 1-planar graphs with specified minimum degree and girth[END_REF]. Some other local structures were extensively studied by many authors including [6-8, 10, 13, 18, 21].

In this paper, we improve Hudák and Madaras's upper bounds for the heights of C 4 and K 4 in the family of 1-planar graphs with minimum degree 6 and 7, respectively. We prove Theorem 1 Each 1-planar graph with minimum degree 6 contains a copy of C 4 with all vertices of degree at most 19.

Theorem 2 Each 1-planar graph with minimum degree 7 contains a copy of K 4 with all vertices of degree at most 11.

However, we still do not know whether or not these bounds in Theorems 1 and 2 are best possible. We leave this as an open problem for further research.

Preliminaries

In the rest of this paper, we always assume that G is a 1-planar graph with minimum degree 6 or 7, and it is drawn on a plane so that (1) every edge is crossed by at most one another edge and (2) the number of crossings is as small as possible. The associated plane graph G × of G is the plane graph that is obtained from G by turning all crossings of G into new 4-valent vertices. By [START_REF] Albertson | Coloring vertices and faces of locally planar graphs[END_REF], no two 4-vertices are adjacent in G × . A 3-face in G × is called true if it is not incident with 4-vertices and f alse otherwise. A big face denotes a face of degree at least 4.

For convenience, we use some specialized notations during the proofs in the next section. Let v be a 4-vertex in G × and let v 1 , v 2 , v 3 , v 4 be its neighbors in clockwise order. By f i denote the face incident with vv i and vv i+1 in G × , where the subtraction and addition on subscripts are taken modulo 4. We call a

4-vertex v closed if d(f 1 ) = d(f 2 ) = d(f 3 ) = d(f 4 ) = 3, and open otherwise. It is easy to see that if d(f i ) = 3, then v i v i+1 ∈ E(G × ).
In this case, let f i be the other face incident with the edge v i v i+1 . If d(f i ) = 3, then the third vertex on the boundary of f i , which is different from v i and v i+1 , will be denoted by v i . So v i is a 4-vertex if and only if f i is false, in which case we denote the neighbor of v i (or v i+1 ) in G, such that the edge connecting them in G contains the crossing point v i , to be v i (or v i+1 , respectively). Namely, v i v i and v i+1 v i+1 are two edges in G that cross each other at the point v i . Denote the face incident with the path x i x i x i+1 (or

x i+1 x i x i ) in G × by f L i (or f R i , respectively
). The proofs of the two theorems are carried out by contradiction and their beginnings are just the same. Suppose that G is a counterexample to the theorem. Consider the associated plane graph G × of G.

Using the well-known Euler formula

v(G × ) -e(G × ) + f (G × ) = 2 and the relation v∈V (G × ) d(v) = f ∈F (G × ) d(v) = 2e(G × ), we have v∈V (G × ) (2d(v) -10) + f ∈F (G × ) (3d(f ) -10) = -20.

Define an initial charge w on

V (G × ) F (G × ) by w(v) = 2d(v) -10 if v ∈ V (G × ) and w(f ) = 3d(f ) -10 if f ∈ F (G × ). Thus we have x∈V (G × ) F (G × ) w(x) = -20.
In order to prove Theorem 1 and Theorem 2, we shall design some discharging rules so that after discharging the new charge w (x) of every element x ∈ V (G × ) F (G × ) is nonnegative. Since our rules only move charge around and do not affect the total charges, this leads to a contradiction at the end and completes the proofs.

Proofs

Proof of Theorem 1

The proof follows the strategy described in Section 2. Suppose that G is a counterexample to Theorem 1. Then each copy of C 4 contained in G has a vertex of degree at least 20; we call such a vertex big. The vertices of degree from 6 to 19 are called intermediate vertices. In the following. we proceed with the discharging method and the initial charges are redistributed according to the following rules. Note that all the faces as mentioned in the rules are faces in G × . R1. Each 6 + -vertex sends 1 3 to each of its incident faces. R2. Each 4-vertex sends 1 3 to each of its incident false 3-faces. R3. Each big face sends 1 to each of its incident 4-vertices. By the above rules, one can prove the following two claims that are quite useful. Claim 1. For a big face f , if R3 is applied to f once, then R9 can be executed at most once. Proof. Suppose that f is a big face with three incident vertices x, y, z such that xy, yz ∈ E(G × ) and y is a 4-vertex. Then xz ∈ E(G) and we can suppose that xx crosses zz in G at y. By R3, there must be a transfer from f to y now. If R3 is applied to f once and R9 is executed at least twice, then xz , x z ∈ E(G) and all of x, x , z, z are intermediate vertices. This implies the existence of a 4-cycle xx zz in G with all its vertices intermediate, a contradiction. Hence R9 can be executed at most once. Claim 2. For a big vertex x, if R5 is applied to x once, then R7 can be executed at most once. Proof. Let xyz be a false 3-face with a big vertex x and a 4-vertex z. Suppose that xx crosses yy in G at z. If R5 is applied to x once, then xy ∈ E(G). Now we prove that R7 cannot be executed twice. For otherwise, x yz, x y z are both false 3-faces and y, y , x are all intermediate vertices. Furthermore, x y is incident with another 3-face x yu such that u = y and u is an intermediate vertex by R7. Consequently, the four intermediate vertices x , y , y, u form a 4-cycle in G, a contradiction.

We now check that the final charge of every vertex and face in G × is nonnegative. Case 1. Suppose that f is a 3-face. Then by R1 and R2, each vertex incident with f sends 1 3 to f . This implies that w (f ) = w(f ) + 3 × 1 3 = -1 + 1 = 0. Case 2. Suppose that f is a big face. Let a be the number of transfers from f to its incident 4-vertices by R3 and let b be the number of transfers from f to its non-incident 4-vertices by R8. Since no two 4-vertices are adjacent in G × , a ≤ d(f )-b 2 and f is incident with at least d(f ) 2 6 + -vertices. By Claim 1, if there is a transfer of 1 from f by R3, then there is a total transfer at most 1 3 from f by R9. Therefore,

w (f ) ≥ w(f ) + 1 3 d(f ) 2 -(1 + 1 3 )a -2 3 b ≥ 19 6 d(f ) -10 -2 3 (2a + b) ≥ 19 6 d(f ) -10 -2 3 d(f ) = 5d(f )-20 2
≥ 0 by R1 for d(f ) ≥ 4. Case 3. Suppose that v is a 4-vertex. Then w(v) = 2d(v) -10 = -2. Subcase 3.1. Suppose that v is incident with at least three big faces. Then by R2 and R3, w (v) ≥ w(v) -1 3 + 3 × 1 = 2 3 > 0. Subcase 3.2. Suppose that v is incident with two big faces and two false 3-faces. We follow the definitions in Section 2 and split our proofs into two subcases. Subcase 3.2.1. Without loss of generality, suppose that f 1 , f 3 are big faces and f 2 , f 4 are false 3-faces.

Then α = [v 1 v 3 v 2 v 4
] is a 4-cycle and thus at least one of the vertices on the boundary of α, say v 1 , is a big vertex. This implies that v will receive 1 from v 1 by R6. Finally, by R2 and R3, we also have

w (v) ≥ w(v) + 1 + 2 × 1 -2 × 1 3 = 1 3 > 0. Subcase 3.2.2.
In this case, we suppose that f 1 , f 2 are big faces and f 3 , f 4 are false 3-faces. If v is adjacent to at least two big vertices, then at least one of them will send charge to v by R6. Thus we still have w

(v) ≥ w(v) + 1 + 2 × 1 -2 × 1 3 = 1 3 > 0 by
) ≥ 5 3 d(v)-10-7 6 d(v) = d(v)-20 2 ≥ 0 for d(v) ≥ 20.

Proof of Theorem 2

The proof also follows the strategy described in Section 2. Let G be a counterexample to Theorem 2. So each copy of K 4 in G contains a 12 + -vertex, which is called big vertex. The vertices of degree from 7 to 11 are called intermediate vertices. Let t(v) be the number of 3-faces that are incident with v. Then v is closed if and only if t(v) = 4 (recall the definition of closed vertices in Section 2). Let c(v) (or c(f )) be the number of 4-vertices that are adjacent to (or incident with) v (or f ). By c 1 (v) and c 2 (v), respectively, we denote the number of closed 4-vertices and open 4-vertices adjacent to v. Obviously we have c

1 (v) + c 2 (v) = c(v). Claim 1. If d(v) = 7, then t(v) ≤ 6 if c(v) = 4, t(v) ≤ 4 if c(v) = 5, t(v) ≤ 2 if c(v) ≥ 6.
Proof. This follows directly from the fact that no two 4-vertices are adjacent in

G × . Claim 2. If d(v) ≥ 8, then t(v) + c(v) ≤ 3 2 d(v) and t(v) + 2c(v) ≤ 2d(v). Proof. If c(v) ≤ d(v)

2

, then this holds trivially. So we assume that c(v) ≥ d(v)

2

. Beginning with

d(v) 2
, each unit of increase on c(v) will imply two units of decrease on the largest possible number of the 3-faces that are incident with v, that is because no two 4-vertices are adjacent in G × . Therefore, ) ≥ 2(c 1 (v) + c 2 (v)) -d(v). Therefore, we have 2c 1 (v) + c 2 (v) ≤ d(v). We complete the proof of Theorem 2 by applying the following rules of discharging. R1. Each big face sends 1 to each of its incident 4-vertices. R2. Each intermediate vertex sends 1 3 to each of its adjacent 4-vertices.

t(v) ≤ d(v) -2(c(v) -d(v)

  R4. Let α = [xyz] be a true 3-face having a common edge yz with a false 3-face β = [uyz]. If x is a big vertex, then x sends 2 3 to u through yz. R5. Let α = [xyz] and β = [uyz] be two adjacent false 3-faces and z be a 4-vertex. If y is a big vertex, then y sends 2 to z. R6. Let α = [xyz] be a false 3-face having a common edge yz with a big face β. If y is a big vertex and z is a 4-vertex, then y sends 1 to z. R7. Let α = [xyz] and β = [uyz] be two adjacent false 3-faces, x be a big vertex, z be a 4-vertex, and y, u be two intermediate vertices. Suppose that yu is incident with another false 3-face γ = [yuw] and yy crosses uu in G at w. If yu ∈ E(G) and u is an intermediate vertex, or y u ∈ E(G) and y is an intermediate vertex, then x sends 1 3 to w through yz and yu. R8. Let α be a big face having a common edge xy with a false 3-face β = [xyz]. If z is a 4-vertex, then α sends 2 3 to z through xy. R9. Let α be a big face having a common edge xy with a false 3-face β = [xyz]. If x is a 4-vertex, y, z are both intermediate vertices, and yz is incident with another false 3-face γ = [yzu], then α sends 1 3 to u through xy and yz.

2 ) 2 ) 2 . 2 ,

 2222 if d(v) is even, and t(v) ≤ d(v) -1 -2(c(v) -d(v) if d(v) is odd. In either case, t(v) + 2c(v) ≤ 2d(v). Since c(v) ≥ d(v) 2 , we have t(v) + c(v) ≤ 2d(v) -c(v) ≤ 3 2 d(v). Claim 3. If d(v) ≥ 12, then 2c 1 (v) + c 2 (v) ≤ d(v). Proof. Since no two 4-vertices are adjacent in G × , we have c 1 (v) ≤ d(v) If c(v) ≤ d(v) 2 , then 2c 1 (v) + c 2 (v) = c 1 (v) + c(v) ≤ d(v). If c(v) > d(v) then each unit of increase on c(v) from d(v) 2implies the existence of at least two open 4-vertices that are adjacent to v. This implies that c 2 (v) ≥ 2(c(v) -d(v)

2

 2

  R2, R3 and R6. So we suppose that v is adjacent to

		v									v						v
											. . .
								4	+	4	+	4	+	4	+
	x	y		z		x		y									x	y
		t y p e 1									t y p e 2						t y p e 3
						v											v
						. . .											. . .
			4	+	4	+	4	+				4	+	4	+	4	+	4	+	4	+
		x	y			t y p e 4		u w							t y p e 5
						Fig. 1: Five types of cluster
	5 3 d(v)-10-7 6 (2n 1 +2n 2 +n 3 +3n 4 +n 5 )+(n 2 + 1 2 n 3 + 5 6 n 4 + 7 6 n 5

Supported by NSFC grants 10971121, 11101243, 10871119, RFDP grant 20100131120017 and GIIFSDU grant yzc10040.

at most one big vertex. If one of v 1 , v 3 and v 4 is big, then the redistributed charge of v can be calculated as before, hence, it is nonnegative. If none of v 1 , v 3 and v 4 is big (namely, all of them are intermediate), then v 2 will not send charge to v by any of the rules no matter v 2 is big or intermediate. Now, consider the face f 3 . If it is a big face, then it will send 2 3 to v through v 3 v 4 by R8. If f 3 is 3-face, denoted by v 3 v 4 v 3 (note that v 3 = v 1 , v 2 ), then v 3 must be a big vertex while f 3 is true, that is because v 1 v 3 v 3 v 4 forms a 4-cycle in G with v 1 , v 3 , v 4 being intermediate. In such a case, v 3 will send 2 3 to v through v 3 v 4 by R4. If

intermediate, which implies that v 4 must be a big vertex. Then by R7, v 4 will send 1 3 to v through v 3 v 4 . By a similar discussion on f R 3 , v will receive another 1 3 from f R 3 or v 3 through v 3 v 4 (again, note that v 3 = v 1 , and if v 3 = v 2 , then f R 3 must be a big face). Consequently, using the transfers through v 3 v 4 , v receives totally 2 × 1 3 = 2 3 . By symmetry, the same discussion can be applied to the calculation of the transfers through v 1 v 4 . Thus, by R2 and R3, we still have

Suppose that v is incident with one big faces and three false 3-faces. Without loss of generality, we assume that f 1 is big and the other three faces are false. Since v 1 v 3 v 4 v 2 forms a 4-cycle in G, v must be adjacent to at least one big vertex. If v is adjacent to at least two big vertices, then by R5 and R6, v receives at least 2 × 1 = 2 from its big neighbors. Together with R2 and R3, we have

3 + 2 = 0. Now we consider the case when v is adjacent to exactly one big vertex. If v 3 or v 4 is big, then by R5, a transfer of 2 from v 3 or v 4 to v will be put into practice. This implies that w

. By the same argument as in Subcase 3.2.2, v will also receive 2 3 through the edge v 3 v 4 and another 2 3 through the edge v 1 v 4 . In total, by R2 and R3, we shall also have w

≥ 0 for d(v) ≥ 6. Case 5. Suppose that v is a big vertex. Let F denote the subgraph induced by the faces which are incident with v. Then F can be decomposed into many parts, each of which is one of the following five clusters in Figure 1, and any two parts of which are adjacent only if they have a common edge vw such that w is a 6 + -vertex. The hollow vertices in Figure 1 are 4-vertices and the solid ones are 6 + -vertices; all the faces marked by 4 + are big faces and there is at least one big face contained in the clusters of type 2, 4 and 5.

Let n i be the number of clusters of type i contained in F . By their definitions, one can easily observe that 2n 1 + 2n 2 + n 3 + 3n 4 + n 5 ≤ d(v). If there is a cluster of type 1 in F , then v will send 2 to y by R5. Meanwhile, v will also send out at most 1 3 through either xy or yz by R7 and Claim 2. If there is a cluster of type 2 in F , then v will send 1 to y by R6 and send out at most 1 3 through xy by R7. If there is a cluster of type 3 in F , then v will send out at most 2 3 though xy by R4. If there is a cluster of type 4 in F , then v will send 1 to each of y and u by R6 and totally send out at most 2 × 1 3 = 2 3 through xy and uw by R7. If there is a cluster of type 5 in F , then v will not send out charges via this cluster by any of the rules. Therefore, together with R1, we have w

R3. Each big vertex sends 1 3 to each of its adjacent open 4-vertices, and 13 9 to each of its adjacent closed 4-vertices. R4. Let α = [xyz] be a true 3-face. Then each of x, y, z sends 1 3 to α. R5. Let α = [xyz] be a false 3-face. If x is a 4-vertex, then x sends 1 9 while both y and z sends 4 9 to α. We now check that the final charge of every vertex and face in G × is nonnegative. Case 1. Suppose that f is a 3-face. By R4 and R5, one can observe that w (f ) = w(f ) + 1 = -1 + 1 = 0. Case 2. Suppose that f is a big face. Since no two 4-vertices are adjacent in G × , c(f

If v is incident with exactly one big face, then we still have w (v) ≥ w(v) + 1 + 4 × 1 3 -3 × 1 9 = 0. If v is incident with no big faces, then v is closed. Meanwhile, v 1 , v 2 , v 3 and v 4 forms a K 4 in G, which implies that at least one of them is a big vertex, say v 1 . Then v 1 will send 13 9 to v by R3. Since v 2 , v 3 and v 4 are either intermediate or big, each of them shall send at least 1 3 to v by R2 and R3. Together with R5, we also have w (v) ≥ w(v)+ 13 9 +3× 1 3 -4× 1 9 = 0. Case 4. Suppose that v is an intermediate vertex.

2

, then by R3, R4 and R5, w (v) ≥ w(v)- 13 9 c(v)-


S Janfaoui
email: sabri.janfaoui@yahoo.fr

C Simon

N Coulon

T Mohammed-Brahim

Behavior of the parameters of microcrystalline silicon TFTs under mechanical strain

Keywords: µc-Si TFT, PEN, Mechanical Stress

N-type and P-type microcrystalline silicon top-gate TFTs, processed directly on PEN plastic substrate at maximum temperature of 180°C, were mechanically stressed. These TFTs were bent by different curvature radii varying between infinite (flat) and 0.5 cm. The tensile stress increases the electron mobility and the compressive stress decreases it.

The tensile stress decreases the threshold voltage of N-type TFTs while the compressive stress increases it. These trends are inversed if the type of stress changes OR the type of TFTs changes.

The total behavior under mechanical stress is exactly similar to that of single crystalline silicon MOSFETs in nano-scale technologies (90, 65, 45, 32 nm), where nano-scale stress is introduced in the goal to engineer the electrical parameters. The similarity originates from the microcrystalline silicon active layer that behaves like single crystalline silicon even if the stress effects are softened by the grain boundaries and the multiple crystalline orientations of the grains

Several research studies are launched now to develop electronic devices on flexible substrate. The main targets of this electronics are the flexible displays, the intelligent textile, RFID tags and others. Some of these applications require the transparency of substrate.

That's why the most used substrates are transparent plastics. However, most of transparent plastics cannot support a temperature higher than 120°C. The heat stabilised PEN (Polyethylene naphthalate) produced by DuPont Teijin Films can reach 180°C with 0.2% shrinkage during 30 minutes. Therefore, the maximum temperature that can be reached during the process is 180°C.

A number of methods and materials can be used to develop electronics on flexible substrates that cannot support a temperature highest than 180°C. One way is to fabricate the devices as usual on silicon wafers or on glass (large area electronics) and then transfer it on flexible substrate. Of course the performance of these devices is typical but the cost of the transfer will be prohibitive. The flexibility of such devices is also limited.

The other option is to fabricate the devices directly on the flexible substrate at the maximum temperature of 180°C. At such low temperature, the performance will be limited but the cost is low. So depending on the required performance and then on the targeted application, one of these two alternatives can be used. For example, electronics accompanying the sensors that sense human activities has not to work at very high frequency. In this case, direct fabrication of devices on flexible substrate can be developed.

When choosing this direct fabrication, different materials can be used. Organic materials are intensively used in many works in order to develop an organic electronics. Indeed, organic materials can hold a very low radius of curvature. However, a very long development is still needed to reach commercial electronic devices with needed reproducibility and reliability.

In this paper, N-type and P-type transistors based on inorganic materials are shown to hold a low radius of curvature without breaking. This result is interesting knowing the superior reproducibility and reliability of inorganic based devices.

Previously, we succeeded in depositing microcrystalline silicon (µc-Si:H) on glass at 165°C with sufficient electrical quality, leading to stable TFTs. [1][2]. This result was obtained thanks to the use of a mixture of silane, hydrogen and argon for the deposition [1][2] and of a very thin active layer [3][4]. The choice of µc-Si:H material is mainly due to being more stable than most of similar materials deposited at low temperature [amorphous silicon,…]. It offers in addition the possibility to produce both N-type and P-type transistors [5][START_REF] Mohammed-Brahim | Proc. Active Matrix Flat Panel Displays 2012[END_REF] and therefore to develop CMOS devices. Within this study, the optimized process of TFTs on glass is transferred on PEN substrate producing then N-type and P-type µc-Si TFTs on plastics. The success of the process led us to study the electrical behaviours of these TFTs under mechanical stress. These behaviours are explained tentatively using the numerous works on the strain on single crystalline silicon MOSFETs.

Experiment

2.1

Process µc-Si:H Top-Gate TFTs are fabricated on 5 x 5 cm2 sheets of PEN (Polyethylene naphthalate). The thickness of the sheets of PEN is e = 125 µm. The sheet can reach 180°C with 0.2% shrinkage during 30 minutes. This feature limits the temperature of the process at 180°C.

The sheet of PEN is encapsulated on both sides with 250 nm thick silicon nitride. This layer protects the device from organic contamination during the process. A 100 nm thick layer undoped µc-Si:H is deposited in a PECVD reactor at 13.56 MHz using a gas mixture of silane, argon and hydrogen. Flows used for deposition are respectively 1.5, 75 and 75 sccm.

The pressure is adjusted at 0.9 mbar and the RF power is fixed at 15 watts. The deposited film was optimized at 165°C [2]. After that, a layer 70 nm thick doped µc-Si:H is deposited in the same manner as the undoped µc-Si:H using a mixture of silane, hydrogen and doping gas. The doping gas is arsenic for N-type TFTs and diborane for P-type TFTs. A first photolithography step is used to define drain, source and channel regions. The µc-Si:H doped layer is etched by SF6 plasma in a Reactive Ion Etch (RIE) reactor to define source and drain regions. Then, a second photolithography step is necessary in the purpose to insulate transistors one from each other. The undoped µc-Si:H is etched by SF6 plasma. This step is followed by an RCA cleaning. After that, 300 nm thick silicon nitride film acting as gate insulator is deposited by PECVD at 150°C using mixture of silane, nitrogen and ammonia. The gas flows used for the Si3N4 deposition are respectively 2, 80 and 40 sccm. The pressure is adjusted at 0.6 mbar and the RF power is fixed at 30 watts. A third photolithography step is used to open windows for drain and source contacts. The silicon nitride film is etched by SF6 plasma. A layer of aluminum is deposited by thermal evaporation, and a fourth photolithography step is used to define the drain, source and gate electrodes. Aluminum is etched by wet way. The final structure is presented in Fig. 1. Finally, an annealing at 180°C is performed under nitrogen. Note that the maximum temperature reached during the process is 165°C in order to avoid shrinking of the substrate between 2 photolithography steps. We maintain then the temperature of the process at much lower values than the needed maximum (180°C).

Aluminum

After processing, the TFTs are electrically characterized to extract the main parameters.

The mobility value is deduced from the transconductance gm in the linear mode using the usual MOSFET equation. gm is the maximum slope of the linear plot of the transfer characteristics. The threshold voltage is determined in the linear mode by a linear extrapolation of the drain current versus gate voltage curve. The ratio Ion/Ioff is the maximum value of the ratio between the on-current and the off-current. The subthreshold swing S is the minimum reverse slope of the transfer characteristic (VGS/logIDS) measured in the switching region.

Mechanical behavior

The mechanical behaviors of the previous electrical parameters (mobility, threshold voltage, subthreshold swing) were studied by bending the flexible substrate at different radii of curvature. For this, the TFTs are electrically characterized under bending in the direction of their channel, using homemade tools (Fig. 2 and3) allowing the bending of the substrate in tensile or compressive stress. Starting from this modeled structure, the strain  surface created at the surface of the TFT by a bending at a radius of curvature R is calculated using the following equation [START_REF] Gleskova | [END_REF]

         1 1 1 2 2 1 1 2 1 2 2 1 2 2 1 1 2 2 2 1 2 1 0                                     f f S surface d d d R R with: S f S f S f d d d d Y Y 2 2 1 1 ; ;       .
Y f and Y s are the Young modulus of silicon nitride and of PEN respectively. d f1 , d f2 and d s are the thicknesses of the bottom silicon nitride layer, of the top one and of the PEN sheet. R is the curvature radius and R 0 the initial curvature radius (infinite here in our case where we start from a flat sheet).

Fig. 5 shows the behavior of the strain  surface as a function of the radius of curvature R when the stress is tensile or compressive. This curve will be used in the following to determine the behavior of the different parameters of the TFTs as a function of the strain.

Results

Electrical Characterization

The TFTs are electrically characterized before starting the mechanical study. Fig. 6 shows the transfer characteristics of N-type and P-type TFTs in the linear regime (V DS =+1V for Ntype and -1V for P-type). Both TFTs have the same size with a channel width W= 100µm and a channel length L=20 µm. The characteristics are symmetric with the same absolute value of the threshold voltage VTH and the same Subthreshold swing S. The on-current of the N-type TFT is of course higher due to the higher value of the electron mobility than that of the hole mobility. The low mobility value is usual when using silicon nitride as gate insulator in microcrystalline silicon TFTs even on glass substrate [3]. Despite this low mobility, TFTs are very stable under gate bias stress [3][4]. Finally and most importantly, the present TFTs show the possibility to fabricate symmetric N-type and P-type TFTs directly on a PEN sheet at a maximum temperature of 180°C. This temperature is reached only during the last annealing step. CMOS electronics fabricated directly on PEN is in way.

V GS +/-1V V GS V GS +/-1V I DS (A) I DS (A)

Mechanical Characterization

The demonstrated possibility of CMOS electronics fabricated directly on flexible PEN sheets needs its behavior to be checked under mechanical tensile stress and compressive stress. Both, the decrease of the threshold voltage and the increase of the mobility appear to be independent of the size of the transistor. However, a deep analysis of the behavior (particularly for the highest strain shown by the insets in Figs. 7 and8) shows that the threshold voltage and the mobility depend much more on the channel length than on its width. The variation becomes more important when the channel length decreases. This remark is not surprising if we consider that the tensile stress is applied in the direction of the channel length.

N-type TFT

Similarly to this previous tensile stress, a compressive stress is applied to TFTs with the same size. The behaviors of their threshold voltage and of their mobility, through the ratio between their value at a curvature radius R and their initial value when the TFT is flat, are shown in Figs. 9 and 10. On the contrary of the effect of the tensile stress, these figures show an increase of the threshold voltage V TH and a decrease of the mobility µ when the compressive strain increases. Under tensile stress, the behaviors of the threshold voltage and of the mobility show opposite trends for N-type and P-type TFTs.. Finally the same W/L=100µm/20µm P-type TFT is submitted to a compressive stress. The behaviors of its threshold voltage and of its mobility, through the ratio between their value at a curvature radius R and their initial value when the TFT is flat are shown in Figs. 13 and 14. On the contrary of the tensile stress, these figures show a decrease of the threshold voltage V TH and an increase of the mobility µ when the compressive strain increases. Group [START_REF] Gleskova | [END_REF][8][9]. It is possible to find also some papers on the mechanical behavior of crystallized silicon TFTs mainly on LTPS TFTs fabricated on metal foils [10][11][12]. The electron mobility of a-Si:H TFTs was found to increase with tensile stress and to decrease with compressive stress. The electron mobility increases with tensile stress [10] and the hole mobility decreases under the same tensile stress [10,11] for LTPS TFTs. These results are limited particularly when it comes to crystallized silicon TFTs. However, they are not inconsistent with our results.

On the other hand, a lot of complete studies on the mechanical behavior of single crystalline silicon MOSFETs are available. These intensive studies were done in nano-scale technologies (90, 65, 45, 32 nm) where nano-scale stress is introduced in the aim to increase the mobility of the electrons or of the holes. Some of the methods are given in a review [13].

These numerous works focus on the attribution of the increase of the mobility to the change in the energy bands due to the uniaxial stress, decreasing mainly the conductivity effective mass. For example, the threshold voltage decreases and the electron mobility increases for N-MOSFETs submitted to uniaxial tensile stress [13]. The decrease of the threshold voltage is attributed to a decrease of the energy band-gap and to the variation of the valence band density of states.

The same group [14] gives a 1.55 (µ/µ0) increase of the electron mobility under a tensile uniaxial strain of 0,0045% and under a vertical field of 0.7 MV/cm . The increase of the hole mobility is 3.8 (µ/µ0) under 0.005% compressive strain and under the same vertical field. In the present microcrystalline silicon TFTs, the increase of the mobility is 1.4 for electrons and 1.27 for holes, under the same order of vertical field but under a much higher tensile strain or a much higher compressive strain (0.45%).The need of a much higher strain to get the same increase of the mobility is probably due to the microcrystalline structure with grains boundaries that soften the effect of the stress and also to the different crystalline orientations of the grains even if the (220) orientation dominates.

Even if the magnitude of the mobility variations is lower with microcrystalline silicon TFTs, the most important is that the trends of the transistor parameters observed in the present study are exactly similar to that of the same parameters for MOSFETs. It may be then interesting to check what happens in microcrystalline silicon films under stress.

First, an undoped microcrystalline silicon film was deposited on a PEN sheet covered with silicon nitride, in the same conditions as for the active layer of TFTs. Its electrical conductivity was measured as a function of the tensile strain. The conductivity value increases with the strain with a little bit lower slope than that of the electron mobility of TFTs (Fig. 15). It means that the increase of the mobility of TFTs under tensile stress is due to a change in the electronic transport properties of the microcrystalline silicon active layer. Finally, it can be interesting to check the effect of the strain on the crystalline grains of microcrystalline silicon when the stress is applied to the total structure that is constituted by crystalline grains and grain boundaries. This check can be done by using Raman spectroscopy. Indeed, amorphous and crystalline regions in the material contribute differently to the Raman spectrum. For example the transverse optic (TO) mode presents a band located at 480 cm-1 for amorphous silicon and at 520 cm-1 for single crystalline silicon. Moreover, another band located at 494-510 cm-1 is attributed to bond dilation at grain boundaries [15]. Fig. 17 gives an example of the TO band of microcrystalline silicon that is constituted by 3 sub-bands. The Raman spectrum of previous microcrystalline silicon film submitted to different tensile stresses is measured at an excitation wavelength of 325nm. The position of the band attributed to single crystalline grains moves towards lower values of the Raman shift when the tensile strain increases (Fig. 18). The lower position of this band can be attributed to tensile strained crystalline grains as usual [16]. Here, this lower position of the band is not surprising as a macroscopic tensile stress is applied. However it means that the macroscopic stress affects directly the crystalline grain and then its electrical properties as for single crystalline silicon of MOSFETs. All these previous experiments lead to attribute the different effects of the tensile and compressive stresses on the parameters of microcrystalline silicon TFTs to the same origins already given for single crystalline silicon MOSFETs. Only the magnitude of the effects is softened by the presence of disordered boundaries between the crystalline grains and by the different crystalline orientations of the grains.

Conclusion

N-type and P-type microcrystalline silicon TFTs were directly fabricated on PEN sheets at a maximum temperature of 180°C. For the first time, systematic study of the behavior of such TFTs under tensile and compressive stresses is presented here. The total behavior is exactly similar to that of single crystalline silicon MOSFETs in nano-scale technologies (90, 65, 45, 32 nm) where nano-scale stress is introduced in the aim to engineer the electrical parameters. Complementary studies show that this similarity is due to the microcrystalline silicon active layer that behaves like single crystalline silicon material even if the stress effects are softened by the grain boundaries and the multiple crystalline orientations of the grains.

This study shows also that microcrystalline silicon films can hold high strain at a level of 1.35% corresponding to a curvature radius of 5 mm. Flexible electronics based on silicon can be the future in many applications considering the present mechanical behavior and the known stability of microcrystalline silicon.

Figure Captions

Fig. 1 .

 1 Fig. 1. Structure of µc-Si:H Top-Gate TFT.

Fig. 2 .Fig. 3 .Fig. 4 :

 234 Fig. 2. Tool allowing the application of a tensile strain. The TFTs are bended outward and in parallel to the length L of the channel.

Fig. 5 :

 5 Fig.5: Evolution of the strain at the surface of the TFTs as a function of the radius of curvature of the substrate when the stress is tensile or compressive.

Fig 6 .

 6 Fig 6. Transfer characteristics of N-type TFT (filled red triangle) and P-type TFT (open dark triangle) under a drain-source voltage of +1V (N-type) and -1V (P-type). The TFTs have the same size (W=100 µm, L=20µm). The characteristic is presented in linear scale (a) and in log scale (b).

Fig. 7 :Fig. 8 :

 78 Fig.7 : Ratio between the threshold voltage at a tensile curvature radius R and its initial value when the TFT is flat for 4 different sizes (W/L=100µm/20µm: full squares, W/L=80µm/20µm: open squares, W/L=100µm/40µm: full triangles, W/L=80µm/40µm: open triangles) of N-type TFTs as a function of the strain.

Fig. 9 :Fig. 10 :Fig. 11 :Fig. 12 :

 9101112 Fig.9: Ratio between the threshold voltage at a compressive curvature radius R and its initial value when the TFT is flat for 4 different sizes (W/L=100µm/20µm: full squares, W/L=80µm/20µm: open squares, W/L=100µm/40µm: full triangles, W/L=80µm/40µm: open triangles) of N-type TFTs as a function of the strain

Fig. 13 :Fig. 14 :

 1314 Fig.13: Ratio between the threshold voltage at a compressive curvature radius R and its initial value when the TFT is flat for W/L=100µm/20µm P-type TFT as a function of the strain

Fig. 15 :Fig. 16 :

 1516 Fig.15: Ratio between the electrical conductivity of an undoped microcrystalline silicon film deposited on PEN sheet covered with silicon nitride at a tensile curvature radius R and its initial value when the film is flat, as a function of the strain.

Fig: 17 :

 17 Fig: 17: Typical Raman transverse optic band of microcrystalline silicon

Fig. 18 :

 18 Fig. 18: Shift of the single crystalline silicon band of an undoped microcrystalline silicon film deposited on PEN sheet covered with silicon nitride as a function of the tensile strain.

Fig. 1 .

 1 Fig. 1. Structure of µc-Si:H Top-Gate TFT.

Fig. 2 .

 2 Fig. 2. Tool for tensile strain. TFTs are bended outward and in parallel to the channel L.

Fig. 3 .

 3 Fig.3. Tool for compressive strain. TFTs are bended inward and in parallel to the channel L.

Fig. 4 :

 4 Fig. 4: Mechanical model of the total structure composed by the PEN sheet, the double silicon nitride film and the TFT.

Fig. 5 :Fig 6 .

 56 Fig.5: Evolution of the strain at the surface of the TFTs as a function of the curvature ratio of the substrate for tensile or compressive stress. Fig 6. Transfer characteristics of N-type TFT (filled triangle) and P-type TFT (open triangle) under a drain-source voltage of +1V (N-type) and -1V (P-type). The TFTs have the same size (W=100 µm, L=20µm). The characteristic is presented in linear scale (a) and in log scale (b).

Fig. 7 :

 7 Fig.7 : Ratio between the threshold voltage at a tensile curvature radius R and its initial value when the TFT is flat for 4 different sizes (W/L=100µm/20µm: full squares, W/L=80µm/20µm: open squares, W/L=100µm/40µm: full triangles, W/L=80µm/40µm: open triangles) of N-type TFTs as a function of the strain.

Fig. 8 :

 8 Fig.8: Ratio between the electron mobility at a tensile curvature radius R and its initial value when the TFT is flat for 4 different sizes (W/L=100µm/20µm: full squares, W/L=80µm/20µm: open squares, W/L=100µm/40µm: full triangles, W/L=80µm/40µm: open triangles) of N-type TFTs as a function of the strain.

Fig. 9 :Fig. 10 :Fig. 11 :

 91011 Fig.9: Ratio between the threshold voltage at a compressive curvature radius R and its initial value when the TFT is flat for 4 different sizes (W/L=100µm/20µm: full squares, W/L=80µm/20µm: open squares, W/L=100µm/40µm: full triangles, W/L=80µm/40µm: open triangles) of N-type TFTs as a function of the strain Fig.10: Ratio between the electron mobility at a compressive curvature radius R and its initial value when the TFT is flat for 4 different sizes (W/L=100µm/20µm: full squares, W/L=80µm/20µm: open squares, W/L=100µm/40µm: full triangles, W/L=80µm/40µm: open triangles) of N-type TFTs as a function of the strain Fig.11: Ratio between the threshold voltage at a tensile curvature radius R and its initial value when the TFT is flat for W/L=100µm/20µm P-type TFT as a function of the strain.

Fig. 12 :

 12 Fig.12: Ratio between the electron mobility at a tensile curvature radius R and its initial value when the TFT is flat for W/L=100µm/20µm P-type TFT as a function of the strain.

Fig. 13 :Fig. 14 :Fig. 15 :

 131415 Fig.13: Ratio between the threshold voltage at a compressive curvature radius R and its initial value when the TFT is flat for W/L=100µm/20µm P-type TFT as a function of the strain Fig.14: Ratio between the electron mobility at a compressive curvature radius R and its initial value when the TFT is flat for W/L=100µm/20µm P-type TFT as a function of the strain Fig.15: Ratio between the electrical conductivity of an undoped microcrystalline silicon film deposited on PEN sheet covered with silicon nitride at a tensile curvature radius R and its initial value when the film is flat as a function of the strain.

Fig. 16 :

 16 Fig. 16: Light energy at fixed low value (4%) of the transmission by undoped microcrystalline silicon film as a function of the strain Fig: 17: Typical Raman transverse optic band of microcrystalline silicon Fig. 18: Shift of the single crystalline silicon band of an undoped microcrystalline silicon film deposited on PEN sheet covered with silicon nitride as a function of the tensile strain.

Fig. 1

 1 Fig.1

Fig. 2

 2 Fig. 2

Fig. 4 -

 4 Fig.4

Fig. 16 400

 16 Fig.16

Fig. 17

 17 Fig.17

  Fig.18

TABLE I

 I summarizes the values of these parameters for both types of TFTs.

Table Captions TABLE I :

 CaptionsI Parameters of the N-type TFTs fabricated on PEN

TABLE II :

 II Trend of the threshold voltage and the mobility µ for N-type and P-type microcrystalline silicon TFTs fabricated on PEN sheets under tensile and compressive stress.

	Aluminum Aluminum Aluminum	Silicon Nitride Silicon Nitride Silicon Nitride
	N-doped µc-Si N-doped µc-Si N-doped µc-Si	Undoped µc-Si Undoped µc-Si Undoped µc-Si
	PEN Substrate PEN Substrate PEN Substrate

Acknnowlegments

This work was done in the frame work of the e-FlexSi project ANR -09-BLAN-0163 France.