text: EXTREME NESTING IN CLE 15 E P PROOF. Since [X1] > 0, we may choose v > 0 so that [X1 ≥ v] ≥ 12. We ∞ partition (− , x) into intervals of length v: ∞ (cid:91) ∞ (− , x) = I where I = [x − (k + 1)v, x − kv) . k k k=0 Then we partition the event S − x ≥ α into subevents τx ∞ ∞ (cid:91) (cid:91) {Sτx − x ≥ α} = En,k where En,k = {Sn ∈ Ik, Sn+1 ≥ x + α} . n=0 k=0 The event En,k implies Xn+1 ≥ kv + α, and since Xn+1 is independent of Sn, we have E P P [eλ0X] [En,k] ≤ [Sn ∈ Ik] × eλ0(kv+α) . On the event Sn ∈ Ik, since Xn+1 is independePnt of what occurred earlier and is larger than v with probability at least 12, we have [Sn+1 ∈ Ik|Sn ∈ Ik, Sn−1, . . . , S1] ≤ 12. Thus ∞ ∑ P E [Sn ∈ Ik] = [ |{n : Sn ∈ Ik}| ] ≤ 2 . n=0 Thus P ∑∞ 2 E[eλ0X] 2 E[eλ0X] [S − x ≥ α] ≤ ≤ × e−λ0α . τx eλ0(kv+α) 1 − e−λ0v k=0 LEMMA 2.9. Let {Xj}j∈N be an i.i.d. sequence of random variables and let Sn = ∑n X . Let N be a positive integer-valued random variable, which need not be independent ofit=h1e Xi j’s. Suppose that there exists λ0 > 0 for which E[eλ0X1] < ∞ and q ∈ (0, 1) for P N which [N ≥ k] ≤ qk−1 for every k ∈ . Then there exist constants C, c > 0 (depending P on q and the law of X1) for which [SN > α] ≤ C exp(−cα) for every α > 0. E PROOF. Since q [eλX] is a continuous function of λ which is ﬁnite for λ = λ0 > 0 E and less than 1 for λ = 0, there is some c > 0 for which q [e2cX] < 1. The Cauchy- Schwarz inequality gives (cid:34) (cid:35) ∞ E E ∑ [ecSN] = ecSk1 {N=k} k=1 ∞ (cid:113) ∞ (cid:18)(cid:113) (cid:19)k ≤ ∑ E[e2cSk]P[N = k] = q−1/2 ∑ E[e2cX1]q < ∞. k=1 k=1 P E We conclude using the Markov inequality [SN > α] ≤ e−cα [ecSN]. ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: EXTREME

font: RCRQMV+URWPalladioL-Roma

text: NESTING

text: IN

text: CLE

text: E

text: P

text: PROOF.

text: Since

text: we

text: may

text: choose

text: v

font: FENOHZ+URWPalladioL-Ital

text: so

text: that

text: v]

text: We

font: RCNJAI+PazoMath

text: partition

text: x)

text: into

text: intervals

text: of

text: length

text: v:

text: x)

text: I

text: where

text: I

