eo = {go, bo }. A go â¬ G, bo e go, bo, â¢., Jk, bk k > 0. {Ii, bi} e. M ; E G b; E. B. Jk+1 â¬ G\ {91. } M. Gk+1. B. M k+1. {9i, b;} 0 < i < k k+ ...

0 downloads 1 Views 261KB Size

On vertex overs,mat hings and random trees

1

Stéphane Coulomb

and Mi hel Bauer

2

Servi e de Physique Théorique de Sa lay

3

CE Sa lay, 91191 Gif sur Yvette, Fran e

Abstra t We study minimal vertex overs and maximal mat hings on trees. We pay spe ial attention to the orresponding ba kbones i.e. these verti es that are o

upied and those that are empty in every minimal vertex over (resp. these egdes that are o

upied and those that are empty in every maximal mat hing). The key result in our approa h is that for trees, the ba kbones an be re overed from a parti ular tri- oloring whi h has a simple hara terization. We give appli ations to the omputation of some averages related to the enumeration of minimal vertex overs and maximal mat hings in the random labeled tree ensemble, both for nite size and in the asymptoti regime.

1

Motivations

For a given (simple : no loops, no multiple edges) graph, nding the size of a minimal vertex over or of a maximal mat hing (see the beginning of se .2 for a reminder of denitions), and ounting the number of solutions all fall 1 Email:

2 Email: 3

oulombspht.sa lay. ea.fr mi hel.bauer ea.fr

Laboratoire de la Dire tion des S ien es de la Matière du Commisariat à l'Energie

Atomique, URA2306 du CNRS

1

