%%Page: 1 1
1 0 bop 300 171 a
 21313290 3196989 -1512980 22628925 41771417 29470228 startTexFig
 300 171 a%%BeginDocument: logo0014.ps
%!PS-Adobe-2.0
%%Title: logo0014.ps
%%Creator: fig2dev Version 3.2 Patchlevel 0-beta3
%%CreationDate: Thu Jan 27 17:17:39 2000
%%For: pope@fry.research.att.com (Sue Pope)
%%Orientation: Portrait
%%BoundingBox: -23 344 635 448
%%Pages: 1
%%BeginSetup
%%IncludeFeature: *PageSize Letter
%%EndSetup
%%Magnification: 1.0000
%%EndComments
/$F2psDict 200 dict def
$F2psDict begin
$F2psDict /mtrx matrix put
/col-1 {0 setgray} bind def
/col0 {0.000 0.000 0.000 srgb} bind def
/col1 {0.000 0.000 1.000 srgb} bind def
/col2 {0.000 1.000 0.000 srgb} bind def
/col3 {0.000 1.000 1.000 srgb} bind def
/col4 {1.000 0.000 0.000 srgb} bind def
/col5 {1.000 0.000 1.000 srgb} bind def
/col6 {1.000 1.000 0.000 srgb} bind def
/col7 {1.000 1.000 1.000 srgb} bind def
/col8 {0.000 0.000 0.560 srgb} bind def
/col9 {0.000 0.000 0.690 srgb} bind def
/col10 {0.000 0.000 0.820 srgb} bind def
/col11 {0.530 0.810 1.000 srgb} bind def
/col12 {0.000 0.560 0.000 srgb} bind def
/col13 {0.000 0.690 0.000 srgb} bind def
/col14 {0.000 0.820 0.000 srgb} bind def
/col15 {0.000 0.560 0.560 srgb} bind def
/col16 {0.000 0.690 0.690 srgb} bind def
/col17 {0.000 0.820 0.820 srgb} bind def
/col18 {0.560 0.000 0.000 srgb} bind def
/col19 {0.690 0.000 0.000 srgb} bind def
/col20 {0.820 0.000 0.000 srgb} bind def
/col21 {0.560 0.000 0.560 srgb} bind def
/col22 {0.690 0.000 0.690 srgb} bind def
/col23 {0.820 0.000 0.820 srgb} bind def
/col24 {0.500 0.190 0.000 srgb} bind def
/col25 {0.630 0.250 0.000 srgb} bind def
/col26 {0.750 0.380 0.000 srgb} bind def
/col27 {1.000 0.500 0.500 srgb} bind def
/col28 {1.000 0.630 0.630 srgb} bind def
/col29 {1.000 0.750 0.750 srgb} bind def
/col30 {1.000 0.880 0.880 srgb} bind def
/col31 {1.000 0.840 0.000 srgb} bind def

end
save
-517.0 907.0 translate
1 -1 scale

/cp {closepath} bind def
/ef {eofill} bind def
/gr {grestore} bind def
/gs {gsave} bind def
/sa {save} bind def
/rs {restore} bind def
/l {lineto} bind def
/m {moveto} bind def
/rm {rmoveto} bind def
/n {newpath} bind def
/s {stroke} bind def
/sh {show} bind def
/slc {setlinecap} bind def
/slj {setlinejoin} bind def
/slw {setlinewidth} bind def
/srgb {setrgbcolor} bind def
/rot {rotate} bind def
/sc {scale} bind def
/sd {setdash} bind def
/ff {findfont} bind def
/sf {setfont} bind def
/scf {scalefont} bind def
/sw {stringwidth} bind def
/tr {translate} bind def
/tnt {dup dup currentrgbcolor
  4 -2 roll dup 1 exch sub 3 -1 roll mul add
  4 -2 roll dup 1 exch sub 3 -1 roll mul add
  4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb}
  bind def
/shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul
  4 -2 roll mul srgb} bind def
 /DrawEllipse {
	/endangle exch def
	/startangle exch def
	/yrad exch def
	/xrad exch def
	/y exch def
	/x exch def
	/savematrix mtrx currentmatrix def
	x y tr xrad yrad sc 0 0 1 startangle endangle arc
	closepath
	savematrix setmatrix
	} def

/$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def
/$F2psEnd {$F2psEnteredState restore end} def
%%EndProlog

$F2psBegin
10 setmiterlimit
n -1000 10376 m -1000 -1000 l 20197 -1000 l 20197 10376 l cp clip
 0.06000 0.06000 sc
%%Page: 1 1
7.500 slw
% Ellipse
n 9113 8513 856 856 0 360 DrawEllipse gs col4 1.00 shd ef gr gs col4 s gr

% Ellipse
n 9113 8516 813 813 0 360 DrawEllipse gs col8 1.00 shd ef gr gs col8 s gr

% Ellipse
n 8502 8404 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr

% Ellipse
n 8901 9100 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr

% Ellipse
n 9731 8402 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr

% Ellipse
n 9518 8034 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr

% Ellipse
n 8706 8044 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr

% Ellipse
n 9105 7889 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr

% Ellipse
n 8569 8815 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr

% Ellipse
n 9662 8830 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr

% Ellipse
n 9339 9104 177 177 0 360 DrawEllipse gs col11 1.00 shd ef gr gs col11 s gr

% Ellipse
n 9120 8517 440 440 0 360 DrawEllipse gs col4 1.00 shd ef gr gs col4 s gr

% Ellipse
n 9518 8034 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr

% Ellipse
n 8705 8040 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr

% Ellipse
n 8569 8815 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr

% Ellipse
n 9105 7885 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr

% Ellipse
n 9662 8830 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr

% Ellipse
n 8500 8400 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr

% Ellipse
n 9339 9104 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr

% Ellipse
n 9731 8402 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr

% Ellipse
n 8901 9098 141 141 0 360 DrawEllipse gs col30 1.00 shd ef gr gs col30 s gr

/Times-Bold ff 225.00 scf sf
8897 9177 m
gs 1 -1 sc (23) dup sw pop 2 div neg 0 rm  col0 sh gr
/Times-Bold ff 225.00 scf sf
9338 9184 m
gs 1 -1 sc (11) dup sw pop 2 div neg 0 rm  col0 sh gr
/Times-Roman ff 480.00 scf sf
10275 8730 m
gs 1 -1 sc (Article 00.1.4) col0 sh gr
/Times-Roman ff 480.00 scf sf
10275 8175 m
gs 1 -1 sc (Journal of Integer Sequences, Vol. 3 \(2000\),) col0 sh gr
/Times-Bold ff 225.00 scf sf
9518 8117 m
gs 1 -1 sc (2) dup sw pop 2 div neg 0 rm  col0 sh gr
/Times-Bold ff 225.00 scf sf
9730 8481 m
gs 1 -1 sc (3) dup sw pop 2 div neg 0 rm  col0 sh gr
/Times-Bold ff 225.00 scf sf
9661 8911 m
gs 1 -1 sc (6) dup sw pop 2 div neg 0 rm  col0 sh gr
% Ellipse
n 8705 8042 42 42 0 360 DrawEllipse gs 0.00 setgray ef gr gs col0 s gr

% Polyline
n 9454 8322 m 9454 8321 l 9454 8315 l 9454 8304 l 9454 8290 l 9453 8278 l
 9452 8268 l 9450 8261 l 9448 8255 l 9444 8250 l 9440 8246 l
 9434 8242 l 9428 8238 l 9421 8236 l 9414 8234 l 9407 8233 l
 9399 8232 l 9392 8232 l 9383 8232 l 9374 8232 l 9365 8233 l
 9356 8235 l 9347 8237 l 9338 8239 l 9331 8242 l 9323 8245 l
 9316 8249 l 9308 8253 l 9301 8259 l 9294 8264 l 9288 8270 l
 9282 8276 l 9277 8281 l 9272 8287 l 9268 8293 l 9263 8300 l
 9259 8308 l 9256 8316 l 9252 8324 l 9250 8332 l 9248 8339 l
 9246 8348 l 9245 8356 l 9245 8366 l 9245 8377 l 9246 8388 l
 9249 8398 l 9252 8409 l 9256 8419 l 9260 8427 l 9265 8435 l
 9271 8444 l 9278 8453 l 9285 8462 l 9293 8471 l 9301 8480 l
 9309 8488 l 9317 8495 l 9325 8502 l 9335 8510 l 9346 8518 l
 9357 8525 l 9367 8533 l 9377 8540 l 9387 8546 l 9394 8552 l
 9401 8558 l 9406 8563 l 9410 8568 l 9413 8574 l 9415 8580 l
 9416 8586 l 9416 8592 l 9416 8598 l 9414 8604 l 9410 8612 l
 9405 8620 l 9398 8629 l 9390 8638 l 9381 8645 l 9373 8650 l
 9365 8654 l 9358 8656 l 9349 8658 l 9340 8659 l 9331 8659 l
 9322 8658 l 9314 8656 l 9306 8653 l 9296 8647 l 9285 8640 l
 9275 8632 l 9266 8626 l 9259 8622 l 9253 8621 l 9250 8623 l
 9247 8626 l 9246 8632 l 9244 8639 l 9244 8647 l 9244 8655 l
 9245 8663 l 9246 8670 l 9247 8676 l 9249 8683 l 9252 8689 l
 9255 8694 l 9260 8699 l 9264 8704 l 9270 8707 l 9275 8711 l
 9282 8713 l 9290 8715 l 9299 8718 l 9309 8719 l 9319 8720 l
 9329 8721 l 9338 8721 l 9348 8721 l 9356 8720 l 9365 8719 l
 9375 8717 l 9384 8714 l 9393 8712 l 9401 8708 l 9409 8705 l
 9416 8702 l 9424 8697 l 9433 8691 l 9441 8684 l 9448 8677 l
 9455 8669 l 9460 8662 l 9465 8654 l 9469 8646 l 9473 8636 l
 9476 8627 l 9479 8618 l 9481 8609 l 9483 8601 l 9484 8593 l
 9484 8583 l 9484 8574 l 9483 8565 l 9482 8557 l 9480 8548 l
 9477 8539 l 9472 8529 l 9468 8519 l 9463 8509 l 9458 8501 l
 9452 8493 l 9446 8485 l 9438 8477 l 9431 8470 l 9424 8463 l
 9417 8457 l 9409 8451 l 9401 8446 l 9393 8439 l 9384 8433 l
 9376 8427 l 9368 8422 l 9361 8415 l 9353 8408 l 9345 8401 l
 9337 8394 l 9331 8387 l 9327 8381 l 9323 8374 l 9320 8367 l
 9318 8360 l 9317 8355 l 9317 8350 l 9317 8345 l 9317 8341 l
 9318 8337 l 9319 8333 l 9319 8331 l 9320 8328 l 9321 8326 l
 9322 8323 l 9324 8321 l 9325 8319 l 9327 8317 l 9329 8314 l
 9331 8312 l 9333 8310 l 9336 8308 l 9337 8306 l 9339 8305 l
 9342 8304 l 9344 8303 l 9346 8303 l 9348 8302 l 9350 8302 l
 9352 8302 l 9355 8302 l 9357 8302 l 9360 8301 l 9362 8301 l
 9365 8300 l 9368 8300 l 9370 8300 l 9373 8300 l 9376 8300 l
 9379 8301 l 9382 8301 l 9384 8302 l 9387 8302 l 9389 8302 l
 9392 8303 l 9395 8304 l 9398 8305 l 9402 8307 l 9406 8310 l
 9410 8313 l 9414 8315 l 9417 8317 l 9420 8319 l 9422 8320 l
 9424 8321 l 9425 8323 l 9427 8324 l 9429 8325 l 9431 8327 l
 9434 8330 l 9436 8332 l 9439 8334 l 9440 8336 l 9442 8337 l
 9444 8338 l 9446 8339 l 9447 8339 l 9449 8338 l 9450 8336 l
 9452 8333 l 9454 8329 l 9455 8326 l 9456 8323 l 9456 8321 l
 9457 8320 l 9457 8318 l 9457 8317 l gs 0.00 setgray ef gr gs col0 s gr 
% Polyline
n 8771 8278 m 8802 8230 l 8990 8230 l 8975 8278 l 8975 8780 l 8912 8842 l
 8833 8842 l 8912 8780 l 8912 8278 l 8771 8278 l 8818 8262 l
 cp gs 0.00 setgray ef gr gs col0 s gr 
% Polyline
n 9069 8230 m 9178 8230 l 9163 8245 l 9147 8278 l 9147 8654 l 9178 8716 l
 9052 8716 l 9069 8701 l 9085 8654 l 9085 8623 l 9085 8278 l
 cp gs 0.00 setgray ef gr gs col0 s gr 
% Ellipse
n 8500 8402 42 42 0 360 DrawEllipse gs 0.00 setgray ef gr gs col0 s gr

/Times-Bold ff 225.00 scf sf
9097 7964 m
gs 1 -1 sc (1) dup sw pop 2 div neg 0 rm  col0 sh gr
/Times-Bold ff 225.00 scf sf
8567 8901 m
gs 1 -1 sc (47) dup sw pop 2 div neg 0 rm  col0 sh gr
$F2psEnd
rs
showpage

%%EndDocument

 endTexFig
 123 556 a Fy(On)32 b(the)g(k)m(ernel)h(of)g(tree)e(incidence)j
(matrices)639 791 y Fx(M.)20 b(Bauer)f(and)g(O.)h(Golinell)o(i)499
911 y Fw(Service)15 b(de)h(Ph)o(ysique)f(Th)o(\023)-23
b(eorique,)15 b(CEA)i(Sacla)o(y)l(,)629 969 y(F-91191,)h(Gif-sur-Yv)o
(ette,)d(F)l(rance.)195 1058 y(Email)f(addresses:)22
b(bauer@sph)o(t.sacla)o(y)l(.cea.fr)p
 [[209 463 333 475] [1 1 1 [3 3]] [0 0 1]] (mailto:bauer@spht.saclay.cea.fr) pdfm 
14 w(and)17 b(golinelli@sph)o(t.sacla)o(y)l(.cea.)o(fr)p
 [[359 463 494 475] [1 1 1 [3 3]] [0 0 1]] (mailto:golinelli@spht.saclay.cea.fr) pdfm 