text: [x

text: (k

text: x

text: kv)

text: k

text: k

text: Then

text: we

text: partition

text: the

text: event

text: S

text: x

text: α

text: into

text: subevents

text: τx

text: {Sτx

text: x

text: α}

text: En,k

text: where

text: En,k

text: {Sn

text: Ik,

text: x

text: α}

text: The

text: event

text: En,k

text: implies

text: kv

text: α,

text: and

text: since

text: is

text: independent

text: of

text: Sn,

text: we

text: have

text: E

text: P

text: P

text: [En,k]

text: [Sn

text: Ik]

text: On

text: the

text: event

text: Sn

text: Ik,

text: since

text: is

text: independePnt

text: of

text: what

text: occurred

text: earlier

text: and

text: is

text: larger

text: than

text: v

text: with

text: probability

text: at

text: least

text: we

text: have

text: Ik|Sn

text: Ik,

text: Thus

text: P

text: E

text: [Sn

text: Ik]

text: |{n

text: Sn

text: Ik}|

text: Thus

text: P

text: [S

text: x

text: α]

text: e−λ0α

text: τx

text: LEMMA

text: Let

text: {Xj}j∈N

text: be

text: an

text: i.i.d.

text: sequence

text: of

text: random

text: variables

text: and

text: let

text: Sn

text: ∑n

text: X

text: Let

text: N

text: be

text: a

text: positive

text: integer-valued

text: random

text: variable,

text: which

text: need

text: not

text: be

text: independent

text: Xi

text: j’s.

text: Suppose

text: that

text: there

text: exists

text: λ0

text: for

text: which

text: and

text: q

text: for

text: P

text: N

text: which

text: [N

text: k]

text: for

text: every

text: k

text: Then

text: there

text: exist

text: constants

text: C,

text: c

text: (depending

text: P

text: on

text: q

text: and

text: the

text: law

text: of

text: for

text: which

text: [SN

text: α]

text: C

text: exp(−cα)

text: for

text: every

text: α

text: E

text: PROOF.

text: Since

text: q

text: [eλX]

text: is

text: a

text: continuous

text: function

text: of

text: λ

text: which

text: is

text: ﬁnite

text: for

text: λ

text: λ0

text: E

text: and

text: less

text: than

text: for

text: λ

text: there

text: is

text: some

text: c

text: for

text: which

text: q

text: The

text: Cauchy-

text: Schwarz

text: inequality

text: gives

text: E

text: E

text: [ecSN]

text: {N=k}

text: k]

text: P

text: E

text: We

text: conclude

text: using

text: the

text: Markov

text: inequality

text: [SN

text: α]

text: e−cα

text: [ecSN].

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 24 JASON MILLER, SAMUEL S.WATSON, AND DAVID B.WILSON P (4.4) [E1] = εγκ(ν)+o(1) as ε → 0 . Corollary 3.5 implies that for sufﬁciently small ε, we have P (4.5) [E2 | E1] ≥ 34 . Lemma 3.7 applied to the log conformal radius increment sequence implies that for some large enough M, (cid:104) (cid:16) (cid:17) (cid:105) (4.6) P CR 0; U0J0∩,ε ≥ M−1/2ε | E1 ≥ 78 . Lemma 2.9 and Corollary 3.5 together imply that for large enough M (cid:20) (cid:18) (cid:19) (cid:21) (cid:16) (cid:17) (4.7) P CR 0; UJ0⊂,ε / CR 0; UJ0∩,ε ≥ M−1/2 | E ≥ 7 . 0 0 1 8 Combining (4.4), (4.5), (4.6), and (4.7), we arrive at P [E1 ∩ E2 ∩ E3] = εγκ(ν)+o(1) as ε → 0 . The event E1 ∩ E2 ∩ E3 implies the event described in the lemma. Γ D We deﬁne the set P = P ( ) as follows. For z ∈ and k ≥ 0 we inductively ν ν deﬁne (see Figure 4.1): • Let τ0 = 0. D • Let Vzk = Uzτk be the connected component of \ Lτzk containing z. In particular, D V0 = D = . z D • Let ϕkz be the conformal map from Vzk to with ϕkz(z) = 0 and (ϕkz)(cid:48)(z) > 0. • Let t = 2−(k+1). k • Let τk+1 be the smallest j ∈ N such that ϕkz(Lzj ) ⊂ B(0, tk). Let Γ(cid:101)kz be the image under ϕkz of the loops of Γ which are surrounded by Lτzk and in the same component of D \ Lτk as z. Then Γ(cid:101)k is a CLE in D. z z κ Let M > 1 be a large enough constant for Lemma 4.3, and let Ek to be the event z described in Lemma 4.3 for the CLE Γ(cid:101)kz and ε = tk. We deﬁne (cid:92) Ek1,k2 := Ek . z z k1≤k<k2 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: paragraph

text: JASON

text: MILLER,

text: SAMUEL

text: S.WATSON,

text: AND

text: DAVID

text: B.WILSON

text: P

label: equation

text: as

text: ε

font: AVTGER+Fourier-Math-Letters-Italic

text: Corollary

text: implies

text: that

text: for

text: sufﬁciently

text: small

text: ε,

text: we

text: have

text: P

text: Lemma

text: applied

text: to

text: the

text: log

text: conformal

text: radius

text: increment

text: sequence

text: implies

text: that

text: for

text: some

text: large

text: enough

text: M,

text: P

text: CR

text: Lemma

text: and

text: Corollary

text: together

text: imply

text: that

text: for

text: large

text: enough

text: M

text: P

text: CR

text: CR

text: E

text: Combining

text: and

text: we

text: arrive

text: at

text: P

text: as

text: ε

text: The

text: event

text: implies

text: the

text: event

text: described

text: in

text: the

text: lemma.

text: Γ

text: D

text: We

text: deﬁne

text: the

text: set

text: P

text: P

text: as

text: follows.

text: For

text: z

text: and

text: k

text: we

text: inductively

text: ν

text: ν

text: deﬁne

text: (see

text: Figure

text: Let

text: τ0

text: D

text: Let

text: Vzk

text: Uzτk

text: be

text: the

text: connected

text: component

text: of

text: Lτzk

text: containing

text: z.

text: In

text: particular,

text: D

text: D

text: z

text: D

text: Let

text: ϕkz

text: be

text: the

text: conformal

text: map

text: from

text: Vzk

text: to

text: with

text: ϕkz(z)

text: and

text: Let

text: t

text: k

text: Let

text: be

text: the

text: smallest

text: j

text: N

text: such

text: that

text: ϕkz(Lzj

text: tk).

text: Let

text: be

text: the

text: image

text: under

text: ϕkz

text: of

text: the

text: loops

text: of

text: Γ

text: which

text: are

text: surrounded

text: by

text: Lτzk

text: and

text: in

text: the

text: same

text: component

text: of

text: D

text: Lτk

text: as

text: z.

text: Then

text: is

text: a

text: CLE

text: in

text: D.

text: z

text: z

text: κ

text: Let

text: M

text: be

text: a

text: large

text: enough

text: constant

text: for

text: Lemma

text: and

text: let

text: Ek

text: to

text: be

text: the

text: event

text: z

text: described

text: in

text: Lemma

text: for

text: the

text: CLE

text: and

text: ε

text: tk.

text: We

text: deﬁne

text: Ek

text: z

text: z

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: EXTREME NESTING IN CLE 39 Using (5.13), observe that if α = 0, then c (α) is less than γ (0, 0), which implies µ κ that ν1 > 0. Therefore, (5.14) follows in the case α = 0 from the lower semiconti- nuity of Λ(cid:63) at 0. For the case α > 0, we observe that νΛ(cid:63)(α/ν) ﬁnite on [ν(cid:48) , ν(cid:48) ]. By µ µ 1 2 lower semicontinuity and convexity of Λ(cid:63), this implies that νΛ(cid:63)(α/ν) is continu- µ µ ous on [ν(cid:48) , ν(cid:48) ]. Since [ν(cid:48) , ν(cid:48) ] is compact, we conclude that νΛ(cid:63)(α/ν) is uniformly 1 2 1 2 µ continuous on [ν(cid:48) , ν(cid:48) ]. Since νΛ(cid:63)(α(cid:48)/ν) can be written as α(cid:48) ναΛ(cid:63)(α/(να/α(cid:48))) (a 1 2 µ α α(cid:48) µ straightforward limiting argument shows that this equality holds even when ν = 0), the uniform continuity of Λ(cid:63) implies (5‹.14) except possibly at the endpoints ν(cid:48) and µ 1 ν(cid:48) . However, since Λ(cid:63) is lower semi-continuous, (5.14) holds at ν(cid:48) and ν(cid:48) as well. 2 µ 1 2 Recall the collection of balls Dr for r > 0 that we deﬁned in the proof of Proposi- N tion 4.2. For n ∈ , let (cid:110) (cid:111) Qn := Q ∈ Dexp(−n) : Sz(ε)(e−n) ∈ (α − δ, α + δ) . Our goal is to show that for all Q ∈ Dexp(−n) and n sufﬁciently large, P (5.15) [Q ∈ Qn] ≤ e−n(cµ(α)−ε/2) . ‹ The rest of the proof is similar to that of Proposition 4.2. To prove (5.15), we abbreviate N(cid:102) (e−n) as N(cid:102) and write z(Q) (cid:104) (cid:104) ‹ (cid:105)(cid:105) P[Q ∈ Qn] =‹ E P Sz(Q)(e−n) ∈ (α − δ, α + δ) | N(cid:102) . ‹ ‹ We split the conditional probability according to the value of N(cid:102): ‹ (cid:104) (cid:104) (cid:105)(cid:105) P E ‹ P [Q ∈ Qn] ≤ (cid:104) 1{N∈/[ν1,ν2]} Sz(Q(cid:104))(e−n) ∈ (α − δ, α + δ) | N(cid:102) (cid:105)(cid:105) E P + (cid:104)1{N∈[ν1,ν2]\[ν1(cid:48)(cid:104),ν2(cid:48) ]} Sz(Q)(e−n) ∈ (α − δ, α + δ(cid:105))(cid:105)| N(cid:102) E P + 1{N∈[ν1(cid:48) ,ν2(cid:48) ]} Sz(Q)(e−n) ∈ (α − δ, α + δ) | N(cid:102) . ‹ ‹ The ﬁrst term on the right-hand side is bounded above by e−n(cµ(α)+o(1)), because of our choice of ν1 and ν2. Similarly, the second term is bounded above by e−n(cµ(α)+o(1)) by Crame´r’s theorem and our ch‹oice of‹ν1(cid:48) a‹nd ν2(cid:48) .‹Thus it r‹emain‹s to show that the third term is bounde‹d above by e−n(cµ(α)−ε/2) for all n sufﬁciently large. Multiplying and dividing by e−nNΛ(cid:63)(1/N), applying Crame´r’s t‹heorem‹, and using (5.14), we ﬁnd κ ‹ that for large enough n, the third term is bounded above by (cid:104) (cid:105) E 1 e−n(NΛ(cid:63)(α/N)+NΛ(cid:63)(1/N)−ε/2)enNΛ(cid:63)(1/N) µ κ κ {N∈[ν1(cid:48) ,ν2]} (cid:104) (cid:105) ≤ e−n(cµ(α)−ε/4)E 1 enNΛκ(cid:63)(1/N) . N∈[ν1(cid:48) ,ν2(cid:48) ] ##LTLine## ##LTLine##

text: EXTREME

text: NESTING

text: IN

text: CLE

text: Using

text: observe

text: that

text: if

text: α

text: then

text: c

text: (α)

text: is

text: less

text: than

text: γ

text: which

text: implies

text: µ

text: κ

text: that

text: ν1

text: Therefore,

text: follows

text: in

text: the

text: case

text: α

text: from

text: the

text: lower

text: semiconti-

text: nuity

text: of

font: FBXWKP+Fourier-Math-Letters

text: at

text: For

text: the

text: case

text: α

text: we

text: observe

text: that

text: ﬁnite

text: on

text: By

text: µ

text: µ

text: lower

text: semicontinuity

text: and

text: convexity

text: of

text: this

text: implies

text: that

text: is

text: continu-

text: µ

text: µ

text: ous

text: on

text: Since

text: is

text: compact,

text: we

text: conclude

text: that

text: is

text: uniformly

text: µ

text: continuous

text: on

text: Since

text: can

text: be

text: written

text: as

text: (a

text: µ

text: α

text: µ

text: straightforward

text: limiting

text: argument

text: shows

text: that

text: this

text: equality

text: holds

text: even

text: when

text: ν

text: the

text: uniform

text: continuity

text: of

text: implies

text: except

text: possibly

text: at

text: the

text: endpoints

text: and

text: µ

text: However,

text: since

text: is

text: lower

text: semi-continuous,

text: holds

text: at

text: and

text: as

text: well.

text: µ

text: Recall

text: the

text: collection

text: of

text: balls

text: Dr

text: for

text: r

text: that

text: we

text: deﬁned

text: in

text: the

text: proof

text: of

text: Proposi-

text: N

text: tion

text: For

text: n

text: let

text: Qn

text: Q

text: Dexp(−n)

text: Sz(ε)(e−n)

text: (α

text: δ,

text: α

text: δ)

text: Our

text: goal

text: is

text: to

text: show

text: that

text: for

text: all

text: Q

text: Dexp(−n)

text: and

text: n

text: sufﬁciently

text: large,

text: P

text: [Q

text: Qn]

text: The

text: rest

text: of

text: the

text: proof

text: is

text: similar

text: to

text: that

text: of

text: Proposition

text: To

text: prove

text: we

text: abbreviate

text: (e−n)

text: as

text: and

text: write

text: z(Q)

text: P[Q

text: Qn]

text: E

text: P

text: Sz(Q)(e−n)

text: (α

text: δ,

text: α

text: δ)

text: We

text: split

text: the

text: conditional

text: probability

text: according

text: to

text: the

text: value

text: of

text: P

text: E

text: P

text: [Q

text: Qn]

text: (α

text: δ,

text: α

text: δ)

text: E

text: P

text: Sz(Q)(e−n)

text: (α

text: δ,

text: α

text: E

text: P

text: Sz(Q)(e−n)

text: (α

text: δ,

text: α

text: δ)

text: The

text: ﬁrst

text: term

text: on

text: the

text: right-hand

text: side

text: is

text: bounded

text: above

text: by

text: because

text: of

text: our

text: choice

text: of

text: ν1

text: and

text: Similarly,

text: the

text: second

text: term

text: is

text: bounded

text: above

text: by

text: by

text: Crame´r’s

text: theorem

text: and

text: our

text: ch‹oice

text: a‹nd

text: .‹Thus

text: it

text: r‹emain‹s

text: to

text: show

text: that

text: the

text: third

text: term

text: is

text: bounde‹d

text: above

text: by

text: for

text: all

text: n

text: sufﬁciently

text: large.

text: Multiplying

text: and

text: dividing

text: by

text: applying

text: Crame´r’s

text: t‹heorem‹,

text: and

text: using

text: we

text: ﬁnd

text: κ

text: that

text: for

text: large

text: enough

text: n,

text: the

text: third

text: term

text: is

text: bounded

text: above

text: by

text: E

text: µ

text: κ

text: κ

text: ##LTLine##

text: ##LTLine##


text: ‹ ‹ ‹ 40 JASON MILLER, SAMUEL S.WATSON, AND DAVID B.WILSON ‹ ‹ (cid:104) (cid:105) ‹ ‹ E Th‹us it remains to show that 1 enNΛκ(cid:63)(1/N) =‹eo(n). Applying (2.1) from N∈[ν1(cid:48) ,ν2(cid:48) ] Crame´r’s theorem, we ﬁnd that if νtypical ≤ ν2(cid:48) , we have E (cid:20)1 en NΛκ(cid:63)(1/N)(cid:21) ≤ (cid:100)(ν2(cid:48) −ν∑typical)n(cid:101) E (cid:20)1 ‹ en NΛκ(cid:63)(1/N)(cid:21) N∈[νtypical,ν2(cid:48) ] k=1 {(k−1)/n≤ N−νtypical<k/n} (cid:100)(ν2(cid:48) −ν∑typical)n(cid:101) E (cid:20) (cid:21) ≤ enfκ(k/n) 1 {(k−1)/n≤ N−νtypical} k=1 (cid:100)(ν2(cid:48) −ν∑typical)n(cid:101) ≤ en[fκ(k/n)−fκ((k−1)/n)], k=1 (cid:0) (cid:1) where f (ν) := νΛ(cid:63) 1 . The mean value theorem implies that the summand is κ κ ν bounded above by exp(sup ‹ f (cid:48) (ν)‹). Therefore, the expectation on the event ‹ν∈[νtypical,ν2(cid:48) ] κ {N(cid:102) ∈ [νtypical, ν2(cid:48) ]} is O(n). An analogous argument gives the same bound for the expectation on {N(cid:102) ∈ [ν1(cid:48) , νtypical]}, so (cid:104) (cid:105) E 1 en NΛκ(cid:63)(1/N) = O(n) = eo(n). N∈‹[ν1(cid:48) ,ν2(cid:48) ] Now consider the case Λ(cid:63)(0) = ∞, which implies that ν0(0) = 0. As in the case Λ(cid:63)(0) < ∞, it sufﬁces to shoµw that for every ε > 0, there exists δ > 0 such that µ (cid:104) (cid:105) P (5.16) |Sz(e−n)| ≤ δ ≤ e−n(γκ(0,0)−ε) . Choose η > 0 ‹small enough that νΛκ(cid:63)(ν‹) ≥ 1 − 2/κ − 3κ/32 − ε/2 whenever ν ∈ (0, η). Then choose δ > 0 small enough that Λ(cid:63)(x) ≥ 2/η for all x ∈ (−δ/η, δ/η) µ (this is possible by lower semicontinuity‹of Λ(cid:63)). Again abbr‹eviating N(cid:102)z(e−n) as N(cid:102), we write ‹ P (cid:104) (cid:105) E (cid:104)P (cid:104) (cid:105)(cid:105) ‹ |Sz(e−n)| ≤ δ = |Sz(e−n)| ≤ δ | N(cid:102) (cid:104) (cid:104) (cid:105) (cid:105) E P = |Sz(e−n)| ≤ δ | N(cid:102) 1 N∈[0,η) (cid:104) (cid:104) (cid:105) (cid:105) E P + |Sz(e−n)| ≤ δ | N(cid:102) 1N∈[η,∞) . Bounding the conditional probability by 1 and using our choice of η, we see that the ﬁrst term is bounded above by e−n(γκ(0,0)−ε). F‹or the second term, we note by (2.1) in Crame´r’s theorem that the conditional probability is bounded above by (cid:32) (cid:33) 2 exp −nN(cid:102) inf Λ(cid:63)(y) . |y|≤δ/N ##LTLine##

font: IXDXNY+Yhcmex

text: JASON

text: MILLER,

text: SAMUEL

text: S.WATSON,

text: AND

text: DAVID

text: B.WILSON

text: E

text: Th‹us

text: it

text: remains

text: to

text: show

text: that

font: OAKKHH+URWPalladioL-Bold

text: =‹eo(n).

text: Applying

text: from

text: Crame´r’s

text: theorem,

text: we

text: ﬁnd

text: that

text: if

text: νtypical

text: we

text: have

text: E

text: en

text: E

text: en

text: N−νtypical<k/n}

text: E

text: enfκ(k/n)

text: N−νtypical}

text: where

text: f

text: (ν)

text: The

text: mean

text: value

text: theorem

text: implies

text: that

text: the

text: summand

text: is

text: κ

text: κ

text: ν

text: bounded

text: above

text: by

text: exp(sup

text: f

text: (ν)‹).

text: Therefore,

text: the

text: expectation

text: on

text: the

text: event

text: κ

text: [νtypical,

text: is

text: O(n).

text: An

text: analogous

text: argument

text: gives

text: the

text: same

text: bound

text: for

text: the

text: expectation

text: on

text: νtypical]},

text: so

text: E

text: en

text: O(n)

text: eo(n).

text: Now

text: consider

text: the

text: case

text: which

text: implies

text: that

text: As

text: in

text: the

text: case

text: it

text: sufﬁces

text: to

text: shoµw

text: that

text: for

text: every

text: ε

text: there

text: exists

text: δ

text: such

text: that

text: µ

text: P

text: |Sz(e−n)|

text: δ

text: Choose

text: η

text: ‹small

text: enough

text: that

text: whenever

text: ν

text: η).

text: Then

text: choose

text: δ

text: small

text: enough

text: that

text: for

text: all

text: x

text: (−δ/η,

text: δ/η)

text: µ