under the generi name of ombinatorial optimization problems, a eld with a long history. To analyse the average behavior for these questions, the simplest model is the Erdös-Renyi model of random graphs. In this ontext, the evaluation of the average size of a maximal mat hing has been solved by Karp and Sipser [1℄ (see [2℄ for renements and [3℄ for a physi ist approa h) in the

V , the vertex set, and E , the edge set α = 2|E|/|V | has a nite limit. For the average size of a minimal vertex over, the answer is known only when α ≤ e and asymptoti ally for large α [4℄. thermodynami limit, i.e. when both

be ome large, but the ratio

To get more detailed informations on these problems, one an investigate several ombinatorial patterns. In this paper, we on entrate on ba kbones, i.e. these verti es that are o

upied and those that are empty in every minimal vertex over (resp.

these egdes that are o

upied and those that are

empty in every maximal mat hing). While for general graphs the relationships between the ba kbones are ompli ated, this is not true for trees : in that ase the ba kbone geometry an be re overed from a spe ial tri oloring, unique for ea h tree and whi h is easily hara terized. This is the ontent of Theorem 1, the ru ial ingredient for our subsequent analysis.

We use

this theorem to ompute the average size of the ba kbones and the average number of minimal vertex overs and maximal mat hings for random labeled n−2 trees of size n, where ea h of the n labeled trees has the same probability. We also analyse the asymptoti behavior for large

n,

see Theorems 2,4 and

5. Due to the simple, lo ally treelike, stru ture of Erdös-Renyi random

1

graphs , insight an often be obtained from an analysis of trees, even if in the ase of this paper the extension is nontrivial. The present study of ba kbones and the orresponding appli ations to random labeled trees an thus be seen as a preliminary step towards the analysis of their random graph generalizations. Our motivation to study ba kbones omes from physi s. The adja en y matrix of a random graph (whi h is symmetri ) an be seen as an example of a random Hamiltonian, whose average spe trum one would like to ompute. 1 For α ≤ 1, an Erdös-Renyi random graph is a forest for most thermodynami al purposes, but the lo al treelike stru ture remains even after the birth of the giant omponent. Moreover, the nite omponents of size n are distributed with the uniform measure on labeled trees of size n in the thermodynami limit.

2

In the innite

α

limit, one re overs a semi ir le, but for nite

α

matters

are mu h more ompli ated. The spe trum ontains a dense familly of delta peaks plus presumably a ontinuous omponent when

α

ex eeds a thresh-

old. In the ase of the zero eigenvalue, the stru ture of the eigenve tors an

2

be studied in detail . It exhibits interesting phenomena of lo alization and delo alization when

α

varies [6℄. We shall see below that these phase tran-

sitions are losely related to the stru ture of the ba kbones. However, their

ombinatorial interpretation is still un lear to us.

Aknowledgements We thank Martin Weigt for an illuminating remark on ba kbones that initiated this work.

2 A

Main results vertex over

of the graph

one end of ea h edge in

E.

A = (V, E)

is a subset of

V

ontaining at least

We are interested in minimal vertex overs, i.e.

those whose ardinality is the smallest. The positive (resp. negative) vertexba kbone of

A is the set of verti es

vertex over.

whi h belong to every (resp. no) minimal

degenerate verti es. An edge ex lusive if no minimal vertex over

The other verti es are alled

between degenerate verti es is alled

ontains its two extremities. A

mat hing

of

A is a set of non-adja ent edges of A.

are those whose ardinality is the largest.

Maximal mat hings

The positive (resp.

negative)

edge-ba kbone is the set of edges whi h belong to every (resp. no) maximal mat hing. The other edges are alled

degenerate edges.

A vertex for whi h

there is a maximal mat hing none of whose edges ontains it as an extremity is alled

optional.

The verti es that are neither optional, nor an extremity

of an edge in the positive ba kbone are alled If

A

unavoidable.

is a tree or a forest, one an hara terize these obje ts by simple n−2 If the n labeled trees on n

properties and ompute them re ursively.

verti es are hosen at random with the ounting measure, we shall use this to adress questions of the type What is the average size of the edge-ba kbones ? or What is the average number of maximal vertex overs in the random labeled tree ensemble. Note that we are interested in global extrema. A lo al version for, say, 2 This

is indeed an example of a situation where the analysis of random trees proved

ru ial to understand the ase of the Erdös-Renyi model. 3

minimal vertex overs would be vertex overs su h that hanging the state of

3

any o

upied vertex to the empty state destroys the vertex over property . Some problems analogous to the ones we deal with but for lo al problems an be found for instan e in the work of Meir and Moon, see e.g. [7℄ and referen es therein. For lo al extrema problems, the notion of ba kbones seems to be less relevant. A

tri oloring

su h that

B ,G

of the graph

A = (V, E)

is a triple

and the set of end-verti es of

starting point,

R

(B, R, G) ⊂ V × E × V , V . As a

form a partition of

Theorem 1 Suppose A is a tree. Ea h of the three properties (i),(ii) and (iii) hara terizes one and the same tri oloring (B, R, G) of A. (i) Minimal vertex- overs : B is the positive ba kbone; R is the set of ex lusive edges; G is the negative ba kbone. (ii) Maximal mat hings : B is the set of unavoidable verti es; R is the positive ba kbone; G is the set of optional verti es. (iii) The edges in R are non-adja ent; the edges with one end-vertex in G have the other end-vertex in B ; ea h vertex in B is onne ted to G by at least two edges. This unique tri oloring

red

is said lies in

G

if it is in

and

red

R,

(B, R, G)

b- oloring of A. An edge brown if it lies in B , green if it

is alled the

and a vertex is said

if it is an end-vertex of a red edge.

c (where A and Nc (n) is the total number n−2 of verti es with this same olor among the n labeled trees on n verti es. P Nc (n) n We shall work with the generating fun tions Fc (x) ≡ n≥1 n! x . They all P nn−1 n involve the tree generating fun tion T (x) ≡ n≥1 n! x . Our main ombiIn the sequel,

c

Nc (A)

denotes the number of verti es with olor

is either brown, red or green) in the tree

natorial and probabilisti results are ontained in the following theorems.

Theorem 2 The generating fun tions for the total number of brown, red and green verti es are FB = T (x)+T (−T (x))−T (−T (x))2 ; FR = T (−T (x))2 ; FG = −T (−T (x))

and the orresponding expli it rst terms, losed formulæ, and asymptoti s NB = (0, 0, 3, 4, 185, 1026, 30457, 362664, 10245825, 195060070, · · ·)

3 The

sions.

example of a starlike tree shows the dieren e between the lo al and global ver-

4

l n X −l NB (n) 2 n ∼ 0.2276096757 · · · = 1+ −1 n−1 l n n l l=1 NR = (0, 2, 0, 48, 120, 4560, 35700, 1048992, 15514128, 456726240, · · ·) l n X −l 1 n NR (n) ∼ 0.4104940676 · · · = −2 −1 n−1 l n n l l=1 NG = (1, 0, 6, 12, 320, 2190, 51492, 685496, 17286768, 348213690, · · ·) l n X NG (n) −l n ∼ 0.3618962567 · · · = − l nn−1 n l=1

Corollary 3 The size (that is, the ardinality) of the minimal vertex overs and maximal mat hings of a tree A is NB (A) + NR (A)/2, hen e the average fra tion of verti es in a vertex over of a tree on n verti es is n1−n (NB (n) + NR (n)/2) ∼ 0.4328567095 for large n. Let

Nvc (n)

and

Nm (n)

denote the total numbers of minimal vertex ov-

ers and of maximal mat hings among labeled trees on n verti es. The P Nvc (n) n x and Fm (x) ≡

orresponding generating fun tions, Fvc (x) ≡ n≥1 n! P Nm (n) n x , verify n≥1 n!

Theorem 4 The generating fun tion for the total number of minimal vertex

overs is 1 Fvc (x) = (1 − U)xeU − UT (x2 e2U ) + U − U 2 , 2

where xUeU = T (x2 e2U )(exe − 1). U

Nvc = (1, 2, 3, 40, 185, 3936, 35917, 978160, 14301513, 464105440, · · ·)

Theorem 5 The generating fun tion for the number of maximal mat hings is 1 Fm (x) = − (xeU + U)2 + (1 + UxeU )xeU + U − U 2 , 2

where U = x2 e−x

2 e2U +xeU +3U

.

Nm = (1, 1, 6, 24, 320, 3270, 55482, 999656, 21718440, 544829130, · · ·)

Remark 6.

Sket h of the relation with the kernel of the adja en y matrix

(see [6℄ for details).

5

The kernel of the adja en y matrix of a tree is dire tly related to the b- oloring. First one shows, for instan e by indu tion on the size of the tree, that the kernel of the support

4

A has

dimension

NG (A) − NB (A).

Se ond, one shows that

of the kernel onsists of the green verti es. ′ ′ subsets B , G of V su h that ′ ' the edges with one end-vertex in G have the other end-vertex in ′ ′ and ea h vertex in B is onne ted to G by at least two edges, Moreover, the

(iii)

oin ide with

maximal

B

and

G

of the b- oloring of

A.

B′

Thus, in the ase of trees,

maximality allows to dene the sets B and G without mentionning R. ′ ′ Drawing the edges between B and G denes a bi olored subforest of

A.

But there is a partial onverse to these onstru tions : one an show that, ′ ′ for a general graph, a bi olored subforest on B , G satisfying ' allows ′ ′ ′ to dene a |G | − |B | dimensional subspa e of the kernel with support G .

(iii)

For the Erdös-Renyi model, the enumeration of the nite maximal bi olored

subtrees satisfying

o(|V |)

(iii) ' a

ounts for the full dimension of the kernel up to an

orre tion for small or large

innite patterns ontribute

α,

but there is a window of

O(|V |) to the

α's

for whi h

dimension of the kernel. These are

the lo alization-delo alization transitions alluded to before. These are the results that motivated us to have a loser look at the ba kbones.

3

Proof of theorem 1

There are many ways to build a proof, depending on personal tastes, and the hoi e of the authors has been subje t to many u tuations. So it is not unlikely that the reader will spare time nding his own argument instead of understanding the proof that we propose. Let

A = (V, E) be

a tree. Property

izes a unique tri oloring of

•

Step 1 :

(B, R, G)

•

Step 2 :

(iii) ⇒ (ii).

4 The

A.

(ii)

of theorem 1 obviously hara ter-

Hen e, it su es to establish that

dened by

(i)

is a tri oloring, and it satises

(iii);

ve tors on whi h the adja en y matrix a ts an be interpreted as maps from V to the reals and it makes sense to say that a ve tor vanishes on a given vertex. The support of a ve tor is the set of verti es on whi h it does not vanish. The support of a familly of ve tors is the union of the elementary supports.

6

If

A = ({v}, ∅) is the

isolated vertex, any of the three assertions

denes a unique tri oloring now on that

3.1 Let

A

(∅, ∅, {v})

v

(i, ii, iii)

is green and we suppose from

has at least two verti es.

Step 1

(B, R, G)

be the triple dened by

the set of end-verti es of

R

(i)

in theorem 1. Be ause

B, G

and

are mutually disjoint, proving that a degenerate

(B, R, G) is a A. Then we he k that it satises (iii). Deletion of v ∈ V and its in ident edges leaves p ≥ 1 trees A1 , · · · , Ap , with Ai = (Vi , Ei ). Denote by vi the unique vertex of Ai whi h is adja ent to v in A. A vertex over of A obviously indu es a vertex over on ea h Ai . Conversely, suppose we are given a vertex over Ci on ea h Ai , and denote by C the union of the Ci 's. An edge of A is either in some Ei , in whi h ase it has one end in Ci hen e in C , or one of the p edges between v and some vi . Hen e C ∪ {v} is a vertex over of A, but C is not unless it ontains ea h of the vi 's. Now, let us write ni (resp. n ¯ i ) for the minimal ardinality of vertex overs of Ai ontaining (resp. not ontaining) vi . As a onsequen e of the previous remarks, a subset C of V is a minimal vertex over of A if and only if one of vertex is the end of an ex lusive edge should ensure that

tri oloring of

two ex lusive assertions holds :

• Assertion 1

1+

P

¯ i) i min(ni , n a minimal over on ea h Ai . :

≤

P

i

ni , C

ontains

v

and

C

indu es

P P • Assertion 2 : 1 + i min(ni , n ¯ i ) ≥ i ni , C does not ontain v and C indu es on ea h Ai a vertex over of ardinality ni ontaining vi . v being or not in some ba kbone, whi h are ni ≤ n ¯ i + 1 for P all i. P Suppose rst that v is degenerate. Then 1 + ¯ i ) = i ni , and i min(ni , n this implies that ni0 = n ¯ i0 + 1 for a unique i0 . There exists a minimal vertex

over of A ontaining v , whi h indu es a minimal vertex over on Ai0 , hen e does not ontain vi0 . There exists also a minimal vertex over not ontaining v , whi h obviously ontains vi0 : as was to be proved, vi0 is degenerate, and v is the end of an ex lusive edge {v, vi0 }. (B, R, G) is thus a tri oloring. Now, given i 6= i0 , we an nd a minimal vertex over of Ai ontaining vi be ause This gives us onstraints for

very informative if we note that

7

ni ≤ n ¯ i and then extend it into a minimal vertex over of A ontaining both v and vi . Hen e v is a tually the end of a unique ex lusive edge, proving that the edges of R are not adja ent. If v is in the negative ba kbone, a minimal vertex over of A does not

ontain v , hen e it ontains ea h vi . So the neighbors of verti es in G are in B. P P If v is in the positive ba kbone, 1 + ¯ i ) < i ni , whi h proves i min(ni , n the existen e of at least two distin t i's su h that ni = n ¯ i + 1. The orresponding Ai 's do not admit minimal overs ontaining vi . Sin e a minimal

over of A ontains v , it indu es a minimal over on these Ai 's : it does not

ontain the (at least two) orresponding vi 's. Hen e every vertex in B has at least two neighbors in G. This proves that (B, R, G) in (i) is a tri oloring whi h satises (iii) and we now ome to the proof of (iii) ⇒ (ii). 3.2 Let

Step 2

(B, R, G)

be a tri oloring of

R. R is a

A

satisfying

(iii).

Let

R

denote the set of

end-verti es of edges in If

B = G = ∅,

then

perfe t mat hing of the tree

admits at most one perfe t mat hing of

5

A.

,

R

A.

Be ause a tree

is the unique maximal mat hing

e0 = {g0 , b0 } is an edge of A (g0 ∈ G, b0 ∈ B ) and let M be a mat hing of A ontaining e0 . Obviously, there exist paths of the form g0 , b0 , · · · , gk , bk (k ≥ 0) su h that {gi , bi } ∈ M, gi ∈ G and bi ∈ B for all i. Take one with maximal length. Then bk has at least one neighbor gk+1 ∈ G \ {gk }, whi h is not the end of an edge in M (be ause our path is maximal, and all edges ending at gk+1 have the other end in B ). Now, we repla e in M the k + 1 edges {gi , bi } (0 ≤ i ≤ k ) by the k + 1 edges {bi , gi+1 }. This leads to a mat hing with same ardinality as M, but not

ontaining the edge {b0 , g0 }. Relax this assumption, suppose

As a rst onsequen e, there exist maximal maximal mat hings not on-

g ∈ G as an end-vertex (verti es in G are optional). Now, let b ∈ B and suppose M is a mat hing not ontaining b as an end-vertex. We show that M is not maximal. If some neighbor v of b is not the end-vertex of any taining

5 This

is lear by indu tion on the size of the tree, if we note that an edge ending at a leaf is ontained in any perfe t mat hing.

8

M we an append the edge {b, v} to M. On the other hand, suppose that some neighbor of b, g0 ∈ G, is the end of an edge in M. Then, we apply ′ the pro edure above to build a mat hing M of A with same ardinality as that of M, not ontaining g0 as an end-vertex. But these two mat hings

oin ide ex ept on some path g0 , b0 , · · · , gk , bk , gk+1 , whi h does not ontain b 6= b0 . Hen e, M′ does not ontain any edge ending at b or g0 , and we an append the edge {b, g0 }. Hen e verti es in B are unavoidable. edge in

Anti ipating the on lusion of this pragraph, let us all

the edges between two verti es in those edges not in

R

mat hing

p ≥ 1

B , between a vertex in B and one in R, and R. Deletion of the forbidden edges

(B, R, G) indu es form (∅, R ∩ Ei , ∅)

(iii), of the M indu es a

on ea h of these trees a tri oloring or

(B ∩ Vi , ∅, G ∩ Vi ).

mat hing on ea h of these trees and, if

forbidden edges, at least

ontain some vertex in

B

p+1

Moreover, a

M

ontains

R.

By the

of these indu ed mat hings do not

as an end-vertex or some edge in

pre eding remarks, they are not maximal. Hen e, by deleting from

p

M.

M

these

p + 1 mat hings by those of A ontaining at least one more

edges, and by repla ing the edges of these

maximal mat hings, we obtain a mat hing of edge than

edges

with both ends in

leaves some trees, and satisfying

forbidden

So a maximal mat hing does not ontain any forbidden edge

and, as an easy orollary, deletion of these edges leaves maximal mat hings of the resulting trees.

ˆ R, ˆ G) ˆ R are in the positive ba kbone of A. Denote by (B, ˆ R ⊂ the tri oloring of A dened by (ii) : we have proved that B ⊂ B, ˆ ˆ R, G ⊂ G. By general properties of tri olorings, this implies that (B, R, G) = ˆ R, ˆ G) ˆ and on ludes the proof of theorem 1. (B, Thus, edges in

Remark

Let us onsider a minimal vertex over

C

of

A.

It ontains all

NB (A) brown verti es of A and none of the green verti es. The other NR (A) verti es are ends of non-adja ent red edges, and we have seen that C ontains exa tly one end of ea h su h edge : hen e C ontains exa tly NB (A) + NR (A)/2 verti es. A maximal mat hing of A ontains all the NR (A)/2 red edges and exa tly the

one edge ending at ea h brown vertex, the other end being green (hen e not brown).

Moreover it does not ontain any other edge : hen e a maximal

mat hing of

A

ontains exa tly

NB (A) + NR (A)/2

lary 3.

9

edges. This proves orol-

4

Generating fun tions

4.1

Generating fun tion for b- olorings

Our purpose in this se tion is to give an exponential generating fun tion for the number of labeled trees with given olor distribution :

F (g, b, r) ≡ where

An

X X 1 g NG(A) bNB (A) r NR (A) n! n≥1 A∈A n

is the set of labeled trees on

n

verti es.

Re alling that a tree has a unique b- oloring, we say that a rooted tree has

olor

c

if its root has olor

c.

Let

G, B, R

be the (exponential) generating

fun tions for respe tively green, brown, red rooted trees. Let

A

be a rooted tree. Then

• A is green

if, and only if, its root is onne ted to the root of arbitrarily

many trees dened as follows : root adja ent to arbitrarily many rooted

olored trees, with the ondition that at least

one root be green.

all

their generating fun tion.

quasi-brown these trees and denote by U

Let us

Then

G = geU U = beB+R (eG − 1)

(1) (2)

• A is brown if, and only if, its root is onne ted to the root of arbitrarily many brown or red rooted trees and to at least

two

green rooted trees,

so

B = beB+R (eG − 1 − G) •

Finally,

(3)

A is red if, and only if, its root is onne ted to arbitrarily many

brown or red rooted trees and to exa tly one tree dened as follows : root adja ent to arbitrarily many red or brown rooted trees. Let us all

quasi-red

these trees and denote by

Q

their generating fun tion. Then

R = rQeB+R Q = reB+R 10

(4) (5)

Now, the generating fun tion F for olored trees is the only fun tion of = G, b ∂F = B , r ∂F = R and F (0, 0, 0) = 0. The g, b, r su h that g ∂F ∂g ∂b ∂r following F indeed satises these onditions, thus the generating fun tion for

olored trees is

1 F (g, b, r) = − ((B +R)2 +Q2 )−GU +beB+R (eG −1−G)+geU +rQeB+R 2

(6)

F (x, x, ba k the usual generating fun tion for Px) gives n−2 F0 (x) = n≥1 n n! xn . Re all that the generating fun tion T = xF0′ (x) for rooted trees veries T (x) = xeT (x) for |x| < 1/e. Putting S = B + R and taking g, b, r = x in the equations (3)+(4)-(2) and We he k that

labeled trees :

(5)-(1) yields

S − U = (Q − G)xeS Q − G = xeU (1 − eS−U ) x → 0,

S = U and G = Q, so (2)+(5) yields S + G = xe . Hen e S + G = S + Q = T (x), and it follows from (5) that Q S+Q Qe = xe = xeT (x) = T (x). Finally : Taking

this implies

S+G

S = U = T (x) + T (−T (x)) G = Q = −T (−T (x)) Inje t these into equal to

F (x, x, x)

to get

F0 (x).

Remark 7. Dene

F = T (x) − 12 T (x)2 ,

whi h is indeed

Sket h of the relation with Feynman graph enumeration.

S(S = B + R, U, G, Q, g, b, r)

by the right hand-side of eq.(6)

but seen as a fun tion of seven independent variables. Then the vanishing of the partial derivative of

S

with respe t to

S

leads to the ombination

eq.(3)+eq.(4), whereas the vanishing of the partial derivatives with respe t to

U, G

and

value of

S

Q

leads to eq.(1), eq.(2) and eq.(5) respe tively. Thus,

at the (unique in the small

apital variables.

g, b, r

F

is the

expansion) extremum in the

The same kind of onsiderations would apply to all the

generating fun tions in this paper We do not know if there is a simple ombinatorial explanation for this extremal property, but there is a simple physi al interpretation that we give 11

in appendix A to illustrate how two s ienti ommunities deal with the same problem.

The reader interested in a more thourough study of the

ombinatori s of Feynman graphs an onsult e.g. [10℄. The generating fun tion for the total number of verti es with a given

olor omes from dierentiation with respe t to the orresponding variable, followed by the identi ation

b=g=r=x

:

X NB (n)

xn = T (x) + T (−T (x)) − T (−T (x))2

X NG (n)

xn = −T (−T (x))

X NR (n)

xn = T (−T (x))2

n

n

n

n!

n!

n!

In order to give expli it formulæ for the average numbers of verti es of ea h 2

olor, we need to know the term of given degree in T (−T (x)) and T (−T (x)) . Writing these as ontours integrals along a small ontour surrounding 0 and t

hanging the integration variable x into −te yields

I dt −nt ′ (−1)n dx T (−T (x)) = e T (t) n+1 x n tn I I I dx dt −nt ′ (−1)n dt −nt 2 T (−T (x)) = 2 e T (t) − e T (t) , xn+1 n tn tn+1 I

from whi h follow both the losed forms and, by the steepest des ent method,

6

their large-size asymptoti s

l n X −l NB (n) 2 n ∼ 1 + T ′ (−1) + 2T (−1)) = 1+ −1 n−1 l n n l l=1 l n X −l n NG (n) ∼ T ′ (−1) = − n−1 l n n l=1 l n X −l NR (n) 1 n ∼ −2(T ′ (−1) + T (−1)) = −2 −1 n−1 l n n l l=1 6 In

this simple situation, we an pro eed naively to get the asymptoti s. For a more rigorous treatment in a similar but slightly more involded ontext, see e.g. [8℄. 12

4.2

Generating fun tion for minimal vertex overs

Let us dene a

C

overed tree

(A, C), where A is a rooted tree and

to be a pair

is a minimal vertex over of

A.

The generating fun tions for brown and

green overed trees are denoted respe tively by

B

and

G

in this se tion. For

red overed trees, it is useful to make the distin tion between the minimal

overs whi h ontain the root and those whi h do not : let us denote by

R+ , R−

the orresponding generating fun tions.

Consider a pair

(A, C),

where

subset of the set of verti es of

• (A, C)

A.

A

is a rooted tree with root

v

and

C

a

Then

is a green overed tree if, and only if,

arbitrarily many quasi-brown trees, and

C

v ∈ / C, v

is atta hed to

indu es on ea h of these

trees a vertex over with minimal ardinality among those ontaining the root.

• (A, C) is a brown overed

tree if, and only if,

v ∈ C, v

is atta hed to at

least 2 green trees and to arbitrarily many brown or red rooted trees,

and

C

• (A, C)

indu es on ea h of these trees a minimal vertex over. is a red overed tree if, and only if,

one quasi-red tree

Ai0

v

is atta hed to exa tly

and to arbitrarily many brown or red trees, and

(1) v ∈ C , v indu es a minimal (2) v ∈ / C , v indu es on ea h of the

one of two ex lusive assertions holds :

over on ea h of the atta hed tree;

atta hed trees a over with minimal ardinality among those ontaining the root. This leads to

B = b(eG − 1 − G)eB+R+ +R− R+ = rQ− eB+R+ +R− where the auxiliary fun tion

U, Q+ , Q−

G = geU R− = rQ+ eB+R+

are dened as

U ≡ b(eG − 1)eB+R+ +R− , Q+ ≡ reB+R− +R+ , Q− ≡ reB+R+ . The generating fun tion for overed rooted trees is

G + B + R+ + R−

and

Fvc = geU + b(eG − 1 − G)eB+R+ +R− + rQ− eB+R+ +R− + rQ+ eB+R+ 1 2 −GU − (B 2 + R+ ) − R+ R− − B(R+ + R− ) − Q+ Q− 2 13

turns out to be the only fun tion with orre t satisfying

b, r, g

partial derivatives

Fvc (0, 0, 0) = 0.

Let us identify b, r, g 2 2U +R

= x. Then B + R+ = U , G = Q− and R+ = R− ≡ R = x e = T (x2 e2U ). Hen e the losed formula for U is xUeU = xeU 2 2U (e − 1)T (x e ), and the expression for Fvc follows immediately. 4.3

Generating fun tion for maximal mat hings

We shall skip the details, the ru ial points being that

•

A maximal mat hing of a tree

A ontains all the

red edges and exa tly

one edge ending at ea h brown vertex, the other end being green. It does not ontain any other edge.

•

B − G, there exist maximal mat hings whi h do not g is optional). There also exist some whi h do

ontain it. Indeed, let e = {b, g} be an edge of A with b ∈ B, g ∈ G. There exists a maximal mat hing not ontaining g as an end vertex ′ and, as a maximal one, this mat hing ontains an edge e ending at b. ′ Just repla e e by e. Given an edge

ontain it (be ause

Then the generating fun tions for mat hed trees read

G+ = gU− eU+ B = bG− (eG+ +G− − 1)eB+R

G− = geU+ R = rQeB+R

where

U+ ≡ bG− eG+ +G− +B+R , U− ≡ b(eG+ +G− − 1)eB+R , Q ≡ reB+R The generating fun tion writes

Fm = gU− eU+ + geU+ + bG− (eG+ +G− − 1)eB+R + rQeB+R 1 1 −G+ U+ − G− (U+ + U− ) − (B + R)2 − Q2 . 2 2 b = r = g = x, we nd B+R = U+ ≡ U, Q = G− . 2 3U +xeU −x2 e2U and U = x e , as was to be proved. For

Remark 8.

Hen e,

G+ = U −x2 e2U

1 log Nvc (n), n1 log Nm (n) given analyti ally by n theorems 4,5 are di ult to onfront to numeri al simulations sampling the The quantities

14

nn−2

trees uniformly. They are typi al examples of non self-averaging quan-

tities. This means basi ally that a small fra tion of trees ontributes signifi antly to the average although it is unlikely to be visited in reasonable time by a Monte-Carlo algorithm sampling trees uniformly. A simpler task 1 is the numeri al estimation of < log Nvc (A) > or n1 < log Nm (A) >, a self n averaging quantity whi h answers the question : how many minimal vertex

overs or maximal mat hings does a typi al tree have. This question will be adressed analyti ally and numeri ally in a work to ome, again based on the use of b- olorings [9℄.

A A note on Feynman graphs In quantum eld theory, graph ounting o

urs for the following reasons. A physi al system is hara terized by an a tion denote dynami al variables and

gi

S(Ta , gi )

oupling onstants.

where the

The index

a

Ta 's

often

runs through a ontinuum, but for the present di ussion, we assume it to take a nite number of values.

This is the usual ase that there is only

a nite number of oupling onstants. The general stru ture of S is S = P P S0 + i gi Pi (Ta ) where S0 = − 12 a,b Cab Ta Tb is a quadrati form whi h we assume here to be nondegenerate and the Pi (Ta ) are analyti fun tions. The quantity to be omputed is the free energy

Z Y S(Ta , gi ) dTa √ √ , ~ log det C exp ~ 2π~ a

(7)

gi 's

are hoosen to en-

where the integration ontours and values of the

~

sure onvergen e of the integral, and the oupling onstants

gi

is Plank's onstant. Note that when

all vanish, this expression vanishes too.

The so-

alled semi- lassi al expansion expresses the free energy of the system as an n asymptoti expansion in powers of ~, the ~ term being omputable by denite rules from ertain non simple onne ted graphs, the so- alled Feynman graphs, with

n independent y les.

To understand the appearan e of graphs,

the easy way is to rst expand formally the integrand in (7) in powers of the oupling onstants and then the

Pi 's

in powers of the elds

Ta .

This

redu es the integral to integration of a monomial against a gaussian weight, and the ombinatori s of the result is obtained by repeated integration by parts, whi h amounts to pair su

essively and in all possible ways all pairs

15

of variables

Ta Tb

~(C −1 )ab .

in the monomial and repla e them by

In that

way, one an interpret the monomial in the Pi 's as verti es marked with the −1 elds they involve, and ~(C )ab is the weight for an edge of type ab between two verti es : all possible graphs that an be built in that way appear in the formal power series expansion of the integral. Taking the logarithm to

ompute the free energy amounts to keep only onne ted graphs as usual in

ombinatori s. To make this general idea on rete take the quadrati form is asso iated to the

1×1

S = −T 2 /2 + geT .

In that ase T identity matrix and e des ribes

verti es of arbitrary degree. The integral along the real axis with a purely imaginary small

g.

g

makes sense and on an ompute the asymptoti expansion at

The result is that

Z

dT S(T, g) X (g~−1)n n2 ~/2 √ exp ∼ e ~ n! 2π~ n≥0

On the other hand, if to an arbitrary graph (not ne essarily simple) on verti es, des ribed by a symmetri matrix

M = (mpq ),

n

one gives a weight

Y ~mpq Y 1 mpq ! p 2mpp p≤q whi h is essentially its symmetry fa tor, the sum over all graphs re onstru ts n2 ~/2 the fa tor e . 0 The lassi al limit orresponds to keeping only the ~ ontribution, i.e. trees. On the other hand, in the lassi al limit the system is de ribed by the

lassi al equations of motion, whi h say that the a tion

S

is extremal with

respe t to all eld variations : in the present ontext, this boils down to the stationary phase method. And indeed, for the on rete example above, this T extremum ondition leads to T = ge , so that T is the rooted labeled tree generating fun tion. We leave it to the reader to ompute the inverse of

C , to extra t the kinds

of verti es and edges that Feynman graphs produ e when

1 S(T, U, G, Q, g, b, r) = − (T 2 + Q2 ) − GU + beT (eG − 1 − G) + geU + rQeT 2 and retrieve in that way the onditions

(iii).

The main message is that, while for a ombinatorist eqs.(1,2,3,4,5) for rooted trees follow from routine arguments, for a quantum eld theorist it is 16

S(T, U, G, Q, g, b, r)

whi h omes immediately to mind to ount the desired

unrooted graphs and, at the extremum in

(T, U, G, Q),

trees.

Referen es [1℄ R. M. Karp, M. Sipser,

Maximum Mat hings in Sparse Random Graphs,

FOCS 1981: 364-375.

Maximum mat hings in sparse random graphs, Karp-Sipser revisited, Random Stru tures and Algorithms

[2℄ J. Aronson, A. Frieze and B.G. Pittel, 12 (1998), 111177.

Core per olation in random graphs : a riti al phenomena analysis, Eur. Phys. J. B 24 (2001), 339-352 , ond-mat/0102011.

[3℄ M. Bauer, O. Golinelli,

[4℄ A.M. Frieze,

On the independen e number of random graphs, Dis r. Math.

81 (1990), 171. [5℄ M. Bauer and O. Golinelli,

On the kernel of tree in iden e matri es, Jour-

nal of Integer Sequen es, Arti le 00.1.4, Vol. 3 (2000).

An exa tly solvable model with two ondu torinsulator transitions driven by impurities, Phys. Rev. Lett. 86, 2621-2624

[6℄ M. Bauer and O. Golinelli, (2001). [7℄ A. Meir and J.W. Moon,

On maximal independent sets of nodes in trees,

Journal of Graph Theory Vol 12 N

0

2, 265-283 (1988).

Asymptoti distribution and a multivariate Darboux method in enumeration problems, Journal of Combinatorial Theory, Ser. A67, 169-

[8℄ M. Drmota, 184 (1994).

[9℄ S. Coulomb, [10℄ C.

in preparation.

Itzykson

and

J.-B.

Zuber,

Hill,(1980).

17

Quantum Field Theory,

M Graw-