868 1411 a Fv(Abstract)299 1469 y Fu(We)k(give)i(a)e(close)n(d)h(form,)
f(a)h(gener)n(ating)h(function,)g(and)f(an)f(asymptotic)228
1527 y(estimate)f(for)f(the)h(se)n(quenc)n(e)h Fw(\()p
Ft(z)829 1534 y Fs(n)852 1527 y Fw(\))871 1534 y Fs(n)p
Fr(\025)p Fq(1)957 1527 y Fw(=)c(1)p Ft(;)8 b Fw(0)p
Ft(;)g Fw(3)p Ft(;)g Fw(8)p Ft(;)g Fw(135)p Ft(;)g Fw(1164)p
Ft(;)g Fw(2)q(103)q(5)p Ft(;)g(:)g(:)g(:)30 b Fu(that)228
1585 y(gives)22 b(the)f(total)h(multiplicity)g(of)e(the)i(eigenvalue)h
Fw(0)f Fu(in)f(the)g(set)g(of)g Ft(n)1556 1567 y Fs(n)p
Fr(\000)p Fq(2)1646 1585 y Fu(tr)n(e)n(e)228 1644 y(incidenc)n(e)e
(matric)n(es)e(of)g(size)h Ft(n)p Fu(.)765 1772 y Fw(1.)27
b Fp(Intr)o(oduction.)278 1859 y Fw(By)13 b(a)i(classical)e(result)h
(in)f(graph)i(theory)l(,)f(the)g(n)o(um)o(b)q(er)e(of)j(lab)q(eled)e
(trees)1637 1841 y Fq(1)p
 (#Hfootnote.1) [[465 271 470 283] [1 1 1 [3 3]] [0 0 1]] pdfm 
1671 1859 a Fw(on)228 1918 y Ft(n)i Fo(\025)f Fw(1)j(v)o(ertices)e(is)i
Ft(n)622 1900 y Fs(n)p Fr(\000)p Fq(2)691 1918 y Fw(.)22
b(W)l(e)17 b(endo)o(w)g(the)f(set)h Fo(T)1151 1925 y
Fs(n)1192 1918 y Fw(of)g(lab)q(eled)f(trees)g(on)h Ft(n)e
Fo(\025)g Fw(1)228 1976 y(v)o(ertices)f(with)i(uniform)f(probabilit)o
(y)l(,)g(giving)h(w)o(eigh)o(t)f Ft(n)1285 1958 y Fq(2)p
Fr(\000)p Fs(n)1370 1976 y Fw(to)i(eac)o(h)f(tree.)278
2034 y(Eac)o(h)d(tree)f(in)h Fo(T)571 2041 y Fs(n)608
2034 y Fw(comes)f(with)h(its)g(incidence)e(matrix,)h(the)h
Ft(n)5 b Fo(\002)g Ft(n)13 b Fw(symmetric)228 2092 y(matrix)k(with)h
(en)o(try)g Ft(ij)j Fw(equal)d(to)i(1)f(if)f(there)g(is)g(an)h(edge)g
(b)q(et)o(w)o(een)f(v)o(ertices)f Ft(i)228 2150 y Fw(and)h
Ft(j)j Fw(and)e(to)f(0)h(otherwise.)26 b(Eac)o(h)18 b(suc)o(h)g(matrix)
e(has)j Ft(n)f Fw(\(real\))g(eigen)o(v)m(alues,)228 2208
y(whic)o(h)d(b)o(y)g(de\014nition)g(form)f(the)i(sp)q(ectrum)e(of)i
(the)f(corresp)q(onding)i(tree.)j(This)228 2266 y(leads)g(in)f(turn)h
(to)g Ft(n)8 b(n)655 2248 y Fs(n)p Fr(\000)p Fq(2)744
2266 y Fw(=)20 b Ft(n)831 2248 y Fs(n)p Fr(\000)p Fq(1)920
2266 y Fw(eigen)o(v)m(alues)f(coun)o(ted)g(with)h(m)o(ultiplic)o(it)n
(y)228 2324 y(for)14 b Fo(T)327 2331 y Fs(n)364 2324
y Fw(as)g(a)h(whole.)20 b(In)13 b(the)h(sequel,)f(w)o(e)g(will)f
(concen)o(trate)h(on)i(the)e(m)o(ultiplic)o(it)n(y)228
2383 y(of)i(the)g(eigen)o(v)m(alue)e(0.)21 b(Let)15 b
Ft(Z)t Fw(\()p Ft(T)7 b Fw(\))14 b(b)q(e)h(the)g(m)o(ultiplic)o(it)n(y)
d(of)j(the)g(eigen)o(v)m(alue)e(0)j(in)228 2441 y(the)g(sp)q(ectrum)f
(of)i(the)f(incidence)f(matrix)g(of)h(the)h(tree)e Ft(T)7
b Fw(,)16 b(i.e.)21 b(the)16 b(dimension)228 2499 y(of)e(the)g(k)o
(ernel.)19 b(F)l(or)14 b(eac)o(h)f Ft(n)h Fo(\025)g Fw(1,)g(the)g
(restriction)f Ft(Z)1211 2506 y Fs(n)1248 2499 y Fw(of)i
Ft(Z)j Fw(to)c Fo(T)1437 2506 y Fs(n)1475 2499 y Fw(is)f(a)i(random)p
228 2561 250 2 v 278 2593 a Fn(1)296 2608 y Fm(Precise)h(de\014nitions)
e(for)f(this)h(and)g(the)g(follo)o(wing)e(terms)h(can)h(b)q(e)h(found)e
(in)h(Section)g(2)p
 (#section.2) [[473 91 478 103] [1 1 1 [3 3]] [0 0 1]] pdfm (.)965
2658 y Fl(1)p eop
%%Page: 2 2
2 1 bop 228 116 a Fl(2)228 213 y Fw(v)m(ariable.)41 b(W)l(e)23
b(set)g Ft(z)647 220 y Fs(n)695 213 y Fw(=)759 175 y
Fk(P)811 227 y Fs(T)5 b Fr(2T)880 231 y Fj(n)911 213
y Ft(Z)944 220 y Fs(n)968 213 y Fw(\()p Ft(T)i Fw(\).)41
b(The)23 b(exp)q(ectation)g(of)g Ft(Z)1569 220 y Fs(n)1593
213 y Fw(\()p Ft(T)7 b Fw(\))22 b(is)228 275 y Fi(E)t
Fw(\()p Ft(Z)310 282 y Fs(n)337 275 y Fw(\))14 b(=)f
Ft(z)444 282 y Fs(n)468 275 y Ft(=n)521 257 y Fs(n)p
Fr(\000)p Fq(2)590 275 y Fw(.)278 333 y(T)l(o)23 b(illustrate)f(these)g
(de\014nitions,)i(w)o(e)e(giv)o(e)g(an)h(explicit)e(en)o(umeration)g
(of)228 391 y Ft(z)251 398 y Fq(1)270 391 y Ft(;)8 b
Fo(\001)g(\001)g(\001)17 b Ft(;)8 b(z)412 398 y Fq(4)447
391 y Fw(in)16 b(App)q(endix)g(A)p
 (#section.A) [[247 623 256 635] [1 1 1 [3 3]] [0 0 1]] pdfm (.)278
485 y(Our)g(aim)f(is)h(to)g(pro)o(v)o(e)g(:)228 579 y
Fv(Theorem)g(1.)24 b Fu(L)n(et)17 b Ft(z)640 586 y Fs(n)680
579 y Fu(b)n(e)g(the)g(total)h(multiplicity)g(of)e(the)i(eigenvalue)h
Fw(0)f Fu(in)f(the)228 637 y(sp)n(e)n(ctr)n(a)f(of)h(the)h
Ft(n)556 619 y Fs(n)p Fr(\000)p Fq(2)642 637 y Fu(lab)n(ele)n(d)h(tr)n
(e)n(es)e(on)h Ft(n)f Fu(vertic)n(es.)23 b(Then)18 b(:)278
695 y(i\))f(Close)n(d)g(form)g(:)405 817 y Ft(z)428 824
y Fs(n)493 817 y Fw(=)42 b Ft(n)602 797 y Fs(n)p Fr(\000)p
Fq(1)682 817 y Fo(\000)11 b Fw(2)791 770 y Fk(X)764 875
y Fq(2)p Fr(\024)p Fs(m)p Fr(\024)p Fs(n)890 817 y Fw(\()p
Fo(\000)p Fw(1\))991 797 y Fs(m)1024 817 y Ft(n)1053
797 y Fs(n)p Fr(\000)p Fs(m)1135 817 y Ft(m)1178 797
y Fs(m)p Fr(\000)p Fq(2)1256 747 y Fk(\022)1300 784 y
Ft(n)g Fo(\000)g Fw(1)1293 852 y Ft(m)g Fo(\000)f Fw(1)1421
747 y Fk(\023)374 958 y Ft(z)397 965 y Fs(n)p 349 980
98 2 v 349 1026 a Ft(n)378 1012 y Fs(n)p Fr(\000)p Fq(2)493
992 y Fo(\021)41 b Fi(E)t Fw(\()p Ft(Z)656 999 y Fs(n)682
992 y Fw(\))28 b(=)f Ft(n)831 907 y Fk( )871 992 y Fw(1)12
b Fo(\000)f Fw(2)1016 944 y Fk(X)989 1050 y Fq(2)p Fr(\024)p
Fs(m)p Fr(\024)p Fs(n)1128 958 y Fw(\()p Fo(\000)p Fw(1\))1229
940 y Fs(m)p 1128 980 135 2 v 1174 1026 a Ft(m)1275 936
y Fk(\020)1310 958 y Ft(m)p 1310 980 43 2 v 1317 1026
a(n)1358 936 y Fk(\021)1387 948 y Fs(m)1429 921 y Fk(\022)1472
958 y Ft(n)1466 1026 y(m)1508 921 y Fk(\023)1545 907
y(!)1593 992 y Ft(:)278 1135 y Fu(ii\))17 b(F)l(ormal)g(p)n(ower)g
(series)h(identity)g(:)588 1240 y Ft(x)616 1219 y Fq(2)646
1240 y Fw(+)11 b(2)p Ft(x)h Fo(\000)e Ft(xe)859 1219
y Fs(x)895 1240 y Fw(=)946 1192 y Fk(X)949 1298 y Fs(n)p
Fr(\025)p Fq(1)1032 1206 y Ft(z)1055 1213 y Fs(n)p 1032
1228 47 2 v 1034 1274 a Ft(n)p Fw(!)1091 1199 y Fk(\000)1114
1240 y Ft(xe)1165 1219 y Fs(x)1186 1240 y Ft(e)1209 1219
y Fr(\000)p Fs(xe)1272 1207 y Fj(x)1294 1199 y Fk(\001)1317
1210 y Fs(n)1349 1240 y Ft(:)228 1423 y Fv(Corollary)19
b(2.)k Fu(F)l(or)15 b(lar)n(ge)g Ft(n)p Fu(,)h Fi(E)t
Fw(\()p Ft(Z)891 1430 y Fs(n)918 1423 y Fw(\))e Fu(has)h(an)g
(asymptotic)g(exp)n(ansion)h(in)f(p)n(ow-)228 1481 y(ers)i(of)g
Fw(1)p Ft(=n)i Fu(whose)f(\014rst)f(two)h(terms)f(ar)n(e)504
1604 y Fi(E)t Fw(\()p Ft(Z)587 1611 y Fs(n)613 1604 y
Fw(\))d(=)g(\(2)p Ft(x)769 1611 y Fr(\003)800 1604 y
Fo(\000)d Fw(1\))p Ft(n)g Fw(+)987 1570 y Ft(x)1015 1552
y Fq(2)1015 1582 y Fr(\003)1035 1570 y Fw(\()p Ft(x)1082
1577 y Fr(\003)1112 1570 y Fw(+)g(2\))p 987 1592 218
2 v 1001 1638 a(\()p Ft(x)1048 1645 y Fr(\003)1078 1638
y Fw(+)g(1\))1170 1623 y Fq(3)1220 1604 y Fw(+)g Ft(O)q
Fw(\(1)p Ft(=n)p Fw(\))d Ft(;)228 1722 y Fu(wher)n(e)23
b Ft(x)399 1729 y Fr(\003)441 1722 y Fw(=)h(0)p Ft(:)p
Fw(5671432904)q(097)q(83)q(872)q(999)q(9)9 b Fo(\001)f(\001)g(\001)34
b Fu(is)22 b(the)h(unique)h(r)n(e)n(al)e(r)n(o)n(ot)f(of)228
1780 y Ft(x)d Fw(=)g Ft(e)353 1762 y Fr(\000)p Fs(x)402
1780 y Fu(.)29 b(In)20 b(p)n(articular,)g(the)g(aver)n(age)g(fr)n
(action)g(of)f(the)h(sp)n(e)n(ctrum)g(o)n(c)n(cupie)n(d)228
1838 y(by)e(the)h(eigenvalue)j Fw(0)d Fu(in)g(a)f(lar)n(ge)h(r)n(andom)
e(tr)n(e)n(e)h(is)h(asymptotic)f(to)h Fw(2)p Ft(x)1562
1845 y Fr(\003)1593 1838 y Fo(\000)12 b Fw(1)k(=)228
1896 y(0)p Ft(:)p Fw(1342865808)q(195)q(67)q(745)q(999)q(9)9
b Fo(\001)f(\001)g(\001)j Fu(.)228 2027 y Fv(Remark)16
b(3.)24 b Fw(W)l(e)17 b(do)h(not)f(try)g(to)h(sho)o(w)g(here)e(that)i
(the)f(\015uctuations)h(in)e(ran-)228 2085 y(dom)c(trees)g(b)q(ecome)g
(small)f(when)i(the)f(n)o(um)o(b)q(er)g(of)h(v)o(ertices)e(is)h(large.)
20 b(Ho)o(w)o(ev)o(er,)228 2144 y(it)13 b(is)g(exp)q(ected)f(that)i
Fi(E)t Fw(\()p Ft(Z)710 2125 y Fq(2)706 2156 y Fs(n)732
2144 y Fw(\))5 b Fo(\000)g Fi(E)t Fw(\()p Ft(Z)883 2151
y Fs(n)909 2144 y Fw(\))928 2125 y Fq(2)961 2144 y Fw(gro)o(ws)15
b(only)e(linearly)f(with)h(the)g(n)o(um)o(b)q(er)228
2202 y(of)h(v)o(ertices,)e(so)i(that)g(in)g(an)g(appropriate)g(sense)g
(the)f(fraction)h(of)g(the)f(sp)q(ectrum)228 2260 y(o)q(ccupied)i(b)o
(y)f(the)h(eigen)o(v)m(alue)f(0)i(in)f(an)h(in\014nite)e(random)h(tree)
f(is)h(2)p Ft(x)1511 2267 y Fr(\003)1540 2260 y Fo(\000)9
b Fw(1)15 b(with)228 2318 y(probabilit)o(y)g(1.)228 2449
y Fv(Remark)h(4.)24 b Fw(With)15 b(the)g(explicit)e(form)o(ula)g(ab)q
(o)o(v)o(e,)i(it)g(is)f(easy)h(to)h(list)e(the)h(\014rst)228
2507 y(terms)g(in)g(the)h(sequence)g(\()p Ft(z)749 2514
y Fs(n)772 2507 y Fw(\))791 2514 y Fs(n)p Fr(\025)p Fq(1)859
2507 y Fw(,)g(whic)o(h)g(are)236 2598 y(1)p Ft(;)8 b
Fw(0)p Ft(;)g Fw(3)p Ft(;)g Fw(8)p Ft(;)g Fw(135)p Ft(;)g
Fw(1164)q Ft(;)g Fw(210)q(35)q Ft(;)g Fw(322)q(832)q
Ft(;)g Fw(704)q(09)q(43)p Ft(;)g Fw(1)q(531)q(53)q(620)q
Ft(;)g Fw(404)q(873)q(70)q(99)p Ft(;)g Fo(\001)g(\001)h(\001)p
eop
%%Page: 3 3
3 2 bop 1703 116 a Fl(3)278 213 y Fw(T)l(o)13 b(pro)o(v)o(e)f(part)h
(i\))f(of)h(Theorem)e(1)p
 (#theo.1) [[282 666 288 678] [1 1 1 [3 3]] [0 0 1]] pdfm 
13 w(w)o(e)h(establish)g(a)h(few)g(preparatory)g(lemmas)228
271 y(of)e(indep)q(enden)o(t)g(in)o(terest.)18 b(Then)11
b(w)o(e)g(pro)o(v)o(e)f(ii\))g(using)i(Lagrange)h(in)o(v)o(ersion)d
(and)228 329 y(obtain)17 b(Corollary)f(2)p
 (#theo.2) [[215 638 221 650] [1 1 1 [3 3]] [0 0 1]] pdfm 
17 w(b)o(y)f(the)h(steep)q(est)h(descen)o(t)e(metho)q(d.)278
387 y(There)e(is)g(an)h(application)f(of)g Ft(Z)861 394
y Fs(n)899 387 y Fw(to)g(random)g(graph)i(theory)e(|)g(see)g(Remark)228
445 y(22)p  (#theo.22) [[127 610 138 622] [1 1 1 [3 3]] [0 0 1]] pdfm 
(.)791 587 y(2.)28 b Fp(Definitions.)278 674 y Fw(Ev)o(en)12
b(if)h(ultimately)e(w)o(e)i(are)g(in)o(terested)f(only)h(in)g(trees,)g
(w)o(e)g(shall)h(need)f(more)228 732 y(general)j(graphs)h(\(for)g
(instance,)e(forests\))i(in)f(the)g(pro)q(ofs.)228 819
y Fv(De\014nition)21 b(5)p Fw(.)29 b(A)19 b Fu(simple)h(gr)n(aph)i
Ft(G)d Fw(is)g(a)h(pair)f(\()p Ft(V)s(;)8 b(E)s Fw(\))19
b(where)f Ft(V)31 b Fw(is)18 b(a)i(\014nite)228 879 y(set)d(called)g
(the)g(set)h(of)g Fu(vertic)n(es)23 b Fw(and)18 b Ft(E)i
Fw(is)e(a)g(subset)g(of)g Ft(V)1338 861 y Fq(\(2\))1402
879 y Fo(\021)e(f)8 b(f)p Ft(x;)g(y)r Fo(g)p Ft(;)15
b(x)h Fo(2)228 937 y Ft(V)s(;)g(y)g Fo(2)e Ft(V)s(;)i(x)d
Fo(6)p Fw(=)h Ft(y)r Fo(g)i Fw(called)f(the)h(set)g(of)h
Fu(e)n(dges)p Fw(.)228 1062 y Fv(Remark)f(6.)24 b Fw(The)f(adjectiv)o
(e)d Fu(simple)27 b Fw(refers)21 b(to)i(the)f(fact)g(that)h(there)f(is)
g(at)228 1120 y(most)13 b Fu(one)18 b Fw(edge)13 b(b)q(et)o(w)o(een)g
(t)o(w)o(o)g(v)o(ertices)f(and)i(that)g(edges)g(are)g(pairs)f(of)h
Fu(distinct)228 1179 y Fw(v)o(ertices.)19 b(F)l(rom)c(no)o(w)i(on)g(w)o
(e)e(use)i Fu(gr)n(aph)i Fw(for)d Fu(simple)i(gr)n(aph)p
Fw(.)228 1304 y Fv(De\014nition)h(7)p Fw(.)24 b(If)17
b Ft(V)29 b Fw(is)17 b(empt)o(y)l(,)e(then)i(w)o(e)g(sa)o(y)g(that)h
(the)f(graph)i Ft(G)e Fw(is)h Fu(empty)p Fw(.)228 1362
y(The)d(v)o(ertices)e(adjacen)o(t)i(to)h(a)f(giv)o(en)f(v)o(ertex)g
Ft(x)h Fw(are)g(called)f(the)h Fu(neighb)n(ors)20 b Fw(of)15
b Ft(x)p Fw(.)228 1420 y(The)g(n)o(um)o(b)q(er)f(of)i(neigh)o(b)q(ors)g
(of)g(a)g(v)o(ertex)e Ft(x)i Fw(is)f(called)g(the)g Fu(de)n(gr)n(e)n(e)
k Fw(of)d Ft(x)p Fw(.)21 b(A)15 b Fu(le)n(af)228 1478
y Fw(of)f Ft(G)h Fw(is)f(a)h(v)o(ertex)e(of)h(degree)g(1.)21
b(Tw)o(o)15 b(edges)f(of)h Ft(G)f Fw(with)h(a)f(common)e(v)o(ertex)h
(are)228 1536 y(called)i Fu(adjac)n(ent)j(e)n(dges)228
1653 y Fv(De\014nition)c(8)p Fw(.)21 b(A)13 b Fu(lab)n(ele)n(d)20
b Fw(graph)14 b(on)g Ft(n)g Fo(\025)g Fw(1)g(v)o(ertices)d(is)j(a)g
(graph)g(with)g(v)o(ertex)228 1712 y(set)i([)p Ft(n)p
Fw(])d(=)h Fo(f)p Fw(1)p Ft(;)8 b Fo(\001)g(\001)g(\001)17
b Ft(;)8 b(n)p Fo(g)p Fw(.)228 1837 y Fv(Remark)16 b(9.)24
b Fw(If)19 b(the)g(graph)i Ft(G)f Fw(has)g Fo(j)p Ft(V)11
b Fo(j)19 b Fw(=)g Ft(n)h Fo(\025)f Fw(1)g(v)o(ertices)1392
1819 y Fq(2)p
 (#Hfootnote.2) [[406 276 410 288] [1 1 1 [3 3]] [0 0 1]] pdfm 
18 x Fw(,)h(an)o(y)f(bijection)228 1895 y(b)q(et)o(w)o(een)i
Ft(V)33 b Fw(and)22 b([)p Ft(n)p Fw(])g(de\014nes)f(a)i(lab)q(eled)e
(graph.)39 b(The)22 b(incidence)e(matrices)228 1953 y(for)i(di\013eren)
o(t)e(bijections)h(di\013er)g(only)g(b)o(y)g(a)h(p)q(erm)o(utation)f
(of)g(the)h(ro)o(ws)g(and)228 2011 y(columns.)d(In)12
b(particular)g(the)g(eigen)o(v)m(alues)g(are)h(indep)q(enden)o(t)e(of)i
(the)g(bijection.)228 2136 y Fv(De\014nition)26 b(10)p
Fw(.)44 b(The)24 b Fu(sp)n(e)n(ctrum)i Fw(of)f(a)f(graph)g(is)g(the)f
(set)h(of)g(eigen)o(v)m(alues)228 2195 y(\(coun)o(ted)13
b(with)h(m)o(ultipli)o(cit)n(y\))d(of)j(an)o(y)f(of)h(the)g(asso)q
(ciated)h(incidence)d(matrices.)228 2253 y(By)j(con)o(v)o(en)o(tion,)g
(the)h(sp)q(ectrum)f(of)h(the)g(empt)o(y)e(graph)k(is)e(empt)o(y)l(.)
228 2370 y Fv(De\014nition)k(11)p Fw(.)27 b(A)17 b Fu(sub)n(gr)n(aph)22
b Fw(of)c(a)h(graph)g Ft(G)e Fw(=)g(\()p Ft(V)s(;)8 b(E)s
Fw(\))19 b(is)f(a)g(graph)h(\()p Ft(W)o(;)8 b(F)f Fw(\))228
2428 y(suc)o(h)18 b(that)h Ft(W)25 b Fo(\032)18 b Ft(V)30
b Fw(and)19 b Ft(F)25 b Fo(\032)18 b Ft(E)s Fw(.)28 b(An)19
b Fu(induc)n(e)n(d)h(sub)n(gr)n(aph)h Fw(of)e Ft(G)h
Fw(is)e(a)h(graph)228 2486 y(\()p Ft(W)o(;)8 b(F)f Fw(\))15
b(suc)o(h)h(that)h Ft(W)j Fo(\032)14 b Ft(V)27 b Fw(and)17
b Ft(F)j Fw(=)14 b Ft(E)g Fo(\\)e Ft(W)1124 2468 y Fq(\(2\))1171
2486 y Fw(.)p 228 2561 250 2 v 278 2593 a Fn(2)296 2608
y Fm(F)m(or)i(an)o(y)f(\014nite)h(set)h Fh(S)i Fm(,)c
Fg(j)p Fh(S)r Fg(j)h Fm(is)g(the)g(n)o(um)o(b)q(er)f(of)h(elemen)o(ts)f
(in)h Fh(S)r Fm(.)p eop
%%Page: 4 4
4 3 bop 228 116 a Fl(4)228 213 y Fv(De\014nition)15 b(12)p
Fw(.)21 b(W)l(e)14 b(sa)o(y)g(that)h(t)o(w)o(o)f(v)o(ertices)e
Ft(x)i Fw(and)h Ft(x)1273 195 y Fr(0)1298 213 y Fo(2)f
Ft(V)26 b Fw(are)14 b(in)g(the)g Fu(same)228 271 y(c)n(omp)n(onent)23
b Fw(of)c Ft(G)g Fw(if)f(there)g(is)g(a)h(sequence)e
Ft(x)g Fw(=)h Ft(x)1192 278 y Fq(1)1211 271 y Ft(;)8
b Fo(\001)g(\001)g(\001)17 b Ft(;)8 b(x)1358 278 y Fs(n)1398
271 y Fw(=)18 b Ft(x)1482 253 y Fr(0)1512 271 y Fw(in)g
Ft(V)29 b Fw(suc)o(h)228 329 y(that)19 b(adjacen)o(t)g(terms)e(in)i
(the)g(sequence)e(are)i(adjacen)o(t)g(in)g Ft(G)g Fw(\(taking)g
Ft(n)g Fw(=)f(1)228 387 y(sho)o(ws)j(that)h(luc)o(kily)c
Ft(x)j Fw(and)g Ft(x)g Fw(are)f(in)h(the)f(same)g(comp)q(onen)o(t\).)34
b(This)21 b(giv)o(es)228 445 y(a)e(partition)g(of)g Ft(V)12
b Fw(.)29 b(Eac)o(h)19 b(comp)q(onen)o(t)f(de\014nes)h(an)g(induced)f
(subgraph)i(of)g Ft(G)228 503 y Fw(whic)o(h)d(is)h(called)f(a)i
Fu(c)n(onne)n(cte)n(d)h(c)n(omp)n(onent)j Fw(of)c Ft(G)p
Fw(.)27 b(Then)18 b Ft(G)h Fw(can)f(b)q(e)h(though)o(t)228
561 y(of)c(as)h(the)f(disjoin)o(t)f(union)i(of)f(its)g(connected)f
(comp)q(onen)o(ts.)20 b(W)l(e)15 b(sa)o(y)g(that)h Ft(G)f
Fw(is)228 619 y Fu(c)n(onne)n(cte)n(d)22 b Fw(if)16 b(it)g(has)h(only)f
(one)g(connected)g(comp)q(onen)o(t.)228 737 y Fv(De\014nition)k(13)p
Fw(.)28 b(A)18 b Fu(p)n(olygon)k Fw(in)c(a)h(graph)g
Ft(G)g Fw(is)f(a)h(sequence)e Ft(x)1450 744 y Fq(0)1470
737 y Ft(;)8 b(x)1520 744 y Fq(1)1539 737 y Ft(;)g Fo(\001)g(\001)g
(\001)17 b Ft(;)8 b(x)1686 744 y Fs(n)1709 737 y Fw(,)228
795 y Ft(n)14 b Fo(\025)f Fw(3)i(of)f(v)o(ertices)f(suc)o(h)g(that)i
(adjacen)o(t)f(terms)f(in)g(the)h(sequence)f(are)h(adjacen)o(t)228
853 y(in)i Ft(G)p Fw(,)g Ft(x)381 860 y Fq(0)414 853
y Fw(=)e Ft(x)494 860 y Fs(n)533 853 y Fw(and)j Ft(x)656
860 y Fq(1)676 853 y Ft(;)8 b Fo(\001)g(\001)g(\001)16
b Ft(;)8 b(x)822 860 y Fs(n)862 853 y Fw(are)16 b(distinct.)228
970 y Fv(De\014nition)24 b(14)p Fw(.)39 b(A)22 b Fu(for)n(est)27
b Fw(is)22 b(a)g(graph)h(without)g(p)q(olygons.)40 b(A)22
b Fu(tr)n(e)n(e)k Fw(is)c(a)228 1028 y(non-empt)o(y)15
b(connected)g(forest.)228 1148 y Fv(Remark)h(15.)24 b
Fw(Clearly)13 b(a)i(subgraph)g(of)f(a)h(forest)f(is)g(a)g(forest.)21
b(The)14 b(connected)228 1206 y(comp)q(onen)o(ts)f(of)i(a)f(nonempt)o
(y)f(forest)h(are)g(trees.)20 b(One)14 b(sho)o(ws)h(easily)e(that)i
(that)228 1264 y(a)23 b(tree)f(with)h Ft(n)j Fo(\025)f
Fw(2)e(v)o(ertices)e(has)j(at)f(least)g(t)o(w)o(o)g(lea)o(v)o(es.)40
b(Then)23 b(a)g(simple)228 1322 y(induction)15 b(sho)o(ws)h(that)f(a)h
(tree)f(is)g(exactly)f(a)h(connected)g(graph)h(for)g(whic)o(h)e(the)228
1380 y(n)o(um)o(b)q(er)h(of)j(v)o(ertices)d(is)i(1)g(plus)g(the)g(n)o
(um)o(b)q(er)e(of)j(edges.)24 b(A)16 b(classical)h(theorem)228
1438 y(of)f(Ca)o(yley)g(states)g(that)h(there)f(are)g
Ft(n)924 1420 y Fs(n)p Fr(\000)p Fq(2)1009 1438 y Fw(lab)q(eled)g
(trees)g(on)h Ft(n)f Fw(v)o(ertices\(see)e(for)228 1497
y(instance)i(Prop)q(osition)h(5.3.2)g(in)f([3)p
 (#cite.stanley) [[280 358 286 370] [1 1 1 [3 3]] [0 0 1]] pdfm (]\).)
611 1611 y(3.)28 b Fp(Tw)o(o)18 b(prep)m(ara)m(tor)m(y)e(lemmas.)278
1698 y Fw(The)g(\014rst)h(lemma)d(is)i(a)h(c)o(haracterization)f(of)g
(the)h(dimension)e(of)i(the)f(k)o(ernel)228 1756 y(of)g(incidence)f
(matrices)f(view)o(ed)h(as)i(a)f(function)h(on)f(forests.)228
1846 y Fv(Lemm)o(a)g(16.)24 b Fu(The)18 b(function)g
Ft(Z)j Fu(which)d(asso)n(ciates)f(to)h(any)f(for)n(est)f(the)i(multi-)
228 1904 y(plicity)j(of)f(the)i(eigenvalue)h Fw(0)e Fu(in)g(its)g(sp)n
(e)n(ctrum)f(is)g(char)n(acterize)n(d)h(by)f(the)h(fol-)228
1962 y(lowing)e(pr)n(op)n(erties)d(:)278 2021 y(i\))h(The)h(function)g
Ft(Z)k Fu(takes)c(the)g(value)h Fw(0)f Fu(on)f Fo(;)p
Fu(,)h(the)g(empty)f(for)n(est.)278 2079 y(ii\))d(The)h(function)h
Ft(Z)j Fu(takes)c(the)g(value)h Fw(1)f Fu(on)1128 2070
y Ff(q)1149 2079 y Fu(,)g(the)g(for)n(est)f(with)h(one)h(vertex.)278
2137 y(iii\))21 b(The)h(function)h Ft(Z)j Fu(is)c(additive)g(on)g
(disjoint)g(c)n(omp)n(onents,)h(i.e.)36 b(if)22 b(the)228
2195 y(for)n(est)e Ft(F)27 b Fu(is)21 b(the)g(union)h(of)f(two)g
(disjoint)g(for)n(ests)f Ft(F)1229 2202 y Fq(1)1269 2195
y Fu(and)h Ft(F)1399 2202 y Fq(2)1439 2195 y Fu(then)h
Ft(Z)t Fw(\()p Ft(F)7 b Fw(\))19 b(=)228 2253 y Ft(Z)t
Fw(\()p Ft(F)316 2260 y Fq(1)335 2253 y Fw(\))11 b(+)g
Ft(Z)t Fw(\()p Ft(F)502 2260 y Fq(2)521 2253 y Fw(\))278
2311 y Fu(iv\))19 b(The)g(function)i Ft(Z)i Fu(is)c(invariant)h(under)f
(\\le)n(af)g(r)n(emoval",)h(i.e.)27 b(if)19 b Ft(x)g
Fu(is)g(a)228 2369 y(le)n(af)j(of)g Ft(F)7 b Fu(,)23
b Ft(y)h Fu(is)e(its)g(\(unique\))i Ft(neig)r(hbor)q
Fu(,)f Ft(V)1107 2351 y Fr(0)1142 2369 y Fw(=)f Ft(V)12
b Fo(nf)p Ft(x;)c(y)r Fo(g)p Fu(,)22 b(and)g Ft(F)1568
2351 y Fr(0)1602 2369 y Fu(is)g(the)228 2427 y(subfor)n(est)17
b(of)g Ft(F)24 b Fu(induc)n(e)n(d)18 b(by)f Ft(V)822
2409 y Fr(0)851 2427 y Fu(then)h Ft(Z)t Fw(\()p Ft(F)7
b Fw(\))13 b(=)h Ft(Z)t Fw(\()p Ft(F)1233 2409 y Fr(0)1244
2427 y Fw(\))p Fu(.)228 2550 y Fv(Remark)i(17.)24 b Fw(That)f(the)g
(function)f Ft(Z)27 b Fw(satis\014es)22 b(prop)q(erties)h(i\){iv\))f(w)
o(as)h(no)228 2608 y(doubt)15 b(kno)o(wn)f(decades)g(ago)i(\(see)d(for)
i(instance)f(Section)f(8.1,)i(H)q(\177)-26 b(uc)o(k)o(els)13
b(theory)l(,)p eop
%%Page: 5 5
5 4 bop 1703 116 a Fl(5)228 213 y Fw(in)18 b([1)p
 (#cite.cvetkovic) [[144 666 150 678] [1 1 1 [3 3]] [0 0 1]] pdfm 
(]\).)27 b(W)l(e)18 b(giv)o(e)f(a)i(pro)q(of,)g(b)q(ecause)g(in)f(the)g
(sequel)f(w)o(e)h(w)o(an)o(t)g(to)h(emphasize)228 271
y(and)d(use)g(the)f(simple)f(fact)i(that)g(these)f(prop)q(erties)h(c)o
(haracterize)e(the)h(function)228 329 y Ft(Z)t Fw(.)278
418 y Fu(Pr)n(o)n(of)j(of)i(L)n(emma)f(16)p
 (#theo.16) [[227 617 239 629] [1 1 1 [3 3]] [0 0 1]] pdfm 
Fw(.)29 b(First,)19 b(w)o(e)g(sho)o(w)g(that)h(the)f(function)g
Ft(Z)k Fw(has)c(prop-)228 476 y(erties)d(i\){iv\).)23
b(In)17 b(fact,)g(this)g(is)g(true)g(for)g(general)g(graphs)i(\(not)e
(only)g(forests\).)228 534 y(Prop)q(erties)12 b(i\))g(and)h(ii\))f
(follo)o(w)g(from)f(the)h(de\014nition)g(of)h Ft(Z)t
Fw(,)g(prop)q(ert)o(y)f(iii\))f(follo)o(ws)228 592 y(from)j(the)h(fact)
g(that)h(the)f(incidence)e(matrix)h(can)h(b)q(e)g(put)h(in)o(to)f(blo)q
(c)o(k)f(diagonal)228 650 y(form,)k(eac)o(h)h(blo)q(c)o(k)f(corresp)q
(onding)i(to)g(a)f(connected)f(comp)q(onen)o(t.)29 b(Prop)q(ert)o(y)228
708 y(iv\))16 b(is)g(only)g(sligh)o(tly)f(more)g(complicated.)20
b(With)c(an)h(appropriate)g(lab)q(eling)f(of)228 766
y(the)g(v)o(ertices,)e(the)i(incidence)e(matrix)h Fv(M)h
Fw(of)h Ft(F)22 b Fw(can)17 b(b)q(e)f(decomp)q(osed)g(as)734
906 y Fv(M)e Fw(=)853 806 y Fk(0)853 895 y(@)919 847
y Fw(0)61 b(1)77 b Fv(0)919 905 y Fw(1)61 b(0)69 b Fv(N)917
963 y(0)987 945 y Fs(t)1001 963 y Fv(N)42 b(M)1140 945
y Fr(0)1172 806 y Fk(1)1172 895 y(A)228 1045 y Fw(where)17
b(the)h(\014rst)g(ro)o(w)h(and)f(column)f(are)h(indexed)f(b)o(y)g(the)h
(leaf)g Ft(x)p Fw(,)f(the)h(second)228 1103 y(ro)o(w)g(and)g(column)e
(are)h(indexed)g(b)o(y)g(its)g(neigh)o(b)q(or)h Ft(y)r
Fw(,)f Fv(N)h Fw(describ)q(es)f(the)g(edges)228 1161
y(b)q(et)o(w)o(een)g(this)g(neigh)o(b)q(or)h(and)g Ft(V)851
1143 y Fr(0)863 1161 y Fw(,)g(and)g Fv(M)1044 1143 y
Fr(0)1073 1161 y Fw(is)g(the)f(incidence)f(matrix)g(for)i
Ft(V)1697 1143 y Fr(0)1709 1161 y Fw(.)228 1219 y(Then)e
Fv(v)e Fw(=)459 1201 y Fs(t)466 1219 y Fw(\()p Ft(v)509
1226 y Fq(1)528 1219 y Ft(;)8 b(v)574 1226 y Fq(2)593
1219 y Ft(;)g Fv(v)646 1201 y Fr(0)657 1219 y Fw(\))16
b(is)g(in)g(the)g(k)o(ernel)f(of)i Fv(M)f Fw(if)g(and)h(only)f(if)848
1301 y Ft(v)872 1308 y Fq(2)932 1301 y Fw(=)42 b(0)848
1373 y Ft(v)872 1380 y Fq(1)932 1373 y Fw(=)g Fo(\000)p
Fv(Nv)1126 1353 y Fr(0)784 1446 y Fv(M)837 1425 y Fr(0)849
1446 y Fv(v)880 1425 y Fr(0)932 1446 y Fw(=)g Fo(\000)1051
1425 y Fs(t)1065 1446 y Fv(N)p Ft(v)1133 1453 y Fq(2)1152
1446 y Ft(:)228 1528 y Fw(So)22 b Ft(v)325 1535 y Fq(2)366
1528 y Fw(=)h(0)f(whic)o(h)e(from)h(the)g(third)g(equation)g(giv)o(es)g
Fv(M)1336 1509 y Fr(0)1347 1528 y Fv(v)1378 1509 y Fr(0)1412
1528 y Fw(=)h Fv(0)p Fw(,)h(implying)228 1586 y(that)17
b Fv(v)365 1568 y Fr(0)392 1586 y Fw(is)f(in)g(the)g(k)o(ernel)f(of)h
Fv(M)834 1568 y Fr(0)846 1586 y Fw(,)g(and)h(then)f(the)g(second)g
(equation)g(just)h(giv)o(es)228 1644 y Ft(v)252 1651
y Fq(1)289 1644 y Fw(the)h(appropriate)g(v)m(alue.)26
b(So)19 b(the)e(k)o(ernels)g(of)h Fv(M)g Fw(and)h Fv(M)1387
1626 y Fr(0)1416 1644 y Fw(ha)o(v)o(e)f(the)f(same)228
1702 y(dimension.)i(This)e(pro)o(v)o(es)e(iv\).)278 1760
y(No)o(w,)f(an)o(y)g(tree)g(with)h(more)e(than)i(1)g(v)o(ertex)e(has)i
(lea)o(v)o(es,)e(so)j(leaf)e(remo)o(v)m(al)f(as)228 1818
y(de\014ned)k(in)g(iv\))g(allo)o(ws)g(one)h(to)f(reduce)g(the)g(forest)
h Ft(F)23 b Fw(to)18 b(a)g(\(p)q(ossibly)f(empt)o(y\))228
1876 y(family)j(of)j(isolated)g(v)o(ertices)e(\(all)h(connected)g(comp)
q(onen)o(ts)g(ha)o(v)o(e)g(only)h(one)228 1934 y(v)o(ertex\).)42
b(Hence)23 b(there)g(is)g(at)i(most)e(one)h(function,)h(namely)d
Ft(Z)t Fw(,)j(that)f(can)228 1992 y(satisfy)16 b(prop)q(erties)g
(i\){iv\).)p 754 1990 18 18 v 228 2081 a Fv(Remark)g(18.)24
b Fw(Leaf)c(remo)o(v)m(al)e(and)j(additivit)o(y)d(giv)o(e)g(an)j
(e\016cien)o(t)c(algorithm)228 2139 y(for)j(computing)g(the)g(m)o
(ultiplic)o(it)n(y)e(of)i(the)g(eigen)o(v)m(alue)g(0)h(for)f(a)h(giv)o
(en)f(forest,)228 2198 y(esp)q(ecially)15 b(when)h(this)g(forest)g(is)g
(giv)o(en)g(as)h(a)f(dra)o(wing.)278 2286 y(The)c(next)f(lemma)f(giv)o
(es)h(an)i(impractical)c(but)k(theoretically)d(useful)i(form)o(ula)228
2345 y(for)k(the)g(function)g Ft(Z)t Fw(.)228 2433 y
Fv(Lemm)o(a)g(19.)24 b Fu(L)n(et)17 b Ft(L)h Fu(b)n(e)g(the)g(function)
h(on)e(for)n(ests)g(de\014ne)n(d)i(by:)278 2492 y(i'\))e(The)g
(function)i Ft(L)f Fu(takes)g(the)g(value)h Fw(0)f Fu(on)f
Fo(;)p Fu(,)h(the)g(empty)f(for)n(est.)278 2550 y(ii'\))c(The)h
(function)i Ft(L)e Fu(takes)g(the)h(value)g Fw(1)f Fu(on)1132
2541 y Ff(q)1153 2550 y Fu(,)g(the)h(for)n(est)e(with)h(one)h(vertex.)
278 2608 y(iii'\))i(The)g(function)i Ft(L)f Fu(takes)g(the)g(value)h
Fw(0)f Fu(on)f(disc)n(onne)n(cte)n(d)i(for)n(ests.)p
eop
%%Page: 6 6
6 5 bop 228 116 a Fl(6)278 213 y Fu(iv'\))21 b(The)h(function)h
Ft(L)f Fu(takes)h(the)f(value)h Fw(2\()p Fo(\000)p Fw(1\))1194
195 y Fs(n)p Fr(\000)p Fq(1)1284 213 y Fu(on)f(tr)n(e)n(es)g(with)g
Ft(n)f Fo(\025)h Fw(2)228 271 y Fu(vertic)n(es.)278 329
y(Then,)c(for)e(any)i(for)n(est)f Ft(F)633 415 y(Z)t
Fw(\()p Ft(F)7 b Fw(\))13 b(=)822 368 y Fk(X)812 474
y Fs(F)839 465 y Fe(0)850 474 y Fr(\032)p Fs(F)913 415
y Ft(L)p Fw(\()p Ft(F)1004 395 y Fr(0)1015 415 y Fw(\))h(=)1109
368 y Fk(X)1100 474 y Fs(T)1126 465 y Fe(0)1136 474 y
Fr(\032)p Fs(F)1199 415 y Ft(L)p Fw(\()p Ft(T)1287 395
y Fr(0)1298 415 y Fw(\))228 540 y Fu(wher)n(e)h(the)g(\014rst)g(sum)f
(is)h(over)g(induc)n(e)n(d)g(subfor)n(ests)f(of)h Ft(F)7
b Fu(,)14 b(and)h(the)g(se)n(c)n(ond)g(over)228 599 y(induc)n(e)n(d)i
(subtr)n(e)n(es)h(of)f Ft(F)7 b Fu(.)228 711 y Fv(Remark)16
b(20.)24 b Fw(F)l(or)13 b(a)g(giv)o(en)f(forest,)h(there)f(is)g(a)h(m)o
(uc)o(h)e(nicer)g(form)o(ula,)h(directly)228 769 y(connected)h(to)i
(the)e(geometry)g(of)h(the)g(forest)g(\(again,)h(see)f(for)g(instance)g
(Section)228 827 y(8.1,)j(H)q(\177)-26 b(uc)o(k)o(els)15
b(theory)l(,)h(in)h([1)p
 (#cite.cvetkovic) [[248 519 254 531] [1 1 1 [3 3]] [0 0 1]] pdfm 
(]\).)22 b(In)16 b(fact,)g(let)g Ft(Q)p Fw(\()p Ft(F)7
b Fw(\))16 b(b)q(e)h(the)f(maxim)o(um)c(among)228 886
y(the)i(cardinalities)f(of)i(sets)f(of)h(pairwise)f(non-adjacen)o(t)h
(edges)f(in)g Ft(F)7 b Fw(,)14 b(and)h Ft(N)5 b Fw(\()p
Ft(F)i Fw(\))228 944 y(b)q(e)19 b(the)g(n)o(um)o(b)q(er)f(of)h(v)o
(ertices)f(in)h Ft(F)7 b Fw(.)29 b(Then)19 b Ft(Z)t Fw(\()p
Ft(F)7 b Fw(\))19 b(=)g Ft(N)5 b Fw(\()p Ft(F)i Fw(\))12
b Fo(\000)h Fw(2)p Ft(Q)p Fw(\()p Ft(F)7 b Fw(\).)30
b(It)18 b(is)228 1002 y(easy)f(to)h(sho)o(w)g(that)f
Ft(N)5 b Fw(\()p Ft(F)i Fw(\))12 b Fo(\000)f Fw(2)p Ft(Q)p
Fw(\()p Ft(F)c Fw(\))17 b(satis\014es)g(prop)q(erties)g(i\){iv\))g(of)g
(Lemma)228 1060 y(16)p
 (#theo.16) [[127 463 138 475] [1 1 1 [3 3]] [0 0 1]] pdfm (.)44
b(In)23 b(particular,)i(a)f(p)q(ossible)g(w)o(a)o(y)f(to)h(maximize)c
(the)j(n)o(um)o(b)q(er)f(of)i(non-)228 1118 y(adjacen)o(t)d(edges)h(in)
f Ft(F)28 b Fw(in)21 b(case)g(iv\))g(is)g(to)h(do)g(so)g(on)g
Ft(F)1305 1100 y Fr(0)1338 1118 y Fw(and)g(add)g(the)f(edge)228
1176 y Fo(f)p Ft(x;)8 b(y)r Fo(g)p Fw(.)19 b(This)14
b(explicit)d(form)o(ula)h(allo)o(ws)i(us)g(to)g(restate)f(our)h
(theorems)e(in)i(terms)228 1234 y(of)i(the)g(random)f(v)m(ariable)h
Ft(Q)767 1241 y Fs(n)790 1234 y Fw(,)g(the)f(restriction)g(of)i
Ft(Q)e Fw(to)h Fo(T)1332 1241 y Fs(n)1356 1234 y Fw(.)21
b(F)l(or)16 b(instance,)g(in)228 1292 y(a)d(large)g(random)g(tree)f(on)
i Ft(n)f Fw(v)o(ertices,)e(one)j(can)f(\014nd)g(ab)q(out)i(\(1)5
b Fo(\000)g Ft(x)1469 1299 y Fr(\003)1487 1292 y Fw(\))p
Ft(n)14 b Fw(pairwise)228 1351 y(non-adjacen)o(t)h(edges.)20
b(Note)14 b(that)g(1)7 b Fo(\000)g Ft(x)988 1358 y Fr(\003)1021
1351 y Fw(=)14 b(0)p Ft(:)p Fw(4328567095)q(90)q(216)q(12)q(700)q(00)9
b Fo(\001)f(\001)g(\001)228 1409 y Fw(is)19 b(not)g(m)o(uc)o(h)e
(smaller)g(than)j(0)p Ft(:)p Fw(5)f(\(the)g(upp)q(er)h(b)q(ound)g(for)f
Ft(Q)p Fw(\()p Ft(T)7 b Fw(\))p Ft(=)m(N)e Fw(\()p Ft(T)i
Fw(\))18 b(for)i(a)228 1467 y(giv)o(en)15 b(tree)h(b)q(ecause)g
Ft(Z)t Fw(\()p Ft(T)7 b Fw(\))13 b(=)h Ft(N)5 b Fw(\()p
Ft(T)i Fw(\))k Fo(\000)f Fw(2)p Ft(Q)p Fw(\()p Ft(T)d
Fw(\))16 b(is)g(alw)o(a)o(ys)g(nonnegativ)o(e\).)278
1552 y Fu(Pr)n(o)n(of)i(of)i(L)n(emma)f(19)p
 (#theo.19) [[227 345 239 357] [1 1 1 [3 3]] [0 0 1]] pdfm 
Fw(.)30 b(Our)19 b(strategy)h(is)f(to)g(use)h(the)f(c)o
(haracterization)f(of)228 1610 y Ft(Z)i Fw(in)15 b(Lemma)f(16)p
 (#theo.16) [[195 331 206 343] [1 1 1 [3 3]] [0 0 1]] pdfm (.)22
b(First,)15 b(w)o(e)h(observ)o(e)f(that)i(the)f(second)g(equalit)o(y)e
(is)i(a)g(trivial)228 1668 y(consequence)g(of)h(i'\))f(and)h(iii'\).)k
(W)l(e)c(de\014ne)f(a)h(new)g(function)g Ft(Z)1425 1650
y Fr(0)1453 1668 y Fw(on)h(the)e(set)h(of)228 1727 y(forests)f(b)o(y)
770 1793 y Ft(Z)807 1772 y Fr(0)819 1793 y Fw(\()p Ft(F)7
b Fw(\))13 b Fo(\021)971 1745 y Fk(X)962 1852 y Fs(T)988
1842 y Fe(0)998 1852 y Fr(\032)p Fs(F)1061 1793 y Ft(L)p
Fw(\()p Ft(T)1149 1772 y Fr(0)1161 1793 y Fw(\))228 1910
y(\(where)e(the)h(sum)f(is)h(o)o(v)o(er)f(induced)g(subtrees)h(of)g
Ft(F)7 b Fw(\))k(and)h(sho)o(w)h(that)f Ft(Z)1535 1892
y Fr(0)1559 1910 y Fw(satis\014es)228 1969 y(prop)q(erties)k(i\){iv\))f
(of)i(Lemma)d(16)p
 (#theo.16) [[268 244 280 256] [1 1 1 [3 3]] [0 0 1]] pdfm (.)278
2027 y(As)g(the)g(empt)o(y)e(forest)j(has)g(no)g(non-empt)o(y)e
(induced)h(subtree)g(i'\))f(implies)f(i\).)278 2085 y(In)i(the)h(same)f
(v)o(ein,)f(the)h(forest)h(with)g(one)g(v)o(ertex)e(has)j(only)f(one)g
(non-empt)o(y)228 2143 y(induced)g(subtree,)h(namely)e(itself,)h(so)i
(ii'\))e(implies)e(ii\).)278 2201 y(If)21 b(the)h(forest)h
Ft(F)28 b Fw(is)22 b(the)g(union)g(of)h(t)o(w)o(o)f(disjoin)o(t)f
(forests)i Ft(F)1440 2208 y Fq(1)1481 2201 y Fw(and)g
Ft(F)1614 2208 y Fq(2)1634 2201 y Fw(,)g(an)228 2259
y(induced)16 b(subtree)h(of)g Ft(F)23 b Fw(is)17 b(either)f(an)h
(induced)f(subtree)h(of)g Ft(F)1392 2266 y Fq(1)1428
2259 y Fw(or)h(an)f(induced)228 2317 y(subtree)i(of)i
Ft(F)494 2324 y Fq(2)513 2317 y Fw(,)f(and)h(the)e(sum)g(de\014ning)h
Ft(Z)1065 2299 y Fr(0)1077 2317 y Fw(\()p Ft(F)7 b Fw(\))19
b(splits)g(as)i Ft(Z)1405 2299 y Fr(0)1417 2317 y Fw(\()p
Ft(F)1468 2324 y Fq(1)1487 2317 y Fw(\))13 b(+)h Ft(Z)1608
2299 y Fr(0)1619 2317 y Fw(\()p Ft(F)1670 2324 y Fq(2)1690
2317 y Fw(\),)228 2375 y(sho)o(wing)j(that)f Ft(Z)556
2357 y Fr(0)584 2375 y Fw(satis\014es)h(prop)q(ert)o(y)f(iii\).)278
2433 y(No)o(w,)f(if)g Ft(x)g Fw(is)g(a)h(leaf)f(of)h
Ft(F)22 b Fw(and)16 b Ft(y)h Fw(its)e(neigh)o(b)q(or,)h(w)o(e)f
(de\014ne)g Ft(V)1442 2415 y Fr(0)1468 2433 y Fw(=)f
Ft(V)d Fo(nf)p Ft(x;)d(y)r Fo(g)p Fw(,)228 2492 y Ft(V)267
2473 y Fr(00)306 2492 y Fw(=)19 b Fo(f)p Ft(x;)8 b(y)r
Fo(g)17 b Fw(and)j(consider)e Ft(F)835 2473 y Fr(0)865
2492 y Fw(and)i Ft(F)1002 2473 y Fr(0)n(0)1022 2492 y
Fw(,)f(the)g(subforests)g(of)g Ft(F)26 b Fw(induced)18
b(b)o(y)228 2550 y Ft(V)267 2532 y Fr(0)300 2550 y Fw(and)j
Ft(V)439 2532 y Fr(0)o(0)481 2550 y Fw(resp)q(ectiv)o(ely)l(.)33
b(W)l(e)21 b(split)f(the)h(sum)f(de\014ning)h Ft(Z)1401
2532 y Fr(0)1413 2550 y Fw(\()p Ft(F)7 b Fw(\))20 b(in)o(to)h(three)228
2608 y(pieces.)30 b(The)20 b(\014rst)g(is)g(o)o(v)o(er)e(the)i(induced)
f(subtrees)h(of)g Ft(F)1331 2590 y Fr(0)1342 2608 y Fw(.)31
b(This)20 b(is)g(just)f(the)p eop
%%Page: 7 7
7 6 bop 1703 116 a Fl(7)228 213 y Fw(sum)18 b(de\014ning)h
Ft(Z)558 195 y Fr(0)570 213 y Fw(\()p Ft(F)628 195 y
Fr(0)639 213 y Fw(\).)30 b(The)20 b(second)f(is)g(o)o(v)o(er)g(the)g
(induced)f(subtrees)h(of)h Ft(F)1688 195 y Fr(0)o(0)1709
213 y Fw(,)228 271 y(whic)o(h)i(is)g(a)h(tree)e(on)i(t)o(w)o(o)f(v)o
(ertices.)38 b(Its)23 b(subtrees)f(are)g(itself,)h(with)f(w)o(eigh)o(t)
228 329 y Ft(L)p Fw(\()p Ft(F)319 311 y Fr(0)o(0)340
329 y Fw(\))g(=)h(2\()p Fo(\000)p Fw(1\))567 311 y Fq(2)p
Fr(\000)p Fq(1)655 329 y Fw(=)f Fo(\000)p Fw(2,)h(and)f(t)o(w)o(o)f
(trees)g(with)g(one)h(v)o(ertex,)e(eac)o(h)h(with)228
387 y(w)o(eigh)o(t)f Ft(L)p Fw(\()447 379 y Ff(q)455
387 y Fw(\))h(=)g(1,)h(so)f(this)f(second)h(sum)f(giv)o(es)f(0.)35
b(The)20 b(third)g(sum)g(is)g(o)o(v)o(er)228 445 y(induced)10
b(subtrees)h(that)h(ha)o(v)o(e)e(v)o(ertices)f(in)i(b)q(oth)h
Ft(V)1170 427 y Fr(0)1192 445 y Fw(and)g Ft(V)1321 427
y Fr(00)1343 445 y Fw(.)19 b(If)11 b(this)g(sum)f(is)h(not)228
503 y(empt)o(y)l(,)h(ev)o(ery)h(tree)g(that)i(app)q(ears)h(in)e(it)g
(has)h Ft(y)h Fw(as)f(a)g(v)o(ertex)e(\(b)o(y)g(connectivit)o(y\))228
561 y(and)21 b(has)h(at)f(least)g(t)o(w)o(o)g(v)o(ertices)e(\(b)q
(ecause)i(the)f(tree)g(consisting)h(of)h Ft(y)g Fw(alone)228
619 y(has)c(already)f(b)q(een)g(coun)o(ted\).)25 b(Then)17
b(w)o(e)g(can)h(group)g(these)f(trees)g(in)g(pairs,)h(a)228
678 y(tree)e(con)o(taining)i Ft(x)f Fw(b)q(eing)g(paired)g(with)g(the)g
(same)f(tree)h(but)g(with)h Ft(x)f Fw(and)g(the)228 736
y(edge)h Fo(f)p Ft(x;)8 b(y)r Fo(g)17 b Fw(deleted.)25
b(The)18 b(function)g Ft(L)g Fw(tak)o(es)f(opp)q(osite)i(v)m(alues)f
(on)h(the)e(t)o(w)o(o)228 794 y(mem)n(b)q(ers)f(of)i(a)g(pair,)g(so)g
(the)g(third)f(sum)g(con)o(tributes)g(0.)27 b(Hence)16
b Ft(Z)1529 776 y Fr(0)1559 794 y Fw(satis\014es)228
852 y(prop)q(ert)o(y)g(iv\).)k(So)d Ft(Z)625 834 y Fr(0)637
852 y Fw(\()p Ft(F)7 b Fw(\))13 b(=)h Ft(Z)816 834 y
Fr(0)827 852 y Fw(\()p Ft(F)885 834 y Fr(0)896 852 y
Fw(\).)p 945 850 18 18 v 228 943 a Fv(Remark)i(21.)24
b Fw(These)c(t)o(w)o(o)g(lemm)o(as)d(ha)o(v)o(e)i(an)i(ob)o(vious)e
(extension)h(to)g(bicol-)228 1001 y(ored)g(forests.)34
b(If)20 b(w)o(e)f(use)i(blac)o(k)e(and)i(white)f(as)g(the)g(colors,)h
(and)g(coun)o(t)f(the)228 1060 y(zero)c(eigen)o(v)o(ectors)f(ha)o(ving)
i(v)m(alue)g(zero)f(on)i(white)e(v)o(ertices,)f(w)o(e)h(only)g(need)h
(to)228 1118 y(replace)e(ii\))g(in)h(Lemma)e(16)p
 (#theo.16) [[237 449 248 461] [1 1 1 [3 3]] [0 0 1]] pdfm 
17 w(b)o(y)278 1176 y Fu(ii\))i(The)i(function)g Ft(Z)j
Fu(takes)d(the)f(value)h Fw(1)g Fu(on)f Fo(\017)p Fu(,)g(the)g(for)n
(est)g(with)g(one)h(vertex)228 1234 y(c)n(olor)n(e)n(d)d(in)h(black)i
(and)f Fw(0)f Fu(on)g Fo(\016)p Fu(,)h(the)f(for)n(est)g(with)g(one)h
(vertex)h(c)n(olor)n(e)n(d)d(in)h(white,)228 1292 y Fw(and)h(ii'\))e
(and)h(iii'\))f(in)h(Lemma)e(19)p
 (#theo.19) [[267 407 279 419] [1 1 1 [3 3]] [0 0 1]] pdfm 
17 w(b)o(y)278 1350 y Fu(ii'\))i(The)g(function)h Ft(L)g
Fu(takes)g(the)f(value)i Fw(1)e Fu(on)h Fo(\017)p Fu(,)f(the)h(for)n
(est)e(with)i(one)g(vertex)228 1408 y(c)n(olor)n(e)n(d)e(in)h(black)i
(and)f Fw(0)f Fu(on)g Fo(\016)p Fu(,)h(the)f(for)n(est)g(with)g(one)h
(vertex)h(c)n(olor)n(e)n(d)d(in)h(white,)278 1466 y(iii'\))22
b(The)h(function)h Ft(L)f Fu(takes)h(the)f(value)h Fw(\()p
Fo(\000)p Fw(1\))1185 1448 y Fs(n)p Fr(\000)p Fq(1)1277
1466 y Fu(on)f(tr)n(e)n(es)f(with)h Ft(n)h Fo(\025)g
Fw(2)228 1525 y Fu(vertic)n(es.)278 1583 y Fw(The)16
b(pro)q(ofs)h(remain)e(the)h(same.)228 1708 y Fv(Remark)g(22.)24
b Fw(The)17 b(form)o(ula)774 1794 y Ft(Z)t Fw(\()p Ft(F)7
b Fw(\))13 b(=)964 1746 y Fk(X)953 1853 y Fs(F)980 1843
y Fe(0)992 1853 y Fr(\032)p Fs(F)1055 1794 y Ft(L)p Fw(\()p
Ft(F)1146 1773 y Fr(0)1157 1794 y Fw(\))228 1926 y(can)j(b)q(e)h(in)o
(v)o(erted)d(using)j(inclusion-exclusion)d(to)j(giv)o(e)598
2020 y Ft(L)p Fw(\()p Ft(F)7 b Fw(\))13 b(=)784 1973
y Fk(X)773 2079 y Fs(F)800 2070 y Fe(0)812 2079 y Fr(\032)p
Fs(F)866 2020 y Fw(\()p Fo(\000)p Fw(1\))967 2000 y Fr(j)p
Fs(V)8 b Fq(\()p Fs(F)d Fq(\))p Fr(j\000j)p Fs(V)i Fq(\()p
Fs(F)1177 1988 y Fe(0)1188 2000 y Fq(\))p Fr(j)1213 2020
y Ft(Z)t Fw(\()p Ft(F)1308 2000 y Fr(0)1319 2020 y Fw(\))p
Ft(:)228 2156 y Fw(This)15 b(iden)o(tit)o(y)e(has)i(an)h(application)f
(in)f(random)h(graph)h(theory)e([2)p
 (#cite.nous) [[421 200 427 212] [1 1 1 [3 3]] [0 0 1]] pdfm (],)h
(whic)o(h)f(led)228 2214 y(to)i(our)h(in)o(terest)e(in)h(Lemma)e(19)p
 (#theo.19) [[259 186 271 198] [1 1 1 [3 3]] [0 0 1]] pdfm (.)777
2335 y(4.)28 b Fp(Main)18 b(pr)o(oofs.)278 2422 y Fu(Pr)n(o)n(of)d(of)j
(The)n(or)n(em)e(1)p
 (#theo.1) [[232 136 238 148] [1 1 1 [3 3]] [0 0 1]] pdfm 
Fw(.)21 b(By)16 b(Lemma)e(16)p
 (#theo.16) [[307 136 318 148] [1 1 1 [3 3]] [0 0 1]] pdfm 
556 2556 a Ft(z)579 2563 y Fs(n)616 2556 y Fo(\021)678
2509 y Fk(X)669 2615 y Fs(T)5 b Fr(2T)738 2619 y Fj(n)767
2556 y Ft(Z)800 2563 y Fs(n)824 2556 y Fw(\()p Ft(T)i
Fw(\))13 b(=)990 2494 y Fs(n)965 2509 y Fk(X)962 2614
y Fs(m)p Fq(=1)1056 2509 y Fk(X)1047 2615 y Fs(T)5 b
Fr(2T)1116 2619 y Fj(n)1155 2494 y Fs(T)1181 2482 y Fe(0)1191
2494 y Fr(\032)p Fs(T)1163 2509 y Fk(X)1145 2615 y Fs(T)1171
2606 y Fe(0)1182 2615 y Fr(2T)1225 2619 y Fj(m)1262 2556
y Ft(L)p Fw(\()p Ft(T)1350 2536 y Fr(0)1361 2556 y Fw(\))p
Ft(:)p eop
%%Page: 8 8
8 7 bop 228 116 a Fl(8)228 213 y Fw(As)20 b(the)g(function)g
Ft(L)h Fw(dep)q(ends)g(only)f(on)h(the)f(n)o(um)o(b)q(er)f(of)i(v)o
(ertices,)e(for)i(\014xed)228 276 y Ft(m)e Fw(the)f(double)i(sum)643
239 y Fk(P)695 291 y Fs(T)5 b Fr(2T)764 295 y Fj(n)795
239 y Fk(P)848 252 y Fs(T)874 240 y Fe(0)884 252 y Fr(\032)p
Fs(T)848 291 y(T)874 281 y Fe(0)884 291 y Fr(2T)927 295
y Fj(m)978 276 y Fw(is)19 b(simply)e(a)i(m)o(ultiplici)o(t)o(y)l(.)26
b(W)l(e)19 b(coun)o(t)228 336 y(this)e(m)o(ultiplic)o(it)n(y)d(as)k
(follo)o(ws)f(:)24 b(w)o(e)16 b(remo)o(v)o(e)f(from)h
Ft(T)24 b Fw(the)17 b(edges)g(of)h Ft(T)1564 317 y Fr(0)1575
336 y Fw(,)f(so)h(w)o(e)228 394 y(are)f(left)f(with)g
Ft(m)h Fw(trees,)f(eac)o(h)g(with)h(a)g(sp)q(ecial)g(v)o(ertex,)e(the)h
(one)h(b)q(elonging)h(to)228 452 y Ft(T)264 434 y Fr(0)275
452 y Fw(.)35 b(This)20 b(is)h(what)g(is)g(called)f(a)h(plan)o(ted)f
(forest)h(\(or)g(ro)q(oted)h(forest\))e(with)h Ft(n)228
511 y Fw(v)o(ertices)14 b(and)i Ft(m)g Fw(trees.)k(The)c(n)o(um)o(b)q
(er)e(of)i(suc)o(h)g(ob)s(jects)f(is)h Ft(m)1392 470
y Fk(\000)1419 489 y Fs(n)1414 528 y(m)1446 470 y Fk(\001)1468
511 y Ft(n)1497 493 y Fs(n)p Fr(\000)p Fs(m)p Fr(\000)p
Fq(1)1641 511 y Fw(\(see)228 570 y(for)g(instance)g(Prop)q(osition)i
(5.3.2)e(in)g([3)p
 (#cite.stanley) [[298 580 304 592] [1 1 1 [3 3]] [0 0 1]] pdfm (]\).)
21 b(Con)o(v)o(ersely)l(,)15 b(starting)i(from)e(suc)o(h)h(a)228
628 y(plan)o(ted)e(forest)g(with)h Ft(m)f Fw(trees)g(\(eac)o(h)g(with)g
(a)h(sp)q(ecial)f(v)o(ertex\))f(and)i Ft(n)g Fw(v)o(ertices,)228
686 y(w)o(e)h(can)g(build)g(a)g(tree)g(on)h(the)f(sp)q(ecial)f(v)o
(ertices)g(in)h Ft(m)1239 668 y Fs(m)p Fr(\000)p Fq(2)1333
686 y Fw(w)o(a)o(ys.)21 b(So)628 772 y Fk(X)619 877 y
Fs(T)5 b Fr(2T)688 881 y Fj(n)727 757 y Fs(T)753 745
y Fe(0)763 757 y Fr(\032)p Fs(T)735 772 y Fk(X)717 878
y Fs(T)743 869 y Fe(0)754 878 y Fr(2T)797 882 y Fj(m)834
819 y Fw(1)14 b(=)g Ft(m)967 798 y Fs(m)p Fr(\000)p Fq(1)1045
749 y Fk(\022)1089 785 y Ft(n)1082 853 y(m)1125 749 y
Fk(\023)1161 819 y Ft(n)1190 798 y Fs(n)p Fr(\000)p Fs(m)p
Fr(\000)p Fq(1)1318 819 y Ft(:)278 952 y Fw(Hence)h(summation)f(o)o(v)o
(er)h Ft(m)h Fw(giv)o(es)490 1064 y Ft(z)513 1071 y Fs(n)550
1064 y Fw(=)e Ft(n)631 1044 y Fs(n)p Fr(\000)p Fq(1)711
1064 y Fo(\000)d Fw(2)820 1017 y Fk(X)793 1122 y Fq(2)p
Fr(\024)p Fs(m)p Fr(\024)p Fs(n)918 1064 y Fw(\()p Fo(\000)p
Fw(1\))1019 1044 y Fs(m)1053 1064 y Ft(n)1082 1044 y
Fs(n)p Fr(\000)p Fs(m)p Fr(\000)p Fq(1)1209 1064 y Ft(m)1252
1044 y Fs(m)p Fr(\000)p Fq(1)1330 994 y Fk(\022)1374
1031 y Ft(n)1367 1099 y(m)1410 994 y Fk(\023)1446 1064
y Ft(:)228 1201 y Fw(Simple)18 b(rearrangemen)o(ts)h(lead)i(to)g(the)f
(t)o(w)o(o)g(equiv)m(alen)o(t)f(form)o(ul\032)g(in)i(i\),)f(the)228
1259 y(\014rst)c(one)h(making)e(clear)g(that)i Ft(z)835
1266 y Fs(n)874 1259 y Fw(is)f(an)h(in)o(teger.)278 1317
y(T)l(o)j(obtain)g(the)f(generating)h(function)g(in)f(ii\),)g(w)o(e)g
(need)g(a)h(mild)e(extension)228 1375 y(of)f(the)g(Lagrange)h(in)o(v)o
(ersion)e(form)o(ula)f(\(see)i(for)g(instance)f(Section)h(5.4)g(in)f
([3)p  (#cite.stanley) [[468 387 474 399] [1 1 1 [3 3]] [0 0 1]] pdfm 
(]\),)228 1433 y(whic)o(h)d(states)h(that)g(if)g Ft(f)5
b Fw(\()p Ft(x)p Fw(\))13 b(is)h(a)g(formal)f(p)q(o)o(w)o(er)g(series)g
(in)h Ft(x)f Fw(b)q(eginning)h Ft(f)5 b Fw(\()p Ft(x)p
Fw(\))14 b(=)228 1491 y Ft(x)d Fw(+)g Ft(O)q Fw(\()p
Ft(x)401 1473 y Fq(2)421 1491 y Fw(\))16 b(and)h Ft(g)r
Fw(\()p Ft(x)p Fw(\))f(is)g(an)h(arbitrary)f(formal)f(p)q(o)o(w)o(er)h
(series)g(in)g Ft(x)p Fw(,)f(then)497 1566 y Fk(\000)520
1607 y Ft(g)f Fo(\016)d Ft(f)622 1586 y Fr(\000)p Fq(1)669
1566 y Fk(\001)700 1607 y Fw(\()p Ft(t)p Fw(\))j(=)f
Ft(g)r Fw(\(0\))f(+)969 1559 y Fk(X)972 1665 y Fs(n)p
Fr(\025)p Fq(1)1056 1573 y Fw(1)p 1054 1595 30 2 v 1054
1641 a Ft(n)1097 1536 y Fk(\024)1128 1573 y Ft(x)1156
1555 y Fs(n)1179 1573 y Ft(g)1204 1555 y Fr(0)1216 1573
y Fw(\()p Ft(x)p Fw(\))p 1128 1595 154 2 v 1145 1641
a Ft(f)5 b Fw(\()p Ft(x)p Fw(\))1240 1626 y Fs(n)1286
1536 y Fk(\025)1313 1656 y Fs(n)p Fr(\000)p Fq(1)1390
1607 y Ft(t)1408 1586 y Fs(n)1439 1607 y Ft(;)228 1747
y Fw(where)21 b([)p Ft(h)p Fw(\()p Ft(v)r Fw(\)])494
1754 y Fs(k)535 1747 y Fw(is)g(b)o(y)g(de\014nition)f(the)h
Ft(k)999 1729 y Fs(th)1056 1747 y Fw(co)q(e\016cien)o(t)f(of)h(the)g
(formal)f(p)q(o)o(w)o(er)228 1805 y(series)15 b Ft(h)p
Fw(\()p Ft(v)r Fw(\).)278 1863 y(As)h(an)g(immediate)d(application,)i
(w)o(e)h(see)g(that)h(if)e Ft(t)f Fw(=)g Ft(xe)1357 1845
y Fs(x)1394 1863 y Fw(then)758 1970 y Ft(x)g Fw(=)854
1922 y Fk(X)852 2027 y Fs(m)p Fr(\025)p Fq(1)928 1970
y Fw(\()p Fo(\000)p Ft(m)p Fw(\))1048 1949 y Fs(m)p Fr(\000)p
Fq(1)1133 1936 y Ft(t)1151 1918 y Fs(m)p 1131 1958 57
2 v 1131 2004 a Ft(m)p Fw(!)228 2103 y(and)654 2180 y
Fo(\000)p Ft(x)c Fo(\000)h Ft(x)809 2159 y Fq(2)828 2180
y Ft(=)p Fw(2)k(=)945 2132 y Fk(X)943 2237 y Fs(m)p Fr(\025)p
Fq(1)1019 2180 y Fw(\()p Fo(\000)p Ft(m)p Fw(\))1139
2159 y Fs(m)p Fr(\000)p Fq(2)1224 2146 y Ft(t)1242 2128
y Fs(m)p 1222 2168 V 1222 2214 a Ft(m)p Fw(!)1283 2180
y Ft(:)278 2307 y Fw(No)o(w)h(w)o(e)g(in)o(tro)q(duce)f
Ft(y)h Fw(=)d Ft(te)809 2289 y Fr(\000)p Fs(t)867 2307
y Fw(and)k(de\014ne)f(a)h(sequence)e Ft(z)1371 2289 y
Fr(0)1369 2319 y Fs(n)1392 2307 y Ft(;)8 b(n)14 b Fo(\025)f
Fw(1,)j(b)o(y)696 2416 y Ft(x)724 2395 y Fq(2)755 2416
y Fw(+)11 b(2)p Ft(x)g Fo(\000)g Ft(xe)968 2395 y Fs(x)1003
2416 y Fw(=)1055 2369 y Fk(X)1057 2474 y Fs(n)p Fr(\025)p
Fq(1)1135 2416 y Ft(z)1160 2395 y Fr(0)1158 2428 y Fs(n)1186
2382 y Ft(y)1212 2364 y Fs(n)p 1186 2405 50 2 v 1189
2450 a Ft(n)p Fw(!)1240 2416 y Ft(;)228 2550 y Fw(but)25
b(instead)h(of)f(directly)f(applying)h(the)g(Lagrange)i(in)o(v)o
(ersion)d(form)o(ula)g(to)228 2608 y Ft(y)j Fw(=)e Ft(xe)393
2590 y Fs(x)415 2608 y Ft(e)438 2590 y Fr(\000)p Fs(xe)501
2578 y Fj(x)522 2608 y Fw(,)g(w)o(e)d(\014rst)i(substitute)f(the)g
Ft(t)p Fw(-expansion)g(\(already)g(obtained)p eop
%%Page: 9 9
9 8 bop 1703 116 a Fl(9)228 213 y Fw(b)o(y)16 b(Lagrange)i(in)o(v)o
(ersion\))c(on)j(the)f(left-hand)g(side,)g(whic)o(h)f(yields)723
332 y Fo(\000)p Fw(2)797 284 y Fk(X)794 389 y Fs(m)p
Fr(\025)p Fq(1)871 332 y Fw(\()p Fo(\000)p Ft(m)p Fw(\))991
311 y Fs(m)p Fr(\000)p Fq(2)1076 298 y Ft(t)1094 280
y Fs(m)p 1074 320 57 2 v 1074 366 a Ft(m)p Fw(!)1146
332 y Fo(\000)c Ft(t;)228 479 y Fw(and)17 b(then)f(apply)g(Lagrange)i
(in)o(v)o(ersion)d(with)h Ft(y)f Fw(=)f Ft(te)1228 461
y Fr(\000)p Fs(t)1270 479 y Fw(.)21 b(The)16 b(result)g(is)495
583 y Ft(z)520 564 y Fr(0)518 595 y Fs(n)p 495 605 47
2 v 497 650 a Ft(n)p Fw(!)560 616 y(=)619 583 y(1)p 617
605 30 2 v 617 650 a Ft(n)659 531 y Fk(")688 616 y Ft(e)711
596 y Fs(nt)755 531 y Fk( )795 616 y Fw(1)11 b Fo(\000)g
Fw(2)915 569 y Fk(X)912 674 y Fs(m)p Fr(\025)p Fq(2)1002
583 y Fw(\()p Fo(\000)p Ft(m)p Fw(\))1122 564 y Fs(m)p
Fr(\000)p Fq(2)p 1002 605 198 2 v 1011 650 a Fw(\()p
Ft(m)g Fo(\000)g Fw(1\)!)1205 616 y Ft(t)1223 596 y Fs(m)p
Fr(\000)p Fq(1)1301 531 y Fk(!#)1370 687 y Fs(n)p Fr(\000)p
Fq(1)1446 616 y Ft(:)228 767 y Fw(Straigh)o(tforw)o(ard)j(expansion)h
(of)f(this)g(form)o(ula)f(sho)o(ws)h(that)h Ft(z)1390
749 y Fr(0)1388 779 y Fs(n)1425 767 y Fw(=)f Ft(z)1500
774 y Fs(n)1523 767 y Fw(,)g(and)g(this)228 825 y(establishes)i(the)g
(generating)g(function)g(represen)o(tation)g(in)g(ii\).)p
1435 823 18 18 v 228 922 a Fv(Remark)g(23.)24 b Fw(The)16
b(deriv)m(ation)g(of)h(ii\))e(is)h(quite)f(arti\014cial.)20
b(It)c(turns)g(out)h(that)228 980 y(random)f(graph)h(theory)g(giv)o(es)
e(a)i(natural)g(pro)q(of)h([2)p
 (#cite.nous) [[353 482 359 494] [1 1 1 [3 3]] [0 0 1]] pdfm 
-1 w(])e(using)h(the)f(form)o(ula)g(men-)228 1038 y(tioned)g(in)g
(Remark)e(22.)278 1134 y Fu(Pr)n(o)n(of)22 b(of)j(Cor)n(ol)r(lary)e(2)p
 (#theo.2) [[241 445 247 457] [1 1 1 [3 3]] [0 0 1]] pdfm 
Fw(.)44 b(This)24 b(time)e(w)o(e)h(use)h(Lagrange)i(in)o(v)o(ersion)c
(with)228 1192 y Ft(y)15 b Fw(=)f Ft(xe)370 1174 y Fs(x)391
1192 y Ft(e)414 1174 y Fr(\000)p Fs(xe)477 1162 y Fj(x)499
1192 y Fw(,)i(in)g(a)g(con)o(tour)h(in)o(tegral)e(represen)o(tation)
1284 1174 y Fq(3)p
 (#Hfootnote.3) [[380 431 385 443] [1 1 1 [3 3]] [0 0 1]] pdfm 
1304 1192 a Fw(.)21 b(So)575 1277 y Ft(z)598 1284 y Fs(n)p
575 1299 47 2 v 577 1345 a Ft(n)p Fw(!)640 1311 y(=)699
1277 y(1)p 697 1299 30 2 v 697 1345 a Ft(n)739 1243 y
Fk(I)896 1277 y Ft(dx)p 802 1299 242 2 v 802 1345 a Fw(\()p
Ft(xe)872 1330 y Fs(x)893 1345 y Ft(e)916 1330 y Fr(\000)p
Fs(xe)979 1321 y Fj(x)1001 1345 y Fw(\))1020 1330 y Fs(n)1049
1311 y Fw(\(1)11 b(+)g Ft(x)p Fw(\)\(2)g Fo(\000)g Ft(e)1326
1290 y Fs(x)1348 1311 y Fw(\))p Ft(;)228 1432 y Fw(where)19
b(the)g(con)o(tour)h(is)g(a)g(small)e(an)o(ticlo)q(c)o(kwise-orien)o
(ted)f(circle)h(around)i(the)228 1490 y(origin.)27 b(F)l(or)19
b(large)f Ft(n)h Fw(w)o(e)f(use)g(the)g(steep)q(est)h(descen)o(t)e
(metho)q(d)h(to)h(obtain)f(the)228 1548 y(asymptotic)d(expansion)i(of)f
Ft(z)784 1555 y Fs(n)808 1548 y Fw(.)21 b(As)931 1529
y Fs(d)p 921 1537 39 2 v 921 1566 a(dx)964 1548 y Ft(xe)1015
1530 y Fs(x)1036 1548 y Ft(e)1059 1530 y Fr(\000)p Fs(xe)1122
1519 y Fj(x)1158 1548 y Fw(=)14 b(\(1)e(+)f Ft(x)p Fw(\)\(1)g
Fo(\000)g Ft(xe)1516 1530 y Fs(x)1537 1548 y Fw(\))p
Ft(e)1579 1530 y Fs(x)1601 1548 y Ft(e)1624 1530 y Fr(\000)p
Fs(xe)1687 1519 y Fj(x)1709 1548 y Fw(,)228 1610 y(the)k(saddle)g(p)q
(oin)o(ts)g(of)h Ft(xe)710 1592 y Fs(x)731 1610 y Ft(e)754
1592 y Fr(\000)p Fs(xe)817 1580 y Fj(x)854 1610 y Fw(are)f
Ft(x)f Fw(=)f Fo(\000)p Fw(1)j(and)f(the)g(solutions)h(to)f
Ft(x)f Fw(=)g Ft(e)1660 1592 y Fr(\000)p Fs(x)1709 1610
y Fw(.)228 1668 y(This)d(equation)h(has)g(a)g(unique)f(real)g(ro)q(ot,)
i Ft(x)1033 1675 y Fr(\003)1052 1668 y Fw(,)f(whic)o(h)f(is)g(p)q
(ositiv)o(e.)19 b(Numerically)l(,)228 1727 y Ft(x)256
1734 y Fr(\003)291 1727 y Fw(=)c(0)p Ft(:)p Fw(567143290)q(40)q(978)q
(38)q(729)q(999)9 b Fo(\001)f(\001)g(\001)20 b Ft(:)d
Fw(On)g(the)g(other)h(hand,)f Ft(x)f Fw(=)f Ft(e)1585
1708 y Fr(\000)p Fs(x)1651 1727 y Fw(has)228 1785 y(an)20
b(in\014nite)f(n)o(um)o(b)q(er)f(of)j(complex)d(solutions,)i(in)g
(complex)e(conjugate)i(pairs.)228 1843 y(Asymptotically)l(,)10
b(the)i(imaginary)f(parts)i(of)g(these)f(zeros)h(are)f(ev)o(enly)f
(spaced)i(b)o(y)228 1901 y(ab)q(out)18 b(2)p Ft(\031)r
Fw(,)e(while)f(their)h(real)g(parts)h(are)g(negativ)o(e)f(and)h(gro)o
(w)g(logarithmically)228 1959 y(in)23 b(absolute)g(v)m(alue.)42
b(Consideration)24 b(of)f(the)g(landscap)q(e)h(pro)q(duced)g(b)o(y)e
(the)228 2017 y(mo)q(dulus)11 b(of)i(the)e(function)h
Ft(xe)789 1999 y Fs(x)810 2017 y Ft(e)833 1999 y Fr(\000)p
Fs(xe)896 1987 y Fj(x)930 2017 y Fw(sho)o(ws)h(that)f(the)g(small)e
(circle)g(around)j(the)228 2075 y(origin)f(can)h(b)q(e)g(deformed)e(to)
i(giv)o(e)e(the)h(union)h(of)g(t)o(w)o(o)g(steep)q(est)f(descen)o(t)g
(curv)o(es,)228 2133 y(one)j(passing)i(through)g Ft(x)c
Fw(=)h Fo(\000)p Fw(1)i(and)g(the)f(other)h(through)g
Ft(x)e Fw(=)f Ft(x)1451 2140 y Fr(\003)1471 2133 y Fw(.)21
b(These)15 b(t)o(w)o(o)228 2191 y(curv)o(es)j(are)i(asymptotic)e(to)i
(the)f(t)o(w)o(o)g(lines)g Ft(y)i Fw(=)e Fo(\006)p Ft(\031)i
Fw(at)e Ft(x)g Fo(!)g Fw(+)p Fo(1)p Fw(.)31 b(Hence,)228
2250 y(despite)10 b(the)h(fact)g(that)h(the)f(v)m(alue)g(of)g
Ft(xe)960 2231 y Fs(x)981 2250 y Ft(e)1004 2231 y Fr(\000)p
Fs(xe)1067 2220 y Fj(x)1100 2250 y Fw(is)g(the)g(same,)g(namely)e(1)p
Ft(=e)p Fw(,)j(at)g(all)228 2308 y(the)i(complex)f(saddle)i(p)q(oin)o
(ts)g(and)g(at)g Ft(x)972 2315 y Fr(\003)992 2308 y Fw(,)f(the)h
(complex)e(saddle)h(p)q(oin)o(ts)h(do)h(not)228 2366
y(con)o(tribute)d(to)i(the)g(asymptotic)e(expansion)i(of)f
Ft(z)1151 2373 y Fs(n)1189 2366 y Fw(at)h(large)f Ft(n)p
Fw(.)21 b(Moreo)o(v)o(er,)13 b(the)228 2425 y(p)q(oin)o(t)e
Ft(x)i Fw(=)h Fo(\000)p Fw(1)d(only)g(giv)o(es)f(sub)q(dominan)o(t)h
(con)o(tributions)f(b)q(ecause)i Fo(\000)p Ft(e)1550
2407 y Fr(\000)p Fq(1)1596 2425 y Ft(e)1619 2407 y Fs(e)1635
2396 y Fe(\000)p Fd(1)1689 2425 y Fw(is)228 2484 y(larger)h(than)i(1)p
Ft(=e)f Fw(in)f(absolute)h(v)m(alue.)20 b(So)14 b(w)o(e)f(concen)o
(trate)g(on)h(the)g(asymptotic)p 228 2561 250 2 v 278
2593 a Fn(3)296 2608 y Fm(W)m(e)g(include)g(the)g(factor)722
2591 y Fn(1)p 706 2598 49 2 v 706 2622 a(2)p Fc(i\031)774
2608 y Fm(in)f(the)i(sym)o(b)q(ol)1036 2574 y Fb(H)1063
2608 y Fm(.)p eop
%%Page: 10 10
10 9 bop 228 116 a Fl(10)228 213 y Fw(expansion)16 b(around)i
Ft(x)648 220 y Fr(\003)667 213 y Fw(.)j(As)403 327 y(log)9
b Ft(xe)525 306 y Fs(x)546 327 y Ft(e)569 306 y Fr(\000)p
Fs(xe)632 294 y Fj(x)668 327 y Fw(=)14 b Fo(\000)p Fw(1)d
Fo(\000)849 293 y Fw(\()p Ft(x)896 300 y Fr(\003)926
293 y Fw(+)g(1\))p 849 315 170 2 v 898 361 a(2)p Ft(x)950
368 y Fr(\003)1023 327 y Fw(\()p Ft(x)g Fo(\000)g Ft(x)1159
334 y Fr(\003)1178 327 y Fw(\))1197 306 y Fq(2)1228 327
y Fw(+)g Ft(O)q Fw(\(\()p Ft(x)h Fo(\000)e Ft(x)1470
334 y Fr(\003)1490 327 y Fw(\))1509 306 y Fq(3)1528 327
y Fw(\))228 436 y(w)o(e)16 b(infer)f(that)558 537 y Ft(e)581
517 y Fr(\000)p Fs(n)632 494 y Fo(p)p 673 494 83 2 v
673 537 a Fw(2)p Ft(\031)r(n)764 470 y Fk(I)922 504 y
Ft(dx)p 828 526 242 2 v 828 572 a Fw(\()p Ft(xe)898 557
y Fs(x)919 572 y Ft(e)942 557 y Fr(\000)p Fs(xe)1005
548 y Fj(x)1027 572 y Fw(\))1046 557 y Fs(n)1074 537
y Fw(\(1)c(+)g Ft(x)p Fw(\)\(2)h Fo(\000)e Ft(e)1351
517 y Fs(x)1373 537 y Fw(\))228 655 y(has)22 b(an)g(asymptotic)e
(expansion)i(in)f(p)q(o)o(w)o(ers)h(of)g(1)p Ft(=n)p
Fw(.)38 b(By)21 b(use)g(of)h(Stirling's)228 713 y(form)o(ula)c(for)h
Ft(n)p Fw(!)g(w)o(e)g(conclude)f(that)i Fi(E)t Fw(\()p
Ft(Z)1018 720 y Fs(n)1045 713 y Fw(\))f(=)f Ft(z)1162
720 y Fs(n)1186 713 y Ft(=n)1239 695 y Fs(n)p Fr(\000)p
Fq(2)1327 713 y Fw(has)i(an)g(asymptotic)228 771 y(expansion)15
b(in)g(p)q(o)o(w)o(ers)h(of)f(1)p Ft(=n)p Fw(.)22 b(The)15
b(\014rst)h(t)o(w)o(o)f(terms)f(are)h(obtained)h(b)o(y)e(brute)228
829 y(force.)p 359 827 18 18 v 267 953 a Fp(Appendix)j
Fw(A.)27 b Fp(Examples)17 b(of)h(direct)i(mul)m(tiplicity)e(counting.)
278 1040 y Fw(This)e(app)q(endix)g(en)o(umerates)f(the)h(m)o(ultiplic)o
(iti)o(es)e(of)i(0)h(in)f(the)g(sp)q(ectrum)f(of)228
1098 y(trees)h(with)g Ft(n)e Fw(=)f(1)p Ft(;)8 b Fw(2)p
Ft(;)g Fw(3)18 b(or)e(4)h(v)o(ertices.)228 1185 y Fv(Example)j(24)p
Fw(.)33 b(F)l(or)20 b Ft(n)g Fw(=)g(1)g(there)g(is)f(only)h(one)g
(tree,)1329 1177 y Ff(q)1350 1185 y Fw(,)h(and)f(one)g(w)o(a)o(y)g(to)
228 1244 y(lab)q(el)f(it,)g(giving)g(1)g(=)g(1)687 1226
y Fq(1)p Fr(\000)p Fq(2)771 1244 y Fw(tree)g(on)g(one)h(v)o(ertex.)28
b(The)20 b(incidence)d(matrix)g(is)228 1302 y(\(0\),)f(so)h(the)f
(eigen)o(v)m(alue)f(0)h(o)q(ccurs)h(with)f(m)o(ultiplici)o(t)o(y)d
Ft(z)1284 1309 y Fq(1)1317 1302 y Fw(=)h(1.)228 1419
y Fv(Example)22 b(25)p Fw(.)36 b(F)l(or)21 b Ft(n)h Fw(=)g(2)g(there)e
(is)h(only)g(one)g(tree,)p 1347 1412 42 2 v 1347 1411
a Ff(q)34 b(q)1410 1419 y Fw(,)22 b(and)f(one)h(w)o(a)o(y)228
1477 y(to)d(lab)q(el)f(it,)g(again)h(giving)f(1)g(=)f(2)875
1459 y Fq(2)p Fr(\000)p Fq(2)959 1477 y Fw(tree)h(on)h(t)o(w)o(o)f(v)o
(ertices.)26 b(The)18 b(incidence)228 1535 y(matrix)c(is)862
1550 y Fk(\022)919 1590 y Fw(0)42 b(1)919 1648 y(1)g(0)1030
1550 y Fk(\023)1075 1620 y Ft(;)228 1725 y Fw(so)17 b(the)f(eigen)o(v)m
(alue)f(0)h(o)q(ccurs)h(with)f(m)o(ultiplic)o(it)o(y)d
Ft(z)1192 1732 y Fq(2)1225 1725 y Fw(=)h(0.)228 1842
y Fv(Example)23 b(26)p Fw(.)41 b(F)l(or)23 b Ft(n)i Fw(=)g(3)e(there)f
(is)g(only)h(one)g(tree,)p 1371 1835 84 2 v 1371 1834
a Ff(q)33 b(q)h(q)1475 1842 y Fw(,)24 b(and)f(three)228
1900 y(w)o(a)o(ys)17 b(to)g(lab)q(el)g(it,)f(giving)h(a)g(total)h(of)f
(3)f(=)f(3)1067 1882 y Fq(3)p Fr(\000)p Fq(2)1149 1900
y Fw(trees)i(on)g(three)g(v)o(ertices.)22 b(Up)228 1958
y(to)17 b(p)q(erm)o(utation)g(of)g(ro)o(ws)h(and)g(columns,)e(the)h
(incidence)e(matrix)h(for)h(eac)o(h)g(of)228 2017 y(these)f(three)f
(lab)q(eled)h(trees)g(is)822 2052 y Fk(0)822 2141 y(@)886
2093 y Fw(0)42 b(1)g(0)886 2151 y(1)g(0)g(1)886 2209
y(0)g(1)g(0)1063 2052 y Fk(1)1063 2141 y(A)1115 2152
y Ft(;)228 2300 y Fw(whic)o(h)19 b(has)h(zero)g(as)g(an)g(eigen)o(v)m
(alue)f(with)g(m)o(ultiplic)o(it)o(y)d(1)k(\(a)g(corresp)q(onding)228
2358 y(eigen)o(v)o(ector)15 b(is)532 2340 y Fs(t)547
2358 y Fw(\(1)p Ft(;)8 b Fw(0)p Ft(;)g Fo(\000)p Fw(1\)\),)17
b(so)h(there)e(is)h(a)g(total)h(of)f(3)12 b Fo(\002)f
Fw(1)18 b(zero)f(eigen)o(v)m(alues,)228 2416 y(and)g
Ft(z)346 2423 y Fq(3)379 2416 y Fw(=)d(3)228 2533 y Fv(Example)g(27)p
Fw(.)20 b(F)l(or)14 b Ft(n)g Fw(=)g(4)g(there)g(are)g(t)o(w)o(o)g
(trees,)p 1206 2526 125 2 v 1206 2525 a Ff(q)34 b(q)f(q)h(q)1365
2533 y Fw(\(12)15 b(w)o(a)o(ys)f(to)h(lab)q(el)228 2608
y(it\),)f(and)p 422 2601 84 2 v 463 2599 2 42 v 422 2599
a Ff(q)34 b(q)g(q)464 2558 y(q)541 2608 y Fw(\(4)16 b(w)o(a)o(ys)f(to)g
(lab)q(el)g(it\),)f(giving)h(a)g(total)g(of)h(12)9 b(+)g(4)14
b(=)g(16)g(=)g(4)1657 2590 y Fq(4)p Fr(\000)p Fq(2)p
eop
%%Page: 11 11
11 10 bop 1684 116 a Fl(11)228 213 y Fw(trees)18 b(on)i(three)e(v)o
(ertices.)28 b(Up)19 b(to)g(p)q(erm)o(utation)f(of)h(ro)o(ws)h(and)f
(columns,)f(the)228 271 y(t)o(w)o(o)e(incidence)e(matrices)h(are)468
297 y Fk(0)468 385 y(B)468 415 y(B)468 447 y(@)533 339
y Fw(0)41 b(1)h(0)g(0)533 397 y(1)f(0)h(1)g(0)533 455
y(0)f(1)h(0)g(1)533 514 y(0)f(0)h(1)g(0)775 297 y Fk(1)775
385 y(C)775 415 y(C)775 447 y(A)925 427 y Fw(and)1109
297 y Fk(0)1109 385 y(B)1109 415 y(B)1109 447 y(@)1174
339 y Fw(0)f(1)h(0)g(0)1174 397 y(1)f(0)h(1)g(1)1174
455 y(0)f(1)h(0)g(0)1174 514 y(0)f(1)h(0)g(0)1416 297
y Fk(1)1416 385 y(C)1416 415 y(C)1416 447 y(A)1468 427
y Ft(:)228 593 y Fw(The)22 b(\014rst)g(do)q(es)h(not)g(ha)o(v)o(e)f(0)g
(as)h(an)g(eigen)o(v)m(alue,)f(whereas)g(the)g(second)g(has)228
652 y(zero)d(as)i(an)f(eigen)o(v)m(alue)f(with)h(m)o(ultipli)o(cit)n(y)
d(2)j(\(corresp)q(onding)h(eigen)o(v)o(ectors)228 710
y(are)f(for)h(instance)587 692 y Fs(t)602 710 y Fw(\(1)p
Ft(;)8 b Fw(0)p Ft(;)g Fo(\000)p Fw(1)p Ft(;)g Fw(0\))21
b(and)961 692 y Fs(t)976 710 y Fw(\(1)p Ft(;)8 b Fw(0)p
Ft(;)g Fw(0)p Ft(;)g Fo(\000)p Fw(1\)\),)22 b(so)f(there)f(is)h(a)g
(total)g(of)228 768 y(12)12 b Fo(\002)e Fw(0)i(+)f(4)g
Fo(\002)g Fw(2)17 b(zero)f(eigen)o(v)m(alues,)f(and)h
Ft(z)1034 775 y Fq(4)1068 768 y Fw(=)d(8.)830 896 y Fp(References)249
975 y Fm([1])19 b(D.-M.)13 b(Cv)o(etk)o(o)o(vi)o(\023)-20
b(c,)13 b(M.)h(Do)q(ob)g(and)g(H.)g(Sac)o(hs,)g Fa(Sp)n(e)n(ctr)n(a)h
(of)g(Gr)n(aphs)p Fm(,)f(Academic)g(Press,)313 1025 y(New)h(Y)m(ork,)d
(1980.)249 1075 y([2])19 b(M.)12 b(Bauer)h(and)g(O.)f(Golinelli,)e
Fa(On)j(the)h(sp)n(e)n(ctrum)f(of)g(r)n(andom)h(gr)n(aphs)p
Fm(,)f(in)f(preparation.)249 1124 y([3])19 b(R.-P)m(.)24
b(Stanley)m(,)j Fa(Enumer)n(ative)f(Combinatorics,)h(V)m(ol)e(II)p
Fm(,)g(Cam)o(bridge)f(Univ)o(ersit)o(y)313 1174 y(Press,)15
b(Cam)o(bridge,)d(1999.)p 225 1391 1500 3 v 228 1479
a Fw(\(Concerned)k(with)g(sequence)f(A053605)p
 [[264 362 308 374] [1 1 1 [3 3]] [0 0 1]] (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=053605) pdfm 
(.\))p 225 1537 V 228 1625 a(Receiv)o(ed)20 b(No)o(v.)40
b(10,)25 b(1999;)i(published)c(in)f(Journal)h(of)g(In)o(teger)f
(Sequences)228 1683 y(Marc)o(h)16 b(2,)g(2000.)p 225
1742 V 228 1830 a(Return)g(to)g(Journal)h(of)g(In)o(teger)e(Sequences)g
(home)g(page)p
 [[181 278 386 290] [1 1 1 [3 3]] [0 0 1]] (http://www.research.att.com/~njas/sequences/JIS/) pdfm 
(.)p 225 1888 V eop
%%Trailer
end 
end