text: (this

text: is

text: possible

text: by

text: lower

text: semicontinuity‹of

text: Again

text: abbr‹eviating

text: as

text: we

text: write

text: P

text: E

text: |Sz(e−n)|

text: δ

text: |Sz(e−n)|

text: δ

text: E

text: P

text: |Sz(e−n)|

text: δ

text: E

text: P

text: |Sz(e−n)|

text: δ

text: Bounding

text: the

text: conditional

text: probability

text: by

text: and

text: using

text: our

text: choice

text: of

text: η,

text: we

text: see

text: that

text: the

text: ﬁrst

text: term

text: is

text: bounded

text: above

text: by

text: F‹or

text: the

text: second

text: term,

text: we

text: note

text: by

text: in

text: Crame´r’s

text: theorem

text: that

text: the

text: conditional

text: probability

text: is

text: bounded

text: above

text: by

text: exp

text: inf

text: |y|≤δ/N

text: ##LTLine##


text: 42 JASON MILLER, SAMUEL S.WATSON, AND DAVID B.WILSON PROOF OF THEOREM 1.3. In light of Theorems 5.1 and 5.3, it sufﬁces to show that the maximum of 2 − γ (α, ν) is obtained when ν = α coth(π2α). As in the proof κ σ σ of Theorem 1.2, we begin by writing (cid:18) (cid:19) (cid:16)α(cid:17) 1 γ (α, ν) = νΛ(cid:63) + νΛ(cid:63) = sup [ηα + λ − ν(Λ (λ) + Λ (η))] . κ κ ν µ ν η,λ κ µ At the minimizing value of ν and the corresponding maximizing values of η and λ, the derivatives of the expression in brackets with respect to ν, λ, and η are all zero. Differentiating, we obtain the system Λ (λ) + Λ (η) = 0 κ µ 1 1 Λ(cid:48) (λ) = Λ(cid:48) (η) = . κ α µ ν √ The ﬁrst equation implies ση = π −2λ as in (5.17). Substituting for λ in the equation Λ(cid:48) (λ) = 1 Λ(cid:48) (η), we get α = σ2η/π2. Finally, substituting into 1 Λ(cid:48) (η) = κ α (cid:16)µ (cid:17) α µ 1/ν gives ν = α coth π2α , as desired. σ σ One of the consequences of Theorem 1.1 is that for each κ ∈ (8/3, 8) there exists a constant c such that the following is true. Almost surely, sup Sz(ε) = c(1 + o(1)) log(1/ε) as ε → 0 . z∈D Is it possible to remove the o(1) and give the order of the correction term? In particular, in analogy with the work of Bramson and Zeitouni [BZ12] for the discrete GFF, is it true that there exist a constant b such that sup Sz(ε) = c log(1/ε) + b log log(1/ε) + O(1) as ε → 0? z∈D Do the discrete loop models that are known to converge to CLE have the same extreme nesting behavior as CLE? ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: JASON

text: MILLER,

text: SAMUEL

text: S.WATSON,

text: AND

text: DAVID

text: B.WILSON

text: PROOF

text: OF

text: THEOREM

text: In

text: light

text: of

text: Theorems

text: and

text: it

text: sufﬁces

text: to

text: show

text: that

text: the

text: maximum

text: of

text: γ

text: (α,

text: ν)

text: is

text: obtained

text: when

text: ν

text: α

text: As

text: in

text: the

text: proof

text: κ

text: σ

text: σ

text: of

text: Theorem

text: we

text: begin

text: by

text: writing

text: γ

text: (α,

text: ν)

text: sup

text: [ηα

text: λ

text: ν(Λ

text: (λ)

text: Λ

text: (η))]

text: κ

text: κ

text: ν

text: µ

text: ν

text: η,λ

text: κ

text: µ

text: At

text: the

text: minimizing

text: value

text: of

text: ν

text: and

text: the

text: corresponding

text: maximizing

text: values

text: of

text: η

text: and

text: λ,

text: the

text: derivatives

text: of

text: the

text: expression

text: in

text: brackets

text: with

text: respect

text: to

text: ν,

text: λ,

text: and

text: η

text: are

text: all

text: zero.

text: Differentiating,

text: we

text: obtain

text: the

text: system

text: Λ

text: (λ)

text: Λ

text: (η)

text: κ

text: µ

text: (λ)

text: (η)

text: κ

text: α

text: µ

text: ν

text: The

text: ﬁrst

text: equation

text: implies

text: ση

text: π

text: −2λ

text: as

text: in

text: Substituting

text: for

text: λ

text: in

text: the

text: equation

text: (λ)

text: (η),

text: we

text: get

text: α

text: Finally,

text: substituting

text: into

text: (η)

text: κ

text: α

text: α

text: µ

text: gives

text: ν

text: α

text: coth

text: π2α

text: as

text: desired.

text: σ

text: σ

text: One

text: of

text: the

text: consequences

text: of

text: Theorem

text: is

text: that

text: for

text: each

text: κ

text: there

text: exists

text: a

text: constant

text: c

text: such

text: that

text: the

text: following

text: is

text: true.

text: Almost

text: surely,

text: sup

text: Sz(ε)

text: as

text: ε

text: z∈D

text: Is

text: it

text: possible

text: to

text: remove

text: the

text: and

text: give

text: the

text: order

text: of

text: the

text: correction

text: term?

text: In

text: particular,

text: in

text: analogy

text: with

text: the

text: work

text: of

text: Bramson

text: and

text: Zeitouni

text: for

text: the

text: discrete

text: GFF,

text: is

text: it

text: true

text: that

text: there

text: exist

text: a

text: constant

text: b

text: such

text: that

text: sup

text: Sz(ε)

text: c

text: b

text: log

text: as

text: ε

text: z∈D

text: Do

text: the

text: discrete

text: loop

text: models

text: that

text: are

text: known

text: to

text: converge

text: to

text: CLE

text: have

text: the

text: same

text: extreme

text: nesting

text: behavior

text: as

text: CLE?

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ‹ EXTREME NESTING IN CLE 7 Hausdorff dimension of the set (cid:26) (cid:27) ‹ Φµ(Γ) := z ∈ D : lim S (z) = α α ε ε→0+ of extremes of the normalized weighted loop counts a graph 1 ∑ (1.6) Sz(ε) = log(1/ε)Sz(ε) where Sz(ε) = Γ ξL , L∈ z(ε) Γ Γ and z(ε) is the set of loops of which surround B(z, ε). This dimension is given in terms of Λ(cid:63) and the Fenchel-Legendre transform Λ(cid:63) of µ. Although the dimension for κ µ general weight measures µ and κ ∈ (8/3, 8) is given by a complicated optimization problem, when κ = 4 and µ is a signed Bernoulli distribution, this dimension takes a particularly nice form. We state this result as our second theorem. THEOREM 1.2. Fix σ > 0, and deﬁne µB({σ}) = µB({−σ}) = 12. In the special case κ = 4 and µ = µB, almost surely (cid:18) (cid:19) 2 (1.7) dim ΦµB(Γ) = max 0, 2 − π α2 . H α 2σ2 This case has a special interpretation which explains the formula (1.7) for the √ dimension. It is proved in [MS14] that for σ = π/2, the random height ﬁeld Sz(ε) converges in the space of distributions as ε → 0 to a two-dimensional Gaussian Γ free ﬁeld h, and the loops can be thought of as the level sets of h. Since h is distribution-valued, h does not have a well-deﬁned value at any given point, nor does h have level sets strictly speaking, but there is a way to make this precise. This GFF interpretation suggests a correspondence between the extremes of Sz(ε) and the extremes of h. The extreme values of h (also called thick points) can be deﬁned by considering the average h (z) of h on ∂B(z, ε) and deﬁning T(α) to be ε the set of points z for which h (z) grows like α log(1/ε) as ε → 0. Thick points were ε introduced by Kahane in the context of Gaussian multiplicative chaos (see [RV13, Sect. 4] for further background). It is shown in [HMP10] that dim T(α) = 2 − πα2, √ H which equals dim ΦµB when σ = π/2 and κ = 4. The following theorem relates H exceptional loop count growth with the extremes of the GFF. Loosely speaking, it says that for each α there is a unique value of ν for which “most” of the α-thick points have loop counts N(cid:102) ≈ ν. √ √ THEO√REM 1√.3. Let κ = 4 and µB({ π/2}) = µB({− π/2}) = 12. For every α ∈ [− 2/π, 2/π], there exists a unique ν = ν(α) ≥ 0 such that the Hausdorff ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: EXTREME

text: NESTING

text: IN

text: CLE

text: Hausdorff

text: dimension

text: of

text: the

text: set

text: Φµ(Γ)

text: z

text: D

text: lim

text: S

text: (z)

text: α

text: α

text: ε

text: ε→0+

text: of

text: extremes

text: of

text: the

text: normalized

text: weighted

text: loop

text: counts

text: a

text: graph

text: Sz(ε)

text: where

text: Sz(ε)

text: Γ

text: ξL

text: L∈

text: z(ε)

text: Γ

text: Γ

text: and

text: z(ε)

text: is

text: the

text: set

text: of

text: loops

text: of

text: which

text: surround

text: B(z,

text: ε).

text: This

text: dimension

text: is

text: given

text: in

text: terms

text: of

text: and

text: the

text: Fenchel-Legendre

text: transform

text: of

text: µ.

text: Although

text: the

text: dimension

text: for

text: κ

text: µ

text: general

text: weight

text: measures

text: µ

text: and

text: κ

text: is

text: given

text: by

text: a

text: complicated

text: optimization

text: problem,

text: when

text: κ

text: and

text: µ

text: is

text: a

text: signed

text: Bernoulli

text: distribution,

text: this

text: dimension

text: takes

text: a

text: particularly

text: nice

text: form.

text: We

text: state

text: this

text: result

text: as

text: our

text: second

text: theorem.

text: THEOREM

text: Fix

text: σ

text: and

text: deﬁne

text: µB({σ})

text: µB({−σ})

text: In

text: the

text: special

text: case

text: κ

text: and

text: µ

text: µB,

text: almost

text: surely

text: dim

text: ΦµB(Γ)

text: max

text: π

text: α2

text: H

text: α

text: This

text: case

text: has

text: a

text: special

text: interpretation

text: which

text: explains

text: the

text: formula

text: for

text: the

text: dimension.

text: It

text: is

text: proved

text: in

text: that

text: for

text: σ

text: the

text: random

text: height

text: ﬁeld

text: Sz(ε)

text: converges

text: in

text: the

text: space

text: of

text: distributions

text: as

text: ε

text: to

text: a

text: two-dimensional

text: Gaussian

text: Γ

text: free

text: ﬁeld

text: h,

text: and

text: the

text: loops

text: can

text: be

text: thought

text: of

text: as

text: the

text: level

text: sets

text: of

text: h.

text: Since

text: h

text: is

text: distribution-valued,

text: h

text: does

text: not

text: have

text: a

text: well-deﬁned

text: value

text: at

text: any

text: given

text: point,

text: nor

text: does

text: h

text: have

text: level

text: sets

text: strictly

text: speaking,

text: but

text: there

text: is

text: a

text: way

text: to

text: make

text: this

text: precise.

text: This

text: GFF

text: interpretation

text: suggests

text: a

text: correspondence

text: between

text: the

text: extremes

text: of

text: Sz(ε)

text: and

text: the

text: extremes

text: of

text: h.

text: The

text: extreme

text: values

text: of

text: h

text: (also

text: called

text: thick

text: points)

text: can

text: be

text: deﬁned

text: by

text: considering

text: the

text: average

text: h

text: (z)

text: of

text: h

text: on

text: ∂B(z,

text: ε)

text: and

text: deﬁning

text: T(α)

text: to

text: be

text: ε

text: the

text: set

text: of

text: points

text: z

text: for

text: which

text: h

text: (z)

text: grows

text: like

text: α

text: as

text: ε

text: Thick

text: points

text: were

text: ε

text: introduced

text: by

text: Kahane

text: in

text: the

text: context

text: of

text: Gaussian

text: multiplicative

text: chaos

text: (see

text: Sect.

text: for

text: further

text: background).

text: It

text: is

text: shown

text: in

text: that

text: dim

text: T(α)

text: πα2,

text: H

text: which

text: equals

text: dim

text: ΦµB

text: when

text: σ

text: and

text: κ

text: The

text: following

text: theorem

text: relates

text: H

text: exceptional

text: loop

text: count

text: growth

text: with

text: the

text: extremes

text: of

text: the

text: GFF.

text: Loosely

text: speaking,

text: it

text: says

text: that

text: for

text: each

text: α

text: there

text: is

text: a

text: unique

text: value

text: of

text: ν

text: for

text: which

text: “most”

text: of

text: the

text: α-thick

text: points

text: have

text: loop

text: counts

text: ν.

text: THEO√REM

text: Let

text: κ

text: and

text: µB({

text: µB({−

text: For

text: every

text: α

text: there

text: exists

text: a

text: unique

text: ν

text: ν(α)

text: such

text: that

text: the

text: Hausdorff

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 30 JASON MILLER, SAMUEL S.WATSON, AND DAVID B.WILSON ∈ ∞ PR−OORF. We claim that for all ψ Cc (D), the se⊂quence ψ fn is∈CaucRhy in H s( d). We choose j large enough that supp ψ K . For all g Hs( d), j |(cid:104) (cid:105) − (cid:104) (cid:105)| |(cid:104) − (cid:105)| ψ fn, g ψ fm, g = ψj( fn fm), ψg . By hypothesis ψj{fn con(cid:107)ve(cid:107)rges in ≤H−s}(Rd) as n → ∞, so we may ta(cid:107)ke th−e sψthufapmtr(cid:107)−feoHmr−Ruse(Rmvde)roy→vψe0r∈asgCmc∞:i(nD(gm),,Htnhs)(eRr→de) e∞xi.s1Stsinfocψef ∈bHo−Hths−(Rss(iddR)edis)s tscouomcchopntlhcelatuetd,ψietffnoψ→llfonwf ψs in H s( d). ∈ ∞ ∞ We deﬁne a linear functional f on C (D) as follows. For g C (D), set c c (cid:104) (cid:105) (cid:104) (cid:105) (5.5) f , g := f ψ, g , where ψ is a smooth compactly supported function which is identically equal to 1 on the support of g. To see that this deﬁnition does not depend on ∈ ∈ ∞ ∞ the choice of ψ, suppose that ψ C (D) and ψ C (D) are both equal 1 c 2 c to 1 on the support of g. Then we have (cid:104) (cid:105) − (cid:104) (cid:105) (cid:104) − (cid:105) f ψ1, g f ψ2, g = nl→im∞ (ψ1 ψ2) fn, g = 0 , as desired. From the deﬁnition in (5.5), f inherits linearity from f ψ and ∈ − thus deﬁnes a linear functional on C∞(D). Furthermore, f H s(D) since ∈ − ∈ c → −loc ψ f =→f ψ H s(Rd)−forRall ψ Cc∞(D). Finally, fn f in Hlocs(D) since ψ fn ψ f = f ψ in H s( d). ∈ ∞ PROOF OF PROPOSITION 5.1. Fix ψ Cc (D). Let Dψ be a bounded open set containing the support ψ and whose closure is contained in D. Since D is − ψ bounded, we may scale and translate it so that it is contained in ( π, π)d. We − − will calcTulate the Fourier coefﬁcients of ψ( fn+1 fn∈) Zin ( π, π)d, identifying it with d. By Fubini’s theorem, we have for all k d ##LTLine## ##LTLine## ##LTLine## ##LTLine##

font: IHVTGK+URWPalladioL-Roma

text: JASON

text: MILLER,

text: SAMUEL

text: S.WATSON,

text: AND

text: DAVID

text: B.WILSON

font: JNKECP+PazoMath

text: PR−OORF.

text: We

text: claim

text: that

text: for

text: all

text: ψ

font: GLFQFV+Fourier-Math-Letters-Italic

text: Cc

font: XDBXPW+URWPalladioL-Ital

text: (D),

text: the

text: se⊂quence

text: ψ

text: fn

text: is∈CaucRhy

text: in

text: H

text: s(

text: d).

text: We

text: choose

text: j

text: large

text: enough

text: that

text: supp

text: ψ

text: K

text: For

text: all

text: g

text: Hs(

text: d),

text: j

text: ψ

text: fn,

text: g

text: ψ

text: fm,

text: g

text: ψj(

text: fn

text: fm),

text: ψg

text: By

text: hypothesis

text: ψj{fn

text: in

text: ≤H−s}(Rd)

text: as

text: n

text: so

text: we

text: may

text: th−e

text: ∈bHo−Hths−(Rss(iddR)edis)s

text: ψs

text: in

text: H

text: s(

text: d).

text: We

text: deﬁne

text: a

text: linear

text: functional

text: f

text: on

text: C

text: (D)

text: as

text: follows.

text: For

text: g

text: C

text: (D),

text: set

text: c

text: c

text: f

text: g

text: f

text: ψ,

text: g

text: where

text: ψ

text: is

text: a

text: smooth

text: compactly

text: supported

text: function

text: which

text: is

text: identically

text: equal

text: to

text: on

text: the

text: support

text: of

text: g.

text: To

text: see

text: that

text: this

text: deﬁnition

text: does

text: not

text: depend

text: on

text: the

text: choice

text: of

text: ψ,

text: suppose

text: that

text: ψ

text: C

text: (D)

text: and

text: ψ

text: C

text: (D)

text: are

text: both

text: equal

text: c

text: c

text: to

text: on

text: the

text: support

text: of

text: g.

text: Then

text: we

text: have

text: f

text: g

text: f

text: g

text: nl→im∞

text: fn,

text: g

text: as

text: desired.

text: From

text: the

text: deﬁnition

text: in

text: f

text: inherits

text: linearity

text: from

text: f

text: ψ

text: and

text: thus

text: deﬁnes

text: a

text: linear

text: functional

text: on

text: C∞(D).

text: Furthermore,

text: f

text: H

text: s(D)

text: since

text: c

text: −loc

text: ψ

text: f

text: =→f

text: ψ

text: H

text: s(Rd)−forRall

text: ψ

text: Cc∞(D).

text: Finally,

text: fn

text: f

text: in

text: Hlocs(D)

text: since

text: ψ

text: fn

text: ψ

text: f

text: f

text: ψ

text: in

text: H

text: s(

text: d).

text: PROOF

text: OF

text: PROPOSITION

text: Fix

text: ψ

text: Cc

text: (D).

text: Let

text: Dψ

text: be

text: a

text: bounded

text: open

text: set

text: containing

text: the

text: support

text: ψ

text: and

text: whose

text: closure

text: is

text: contained

text: in

text: D.

text: Since

text: D

text: is

text: ψ

text: bounded,

text: we

text: may

text: scale

text: and

text: translate

text: it

text: so

text: that

text: it

text: is

text: contained

text: in

text: π,

text: π)d.

text: We

text: will

text: calcTulate

text: the

text: Fourier

text: coefﬁcients

text: of

text: ψ(

text: fn∈)

text: Zin

text: π,

text: π)d,

text: identifying

text: it

text: with

text: d.

text: By

text: Fubini’s

text: theorem,

text: we

text: have

text: for

text: all

text: k

text: d

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: THE CLE NESTING FIELD 33 PROOF. Immediate from Theorem 4.1 and Proposition 5.1. ∈ (cid:104) (cid:105) → ∞ (cid:104)PRO(cid:105)OF OF THEOREM 1.1. We claim that for all g Cc (D), we have hε, g h, g almost surely. Suppose ﬁrst that the loop weights are almost surely ∈ ∞ nonnegative and that g C (D) is a nonnegative test function. Deﬁne (cid:104) (cid:105) (cid:104) c − (cid:105) −(cid:104)E − (cid:105) F(x) := he−x, g , F1(x) := Sz(e x), g , and F2(x) := [Sz(e x)], g . We apply Lemma 6.1 with α as given in Lemma 2.6, which implies (cid:104) (cid:105) (cid:104) (cid:105) ∈ ≥ ∞ (6.1) lim h , g = h, g for g C (D), g 0 . → ε c ε 0 ∈ ∈ ∞ ∞ For arbitrary g C (D), we choose g˜ C (D) so that g˜ and g + g˜ are both c c nonnegative. Applying (6.1) to g˜ and g + g˜, we see that (cid:104) (cid:105) (cid:104) (cid:105) ∈ ∞ (6.2) lim h , g = h, g for g C (D) . → ε c ε 0 Finally, consider loop weights which are not necessarily nonnegative. Deﬁne ± ± − − loop weights ξL = (ξL) , where x+ = max(0, x) and x = max(0, x) ∈ R ± denote the positive and negative parts of x . Deﬁne h to be the weighted ± nesting ﬁelds associated with the weights ξL (associated with the same CLE). (cid:104) ± (cid:105) → (cid:104) ± (cid:105) Then h , g h , g almost surely, and ε (cid:104) (cid:105) (cid:104) (cid:105) − (cid:104) − (cid:105) → (cid:104) (cid:105) − (cid:104) − (cid:105) (cid:104) (cid:105) h , g = h+, g h , g h+, g h , g = h, g , ε ε ε (cid:104) (cid:105) → (cid:104) (cid:105) which concludes the proof that h , g h, g almost surely. ε To see that the ﬁeld h is measurable with respect to the σ-algebra Σ gener- ated by the CLEκ aFnd the weights (ξL)L∈Γ, note that there exists a count- ∞ able dense subset of C (D) [Tao10, Exercise 1.13.6]. Observe that h − c { ∈ N 2 ∈n is Σ-measurable and h is determined by the values h − (g) : n , g F} 2 n . Since h is an almost sure limit of h − , we conclude that h is also Σ- 2 n measurable. ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: THE

text: CLE

text: NESTING

text: FIELD

text: PROOF.

text: Immediate

text: from

text: Theorem

text: and

text: Proposition

text: OF

text: THEOREM

text: We

text: claim

text: that

text: for

text: all

text: g

text: Cc

text: (D),

text: we

text: have

text: hε,

text: g

text: h,

text: g

text: almost

text: surely.

text: Suppose

text: ﬁrst

text: that

text: the

text: loop

text: weights

text: are

text: almost

text: surely

text: nonnegative

text: and

text: that

text: g

text: C

text: (D)

text: is

text: a

text: nonnegative

text: test

text: function.

text: Deﬁne

text: c

text: F(x)

text: he−x,

text: g

text: Sz(e

text: x),

text: g

text: and

text: [Sz(e

text: x)],

text: g

text: We

text: apply

text: Lemma

text: with

text: α

text: as

text: given

text: in

text: Lemma

text: which

text: implies

text: lim

text: h

text: g

text: h,

text: g

text: for

text: g

text: C

text: (D),

text: g

text: ε

text: c

text: ε

text: For

text: arbitrary

text: g

text: C

text: (D),

text: we

text: choose

text: g˜

text: C

text: (D)

text: so

text: that

text: g˜

text: and

text: g

text: g˜

text: are

text: both

text: c

text: c

text: nonnegative.

text: Applying

text: to

text: g˜

text: and

text: g

text: g˜,

text: we

text: see

text: that

text: lim

text: h

text: g

text: h,

text: g

text: for

text: g

text: C

text: (D)

text: ε

text: c

text: ε

text: Finally,

text: consider

text: loop

text: weights

text: which

text: are

text: not

text: necessarily

text: nonnegative.

text: Deﬁne

text: loop

text: weights

text: ξL

text: (ξL)

text: where

text: x+

text: x)

text: and

text: x

text: x)

text: R

text: denote

text: the

text: positive

text: and

text: negative

text: parts

text: of

text: x

text: Deﬁne

text: h

text: to

text: be

text: the

text: weighted

text: nesting

text: ﬁelds

text: associated

text: with

text: the

text: weights

text: ξL

text: (associated

text: with

text: the

text: same

text: CLE).

text: Then

text: h

text: g

text: h

text: g

text: almost

text: surely,

text: and

text: ε

text: h

text: g

text: h+,

text: g

text: h

text: g

text: h+,

text: g

text: h

text: g

text: h,

text: g

text: ε

text: ε

text: ε

text: which

text: concludes

text: the

text: proof

text: that

text: h

text: g

text: h,

text: g

text: almost

text: surely.

text: ε

text: To

text: see

text: that

text: the

text: ﬁeld

text: h

text: is

text: measurable

text: with

text: respect

text: to

text: the

text: σ-algebra

text: Σ

text: gener-

text: ated

text: by

text: the

text: CLEκ

text: aFnd

text: the

text: weights

text: (ξL)L∈Γ,

text: note

text: that

text: there

text: exists

text: a

text: count-

text: able

text: dense

text: subset

text: of

text: C

text: (D)

text: Exercise

text: Observe

text: that

text: h

text: c

text: N

text: ∈n

text: is

text: Σ-measurable

text: and

text: h

text: is

text: determined

text: by

text: the

text: values

text: h

text: (g)

text: n

text: g

text: F}

text: n

text: Since

text: h

text: is

text: an

text: almost

text: sure

text: limit

text: of

text: h

text: we

text: conclude

text: that

text: h

text: is

text: also

text: Σ-

text: n

text: measurable.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: THE CLE NESTING FIELD 35 In this section we prove Theorem 1.2. Suppose that D is a proper simply connected domain, and let Γ be a CLE in D. Let µ be a probability measure κ with ﬁnite second moment and zero mean, and deﬁne ∑n ∈ N hn(z) = ξLk(z), n . k=1 We call (hn)n∈N the step nesting sequence associated with Γ and (ξL)L∈Γ. ∈ LEMMA 7.1. For each κ (8/3, 8) there are positive constants c1, c2, and c3 (cid:40) C (depending on κ(cid:20)) such that for any simply connected (cid:21)proper domain D and ∈ points z, w D, for a CLE in D, κ N ≥ CR(z; D) ≤ − Pr z,w c1 log |z − w| + c2j + c3 exp[ j] . PROOF. Let Xi be i.i.d. copies of the log conformal radius distribution, and let T = ∑(cid:96) X . Then (cid:96) i=1 i Pr[T ≤ t] ≤ E[e−X](cid:96)et (cid:96) Pr[T ≤ log(CR(z; D)/|z − w|)] ≤ E[e−X](cid:96) C|R(−z; D|) . (cid:96) z w | − | ∩ ≤ N ⊂ If T(cid:96) > log(CR(⊂z; D)/−z ∩ w ), then Jz,|z−w| (cid:96). But z,w < Jz,|z−w|, and by Corollary 2.4, J | − | J | − | has exponential tails. z, z w z, z w PROOF OF THEOREM 1.2. We check that (5.4) holds with fn = hn. Writing out each difference as a sum of loop weights and using the linearity of ≤ ≤ ∈ expectation, we calculate for 0 m n and z, w D, E − − ∑n P N ≥ [(hm(z) hn(z))(hm(w) hn(w))] = σ2 [ z,w k] . k=m+1 Let δ(z) be the value for which c log(CR(z; D)/δ(z)) + c = k, where c 1 3 1 and c are as in Lemma 7.1. Let K be compact, and let δ = max ∈ δ(z). 3 z K Then ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: THE

text: CLE

text: NESTING

text: FIELD

text: In

text: this

text: section

text: we

text: prove

text: Theorem

text: Suppose

text: that

text: D

text: is

text: a

text: proper

text: simply

text: connected

text: domain,

text: and

text: let

text: Γ

text: be

text: a

text: CLE

text: in

text: D.

text: Let

text: µ

text: be

text: a

text: probability

text: measure

text: κ

text: with

text: ﬁnite

text: second

text: moment

text: and

text: zero

text: mean,

text: and

text: deﬁne

text: ∑n

text: N

text: hn(z)

text: ξLk(z),

text: n

text: We

text: call

text: (hn)n∈N

text: the

text: step

text: nesting

text: sequence

text: associated

text: with

text: Γ

text: and

text: (ξL)L∈Γ.

text: LEMMA

text: For

text: each

text: κ

text: there

text: are

text: positive

text: constants

text: and

text: C

text: (depending

text: on

text: such

text: that

text: for

text: any

text: simply

text: connected

text: domain

text: D

text: and

text: points

text: z,

text: w

text: D,

text: for

text: a

text: CLE

text: in

text: D,

text: κ

text: N

text: CR(z;

text: D)

text: Pr

text: z,w

text: log

text: |z

text: w|

text: exp[

text: j]

text: PROOF.

text: Let

text: Xi

text: be

text: i.i.d.

text: copies

text: of

text: the

text: log

text: conformal

text: radius

text: distribution,

text: and

text: let

text: T

text: X

text: Then

text: i

text: Pr[T

text: t]

text: Pr[T

text: log(CR(z;

text: D)/|z

text: w|)]

text: C|R(−z;

text: D|)

text: z

text: w

text: N

text: If

text: log(CR(⊂z;

text: D)/−z

text: w

text: then

text: Jz,|z−w|

text: But

text: z,w

text: Jz,|z−w|,

text: and

text: by

text: Corollary

text: J

text: J

text: has

text: exponential

text: tails.

text: z,

text: z

text: w

text: z,

text: z

text: w

text: PROOF

text: OF

text: THEOREM

text: We

text: check

text: that

text: holds

text: with

text: fn

text: hn.

text: Writing

text: out

text: each

text: difference

text: as

text: a

text: sum

text: of

text: loop

text: weights

text: and

text: using

text: the

text: linearity

text: of

text: expectation,

text: we

text: calculate

text: for

text: m

text: n

text: and

text: z,

text: w

text: D,

text: E

text: ∑n

text: P

text: N

text: [(hm(z)

text: hn(z))(hm(w)

text: hn(w))]

text: σ2

text: z,w

text: k]

text: Let

text: δ(z)

text: be

text: the

text: value

text: for

text: which

text: c

text: log(CR(z;

text: D)/δ(z))

text: c

text: k,

text: where

text: c

text: and

text: c

text: are

text: as

text: in

text: Lemma

text: Let

text: K

text: be

text: compact,

text: and

text: let

text: δ

text: max

text: δ(z).

text: z

text: K

text: Then

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: THE CLE NESTING FIELD 41 independently of everything else generated thus far. The resulting loop Γ processes are distributed according to the conformal loop ensemble on i D , and have been coupled to be similar near 0. i ◦ − Let ψ = ψ(2) (ψ(1)) 1 be the conformal map from U(1) to U(2) for which (cid:48) ∈ − − a a ∈ ψ(0) = 0 and ψ (0) = 1. Assuming a ( 3 x, 1 x) and a λ(1) and ∈ 4 2 | (cid:48) − | a λ(2), the Koebe distortion theorem implies that on B(0, ex/4), ψ 1 is exponentially small in x. By [MWW14, Lemma 3.6], except with probability exponentially small in x, both Γ and Γ contain a loop surrounding B(0, 1) which is contained in 1 2 B(0, ex/4). It is possible that ψ maps a loop of Γ surrounding D to a loop of 1 Γ D intersecting or vice versa. But since ψ has exponentially low distortion, 2 any such loop would have to have inradius exponentially close to 1. The Γ expected number of loops of with negative log conformal radius between − 1 log 4 and 1 is bounded by a constant, so by the Koebe quarter theorem, the expected number of loops of Γ with inradius between 1/e and 1 is bounded 1 by a constant. Let D = euD be a third domain, where u is independent 3 1 of everything else and uniformly distributed on (0, 1). It is evident that euΓ has no loop with inradius exponentially (in x) close to 1, except with 1 probability exponentially in x. On the other hand, we can couple a CLE on κ D to Γ in the same manner that we did for domain D , and deduce that Γ 3 1 2 1 must also have no loop with inradius exponentially close to 1, except with probability exponentially small in x. We conclude that it is exponentially unlikely for there to be a loop of Γ surrounding B(0, 1) which ψ maps to a 1 | | loop of Γ intersecting B(0, 1) or vice versa. Thus ψ(Γ ) = Γ , 2 1 B(z,1)+ 2 B(z,1)+ except with probability exponentially small in x. The corresponding estimates for general z and r and domains D and D 1 2 containing B(z, r) follows from the conformal invariance of CLE . κ Given the above estimates for any two proper simply connected domains which contain a sufﬁciently large ball around the origin, it is not difﬁcult to take a limit. For some sufﬁciently large constant k (which depends on κ), we ≥0 let Γ be a CLE in the domain B(0, ek), where k k is an integer. For each k, k κ 0 Γ Γ we couple and as described above. With probability 1 all but ﬁnitely k+1 k | | Γ Γ many of the couplings have that = ψ ( ) for a low- k+1 B(0,ek/2)+ k k B(0,ek/2)+ ≥ distortion conformal map ψ , so suppose that this is the case for all k (cid:96). k ≥ The conformal maps ψ (for k (cid:96)) approach the identity map sufﬁciently k≥ · · · ◦ ◦ rapidly that for each m (cid:96), the inﬁnite composition ψm+1 ψm is well deﬁned and converges uniformly on compact subsets to a limiting conformal | map with distortion exponentially small in m. We deﬁne ΓC to be B(0,em/2)+ ##LTLine## ##LTLine##

text: THE

text: CLE

text: NESTING

text: FIELD

text: independently

text: of

text: everything

text: else

text: generated

text: thus

text: far.

text: The

text: resulting

text: loop

text: Γ

text: processes

text: are

text: distributed

text: according

text: to

text: the

text: conformal

text: loop

text: ensemble

text: on

text: i

text: D

text: and

text: have

text: been

text: coupled

text: to

text: be

text: similar

text: near

text: i

text: Let

text: ψ

text: be

text: the

text: conformal

text: map

text: from

text: to

text: for

text: which

text: a

text: a

text: and

text: ψ

text: Assuming

text: a

text: x,

text: x)

text: and

text: a

text: and

text: a

text: the

text: Koebe

text: distortion

text: theorem

text: implies

text: that

text: on

text: ψ

text: is

text: exponentially

text: small

text: in

text: x.

text: By

text: Lemma

text: except

text: with

text: probability

text: exponentially

text: small

text: in

text: x,

text: both

text: Γ

text: and

text: Γ

text: contain

text: a

text: loop

text: surrounding

text: which

text: is

text: contained

text: in

text: It

text: is

text: possible

text: that

text: ψ

text: maps

text: a

text: loop

text: of

text: Γ

text: surrounding

text: D

text: to

text: a

text: loop

text: of

text: Γ

text: D

text: intersecting

text: or

text: vice

text: versa.

text: But

text: since

text: ψ

text: has

text: exponentially

text: low

text: distortion,

text: any

text: such

text: loop

text: would

text: have

text: to

text: have

text: inradius

text: exponentially

text: close

text: to

text: The

text: Γ

text: expected

text: number

text: of

text: loops

text: of

text: with

text: negative

text: log

text: conformal

text: radius

text: between

text: log

text: and

text: is

text: bounded

text: by

text: a

text: constant,

text: so

text: by

text: the

text: Koebe

text: quarter

text: theorem,

text: the

text: expected

text: number

text: of

text: loops

text: of

text: Γ

text: with

text: inradius

text: between

text: and

text: is

text: bounded

text: by

text: a

text: constant.

text: Let

text: D

text: euD

text: be

text: a

text: third

text: domain,

text: where

text: u

text: is

text: independent

text: of

text: everything

text: else

text: and

text: uniformly

text: distributed

text: on

text: It

text: is

text: evident

text: that

text: euΓ

text: has

text: no

text: loop

text: with

text: inradius

text: exponentially

text: (in

text: x)

text: close

text: to

text: except

text: with

text: probability

text: exponentially

text: in

text: x.

text: On

text: the

text: other

text: hand,

text: we

text: can

text: couple

text: a

text: CLE

text: on

text: κ

text: D

text: to

text: Γ

text: in

text: the

text: same

text: manner

text: that

text: we

text: did

text: for

text: domain

text: D

text: and

text: deduce

text: that

text: Γ

text: must

text: also

text: have

text: no

text: loop

text: with

text: inradius

text: exponentially

text: close

text: to

text: except

text: with

text: probability

text: exponentially

text: small

text: in

text: x.

text: We

text: conclude

text: that

text: it

text: is

text: exponentially

text: unlikely

text: for

text: there

text: to

text: be

text: a

text: loop

text: of

text: Γ

text: surrounding

text: which

text: ψ

text: maps

text: to

text: a

text: loop

text: of

text: Γ

text: intersecting

text: or

text: vice

text: versa.

text: Thus

text: ψ(Γ

text: Γ

text: except

text: with

text: probability

text: exponentially

text: small

text: in

text: x.

text: The

text: corresponding

text: estimates

text: for

text: general

text: z

text: and

text: r

text: and

text: domains

text: D

text: and

text: D

text: containing

text: B(z,

text: r)

text: follows

text: from

text: the

text: conformal

text: invariance

text: of

text: CLE

text: κ

text: Given

text: the

text: above

text: estimates

text: for

text: any

text: two

text: proper

text: simply

text: connected

text: domains

text: which

text: contain

text: a

text: sufﬁciently

text: large

text: ball

text: around

text: the

text: origin,

text: it

text: is

text: not

text: difﬁcult

text: to

text: take

text: a

text: limit.

text: For

text: some

text: sufﬁciently

text: large

text: constant

text: k

text: (which

text: depends

text: on

text: κ),

text: we

text: ≥0

text: let

text: Γ

text: be

text: a

text: CLE

text: in

text: the

text: domain

text: ek),

text: where

text: k

text: k

text: is

text: an

text: integer.

text: For

text: each

text: k,

text: k

text: κ

text: Γ

text: Γ

text: we

text: couple

text: and

text: as

text: described

text: above.

text: With

text: probability

text: all

text: but

text: ﬁnitely

text: k

text: Γ

text: Γ

text: many

text: of

text: the

text: couplings

text: have

text: that

text: ψ

text: for

text: a

text: low-

text: k

text: k

text: distortion

text: conformal

text: map

text: ψ

text: so

text: suppose

text: that

text: this

text: is

text: the

text: case

text: for

text: all

text: k

text: k

text: The

text: conformal

text: maps

text: ψ

text: (for

text: k

text: approach

text: the

text: identity

text: map

text: sufﬁciently

text: k≥

text: rapidly

text: that

text: for

text: each

text: m

text: the

text: inﬁnite

text: composition

text: ψm

text: is

text: well

text: deﬁned

text: and

text: converges

text: uniformly

text: on

text: compact

text: subsets

text: to

text: a

text: limiting

text: conformal

text: map

text: with

text: distortion

text: exponentially

text: small

text: in

text: m.

text: We

text: deﬁne

text: ΓC

text: to

text: be

text: ##LTLine##

text: ##LTLine##


text: ‹ ‹ 8 JASON MILLER, SAMUEL S.WATSON, AND DAVID B.WILSON ⊂ − ∩ COROLLARY 2.4. J J is stochastically dominated by 2N where N is a z,r z,r geometric random variable with parameter p = p(κ) > 0 which depends only on ∈ κ (8/3, 8). PROOF. See Corollary 3.5 in [MWW14]. We use the following estimate for the overshoot of a random walk the ﬁrst time it crosses a given threshold. We will apply this lemma to the random walk which tracks the negative log conformal radius of the sequence of CLE ∈ loops surrounding a given point z D, as viewed from z. See Lemma 2.8 in [MWW14] for a proof. { } LEMMA 2.5. Suppose Xj j∈N are nonnegative i.i.d. random variables for which E[X{1] ≥> 0 and≥E[e}λ0X1] < ∞ for some λ0 > 0. Let Sn = ∑nj=1 Xj and τx = inf n 0 : SPn x−. T≥hen th≤ere exists−C > 0 (dependi≥ng on the law of X1 and λ ) such that [S x α] C exp( λ α) for all x 0 and α > 0. 0 τx 0 The following lemma provides a quantitative version of the statement that it is unlikely that there exists a CLE loop surrounding the inner boundary but not the outer boundary of a given small, thin annulus. We make use of a quantitative coupling between CLE in large domains and full-plane CLE, which appears as Theorem A.1 in the appendix. LEMMA 2.6. Let Γ be a CLEκ in D. There exist constants≤C > 0, α > 0, and ε > 0 depending only on κ such that for 0 < ε < ε and 0 δ < 1/2, 0 0 E N − − N ≤ (2.2) [ (ε(1 δ)) (ε)] Cδ + Cεα . 0 0 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

font: NCWCXR+Yhcmex

text: JASON

text: MILLER,

text: SAMUEL

text: S.WATSON,

text: AND

text: DAVID

text: B.WILSON

text: COROLLARY

text: J

text: J

text: is

text: stochastically

text: dominated

text: by

text: where

text: N

text: is

text: a

text: z,r

text: z,r

text: geometric

text: random

text: variable

text: with

text: parameter

text: p

text: p(κ)

text: which

text: depends

text: only

text: on

text: κ

text: PROOF.

text: See

text: Corollary

text: in

text: We

text: use

text: the

text: following

text: estimate

text: for

text: the

text: overshoot

text: of

text: a

text: random

text: walk

text: the

text: ﬁrst

text: time

text: it

text: crosses

text: a

text: given

text: threshold.

text: We

text: will

text: apply

text: this

text: lemma

text: to

text: the

text: random

text: walk

text: which

text: tracks

text: the

text: negative

text: log

text: conformal

text: radius

text: of

text: the

text: sequence

text: of

text: CLE

text: loops

text: surrounding

text: a

text: given

text: point

text: z

text: D,

text: as

text: viewed

text: from

text: z.

text: See

text: Lemma

text: in

text: for

text: a

text: proof.

text: LEMMA

text: Suppose

text: Xj

text: j∈N

text: are

text: nonnegative

text: i.i.d.

text: random

text: variables

text: for

text: which

text: for

text: some

text: λ0

text: Let

text: Sn

text: Xj

text: and

text: τx

text: inf

text: n

text: SPn

text: x−.

text: T≥hen

text: th≤ere

text: exists−C

text: (dependi≥ng

text: on

text: the

text: law

text: of

text: and

text: λ

text: such

text: that

text: [S

text: x

text: α]

text: C

text: exp(

text: λ

text: α)

text: for

text: all

text: x

text: and

text: α

text: τx

text: The

text: following

text: lemma

text: provides

text: a

text: quantitative

text: version

text: of

text: the

text: statement

text: that

text: it

text: is

text: unlikely

text: that

text: there

text: exists

text: a

text: CLE

text: loop

text: surrounding

text: the

text: inner

text: boundary

text: but

text: not

text: the

text: outer

text: boundary

text: of

text: a

text: given

text: small,

text: thin

text: annulus.

text: We

text: make

text: use

text: of

text: a

text: quantitative

text: coupling

text: between

text: CLE

text: in

text: large

text: domains

text: and

text: full-plane

text: CLE,

text: which

text: appears

text: as

text: Theorem

text: in

text: the

text: appendix.

text: LEMMA

text: Let

text: Γ

text: be

text: a

text: CLEκ

text: in

text: D.

text: There

text: exist

text: constants≤C

text: α

text: and

text: ε

text: depending

text: only

text: on

text: κ

text: such

text: that

text: for

text: ε

text: ε

text: and

text: δ

text: E

text: N

text: N

text: δ))

text: (ε)]

text: Cδ

text: Cεα

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 6 337, 821 (2012). M. J. Lawler, E.-A. Kim, S. Sachdev, and J. C. S. Davis, PNAS 111, 30 (2014). 19 E. Fradkin, S. A. Kivelson, Nature Physics 8, 865 (2012). 25 R. Comin, R. Sutarto, F. He, E. da Silva Neto, L. Chauviere, A. Frano, R. Liang, W. N. Hardy, D. Bonn, Y. Yoshida, H. Eisaki, J. E. 20 J. M. Tranquada, Science 337, 811 (2012). Hoﬀman, B. Keimer, G. A. Sawatzky, A. Damascelli, arXiv:1402.5415. 21 D. LeBoeuf, S. Kra¨mer, W. N. Hardy, R. Liang, D. A. Bonn, and C. Pro26usSt,. NE.atSuerbeaPsthiyans.,9N,.7H9a(r2r0is1o3n),.and G. G. Lonzarich, Rep. Prog. Phys. 75, 102501 (2012). 22 J. P. Hinton, J. D. Koralek, Y. M. Lu, A. Vishwanath, J. Orenstein, D.27AG. B. oHninld,eWbr.aNnd.,HTa.rJd.yH, aagnednRaa.rLs,iaWng. ,HPahnykse., RS.evG.rBab8o8w,s0k6i,0a5n0d8(JR. )Schmalian, Phys. Rev. B 56, 4317 (R) (1997). (2013). 28 Hiroshi Kontani, Rep. Prog. Phys. 71, 026501 (2008) 23 S. E. Sebastian, N. Harrison, F. F. Balakirev, M. M. Altarawneh, P. A. 2G9oJd.dGar.dS,tRor.eLy,iaJn. gL,.DTa. lAlo.nB, oannnd,GW..VN. M. H.aWrdiyll,iaamnds,GE.PGL.1L0o2n,z3a7ri0c0h6, (2013). Nature 511, 61 (2014). 24 K. Fujita, M. H. Hamidian, S. D. Edkins, C. K. Kim, Y. Kohsaka, M. Azuma, M. Takano, H. Takagi, H. Eisaki, Shin-ichi Uchida, A. Allais,

text: M.

text: J.

text: Lawler,

text: E.-A.

text: Kim,

text: S.

text: Sachdev,

text: and

text: J.

text: C.

text: S.

text: Davis,

text: PNAS

text: E.

text: Fradkin,

text: S.

text: A.

text: Kivelson,

text: Nature

text: Physics

text: R.

text: Comin,

text: R.

text: Sutarto,

text: F.

text: He,

text: E.

text: da

text: Silva

text: Neto,

text: L.

text: Chauviere,

text: A.

text: Frano,

text: R.

text: Liang,

text: W.

text: N.

text: Hardy,

text: D.

text: Bonn,

text: Y.

text: Yoshida,

text: H.

text: Eisaki,

text: J.

text: E.

text: J.

text: M.

text: Tranquada,

text: Science

text: Hoﬀman,

text: B.

text: Keimer,

text: G.

text: A.

text: Sawatzky,

text: A.

text: Damascelli,

text: D.

text: LeBoeuf,

text: S.

text: Kra¨mer,

text: W.

text: N.

text: Hardy,

text: R.

text: Liang,

text: D.

text: A.

text: Bonn,

text: and

text: C.

text: G.

text: G.

text: Lonzarich,

text: Rep.

text: Prog.

text: Phys.

text: J.

text: P.

text: Hinton,

text: J.

text: D.

text: Koralek,

text: Y.

text: M.

text: Lu,

text: A.

text: Vishwanath,

text: J.

text: Orenstein,

text: B.

text: oHninld,eWbr.aNnd.,HTa.rJd.yH,

text: aagnednRaa.rLs,iaWng.

text: ,HPahnykse.,

text: )Schmalian,

text: Phys.

text: Rev.

text: B

text: (R)

text: Hiroshi

text: Kontani,

text: Rep.

text: Prog.

text: Phys.

text: S.

text: E.

text: Sebastian,

text: N.

text: Harrison,

text: F.

text: F.

text: Balakirev,

text: M.

text: M.

text: Altarawneh,

text: P.

text: A.

text: gL,.DTa.

text: lAlo.nB,

text: oannnd,GW..VN.

text: M.

text: Nature

text: K.

text: Fujita,

text: M.

text: H.

text: Hamidian,

text: S.

text: D.

text: Edkins,

text: C.

text: K.

text: Kim,

text: Y.

text: Kohsaka,

text: M.

text: Azuma,

text: M.

text: Takano,

text: H.

text: Takagi,

text: H.

text: Eisaki,

text: Shin-ichi

text: Uchida,

text: A.

text: Allais,


text: TREES IN RANDOM SPARSE GRAPHS WITH A GIVEN DEGREE SEQUENCE BEHZAD MEHRDAD Abstract. Let GD be the set of graphs G(V, E) with |V | = n, and the degree sequence equal to D = (d1, d2, ..., dn). In addition, for 12 < a < 1, we deﬁne the set of graphs with an almost given degree sequence D as follows, (cid:12)(cid:12) (cid:12)(cid:12) GDa := ∪GD¯, ≤ ≤ where the union is over all degree sequences D¯ such that, for 1 i n, we − have di d¯i < dai . G G Now, if we chose random graphs g (D) and a (D) uniformly out of the sets GD and GD, respectively, what do they look like? This has been studied G a | | when Gg (D) is a dense graph, i.e. E = Θ| (n| 2), in the sense of graphons, or when g (D) is very sparse, i.e. d2n = o( E ). In the case of sparse graphs with an almost given degree sequence, we investigate this question, and give G the ﬁnite tree subgGraph structure of a (D) under some mild conditions. For the random graph g (D) with a given degree sequence, we re-derive the ﬁnite tree structure in dense and very sparse cases to give a continuous picture. be tMheorreaonvdeor,mfobripaarptaitire ogfravpehcttohrast(iDs 1c,hDos2e)n∈unZinfo1rm×lZyno2u,twoef tlhete Gsebt(GDD11,,DD22), where GD1,D2 is the set of all bipartite graphs with the degree sequence G (D1,D2). We are able to show the result for b (D1,D2) without any fur- ther conditions. Contents 1. Introduction 1 2. Main Results. 3 3. Proofs 15 4. Acknowledgements 47 Appendix A. A concentration inequality. 47 Appendix B. Regularity of r s. 49 i References 53 (cid:80)1. Introduction Let D = (d , d , . . . , d ) be a ﬁnite sequence of positive integers, such that 1 ≤ d ≤ · · · ≤ 1d , 2and M :n= n d is even. In addition, let G be the set of all 1 n i=1 i n simple graphs (undirected, with no loops or multiple edges) with n vertices. For G ∈ G , V(G) will be the set of its vertices indexed by {v , v , . . . , v } and E(G) n (cid:104) (cid:105) 1 2 n is its set of edges e := v , v . We say that G is a graph with the given degree i j 1 ##LTLine##

text: TREES

text: IN

text: RANDOM

text: SPARSE

text: GRAPHS

text: WITH

text: A

text: GIVEN

text: DEGREE

text: SEQUENCE

text: BEHZAD

text: MEHRDAD

text: Abstract.

text: Let

label: abstract

text: GD

text: be

text: the

text: set

text: of

text: graphs

text: G(V,

text: E)

text: with

text: |V

text: n,

text: and

text: the

text: degree

text: sequence

text: equal

text: to

text: D

text: dn).

text: In

text: addition,

text: for

text: a

text: we

text: deﬁne

text: the

text: set

text: of

text: graphs

text: with

text: an

text: almost

text: given

text: degree

text: sequence

text: D

text: as

text: follows,

text: GDa

text: ∪GD¯,

text: where

text: the

text: union

text: is

text: over

text: all

text: degree

text: sequences

text: D¯

text: such

text: that,

text: for

text: i

text: n,

text: we

text: have

text: di

text: d¯i

text: dai

text: G

text: G

text: Now,

text: if

text: we

text: chose

text: random

text: graphs

text: g

text: (D)

text: and

text: a

text: (D)

text: uniformly

text: out

text: of

text: the

text: sets

text: GD

text: and

text: GD,

text: respectively,

text: what

text: do

text: they

text: look

text: like?

text: This

text: has

text: been

text: studied

text: G

text: a

text: when

text: Gg

text: (D)

text: is

text: a

text: dense

text: graph,

text: i.e.

text: E

text: Θ|

text: (n|

text: in

text: the

text: sense

text: of

text: graphons,

text: or

text: when

text: g

text: (D)

text: is

text: very

text: sparse,

text: i.e.

text: o(

text: E

text: In

text: the

text: case

text: of

text: sparse

text: graphs

text: with

text: an

text: almost

text: given

text: degree

text: sequence,

text: we

text: investigate

text: this

text: question,

text: and

text: give

text: G

text: the

text: ﬁnite

text: tree

text: subgGraph

text: structure

text: of

text: a

text: (D)

text: under

text: some

text: mild

text: conditions.

text: For

text: the

text: random

text: graph

text: g

text: (D)

text: with

text: a

text: given

text: degree

text: sequence,

text: we

text: re-derive

text: the

text: ﬁnite

text: tree

text: structure

text: in

text: dense

text: and

text: very

text: sparse

text: cases

text: to

text: give

text: a

text: continuous

text: picture.

text: be

text: tMheorreaonvdeor,mfobripaarptaitire

text: ogfravpehcttohrast(iDs

text: tlhete

text: where

text: is

text: the

text: set

text: of

text: all

text: bipartite

text: graphs

text: with

text: the

text: degree

text: sequence

text: G

text: We

text: are

text: able

text: to

text: show

text: the

text: result

text: for

text: b

text: without

text: any

text: fur-

text: ther

text: conditions.

text: Contents

text: Introduction

text: Main

text: Results.

text: Proofs

text: Acknowledgements

text: Appendix

text: A.

text: A

text: concentration

text: inequality.

text: Appendix

text: B.

text: Regularity

text: of

text: r

text: s.

text: i

text: References

text: Introduction

text: Let

text: D

text: (d

text: d

text: d

text: be

text: a

text: ﬁnite

text: sequence

text: of

text: positive

text: integers,

text: such

text: that

text: d

text: M

text: :n=

text: n

text: d

text: is

text: even.

text: In

text: addition,

text: let

text: G

text: be

text: the

text: set

text: of

text: all

text: n

text: i

text: n

text: simple

text: graphs

text: (undirected,

text: with

text: no

text: loops

text: or

text: multiple

text: edges)

text: with

text: n

text: vertices.

text: For

text: G

text: G

text: V(G)

text: will

text: be

text: the

text: set

text: of

text: its

text: vertices

text: indexed

text: by

text: {v

text: v

text: v

text: and

text: E(G)

text: n

text: n

text: is

text: its

text: set

text: of

text: edges

text: e

text: v

text: v

text: We

text: say

text: that

text: G

text: is

text: a

text: graph

text: with

text: the

text: given

text: degree

text: i

text: j

text: ##LTLine##


text: TREES IN RANDOM SPARSE GRAPHS WITH A GIVEN DEGREE SEQUENCE 2 sequence D, if the degree of a vertex v is d . It is evident that the total number of edges |E(G)| = 1M. We denote the seit of aill such simple graphs by GD ⊂ G . 2 G n A random graph (D) with the given degree sequence D is the one that is uniformly chosen fromgGD. Now, what does the random graph G (D) look like? g Researchers have studied this problem extensively, along with other properties of graphs with a given degree sequence. Before we list a couple of them here, we state some notations. In this paper and for two real functions f(n) and g(n), the notations g = Θ(f), g = O(f) and g = o(f), as n goes to inﬁnity, mean that there exists a real number | | | | ≤ | | ≤ | | C such that lim sup →∞ |f| + |g| C, lim sup →∞ |f| C and lim →∞ |f| = 0, n g f n g n g respectively. (cid:0) (cid:1) Dense graphs are those graphs G ∈ G that |E(G)| = Θ n2 . In [1], Barvinok n and Hartigan studied the structure of dense graphs with a given degree sequence. They showed the relation between the maximum entropy function and the number of such graphs. Under mild conditions (δ- tameness), they found the asymptotic behavior of the number of graphs with a given degree sequence D. Although Barvinok and Hartigan provide an exact formula, it is diﬃcult to touch it. There are also some other approaches to the counting problem which only work in certain regimes. In [19], Mckay and Wormald considered the case of graphs | − | with nearly constant degree d, d d = O(n1/2), using a multidimensional saddle- i point method. The enumeration of graphs with a given degree sequence may lead G to ﬁnding the probabilities of subgraphs of random graph (D). Greenhill and g Mckay studied that in [29] for various regimes. Also, see McKay [28] for a detailed survey of that subject. Another approach toward graphs with a given degree sequence is through graph limits. Recently Lov´asz and Szegedy introduced, in [23], a notion of graph limits called graphons. This has been developed further by Borgs et al [8, 10, 9]. In regard to graphs with a given degree sequence, Chatterjee et al [6] showed that sequences of such graphs have graph limits, in the sense of graphons, if their degree sequences converge to a degree function which satisﬁes the Erdös-Gallai condition for graph limits. Diﬀerent regimes of very sparse graphs, d2 = d2 = o(M), were studied a long max n time ago by Mckay, [27] and [26]. The condition allows us to comput the number of graphs via inclusion-exclusion and switching method. Mckay and Wormald came back to this problem in [30] with a less restrictive condition. Recently Gao et al [18] investigated the probability of subgraphs of a random graph with a given degree sequence in this regime. Look at [17] for more information about subgraphs of random graphs. A bipartite graph is a graph with two set of vertices, where there are no edges with both ends in the same set. The adjacency matrix for a simple bipartite graph with a given degree sequence is a matrix with 0-1 entries with given row and column sums. Barvinok, in [2, 1], studied these matrices in the dense case. Barvinok and Hartigan generalized this in [4, 5] for matrices with non-negative integer entries. ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: TREES

text: IN

text: RANDOM

text: SPARSE

text: GRAPHS

text: WITH

text: A

text: GIVEN

text: DEGREE

text: SEQUENCE

text: sequence

text: D,

text: if

text: the

text: degree

text: of

text: a

text: vertex

text: v

text: is

text: d

text: It

text: is

text: evident

text: that

text: the

text: total

text: number

text: of

text: edges

text: |E(G)|

text: We

text: denote

text: the

text: seit

text: of

text: aill

text: such

text: simple

text: graphs

text: by

text: GD

text: G

text: G

text: n

text: A

text: random

text: graph

text: (D)

text: with

text: the

text: given

text: degree

text: sequence

text: D

text: is

text: the

text: one

text: that

text: is

text: uniformly

text: chosen

text: fromgGD.

text: Now,

text: what

text: does

text: the

text: random

text: graph

text: G

text: (D)

text: look

text: like?

text: g

text: Researchers

text: have

text: studied

text: this

text: problem

text: extensively,

text: along

text: with

text: other

text: properties

text: of

text: graphs

text: with

text: a

text: given

text: degree

text: sequence.

text: Before

text: we

text: list

text: a

text: couple

text: of

text: them

text: here,

text: we

text: state

text: some

text: notations.

text: In

text: this

text: paper

text: and

text: for

text: two

text: real

text: functions

text: f(n)

text: and

text: g(n),

text: the

text: notations

text: g

text: Θ(f),

text: g

text: O(f)

text: and

text: g

text: o(f),

text: as

text: n

text: goes

text: to

text: inﬁnity,

text: mean

text: that

text: there

text: exists

text: a

text: real

text: number

text: C

text: such

text: that

text: lim

text: sup

text: |f|

text: |g|

text: C,

text: lim

text: sup

text: |f|

text: C

text: and

text: lim

text: |f|

text: n

text: g

text: f

text: n

text: g

text: n

text: g

text: respectively.

text: Dense

text: graphs

text: are

text: those

text: graphs

text: G

text: G

text: that

text: |E(G)|

text: Θ

text: In

text: Barvinok

text: n

text: and

text: Hartigan

text: studied

text: the

text: structure

text: of

text: dense

text: graphs

text: with

text: a

text: given

text: degree

text: sequence.

text: They

text: showed

text: the

text: relation

text: between

text: the

text: maximum

text: entropy

text: function

text: and

text: the

text: number

text: of

text: such

text: graphs.

text: Under

text: mild

text: conditions

text: (δ-

text: tameness),

text: they

text: found

text: the

text: asymptotic

text: behavior

text: of

text: the

text: number

text: of

text: graphs

text: with

text: a

text: given

text: degree

text: sequence

text: D.

text: Although

text: Barvinok

text: and

text: Hartigan

text: provide

text: an

text: exact

text: formula,

text: it

text: is

text: diﬃcult

text: to

text: touch

text: it.

text: There

text: are

text: also

text: some

text: other

text: approaches

text: to

text: the

text: counting

text: problem

text: which

text: only

text: work

text: in

text: certain

text: regimes.

text: In

text: Mckay

text: and

text: Wormald

text: considered

text: the

text: case

text: of

text: graphs

text: with

text: nearly

text: constant

text: degree

text: d,

text: d

text: d

text: using

text: a

text: multidimensional

text: saddle-

text: i

text: point

text: method.

text: The

text: enumeration

text: of

text: graphs

text: with

text: a

text: given

text: degree

text: sequence

text: may

text: lead

text: G

text: to

text: ﬁnding

text: the

text: probabilities

text: of

text: subgraphs

text: of

text: random

text: graph

text: (D).

text: Greenhill

text: and

text: g

text: Mckay

text: studied

text: that

text: in

text: for

text: various

text: regimes.

text: Also,

text: see

text: McKay

text: for

text: a

text: detailed

text: survey

text: of

text: that

text: subject.

text: Another

text: approach

text: toward

text: graphs

text: with

text: a

text: given

text: degree

text: sequence

text: is

text: through

text: graph

text: limits.

text: Recently

text: Lov´asz

text: and

text: Szegedy

text: introduced,

text: in

text: a

text: notion

text: of

text: graph

text: limits

text: called

text: graphons.

text: This

text: has

text: been

text: developed

text: further

text: by

text: Borgs

text: et

text: al

text: In

text: regard

text: to

text: graphs

text: with

text: a

text: given

text: degree

text: sequence,

text: Chatterjee

text: et

text: al

text: showed

text: that

text: sequences

text: of

text: such

text: graphs

text: have

text: graph

text: limits,

text: in

text: the

text: sense

text: of

text: graphons,

text: if

text: their

text: degree

text: sequences

text: converge

text: to

text: a

text: degree

text: function

text: which

text: satisﬁes

text: the

text: Erdös-Gallai

text: condition

text: for

text: graph

text: limits.

text: Diﬀerent

text: regimes

text: of

text: very

text: sparse

text: graphs,

text: o(M),

text: were

text: studied

text: a

text: long

text: max

text: n

text: time

text: ago

text: by

text: Mckay,

text: and

text: The

text: condition

text: allows

text: us

text: to

text: comput

text: the

text: number

text: of

text: graphs

text: via

text: inclusion-exclusion

text: and

text: switching

text: method.

text: Mckay

text: and

text: Wormald

text: came

text: back

text: to

text: this

text: problem

text: in

text: with

text: a

text: less

text: restrictive

text: condition.

text: Recently

text: Gao

text: et

text: al

text: investigated

text: the

text: probability

text: of

text: subgraphs

text: of

text: a

text: random

text: graph

text: with

text: a

text: given

text: degree

text: sequence

text: in

text: this

text: regime.

text: Look

text: at

text: for

text: more

text: information

text: about

text: subgraphs

text: of

text: random

text: graphs.

text: A

text: bipartite

text: graph

text: is

text: a

text: graph

text: with

text: two

text: set

text: of

text: vertices,

text: where

text: there

text: are

text: no

text: edges

text: with

text: both

text: ends

text: in

text: the

text: same

text: set.

text: The

text: adjacency

text: matrix

text: for

text: a

text: simple

text: bipartite

text: graph

text: with

text: a

text: given

text: degree

text: sequence

text: is

text: a

text: matrix

text: with

text: entries

text: with

text: given

text: row

text: and

text: column

text: sums.

text: Barvinok,

text: in

text: studied

text: these

text: matrices

text: in

text: the

text: dense

text: case.

text: Barvinok

text: and

text: Hartigan

text: generalized

text: this

text: in

text: for

text: matrices

text: with

text: non-negative

text: integer

text: entries.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: TREES IN RANDOM SPARSE GRAPHS WITH A GIVEN DEGREE SEQUENCE 11 (cid:101) (cid:101) (cid:101) − Remark 2.22. This deﬁnition implies that the vector D is δ tame in the sense that ≤ ≤ − it was deﬁned in [1], which means δ p 1 δ for δ(c , c , c ), where p = (p ) ij 1 2 3 ij i,j is the maximum entropy. The next theorem is equivalent to the computations that appear in the last lines of the proof on page 34 of Theorem 1.1 in [6]. Theorem 2.23. If the degree sequence D satisﬁes the dense Erdös-Rényi condition (the preceding deﬁnition), then the Conjectures 2.18 and 2.19 hold. Therefore, ≤ · − (2.19) Lg (k, D) ck (n log(n)) 21 , where L (k, D) is deﬁned in Eq. (2.18). Moreover, for 1 < a < 1 + 1 , the g 2 2 12 Theorem 2.11 also holds, i.e. ≤ · − (2.20) La (a, k, D) ck n 43+a, where L (a, k, D) is deﬁned in Eq. (2.9). a Let us start this section with the very-sparseness deﬁnition. Deﬁnition 2.24. A graph with a degree sequence D is called very sparse if d2 = n d2 = o(M). max Now, we see the corresponding results to Theorem 2.11 and Conjecture 2.19 for very sparse random graphs. In addition, we see how our method is related to Mckay’s result. Let us introduce new variables, d d ≤ ≤ (cid:54) q := i j , where 1 i, j n and i=j. ij M + d d i j G Deﬁne (D) as a random graph with independent Bernoulli random edges with q parameters q . Let ij G (2.21) p (s, T) = E [1 (T, (D))] , q s q (cid:101) w(cid:101)here (cid:101)1s (T, G) is dGeﬁned in Eq. 2.10. This random(cid:101)graph is an alternative to t(cid:101)he random graph (D), which was constructed according to maximum entropy (cid:39) p = (p ) . The goal is to show that p (s, T) p (s, T), and in particular, (cid:39) ij i,j q p q . ij ij ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: TREES

text: IN

text: RANDOM

text: SPARSE

text: GRAPHS

text: WITH

text: A

text: GIVEN

text: DEGREE

text: SEQUENCE

text: Remark

text: This

text: deﬁnition

text: implies

text: that

text: the

text: vector

text: D

text: is

text: δ

text: tame

text: in

text: the

text: sense

text: that

text: it

text: was

text: deﬁned

text: in

text: which

text: means

text: δ

text: p

text: δ

text: for

text: δ(c

text: c

text: c

text: where

text: p

text: (p

text: ij

text: ij

text: i,j

text: is

text: the

text: maximum

text: entropy.

text: The

text: next

text: theorem

text: is

text: equivalent

text: to

text: the

text: computations

text: that

text: appear

text: in

text: the

text: last

text: lines

text: of

text: the

text: proof

text: on

text: page

text: of

text: Theorem

text: in

text: Theorem

text: If

text: the

text: degree

text: sequence

text: D

text: satisﬁes

text: the

text: dense

text: Erdös-Rényi

text: condition

text: (the

text: preceding

text: deﬁnition),

text: then

text: the

text: Conjectures

text: and

text: hold.

text: Therefore,

text: Lg

text: (k,

text: D)

text: ck

text: (n

text: log(n))

text: where

text: L

text: (k,

text: D)

text: is

text: deﬁned

text: in

text: Eq.

text: Moreover,

text: for

text: a

text: the

text: g

text: Theorem

text: also

text: holds,

text: i.e.

text: La

text: (a,

text: k,

text: D)

text: ck

text: n

text: where

text: L

text: (a,

text: k,

text: D)

text: is

text: deﬁned

text: in

text: Eq.

text: a

text: Let

text: us

text: start

text: this

text: section

text: with

text: the

text: very-sparseness

text: deﬁnition.

text: Deﬁnition

text: A

text: graph

text: with

text: a

text: degree

text: sequence

text: D

text: is

text: called

text: very

text: sparse

text: if

text: n

text: o(M).

text: max

text: Now,

text: we

text: see

text: the

text: corresponding

text: results

text: to

text: Theorem

text: and

text: Conjecture

text: for

text: very

text: sparse

text: random

text: graphs.

text: In

text: addition,

text: we

text: see

text: how

text: our

text: method

text: is

text: related

text: to

text: Mckay’s

text: result.

text: Let

text: us

text: introduce

text: new

text: variables,

text: d

text: d

text: q

text: i

text: j

text: where

text: i,

text: j

text: n

text: and

text: i=j.

text: ij

text: M

text: d

text: d

text: i

text: j

text: G

text: Deﬁne

text: (D)

text: as

text: a

text: random

text: graph

text: with

text: independent

text: Bernoulli

text: random

text: edges

text: with

text: q

text: parameters

text: q

text: Let

text: ij

text: G

text: p

text: (s,

text: T)

text: E

text: (T,

text: (D))]

text: q

text: s

text: q

text: (T,

text: G)

text: is

text: dGeﬁned

text: in

text: Eq.

text: This

text: is

text: an

text: alternative

text: to

text: random

text: graph

text: (D),

text: which

text: was

text: constructed

text: according

text: to

text: maximum

text: entropy

text: p

text: (p

text: The

text: goal

text: is

text: to

text: show

text: that

text: p

text: (s,

text: T)

text: p

text: (s,

text: T),

text: and

text: in

text: particular,

text: ij

text: i,j

text: q

text: p

text: q

text: ij

text: ij

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: TREES IN RANDOM SPARSE GRAPHS WITH A GIVEN DEGREE SEQUENCE 14 (cid:101) G Note that for the random graph (D , D ), there are no edges between the two 1 2 vertices of set 1 or two vertices of set 2. Theorem 2.30. Suppose that the polytope PD1,D2 has a non-empty interior, and deﬁne (cid:88) (cid:101) 1 1 | − | (2.26) L (k, D , D ) := p (s, T) p (s, T) , b 1 2 M ∈T ψ (s, T, D) b (s,T) b(k,n) where we used the notations in Theorem 2.11, and p (s, T) is deﬁned in Eq. b (2.24), and D = (D , D ). (cid:88) 1 2 (cid:101) 1 1 | − | (2.27) L (k, D , D ) := p (s, T) p (s, T) , b 1 2 M ∈T ψ (s, T, D) b (s,T) b(k,n) where we used the notations in Theorem 2.11, and p (s, T) is deﬁned in Eq. b (2.24), and D = (D1, D2). Then, we obtain (cid:18) (cid:19) 1 ≤ · n log(n) 2 L (k, D , D ) c . b 1 2 k M Remark 2.31. Note that we are able to prove the above result in almost the full generality, whereas in Conjecture 2.19, we needed an extra lower bound, which is discussed in Remark 2.20. Moreover, it is also possible to formulate the counter part of Theorem 2.11 for bipartite graphs and prove it without any extra condition. However, that is a repetition of the previous work and so we skip it. Remark 2.32. We observe that strict Erdös- Gallai conditions reduce to a much simpler equations in the case of bipartite graphs. However, dealing with that tech- nicality is out of the scope of this paper, and we simply assume that PD1,D2 has a non-empty interior. Here we list a couple of questions. Question 1.: Can we prove our results under fewer assumptions? In partic- ular, is it possible to drop the last two parts of Deﬁnition 2.3, and only use the Erdös - Gallai conditions for our theorems? (see Conjecture 3.13) Question 2.: What can be said about triangle-counting in the sparse random graph G with a given degree sequence D? How about other subgraphs? Question 3.: What is the correct way of counting the subgraphs? In the sense that, can we deﬁne a metric or a topology for the space of sparse graphs using the weighted subgraph counts? ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: TREES

text: IN

text: RANDOM

text: SPARSE

text: GRAPHS

text: WITH

text: A

text: GIVEN

text: DEGREE

text: SEQUENCE

text: G

text: Note

text: that

text: for

text: the

text: random

text: graph

text: (D

text: D

text: there

text: are

text: no

text: edges

text: between

text: the

text: two

text: vertices

text: of

text: set

text: or

text: two

text: vertices

text: of

text: set

text: Theorem

text: Suppose

text: that

text: the

text: polytope

text: has

text: a

text: non-empty

text: interior,

text: and

text: deﬁne

text: L

text: (k,

text: D

text: D

text: p

text: (s,

text: T)

text: p

text: (s,

text: T)

text: b

text: M

text: ∈T

text: ψ

text: (s,

text: T,

text: D)

text: b

text: (s,T)

text: b(k,n)

text: where

text: we

text: used

text: the

text: notations

text: in

text: Theorem

text: and

text: p

text: (s,

text: T)

text: is

text: deﬁned

text: in

text: Eq.

text: b

text: and

text: D

text: (D

text: D

text: L

text: (k,

text: D

text: D

text: p

text: (s,

text: T)

text: p

text: (s,

text: T)

text: b

text: M

text: ∈T

text: ψ

text: (s,

text: T,

text: D)

text: b

text: (s,T)

text: b(k,n)

text: where

text: we

text: used

text: the

text: notations

text: in

text: Theorem

text: and

text: p

text: (s,

text: T)

text: is

text: deﬁned

text: in

text: Eq.

text: b

text: and

text: D

text: Then,

text: we

text: obtain

text: n

text: log(n)

text: L

text: (k,

text: D

text: D

text: c

text: b

text: k

text: M

text: Remark

text: Note

text: that

text: we

text: are

text: able

text: to

text: prove

text: the

text: above

text: result

text: in

text: almost

text: the

text: full

text: generality,

text: whereas

text: in

text: Conjecture

text: we

text: needed

text: an

text: extra

text: lower

text: bound,

text: which

text: is

text: discussed

text: in

text: Remark

text: Moreover,

text: it

text: is

text: also

text: possible

text: to

text: formulate

text: the

text: counter

text: part

text: of

text: Theorem

text: for

text: bipartite

text: graphs

text: and

text: prove

text: it

text: without

text: any

text: extra

text: condition.

text: However,

text: that

text: is

text: a

text: repetition

text: of

text: the

text: previous

text: work

text: and

text: so

text: we

text: skip

text: it.

text: Remark

text: We

text: observe

text: that

text: strict

text: Erdös-

text: Gallai

text: conditions

text: reduce

text: to

text: a

text: much

text: simpler

text: equations

text: in

text: the

text: case

text: of

text: bipartite

text: graphs.

text: However,

text: dealing

text: with

text: that

text: tech-

text: nicality

text: is

text: out

text: of

text: the

text: scope

text: of

text: this

text: paper,

text: and

text: we

text: simply

text: assume

text: that

text: has

text: a

text: non-empty

text: interior.

text: Here

text: we

text: list

text: a

text: couple

text: of

text: questions.

text: Question

text: Can

text: we

text: prove

text: our

text: results

text: under

text: fewer

text: assumptions?

text: In

text: partic-

text: ular,

text: is

text: it

text: possible

text: to

text: drop

text: the

text: last

text: two

text: parts

text: of

text: Deﬁnition

text: and

text: only

text: use

text: the

text: Erdös

text: Gallai

text: conditions

text: for

text: our

text: theorems?

text: (see

text: Conjecture

text: Question

text: What

text: can

text: be

text: said

text: about

text: triangle-counting

text: in

text: the

text: sparse

text: random

text: graph

text: G

text: with

text: a

text: given

text: degree

text: sequence

text: D?

text: How

text: about

text: other

text: subgraphs?

text: Question

text: What

text: is

text: the

text: correct

text: way

text: of

text: counting

text: the

text: subgraphs?

text: In

text: the

text: sense

text: that,

text: can

text: we

text: deﬁne

text: a

text: metric

text: or

text: a

text: topology

text: for

text: the

text: space

text: of

text: sparse

text: graphs

text: using

text: the

text: weighted

text: subgraph

text: counts?

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: TREES IN RANDOM SPARSE GRAPHS WITH A GIVEN DEGREE SEQUENCE 16 (cid:104) (cid:105) Proof. Let v be any leaf of T, and let u be such that u, v is the only edge of v. Since − V \ { } at most k 1 possible(cid:88)edges from s(u) could lead to vertices of (s(T)) s(v) , we write the inequality ≥ − − 1(cid:104) (cid:105)∈E (G) d (k 1). s(u),x (G) s(u) { (cid:54) (cid:48) ∀ (cid:48)∈V (cid:48)(cid:54) } x:x=s(v ), v (T),v =v This provides a recurrence relation   − F(T − , G) (cid:88)F(T , G) (cid:89) k 1  k  ≤ − 1 1 (k 1) 1(cid:104) (cid:105)∈E (G) , s ds(u) ψ(s, Tk−1, G) e=(cid:104)u1,u2(cid:105)∈E(Tk−1) s(u1),s(u2) (G) where T − is T when we remove v and the edge attached to it from T . Let k 1 k k us denote by H(T − , G) the right hand side of the above formula. Now, we can k 1 bound H(T − , G), as in the previous lemma. So, there is a tree T − by removing k 1 k 2 a vertex of T − such that k 1 ≤ H(T − , G) H(T − , G). k 2 k 2 (cid:80) (cid:80) Continuing with that procedure, we can also assume without loss of generality { } that u is the last vertex to be removed, i.e. T = u in the sequence. Now the upper 1 bound can be estimated and the last step is 1 = n, rather than d = M, i i i because of the extra term 1 in H. Providing us with the estimate ds(u) − ≤ − F(T − , G) F(T , G) (k 1)n, k 1 k Which yields − ≥ − nk(k 1) F(T, G) = F(T , G) M . k 2 (cid:3) { } If we use the degree sequence d in the deﬁnition of the B- function while the i { } actual degrees are some what diﬀerent d˜ that satisﬁes i | − | ≤ d d˜ cda, i i i i.e. G ∈ GD then(cid:88)we(cid:12)(cid:12)ne(cid:89)ed an error bound on(cid:89)the diﬀerence (cid:12)(cid:12) a (cid:12) (cid:12) (cid:12) (cid:2) (cid:3) (cid:104) (cid:105) (cid:12) (cid:101) 1 − 1 (3.1) Zk = s u∈V(T) ds(u)(cid:89)bu−1 u∈V(T) ds(u) bu−1 1s(T, G), where 1 (T, G) = 1(cid:104) (cid:105)∈E (G). s (cid:104) (cid:105)∈E s(u1),s(u2) (G) u1,u2 (T) Lemma 3.3. For Z as in Eq. (3.1), we have k ≤ − Z c k Man1 a. k ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: TREES

text: IN

text: RANDOM

text: SPARSE

text: GRAPHS

text: WITH

text: A

text: GIVEN

text: DEGREE

text: SEQUENCE

text: Proof.

text: Let

text: v

text: be

text: any

text: leaf

text: of

text: T,

text: and

text: let

text: u

text: be

text: such

text: that

text: u,

text: v

text: is

text: the

text: only

text: edge

text: of

text: v.

text: Since

text: V

text: at

text: most

text: k

text: from

text: s(u)

text: could

text: lead

text: to

text: vertices

text: of

text: (s(T))

text: s(v)

text: we

text: write

text: the

text: inequality

text: (G)

text: d

text: (k

text: s(u),x

text: (G)

text: s(u)

font: default

text: x:x=s(v

text: v

text: (T),v

text: =v

text: This

text: provides

text: a

text: recurrence

text: relation

text: F(T

text: G)

text: G)

text: k

text: k

text: (k

text: (G)

text: s

text: ds(u)

text: ψ(s,

text: G)

text: (G)

text: where

text: T

text: is

text: T

text: when

text: we

text: remove

text: v

text: and

text: the

text: edge

text: attached

text: to

text: it

text: from

text: T

text: Let

text: k

text: k

text: k

text: us

text: denote

text: by

text: H(T

text: G)

text: the

text: right

text: hand

text: side

text: of

text: the

text: above

text: formula.

text: Now,

text: we

text: can

text: k

text: bound

text: H(T

text: G),

text: as

text: in

text: the

text: previous

text: lemma.

text: So,

text: there

text: is

text: a

text: tree

text: T

text: by

text: removing

text: k

text: k

text: a

text: vertex

text: of

text: T

text: such

text: that

text: k

text: H(T

text: G)

text: H(T

text: G).

text: k

text: k

text: Continuing

text: with

text: that

text: procedure,

text: we

text: can

text: also

text: assume

text: without

text: loss

text: of

text: generality

text: that

text: u

text: is

text: the

text: last

text: vertex

text: to

text: be

text: removed,

text: i.e.

text: T

text: u

text: in

text: the

text: sequence.

text: Now

text: the

text: upper

text: bound

text: can

text: be

text: estimated

text: and

text: the

text: last

text: step

text: is

text: n,

text: rather

text: than

text: d

text: M,

text: i

text: i

text: i

text: because

text: of

text: the

text: extra

text: term

text: in

text: H.

text: Providing

text: us

text: with

text: the

text: estimate

text: ds(u)

text: F(T

text: G)

text: F(T

text: G)

text: (k

text: k

text: k

text: Which

text: yields

text: nk(k

text: F(T,

text: G)

text: F(T

text: G)

text: M

text: k

text: If

text: we

text: use

text: the

text: degree

text: sequence

text: d

text: in

text: the

text: deﬁnition

text: of

text: the

text: B-

text: function

text: while

text: the

text: i

text: actual

text: degrees

text: are

text: some

text: what

text: diﬀerent

text: d˜

text: that

text: satisﬁes

text: i

text: d

text: d˜

text: cda,

text: i

text: i

text: i

text: i.e.

text: G

text: GD

text: an

text: error

text: bound

text: diﬀerence

text: a

text: Zk

text: s

text: u∈V(T)

text: u∈V(T)

text: ds(u)

text: G),

text: where

text: (T,

text: G)

text: (G).

text: s

text: (G)

text: (T)

text: Lemma

text: For

text: Z

text: as

text: in

text: Eq.

text: we

text: have

text: k

text: Z

text: c

text: k

text: a.

text: k

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##