text: TREES IN RANDOM SPARSE GRAPHS WITH A GIVEN DEGREE SEQUENCE 3 Like the case of usual graphs, they showed the relation of the number of bipartite graphs to entropy function. Look at [3] for a survey on the subject. Canﬁeld et al [11] derived a practical formula for matrices with 0-1 entries and nearly constant row and column sums. Canﬁeld and Mckay, in [12], took a look at matrices with positive integer entries as well. Also, see [20] for similar results in sparse bipartite graphs. Following the work of Lov´asz and Szegedy, many tried to extend the notion of graphons to the sparse graphs. Look at [7] for a survey of attempts to deﬁne a notion of limit in the sparse case. Here, we take another look at the subgraph counting metric. Let us recall the homomorphism density from page 2 of Lovász and Szegedy [23], which is hom (F, G) t (F, G) := |V ||V | . (G) (F) In addition, graphs G are said to be Cauchy in subgraph-counting metric if the n sequence of numbers t (F, G ) are Cauchy for every ﬁnite graph F. So, we use a |nV ||V | uniform normalization, i.e. (G) (F) , for all embeddings of F into G. However, we believe that the normalization should be local and depend on the embedding. We try to justify that throughout this paper. Although we will not provide a metric for sparse graphs, we make a fe(cid:101)w observa- tions in sparse random graphs with a given degree sequence. We adopt the method G G in [6] that compares the random graph (D) with a random graph (D), with g independent Bernoulli random edges. By extending that work to sparse graphs, we obtain the correct normalization for counting the subgraph F, where F is a tree. We leave the case the counting of subgraphs with loops open, since this problem has not been completely understood even in the case of random models with inde- pendent edges like Erdös–Ŕenyi graph. For more discussion, look at [22], [21], and [14]). In this paper, we ﬁrst introduce a modiﬁed version of graphs with the given degree sequence D, which we call graphs with an almost given degree sequence D. Then, under some mild conditions, we ﬁnd the distribution of ﬁnite trees in this model. Second, we go back to our original problem and deal with random graph G (D). In addition, we apply our method to dense, bipartite and very sparse, i.e. g |E | d2 = o( (G) ), random graphs. n Although we need some mild conditions in most of our theorems, we show that our results holds in full generality for bipartite random graphs. So we believe that the same is true for general non-bipartite graphs with a given degree sequence D. In the end, to the best of our knowledge, the method developed here is new and works for a wider range of graphs, from very sparse to dense graphs. We begin the next section with some notation that is needed for the rest of the paper. 2. Main Results. Let us start this section by stating a few notations. Throughout this section c > 0 plays the role of a general constant that only depends on k. Now we provide k the deﬁnitions of our independent model and ordered subgraphs. ##LTLine##

text: TREES

text: IN

text: RANDOM

text: SPARSE

text: GRAPHS

text: WITH

text: A

text: GIVEN

text: DEGREE

text: SEQUENCE

text: Like

text: the

text: case

text: of

text: usual

text: graphs,

text: they

text: showed

text: the

text: relation

text: of

text: the

text: number

text: of

text: bipartite

text: graphs

text: to

text: entropy

text: function.

text: Look

text: at

text: for

text: a

text: survey

text: on

text: the

text: subject.

text: Canﬁeld

text: et

text: al

text: derived

text: a

text: practical

text: formula

text: for

text: matrices

text: with

text: entries

text: and

text: nearly

text: constant

text: row

text: and

text: column

text: sums.

text: Canﬁeld

text: and

text: Mckay,

text: in

text: took

text: a

text: look

text: at

text: matrices

text: with

text: positive

text: integer

text: entries

text: as

text: well.

text: Also,

text: see

text: for

text: similar

text: results

text: in

text: sparse

text: bipartite

text: graphs.

text: Following

text: the

text: work

text: of

text: Lov´asz

text: and

text: Szegedy,

text: many

text: tried

text: to

text: extend

text: the

text: notion

text: of

text: graphons

text: to

text: the

text: sparse

text: graphs.

text: Look

text: at

text: for

text: a

text: survey

text: of

text: attempts

text: to

text: deﬁne

text: a

text: notion

text: of

text: limit

text: in

text: the

text: sparse

text: case.

text: Here,

text: we

text: take

text: another

text: look

text: at

text: the

text: subgraph

text: counting

text: metric.

text: Let

text: us

text: recall

text: the

text: homomorphism

text: density

text: from

text: page

text: of

text: Lovász

text: and

text: Szegedy

text: which

text: is

text: hom

text: (F,

text: G)

text: t

text: (F,

text: G)

text: |V

text: ||V

text: (G)

text: (F)

text: In

text: addition,

text: graphs

text: G

text: are

text: said

text: to

text: be

text: Cauchy

text: in

text: subgraph-counting

text: metric

text: if

text: the

text: n

text: sequence

text: of

text: numbers

text: t

text: (F,

text: G

text: are

text: Cauchy

text: for

text: every

text: ﬁnite

text: graph

text: F.

text: So,

text: we

text: use

text: a

text: |nV

text: ||V

text: uniform

text: normalization,

text: i.e.

text: (G)

text: (F)

text: for

text: all

text: embeddings

text: of

text: F

text: into

text: G.

text: However,

text: we

text: believe

text: that

text: the

text: normalization

text: should

text: be

text: local

text: and

text: depend

text: on

text: the

text: embedding.

text: We

text: try

text: to

text: justify

text: that

text: throughout

text: this

text: paper.

text: Although

text: we

text: will

text: not

text: provide

text: a

text: metric

text: for

text: sparse

text: graphs,

text: we

text: make

text: a

text: observa-

text: tions

text: in

text: sparse

text: random

text: graphs

text: with

text: a

text: given

text: degree

text: sequence.

text: We

text: adopt

text: the

text: method

text: G

text: G

text: in

text: that

text: compares

text: the

text: random

text: graph

text: (D)

text: with

text: a

text: random

text: graph

text: (D),

text: with

text: g

text: independent

text: Bernoulli

text: random

text: edges.

text: By

text: extending

text: that

text: work

text: to

text: sparse

text: graphs,

text: we

text: obtain

text: the

text: correct

text: normalization

text: for

text: counting

text: the

text: subgraph

text: F,

text: where

text: F

text: is

text: a

text: tree.

text: We

text: leave

text: the

text: case

text: the

text: counting

text: of

text: subgraphs

text: with

text: loops

text: open,

text: since

text: this

text: problem

text: has

text: not

text: been

text: completely

text: understood

text: even

text: in

text: the

text: case

text: of

text: random

text: models

text: with

text: inde-

text: pendent

text: edges

text: like

text: Erdös–Ŕenyi

text: graph.

text: For

text: more

text: discussion,

text: look

text: at

text: and

text: In

text: this

text: paper,

text: we

text: ﬁrst

text: introduce

text: a

text: modiﬁed

text: version

text: of

text: graphs

text: with

text: the

text: given

text: degree

text: sequence

text: D,

text: which

text: we

text: call

text: graphs

text: with

text: an

text: almost

text: given

text: degree

text: sequence

text: D.

text: Then,

text: under

text: some

text: mild

text: conditions,

text: we

text: ﬁnd

text: the

text: distribution

text: of

text: ﬁnite

text: trees

text: in

text: this

text: model.

text: Second,

text: we

text: go

text: back

text: to

text: our

text: original

text: problem

text: and

text: deal

text: with

text: random

text: graph

text: G

text: (D).

text: In

text: addition,

text: we

text: apply

text: our

text: method

text: to

text: dense,

text: bipartite

text: and

text: very

text: sparse,

text: i.e.

text: g

text: |E

text: o(

text: (G)

text: random

text: graphs.

text: n

text: Although

text: we

text: need

text: some

text: mild

text: conditions

text: in

text: most

text: of

text: our

text: theorems,

text: we

text: show

text: that

text: our

text: results

text: holds

text: in

text: full

text: generality

text: for

text: bipartite

text: random

text: graphs.

text: So

text: we

text: believe

text: that

text: the

text: same

text: is

text: true

text: for

text: general

text: non-bipartite

text: graphs

text: with

text: a

text: given

text: degree

text: sequence

text: D.

text: In

text: the

text: end,

text: to

text: the

text: best

text: of

text: our

text: knowledge,

text: the

text: method

text: developed

text: here

text: is

text: new

text: and

text: works

text: for

text: a

text: wider

text: range

text: of

text: graphs,

text: from

text: very

text: sparse

text: to

text: dense

text: graphs.

text: We

text: begin

text: the

text: next

text: section

text: with

text: some

text: notation

text: that

text: is

text: needed

text: for

text: the

text: rest

text: of

text: the

text: paper.

text: Main

text: Results.

text: Let

text: us

text: start

text: this

text: section

text: by

text: stating

text: a

text: few

text: notations.

text: Throughout

text: this

text: section

text: c

text: plays

text: the

text: role

text: of

text: a

text: general

text: constant

text: that

text: only

text: depends

text: on

text: k.

text: Now

text: we

text: provide

text: k

text: the

text: deﬁnitions

text: of

text: our

text: independent

text: model

text: and

text: ordered

text: subgraphs.

text: ##LTLine##


text: TREES IN RANDOM SPARSE GRAPHS WITH A GIVEN DEGREE SEQUENCE 21 (cid:16) (cid:17) ∈ (cid:101) Now, for any graph G A, we have (cid:101) G P (D) = G (cid:16) G (cid:17) 1 (cid:12) ≤(cid:12) 1 P(cid:101)( a (a, D) = G) (cid:101)= |GD(cid:12)| (cid:12)p |GD| . a min a Furthermore, P G (D) ∈(cid:101) GD ≤ P · GD , so (cid:16) (cid:17) a (cid:16) max (cid:17) a (cid:101) (cid:16) (cid:17) (cid:101) (cid:101) (cid:101) (cid:101)C P (G (a, D) ∈ A) ≤ Pmax 1 P(G ∈ A) ≤ e2 2(D) P G ∈ A , (cid:101)a (cid:101) Pmin P G ∈ GDa P G ∈ GDa G G (cid:3) where = (D) . We continue with a lemma that investigates some properties of r s that are i required frequently through out this section. ≤ · · · ≤ Lemma 3.7. We suppose that d d , then, 1 n ≤ · · · ≤ a) r r , 1 n (cid:80) b) and r r > 1 . ≥1 n n ≤ ≤ c) If r 1, for some 1 k n, then r /r < n4. k ≤ ≤ k+1 k ≤ d) If r > n2, for some 1 k n, then d 1M, where the sum is over ≤k ≤ − − i 2 1 i n d 1. k (cid:3) Proof. We leave the proof for Appendix B. Lemma 3.8. Suppose that the vector D is a strict graphic sequence of type (ε, ν) as in Deﬁnition 2.7. Then, {C C } ≤ · − − · · (3.9) max 1 (D) , 2 (D) 8 na ν 12 M log (n) , C C where (D) and (D) are deﬁned in Eq. (3.5) and (3.7), respectively, and 1 2 1 < a < ν + 1. 2 4 2 (cid:40) (cid:41) Proof. Let A := {n − d , · · · , n}, and recal(cid:12)(cid:12)l (cid:88)that k k ∈ ≤ M (cid:96)(D) := max k [n] d , (cid:80) (cid:80) ∈ i 2 i Ak ≤ as in Eq. (2.6). Correspondingly, if we denote (cid:96)(D) by (cid:96), then we have ∈ d ≥ ≤i A(cid:96) i M , and ∈ d M . Now, part d of Lemma 3.7 implies that r n2. By p2art a of thie/As(cid:96)amie lem2ma, we get d = d , whenever r = r . Th(cid:96)erefore, the { | ≥ } i i+1 · · · i i+1 set I := r i (cid:96) of distinct values among r , , r can be at most the distinct i · · · −(cid:96) n values among d , , d and has at most d d + 1 elements. Again, by part c of (cid:96) n n (cid:96) that lemma, each r is either less than 1 or can exceed the previous one by at most i n4, hence ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: TREES

label: paragraph

text: IN

text: RANDOM

text: SPARSE

text: GRAPHS

text: WITH

text: A

text: GIVEN

text: DEGREE

text: SEQUENCE

text: Now,

text: for

text: any

text: graph

text: G

text: A,

text: we

text: have

text: G

text: P

text: (D)

text: G

text: G

text: a

text: (a,

text: D)

text: G)

text: |GD|

text: a

text: min

text: a

text: Furthermore,

text: P

text: G

text: (D)

text: GD

text: P

text: GD

text: so

text: a

text: max

text: a

text: P

text: (G

text: (a,

text: D)

text: A)

text: Pmax

text: P(G

text: A)

text: P

text: G

text: A

text: Pmin

text: P

text: G

text: GDa

text: P

text: G

text: GDa

text: G

text: G

text: where

text: (D)

text: We

text: continue

text: with

text: a

text: lemma

text: that

text: investigates

text: some

text: properties

text: of

text: r

text: s

text: that

text: are

text: i

text: required

text: frequently

text: through

text: out

text: this

text: section.

text: Lemma

text: We

text: suppose

text: that

text: d

text: d

text: then,

text: n

text: a)

text: r

text: r

text: n

text: b)

text: and

text: r

text: r

text: ≥1

text: n

text: n

text: c)

text: If

text: r

text: for

text: some

text: k

text: n,

text: then

text: r

text: /r

text: k

text: k

text: d)

text: If

text: r

text: for

text: some

text: k

text: n,

text: then

text: d

text: where

text: the

text: sum

text: is

text: over

text: ≤k

text: i

text: i

text: n

text: d

text: k

text: Proof.

text: We

text: leave

text: the

text: proof

text: for

text: Appendix

text: B.

text: Lemma

text: Suppose

text: that

text: the

text: vector

text: D

text: is

text: a

text: strict

text: graphic

text: sequence

text: of

text: type

text: (ε,

text: ν)

text: as

text: in

text: Deﬁnition

text: Then,

text: {C

text: C

text: max

text: (D)

text: (D)

text: ν

text: M

text: log

text: (n)

text: C

text: C

text: where

text: (D)

text: and

text: (D)

text: are

text: deﬁned

text: in

text: Eq.

text: and

text: respectively,

text: and

text: a

text: ν

text: Proof.

text: Let

text: A

text: {n

text: d

text: n},

text: and

text: k

text: k

text: M

text: max

text: k

text: [n]

text: d

text: i

text: i

text: Ak

text: as

text: in

text: Eq.

text: Correspondingly,

text: if

text: we

text: denote

text: by

text: then

text: we

text: have

text: d

text: ≤i

text: i

text: M

text: and

text: d

text: M

text: Now,

text: part

text: d

text: of

text: Lemma

text: implies

text: that

text: r

text: By

text: a

text: of

text: we

text: get

text: d

text: d

text: whenever

text: r

text: r

text: the

text: i

text: i

text: set

text: I

text: r

text: i

text: of

text: distinct

text: values

text: among

text: r

text: r

text: can

text: be

text: at

text: most

text: the

text: distinct

text: i

text: n

text: values

text: among

text: d

text: d

text: and

text: has

text: at

text: most

text: d

text: d

text: elements.

text: Again,

text: by

text: part

text: c

text: of

text: n

text: n

text: that

text: lemma,

text: each

text: r

text: is

text: either

text: less

text: than

text: or

text: can

text: exceed

text: the

text: previous

text: one

text: by

text: at

text: most

text: i

text: hence

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: TREES IN RANDOM SPARSE GRAPHS WITH A GIVEN DEGREE SEQUENCE 25 (cid:88) 1 p (3.16) δ = (cid:88)α 1 λ ω2 (cid:101) α α 1 1 = (cid:88) p (s, T) µ ∈ M2ψ2(s, T, D)(cid:101) (s,T) A ≤ 1 1 1 p (s, T) M2 µ ∈ ψ(s, T, D) (s,T) A ≤ 1 . M For the last step, we used an argument similar to Lemma 3.1 to get (cid:88) (cid:101) 1 1 ≤ (3.17) p (s, T) M. µ ∈ ψ(s, T, D) (s,T) A (cid:8) (cid:12) (cid:9) ∼ Comp(cid:101)uting(cid:101) δ needs more work. Two ordere(cid:12)d trees are dependent, s (T ) ∼ 2 E ∩ E 1 1(cid:54) ∅ s (T ) (α β), iﬀ they share at least one edge, or (s (T )) (s (T )) = . 2 2 G G ∼1 1 2 2 We let = (D) , and N (s , T ) := (s , T ) s (T ) s (T ) . It follows by 1 1 2 2 1 1 2 2 Lemma 3.12 that (3.18)(cid:88) (cid:88) δ 2 1 1 = (cid:88) EI I(cid:88) (cid:104) (cid:105) λ ∼ ωαωβ α β (cid:101) (cid:101) α β α 1 1 G G = (cid:88) (cid:88) (cid:104) E (cid:105)1 (T , )1 (T , ) µM2 ∈ ∈ ψ(s1, T1, D)ψ(s2, T2, D) (cid:101) s1 1 s2 2 (s1,T1) A (s2,T2) N(s1,T1) ≤ 1 1 G · E 1 (T , ) , µ M2 ∈ ∈ ψ(s3, T3, D) s3 3 (s1,T1) A (s2,T2) N(s1,T1) ∨ where (s , T ) = (s , T ) (s , T ) in the last sum, and we denote the set of all such ordere3d tr3ees (s 1, T 1) by U2(s 2, T ). Moreover, for (s, T) ∈ Sj × Tj and j > k, 3 3 1 1 we let T(k) be the restriction (cid:110)of T to its ﬁrst k(cid:12)ve(cid:16)rtices(cid:17)and we de(cid:111)ﬁne (cid:12) ∈ S × T U (s , T , j) := (s, T) j j s T(k) = s (T ) . 1 1 1 1 In other words, U (s , T , j) is the set of ordered trees of size j that are extensions 1 1 of (s , T ). 1 1 ∨ ≤ ≤ Now, the wedge sum tree (s , T ) (s , T ) is in U (s , T , j), for some k j − 1 1 2 2 1 1 2 (k 1). Alternatively, for each element (s , T ) of U (s , T , j) and by Remark 3 3 1 1 ∨ 3.11, the number of pairs (s , T ) and (s , T ) such that (s , T ) = (s , T ) (s , T ) · − · 1 1 2 2 − · − 3· 3 − 1 1 2 2 is bounded by 2j (j 1) (j!)2 and, hence, by 22(k 1) (2k 3) ((2k 2)!)2. Thus, Eq (3.18) goes as ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##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

label: equation

text: p

text: δ

text: λ

text: ω2

text: α

text: α

text: p

text: (s,

text: T)

text: µ

text: T,

text: (s,T)

text: A

text: p

text: (s,

text: T)

text: µ

text: ψ(s,

text: T,

text: D)

text: (s,T)

text: A

text: M

text: For

text: the

text: last

text: step,

text: we

text: used

text: an

text: argument

text: similar

text: to

text: Lemma

text: to

text: get

text: p

text: (s,

text: T)

text: M.

text: µ

text: ψ(s,

text: T,

text: D)

text: (s,T)

text: A

text: δ

text: needs

text: more

text: work.

text: Two

text: trees

text: are

text: dependent,

text: s

text: (T

text: E

text: E

text: s

text: (T

text: (α

text: β),

text: iﬀ

text: they

text: share

text: at

text: least

text: one

text: edge,

text: or

text: (s

text: (T

text: (s

text: (T

text: G

text: G

text: ∼1

text: We

text: let

text: (D)

text: and

text: N

text: (s

text: T

text: (s

text: T

text: s

text: (T

text: s

text: (T

text: It

text: follows

text: by

text: Lemma

text: that

text: δ

text: EI

text: λ

text: ωαωβ

text: α

text: β

text: α

text: β

text: α

text: G

text: G

text: E

text: (T

text: (T

text: D)

text: A

text: G

text: E

text: (T

text: µ

text: D)

text: A

text: where

text: (s

text: T

text: (s

text: T

text: (s

text: T

text: in

text: the

text: last

text: sum,

text: and

text: we

text: denote

text: the

text: set

text: of

text: all

text: such

text: (s

text: T

text: by

text: T

text: Moreover,

text: for

text: (s,

text: T)

text: Sj

text: Tj

text: and

text: j

text: k,

text: we

text: let

text: T(k)

text: be

text: the

text: restriction

text: T

text: to

text: its

text: ﬁrst

text: we

text: S

text: T

text: U

text: (s

text: T

text: j)

text: (s,

text: T)

text: j

text: j

text: s

text: T(k)

text: s

text: (T

text: In

text: other

text: words,

text: U

text: (s

text: T

text: j)

text: is

text: the

text: set

text: of

text: ordered

text: trees

text: of

text: size

text: j

text: that

text: are

text: extensions

text: of

text: (s

text: T

text: Now,

text: the

text: wedge

text: sum

text: tree

text: (s

text: T

text: (s

text: T

text: is

text: in

text: U

text: (s

text: T

text: j),

text: for

text: some

text: k

text: j

text: (k

text: Alternatively,

text: for

text: each

text: element

text: (s

text: T

text: of

text: U

text: (s

text: T

text: j)

text: and

text: by

text: Remark

text: the

text: number

text: of

text: pairs

text: (s

text: T

text: and

text: (s

text: T

text: such

text: that

text: (s

text: T

text: (s

text: T

text: (s

text: T

text: 3·

text: is

text: bounded

text: by

text: (j

text: and,

text: hence,

text: by

text: Thus,

text: Eq

text: goes

text: as

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: TREES IN RANDOM SPARSE GRAPHS WITH A GIVEN DEGREE SEQUENCE 31 Figure 3.1. The process of changing a weighted bipartite graph { } to a bipartite graph with weights in 0, 1 . The ﬁgure on the upper left hand side shows the live edges of a bipartite graph on 7 vertices. We pick a loop that is shown in green, and change the weights on it. (cid:104) (cid:105) (cid:104) (cid:105) We add 0.2 to the weights of edges 1, 5 and 3, 6 , and subtract 0.2 from (cid:104) (cid:105) (cid:104) (cid:105) (cid:104) (cid:105) w ( 5, 3 ) and w ( 6, 1 ). Now, the edge 1, 6 dies and we get the ﬁgure on the upper right hand side. Since we have no other loops, we choose the biggest path that is shown in green. If we add and subtract 0.1 to and from the weights of (cid:104) (cid:105) edges of this path alternatively, we get the third graph, where the edge 3, 7 becomes dead. ∪ ∅ Here G G is the union of edges of the two graphs G and G , and the graph 1 2 1 2 A is a graph on vertices of A with no edges. \ We actually prove the above theorem for A = I and B = [n] I , where I , 10 10 α for any α > 0, is deﬁned as (cid:8) (cid:12) (cid:9)a1 a1 (cid:12) ≤ (3.25) I := i d logα(n) . α i Our proof has two steps. First, we build the deterministic graph T, and then we show that it can be extended to a graph with an almost given degree sequence with high probability. (cid:88) Lemma 3.19. Let us deﬁne (cid:101) D (i, A) := p , ij ∈ \{ } j A i ∈ { · · · } ⊆ where i [n] and A is a subset of [n] = 1, , n . Then, for every A [n], there \ is a bipartite graph T with vertex sets A and B = [n] A, and edges inside Ed(A, B) such that a) ∈ {(cid:98) (cid:99) (cid:98) (cid:99) } ∈ (3.26) b D (i, B) , D (i, B) + 1 , where i A, i ##LTFigure## ##LTLine## ##LTLine##

text: TREES

text: IN

text: RANDOM

text: SPARSE

text: GRAPHS

text: WITH

text: A

text: GIVEN

text: DEGREE

text: SEQUENCE

text: Figure

text: The

label: caption

text: process

text: of

text: changing

text: a

text: weighted

text: bipartite

text: graph

text: to

text: a

text: bipartite

text: graph

text: with

text: weights

text: in

text: The

text: ﬁgure

text: on

text: the

text: upper

text: left

text: hand

text: side

text: shows

text: the

text: live

text: edges

text: of

text: a

text: bipartite

text: graph

text: on

text: vertices.

text: We

text: pick

text: a

text: loop

text: that

text: is

text: shown

text: in

text: green,

text: and

text: change

text: the

text: weights

text: on

text: it.

text: We

text: add

text: to

text: the

text: weights

text: of

text: edges

text: and

text: and

text: subtract

text: from

text: w

text: and

text: w

text: Now,

text: the

text: edge

text: dies

text: and

text: we

text: get

text: the

text: ﬁgure

text: on

text: the

text: upper

text: right

text: hand

text: side.

text: Since

text: we

text: have

text: no

text: other

text: loops,

text: we

text: choose

text: the

text: biggest

text: path

text: that

text: is

text: shown

text: in

text: green.

text: If

text: we

text: add

text: and

text: subtract

text: to

text: and

text: from

text: the

text: weights

text: of

text: edges

text: of

text: this

text: path

text: alternatively,

text: we

text: get

text: the

text: third

text: graph,

text: where

text: the

text: edge

text: becomes

text: dead.

text: Here

text: G

text: G

text: is

text: the

text: union

text: of

text: edges

text: of

text: the

text: two

text: graphs

text: G

text: and

text: G

text: and

text: the

text: graph

text: A

text: is

text: a

text: graph

text: on

text: vertices

text: of

text: A

text: with

text: no

text: edges.

text: We

text: actually

text: prove

text: the

text: above

text: theorem

text: for

text: A

text: I

text: and

text: B

text: [n]

text: I

text: where

text: I

text: α

text: for

text: any

text: α

text: is

text: deﬁned

text: as

text: I

text: i

text: d

text: logα(n)

text: α

text: i

text: Our

text: proof

text: has

text: two

text: steps.

text: First,

text: we

text: build

text: the

text: deterministic

text: graph

text: T,

text: and

text: then

text: we

text: show

text: that

text: it

text: can

text: be

text: extended

text: to

text: a

text: graph

text: with

text: an

text: almost

text: given

text: degree

text: sequence

text: with

text: high

text: probability.

text: Lemma

text: Let

text: us

text: deﬁne

text: D

text: (i,

text: A)

text: p

text: ij

text: j

text: A

text: i

text: where

text: i

text: [n]

text: and

text: A

text: is

text: a

text: subset

text: of

text: [n]

text: n

text: Then,

text: for

text: every

text: A

text: [n],

text: there

text: is

text: a

text: bipartite

text: graph

text: T

text: with

text: vertex

text: sets

text: A

text: and

text: B

text: [n]

text: A,

text: and

text: edges

text: inside

text: Ed(A,

text: B)

text: such

text: that

text: a)

text: b

text: D

text: (i,

text: B)

text: D

text: (i,

text: B)

text: where

text: i

text: A,

text: i

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##


text: TREES IN RANDOM SPARSE GRAPHS WITH A GIVEN DEGREE SEQUENCE 37 (cid:88) (cid:2) (cid:3) (cid:88) We apply Chernoﬀ’s bound with parameters (cid:101) µ := E 1(cid:104) (cid:105) = p = D (j, B) , j i,j ij ∈ \{ } ∈ \{ } i B j i B j − ≤ ≤ ≤ and δ = D (j, B) 12+a1 1(cid:0), wh(cid:1)ere 1 j(cid:18) n. Hence, (cid:19) ≤ −1 (3.34) P Ec 2 exp D (j, B)2a1 . j 3 Now, for those j in J and by (cid:0)(3.3(cid:1)3), we observe that Eq. (3.34) turns into ≤ − (3.35) P Ejc 2e 13 log2(n). ≤ ≤ Similarly, for 1 j n,(cid:0) (cid:1) (cid:0) (cid:1) ≤ − (3.36) P Fc exp log2(n)D (j, B) , j where δ = 2 log2(n)D (j, B) . In order to complete the bound in Eq (3.36), we ≥ ∈ \ ≥ show D(j, B) 1, for j B. If A = I = [n] B is empty then D(j, B) = d 1. Otherwise, if A (cid:54)=4 ∅, then 1 ∈ A. Wea110observe that rirj is increasing botjh in i and j, so (cid:88) (cid:88) 1+rirj (cid:101) r r (3.37) D(j, B) = (cid:88)∈ \(cid:18){ } pij = (cid:19)∈ \{ } 1 +irjirj i B j i B j ≥ r r − r r i 1 1 j (cid:101) ∈ 1 + rir1 1 + r1rj i B − (cid:101) = D(1, B) p 1j − − = d D(1, A) p . 1 1j (cid:101) ≥ ≤ In addition, we know that d1 (cid:101) 1, and by Proposition 3.21, we get D(1, A) ≥ 14, for large enough n. Thus, if p is smaller than 1, then Eq. (3.37) gives D(j, B) 1. 1≤j ≤ 4 2 On the other hand, we get 1 p(cid:0) (cid:1)D(j, B). 4 1j Therefore, ≤ − (cid:16) (cid:17)P Fjc (cid:88)e 14 log2(n). (cid:88) Combini(cid:101)ng the previous inequality with Eq. (3.35), we have G ∈ ∩ ∩ ≥ − − − − ≥ − 1 P B j∈JEj j∈/J Fj 1 ∈ e 13 log2(n) ∈ e 14 log2(n) 1 n, i J i/J (cid:3) for large enough n. That concludes the proof. ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##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: We

text: apply

text: Chernoﬀ’s

text: bound

text: with

text: parameters

text: µ

text: E

text: p

text: D

text: (j,

text: B)

text: j

text: i,j

text: ij

text: i

text: B

text: j

text: i

text: B

text: j

text: and

text: δ

text: D

text: (j,

text: B)

text: n.

text: Hence,

text: −1

text: P

text: Ec

text: exp

text: D

text: (j,

text: j

text: Now,

text: for

text: those

text: j

text: in

text: J

text: and

text: by

text: we

text: observe

text: that

text: Eq.

text: turns

text: into

text: P

text: Ejc

text: Similarly,

text: for

text: j

text: P

text: Fc

text: exp

text: (j,

text: B)

text: j

text: where

text: δ

text: (j,

text: B)

text: In

text: order

text: to

text: complete

text: the

text: bound

text: in

text: Eq

text: we

text: show

text: D(j,

text: B)

text: for

text: j

text: B.

text: If

text: A

text: I

text: [n]

text: B

text: is

text: empty

text: then

text: D(j,

text: B)

text: d

text: Otherwise,

text: if

text: A

text: then

text: A.

text: that

text: rirj

text: is

text: increasing

text: botjh

text: in

text: i

text: and

text: j,

text: so

text: r

text: r

text: D(j,

text: B)

text: pij

text: +irjirj

text: i

text: B

text: j

text: i

text: B

text: j

text: r

text: r

text: r

text: r

text: i

text: j

text: i

text: B

text: B)

text: p

text: d

text: A)

text: p

text: In

text: addition,

text: we

text: know

text: that

text: and

text: by

text: Proposition

text: we

text: get

text: A)

text: for

text: large

text: enough

text: n.

text: Thus,

text: if

text: p

text: is

text: smaller

text: than

text: then

text: Eq.

text: gives

text: D(j,

text: B)

text: On

text: the

text: other

text: hand,

text: we

text: get

text: B).

text: Therefore,

text: Fjc

text: the

text: previous

text: inequality

text: with

text: Eq.

text: we

text: have

text: G

text: P

text: B

text: j∈JEj

text: j∈/J

text: Fj

text: e

text: e

text: n,

text: i

text: J

text: i/J

text: for

text: large

text: enough

text: n.

text: That

text: concludes

text: the

text: proof.

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: ##LTLine##


text: (cid:0) (cid:1) TREES IN RANDOM SPARSE GRAPHS WITH A GIVEN DEGREE SEQUENCE 45 (cid:16) (cid:17) is greater or equal to n 1/2 n3a1. In addition, we let (cid:15) satisfy M 1 (cid:112)n 1/2 (cid:15)2 = − n2a1, µ M q − which resembles Eq. (3.22) with n ν = n . M We continue and combine part 3 and 4 of Lemma 3.28, and Lemma 3.31 to get, (cid:12) (cid:12)  − (cid:12)(cid:12) (cid:88) (cid:12)(cid:12) L (cid:12) (cid:12)  (cid:12) (cid:12) (cid:12) (cid:12) 1 − G − := P (cid:16) (cid:0) (cid:1) (cid:17) (cid:12)(p (s, T) 1 (T, (a, D))) > µ (cid:15) (cid:12)  ∈ − ψ(s, T, D) (cid:12)(cid:12) q(cid:88) s a (cid:12)(cid:12) (s,T) A (cid:12) (cid:12)  (cid:12) (cid:12) ≤ exp(cid:32)PO(G(qMn∈ G12Dan)a1) P(cid:32)(cid:18)(cid:12) (cid:19)∈ − ψ(cid:33)(s,1T, D) (pq (s,(cid:33)T) − 1s (T, Gq))(cid:12) > µ−(cid:15) (s,T) A 1 ≤ − M 2 exp (cµM) (cid:15)2 + O na1 + O (n log(n)) , n G G where = (D). The rest is th(cid:18)e (cid:16)same(cid:17)process as in(cid:19)the proof of Theorem 2.11, q q and we end up with the bound in Eq. (3.42), i.e. ≤ · n 1/4 d2 I C na1 + n . k M M For the last parts of our theorem, w(cid:16)e use part 1(cid:12)(cid:12) of Lemma 3.(cid:17)28. Therefore, (cid:12) (3.43) P (G (D) ∈ A) = P G (D) ∈ A G (D) ∈ GD q q q ≤ 1 G ∈ P (G (D) ∈ GD)P ( q (D) A) , q where A is a subset of GD, and again, G is the random graph chosen uniformly g from GD. Using Eq. 3.43, the last part of Lemma 3.28, and an argument identical to the proof of Remark 2.20, we obtain (cid:32)(cid:18) (cid:19) (cid:33) (cid:88) (3.44) 1 | − | ≤ · n log(n) 1/2 d2 p (s, T) p (s, T) C + n , ψ(s, T, D) q g k M M ∈S ×T (s,T) k k n where G p (s, T) = E [1 (T, )] , g s g as in Conjecture 2.19. Finally, parts 2 and 3 of the theorem follow from the ﬁrst part of the theorem, (cid:3) Eq. (3.42) and (3.44), and the triangle inequality. (cid:101) | − | Remark 3.32. Although the bound for the diﬀerences p (s, T) p (s, T) in the g second part of the theorem is o(1), compared to Conjecture 2.19, it is not optimal. The reason is that we do not get the lower bound in Conjecture 2.18. Instead, we use parameters p (s, T) and p (s, T) as a middle step to achieve our bound. q a ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##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: is

text: greater

text: or

text: equal

text: to

text: n

text: In

text: addition,

text: we

text: let

text: satisfy

text: M

text: µ

text: M

text: q

text: which

text: resembles

text: Eq.

text: with

text: n

text: ν

text: n

text: M

text: We

text: continue

text: and

text: combine

text: part

text: and

text: of

text: Lemma

text: and

text: Lemma

text: to

text: get,

text: L

text: G

text: P

text: (s,

text: T)

text: (T,

text: (a,

text: D)))

text: µ

text: ψ(s,

text: T,

text: D)

text: s

text: a

text: (s,T)

text: A

text: D)

text: (pq

text: (T,

text: (s,T)

text: A

text: M

text: exp

text: (cµM)

text: O

text: O

text: (n

text: log(n))

text: n

text: G

text: G

text: where

text: (D).

text: The

text: rest

text: is

text: as

text: proof

text: of

text: Theorem

text: q

text: q

text: and

text: we

text: end

text: up

text: with

text: the

text: bound

text: in

text: Eq.

text: i.e.

text: n

text: I

text: C

text: n

text: k

text: M

text: M

text: For

text: the

text: last

text: parts

text: of

text: our

text: theorem,

text: use

text: part

text: of

text: Lemma

text: Therefore,

text: P

text: (G

text: (D)

text: A)

text: P

text: G

text: (D)

text: A

text: G

text: (D)

text: GD

text: q

text: q

text: q

text: G

text: P

text: (G

text: (D)

text: GD)P

text: q

text: (D)

text: A)

text: q

text: where

text: A

text: is

text: a

text: subset

text: of

text: GD,

text: and

text: again,

text: G

text: is

text: the

text: random

text: graph

text: chosen

text: uniformly

text: g

text: from

text: GD.

text: Using

text: Eq.

text: the

text: last

text: part

text: of

text: Lemma

text: and

text: an

text: argument

text: identical

text: to

text: the

text: proof

text: of

text: Remark

text: we

text: obtain

text: n

text: log(n)

text: p

text: (s,

text: T)

text: p

text: (s,

text: T)

text: C

text: n

text: ψ(s,

text: T,

text: D)

text: q

text: g

text: k

text: M

text: M

text: ∈S

text: ×T

text: (s,T)

text: k

text: k

text: n

text: where

text: G

text: p

text: (s,

text: T)

text: E

text: (T,

text: g

text: s

text: g

text: as

text: in

text: Conjecture

text: Finally,

text: parts

text: and

text: of

text: the

text: theorem

text: follow

text: from

text: the

text: ﬁrst

text: part

text: of

text: the

text: theorem,

text: Eq.

text: and

text: and

text: the

text: triangle

text: inequality.

text: Remark

text: Although

text: the

text: bound

text: for

text: the

text: diﬀerences

text: p

text: (s,

text: T)

text: p

text: (s,

text: T)

text: in

text: the

text: g

text: second

text: part

text: of

text: the

text: theorem

text: is

text: compared

text: to

text: Conjecture

text: it

text: is

text: not

text: optimal.

text: The

text: reason

text: is

text: that

text: we

text: do

text: not

text: get

text: the

text: lower

text: bound

text: in

text: Conjecture

text: Instead,

text: we

text: use

text: parameters

text: p

text: (s,

text: T)

text: and

text: p

text: (s,

text: T)

text: as

text: a

text: middle

text: step

text: to

text: achieve

text: our

text: bound.

text: q

text: a

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: ##LTLine##

text: ##LTLine##


text: TREES IN RANDOM SPARSE GRAPHS WITH A GIVEN DEGREE SEQUENCE 47 4. Acknowledgements The author would like to thank S. R. Srinivasa Varadhan for reviewing the manuscript and his useful comments. Thanks to S. Chatterjee for suggesting the problem. Thanks to A. Barvinok, M. Harel, A. Krishnan, and A. Munez for fruitful discussions and references. Appendix A. A concentration inequality. We also need the following concentration theorem for the proof of Theorem 2.11 that is inspired by a paper by Janson [21]. This is the generalized version of Theorem 1 from Janson’s paper, and we modiﬁed the proof for our purpose. (cid:81) Therefore, we begin this part with some notations and a theorem. { } Co(cid:80)nsider a set J ∈ of independent random indicator variables and a fam- { } i i Q ily Q(α) ∈ of subsets of the index set Q, and deﬁne 1 = ∈ J and α A α i Q(α) i S = ∈ 1 1 , where ω are positive numbers. [In other words, S counts the weighteαd nAuωmαbeαr of the giαven sets Q{α} that are contained in the random set { ∈ } i Q : J = 1 , with independently appearing elements.] We assume, for the sake i of simplicity, that the index set A is ﬁnite, but it is easy to see that the results ∞ extend to inﬁnite sums, provided E[S] < . ∼ ∩ (cid:54) ∅ (cid:54) Write α β if Q(α) Q(β) = but α = β, and deﬁne (cid:88) p = E [1 ] , α α (cid:88) 1 λ = E [S] = p , ω α α 1 p (cid:88)δ =(cid:88) α , 1 λ ω2 α α 1 1 δ = E [1 1 ] . 2 λ ∼ ωαωβ α β α β α (cid:20) ≤ ≤ (cid:21) Theorem A.1. With notation above and 0 (cid:15) 1 then ≤ − ≤ − λ − − P(S (1 (cid:15))λ) exp ((cid:15) + (1 (cid:15)) log(1 (cid:15))) . δ + δ 1 2 We want to use the Chernoﬀ bound, but ﬁrst we need an upper bound for the moment-generating function. So the proof of Theorem A.1 follows our next lemma. ≥ Lemma A.2. Using the preceding(cid:20)notations in Theorem A(cid:21).1 and for t 0, we have (cid:2) (cid:3) − ≤ − λ − − E(cid:2) e tS(cid:3) exp (1 e (δ1+δ2)t) . δ + δ 1 2 Proof. Let ψ(t) = E e−tS , for t(cid:2)≥ 0. T(cid:3)hen(cid:88) (cid:20) (cid:21) −dψ(t) − 1 − = E Se tS = E 1 e tS . dt ω α α α ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##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

label: section

text: Acknowledgements

text: The

text: author

text: would

text: like

text: to

text: thank

text: S.

text: R.

text: Srinivasa

text: Varadhan

text: for

text: reviewing

text: the

text: manuscript

text: and

text: his

text: useful

text: comments.

text: Thanks

text: to

text: S.

text: Chatterjee

text: for

text: suggesting

text: the

text: problem.

text: Thanks

text: to

text: A.

text: Barvinok,

text: M.

text: Harel,

text: A.

text: Krishnan,

text: and

text: A.

text: Munez

text: for

text: fruitful

text: discussions

text: and

text: references.

text: Appendix

text: A.

text: A

text: concentration

text: inequality.

text: We

text: also

text: need

text: the

text: following

text: concentration

text: theorem

text: for

text: the

text: proof

text: of

text: Theorem

text: that

text: is

text: inspired

text: by

text: a

text: paper

text: by

text: Janson

text: This

text: is

text: the

text: generalized

text: version

text: of

text: Theorem

text: from

text: Janson’s

text: paper,

text: and

text: we

text: modiﬁed

text: the

text: proof

text: for

text: our

text: purpose.

text: Therefore,

text: we

text: begin

text: this

text: part

text: with

text: some

text: notations

text: and

text: a

text: theorem.

text: a

text: set

text: J

text: of

text: independent

text: random

text: indicator

text: variables

text: and

text: a

text: fam-

text: i

text: i

text: Q

text: ily

text: Q(α)

text: of

text: subsets

text: of

text: the

text: index

text: set

text: Q,

text: and

text: deﬁne

text: J

text: and

text: α

text: A

text: α

text: i

text: Q(α)

text: i

text: S

text: where

text: ω

text: are

text: positive

text: numbers.

text: [In

text: other

text: words,

text: S

text: counts

text: the

text: weighteαd

text: nAuωmαbeαr

text: of

text: the

text: giαven

text: sets

text: Q{α}

text: that

text: are

text: contained

text: in

text: the

text: random

text: set

text: i

text: Q

text: J

text: with

text: independently

text: appearing

text: elements.]

text: We

text: assume,

text: for

text: the

text: sake

text: i

text: of

text: simplicity,

text: that

text: the

text: index

text: set

text: A

text: is

text: ﬁnite,

text: but

text: it

text: is

text: easy

text: to

text: see

text: that

text: the

text: results

text: extend

text: to

text: inﬁnite

text: sums,

text: provided

text: E[S]

text: Write

text: α

text: β

text: if

text: Q(α)

text: Q(β)

text: but

text: α

text: β,

text: and

text: deﬁne

text: p

text: E

text: α

text: α

text: λ

text: E

text: [S]

text: p

text: ω

text: α

text: α

text: p

text: α

text: λ

text: ω2

text: α

text: α

text: δ

text: E

text: λ

text: ωαωβ

text: α

text: β

text: α

text: β

text: α

text: Theorem

text: With

text: notation

text: above

text: and

text: then

text: λ

text: P(S

text: exp

text: δ

text: δ

text: We

text: want

text: to

text: use

text: the

text: Chernoﬀ

text: bound,

text: but

text: ﬁrst

text: we

text: need

text: an

text: upper

text: bound

text: for

text: the

text: moment-generating

text: function.

text: So

text: the

text: proof

text: of

text: Theorem

text: follows

text: our

text: next

text: lemma.

text: Lemma

text: Using

text: the

text: in

text: Theorem

text: and

text: for

text: t

text: we

text: have

text: λ

text: e

text: exp

text: e

text: δ

text: δ

text: Proof.

text: Let

text: ψ(t)

text: E

text: e−tS

text: for

text: −dψ(t)

text: E

text: Se

text: tS

text: E

text: e

text: tS

text: dt

text: ω

text: α

text: α

text: α

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: TREES IN RANDOM SPARSE GRAPHS WITH A GIVEN DEGREE SEQUENCE 48 (cid:80) (cid:48) We split S into two parts; the part that is dependent on 1 : S = 1 1 + ∼ 1 1 , and S(cid:48) =(cid:2)S − S(cid:48) ,(cid:3)which is(cid:104)independe(cid:12)(cid:12)nt of 1 (cid:105). Thuαs, α ωα α α β ωβ β α α α − − (cid:48) − (cid:48)(cid:48) E 1αe tS = pαE e tSα tSα 1α = 1 . ∈ − (cid:48) − (cid:48)(cid:48) funTcthieonesveonftth1eα(cid:2)re=ma1inﬁi(cid:3)xnegsJJi: :ii∈ Q(cid:104)Q, u(αsi)n.(cid:12)g SthinecFe K(cid:105)eGt(cid:104)Siαneaqnuda(cid:12)lietytwSαe (cid:105)gaerte decreasing i (cid:12) (cid:12) − ≥ (cid:104) − (cid:48) (cid:12) (cid:105) (cid:104) − (cid:48)(cid:48)(cid:105) E 1αe tS pαE e tSα(cid:12)1α = 1 E e tSα 1α = 1 (cid:104) − (cid:48) (cid:12) (cid:105) − (cid:48)(cid:48) = pαE e tSα(cid:12)1α = 1 E e tSα ≥ − (cid:48) (A.1) pαE e tSα 1α = 1 ψ(t). Now summing over α and u(cid:88)sing Jens(cid:2)en’s ine(cid:3)qual(cid:88)ity twice(cid:104)we hav(cid:12)e (cid:105) (cid:12) −d logd(ψt (t)) = (cid:88)ψ1(t) ω1(cid:2)E 1α(cid:2)e−t(cid:12)(cid:12)S ≥ (cid:3)(cid:3)ωpα E e−tSα(cid:48) 1α = 1 α α α α ≥ p − (cid:48) (cid:88)α exp tE(cid:2) S (cid:2)1 (cid:12)= 1 (cid:3)(cid:3) ω α α(cid:12) α α (cid:34)1 p (cid:32) − (cid:48) (cid:33)(cid:35) = λ λ ωαα e(cid:88)xp tE S(cid:2)α 1α(cid:12)(cid:12) = 1 (cid:3) α ≥ (cid:34)− (cid:32) 1 p (cid:48) (cid:33)(cid:35) λ exp t (cid:88)λ ωα E Sα 1α = 1 α α − t  1 (cid:48)  = λ exp E [S 1 ] λ (cid:88)ω (cid:2) α (cid:3)α (cid:88)   α α  − t 1 1 = λ exp E 12 + E [1 1 ] λ α ωα2 α α∼β ωαωβ α β − (A.2) = λ exp [ t(δ + δ )] . 1 2 Therefore, (ψ(0) = 1) ˆ − ≥ t − λ − − log(ψ(t)) λe t(δ1+δ2) = (1 e (δ1+δ2)t). δ + δ 0 1 2 (cid:3) Proof of Theorem A.1. Now we are ready to(cid:20) use Chernoﬀ’s bound, (cid:21) (cid:2) (cid:3) ≤ − ≤ − − ≤ − − λ − − P(S (1 (cid:15))λ) et(1 (cid:15))λE e tS exp t(1 (cid:15))λ (1 e (δ1+δ2)t) . δ + δ 1 2 − − − Optimizing over t, we get t = (δ + δ ) 1 log(1 (cid:15)). Thus, 1 2 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##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: We

text: split

text: S

text: into

text: two

text: parts;

text: the

text: part

text: that

text: is

text: dependent

text: on

text: S

text: and

text: of

text: Thuαs,

text: α

text: ωα

text: α

text: α

text: β

text: ωβ

text: β

text: α

text: α

text: α

text: E

text: tS

text: pαE

text: e

text: tSα

text: tSα

text: 1α

text: :ii∈

text: SthinecFe

text: decreasing

text: i

text: E

text: tS

text: pαE

text: e

text: E

text: e

text: tSα

text: 1α

text: pαE

text: e

text: E

text: e

text: tSα

text: pαE

text: e

text: tSα

text: 1α

text: ψ(t).

text: Now

text: summing

text: over

text: α

text: and

text: −d

text: logd(ψt

text: (t))

text: E

text: 1α

text: α

text: α

text: α

text: α

text: p

text: exp

text: S

text: ω

text: α

text: α

text: α

text: p

text: λ

text: λ

text: ωαα

text: tE

text: α

text: p

text: λ

text: exp

text: t

text: ωα

text: E

text: Sα

text: 1α

text: α

text: α

text: t

text: λ

text: exp

text: E

text: [S

text: λ

text: α

text: α

text: α

text: t

text: λ

text: exp

text: E

text: E

text: λ

text: α

text: ωα2

text: α

text: α∼β

text: ωαωβ

text: α

text: β

text: λ

text: exp

text: t(δ

text: δ

text: Therefore,

text: ˆ

text: t

text: λ

text: log(ψ(t))

text: λe

text: e

text: δ

text: δ

text: Proof

text: of

text: Theorem

text: Now

text: we

text: are

text: ready

text: use

text: Chernoﬀ’s

text: bound,

text: λ

text: P(S

text: e

text: tS

text: exp

text: e

text: δ

text: δ

text: Optimizing

text: over

text: t,

text: we

text: get

text: t

text: (δ

text: δ

text: Thus,

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: ##LTLine##

text: ##LTLine##


text: TREES IN RANDOM SPARSE GRAPHS WITH A GIVEN DEGREE SEQUENCE 10 This proves the upper bound that is the easy part of the Conjecture 2.18. How- ever, the lower bound that is crucial for our next Conjecture is open. Conjecture 2.19. Suppose that the vector D is a strict graphic sequence of type ε. Let G p (s, T) = E [1 (T, (D))] , g s g where 1 (T, G) is deﬁned in Eq. 2(cid:88).10. Deﬁne, s (cid:101) 1 1 | − | (2.17) L (k, D) := p (s, T) p (s, T) , g M ∈S ×T ψ (s, T, D) g (cid:101) (s,T) k k n where Tk, Sk and ψ (s, T, D) are deﬁned in Section ??, and p (s, T) is as in n Deﬁnition 2.10. (cid:88) (cid:101) 1 1 | − | (2.18) L (k, D) := p (s, T) p (s, T) , g M ∈S ×T ψ (s, T, D) g (cid:101) (s,T) k k n where Tk, Sk and ψ (s, T, D) are deﬁne(cid:114)d in Section ??, and p (s, T) is as in n Deﬁnition 2.10. Then we have, ≤ · n log(n) L (k, D) c . g k M (cid:16) (cid:17) (cid:101) Remark 2.20. Conjecture 2.18 implies Conjecture 2.19, i.e. − · ≤ G ∈ G e ηn log(n) P (cid:114)(D) D . Thus, we have, ≤ · n log(n) L (k, D) c . g k M We will prove this in the Section ??. In this section, we present why Theorem 2.11 and Conjecture 2.19 are true for dense graphs. ∈ Deﬁnition 2.21. For a positive number c and numbers c , c (0, 1), we say 3 1 2 that a graph with degree sequence D satisﬁes the dense Erdös - Gallai conditions of type (c , c , c ), if 1 2 3 (1) for every i − ≤ ≤ − c (n 1) d c (n 1),  2 i 1 (2) and (cid:88) (cid:88)    1 { | |} | | | | − − ≥ inf min d , B + B ( B 1) d c . n2 B⊆{1,···,n},|B|≥c2n j∈/B j i∈B i 3 ##LTLine## ##LTLine## ##LTLine## ##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: This

text: proves

text: the

text: upper

text: bound

text: that

text: is

text: the

text: easy

text: part

text: of

text: the

text: Conjecture

text: How-

text: ever,

text: the

text: lower

text: bound

text: that

text: is

text: crucial

text: for

text: our

text: next

text: Conjecture

text: is

text: open.

text: Conjecture

text: Suppose

text: that

text: the

text: vector

text: D

text: is

text: a

text: strict

text: graphic

text: sequence

text: of

text: type

text: ε.

text: Let

text: G

text: p

text: (s,

text: T)

text: E

text: (T,

text: (D))]

text: g

text: s

text: g

text: where

text: (T,

text: G)

text: is

text: deﬁned

text: in

text: Eq.

text: Deﬁne,

text: s

text: L

text: (k,

text: D)

text: p

text: (s,

text: T)

text: p

text: (s,

text: T)

text: g

text: M

text: ∈S

text: ×T

text: ψ

text: (s,

text: T,

text: D)

text: g

text: (s,T)

text: k

text: k

text: n

text: where

text: Tk,

text: Sk

text: and

text: ψ

text: (s,

text: T,

text: D)

text: are

text: deﬁned

text: in

text: Section

text: and

text: p

text: (s,

text: T)

text: is

text: as

text: in

text: n

text: Deﬁnition

text: L

text: (k,

text: D)

text: p

text: (s,

text: T)

text: p

text: (s,

text: T)

text: g

text: M

text: ∈S

text: ×T

text: ψ

text: (s,

text: T,

text: D)

text: g

text: (s,T)

text: k

text: k

text: n

text: where

text: Tk,

text: Sk

text: and

text: ψ

text: (s,

text: T,

text: D)

text: are

text: in

text: Section

text: and

text: p

text: (s,

text: T)

text: is

text: as

text: in

text: n

text: Deﬁnition

text: Then

text: we

text: have,

text: n

text: log(n)

text: L

text: (k,

text: D)

text: c

text: g

text: k

text: M

text: Remark

text: Conjecture

text: implies

text: Conjecture

text: i.e.

text: G

text: G

text: e

text: ηn

text: log(n)

text: P

text: D

text: Thus,

text: we

text: have,

text: n

text: log(n)

text: L

text: (k,

text: D)

text: c

text: g

text: k

text: M

text: We

text: will

text: prove

text: this

text: in

text: the

text: Section

text: In

text: this

text: section,

text: we

text: present

text: why

text: Theorem

text: and

text: Conjecture

text: are

text: true

text: for

text: dense

text: graphs.

text: Deﬁnition

text: For

text: a

text: positive

text: number

text: c

text: and

text: numbers

text: c

text: c

text: we

text: say

text: that

text: a

text: graph

text: with

text: degree

text: sequence

text: D

text: satisﬁes

text: the

text: dense

text: Erdös

text: Gallai

text: conditions

text: of

text: type

text: (c

text: c

text: c

text: if

text: for

text: every

text: i

text: c

text: (n

text: d

text: c

text: (n

text: i

text: and

text: inf

text: min

text: d

text: B

text: B

text: B

text: d

text: c

text: j∈/B

text: j

text: i∈B

text: i

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: g g D(cid:61) 1 m (cid:61)50 GeV, Α(cid:61)0 Χ 0.1 mΧ(cid:61)8 GeV, Α(cid:61)0 m (cid:61)50 GeV, Α(cid:61)103 Χ m (cid:61)8 GeV, Α(cid:61)103 (cid:68) 0.01 Χ b ATLAS pred. p (cid:64) B 0.001 Σ 10(cid:45)4 10(cid:45)5 500 1000 1500 2000 2500 3000 3500 (cid:72) (cid:76) M GeV Z' − Figure 5. Observational limit (black dashed lines) with 1 2σ uncertainties (green-yellow band) on the (cid:48) production cross section times branching ratio of decay into leptons for a Z prime particle as reported by ATLAS collaboration. The blue and red lines represent the LUX exclusion limits for g = g and two values D of the DM mass, namely m = 8 and 50 GeV, assuming pure vectorial (solid lines), namely α = 0, and χ substantially pure axial (dashed lines), α = 103. The black dash-dotted line represent the prediction of σB for the SSM. As discussed in the text this coincides with the LUX exclusion for m = 50 GeV and pure χ vectorial couplings since for this value of the mass only a very small invisible branching ratio is allowed. (cid:48) limit on the Z mass. On the contrary, for a 50 GeV dark matter, the LUX experiment substantially disfavors the presence of an invisible branching ratio, in the case of purely vectorial couplings, such that the LUX line practically overlaps with the prediction of the dilepton production cross section for the SSM without dark matter. In all cases, the al- (cid:48) lowed parameter range, for a given Z realization and DM mass, corresponds to the region which is simultaneously below the LHC observational limit (black dashed line in the plots) and above the corresponding LUX exclusion line. It is of interest to present the above constraints in the plane σ − m , see ﬁgure (7). SI χ (cid:48) There we show again the fact that, for a given Z mass, dilepton searches put a lower (cid:48) bound on the Z coupling to dark matter (which is quantiﬁed by V for ﬁxed g ). By the χ D same token, a larger V leads to a larger SI cross section, which may be excluded by direct χ searches. This is illustrated for two diﬀerent (M (cid:48) ,g ) pairs. The features in this ﬁgure are Z D pretty clear. Obviously there is no constraint from resonant production for M (cid:48) > 2m , Z χ (cid:48) (cid:46) since in this case the Z is fully visible. The spike for m M (cid:48)/2 is due to phase-space χ Z suppression, which requires a larger value of the coupling to dark matter to be compatible with dilepton searches (the values of V quoted in the ﬁgure are for m (cid:28) M (cid:48)/2). Of χ χ Z (cid:48) course there are no constraints from dileptons if the Z is too heavy to be produced at the (cid:48) LHC (e.g. for M (cid:48) > 2.8 TeV for g = g), but a lighter Z is a priori possible provided Z ∼ D it has a larger coupling to an invisible sector. However this coupling cannot be arbitrarily – 10 – ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: g

font: default

text: g

text: m

text: GeV,

text: Χ

text: GeV,

text: m

text: GeV,

text: Χ

text: m

text: GeV,

text: Χ

text: b

text: ATLAS

text: pred.

text: p

text: B

text: Σ

text: M

text: GeV

text: Z'

text: Figure

text: Observational

text: limit

text: (black

text: dashed

text: lines)

text: with

text: 2σ

text: uncertainties

text: (green-yellow

text: band)

text: on

text: the

text: production

text: cross

text: section

text: times

text: branching

text: ratio

text: of

text: decay

text: into

text: leptons

text: for

text: a

text: Z

text: prime

text: particle

text: as

text: reported

text: by

text: ATLAS

text: collaboration.

text: The

text: blue

text: and

text: red

text: lines

text: represent

text: the

text: LUX

text: exclusion

text: limits

text: for

text: g

text: g

text: and

text: two

text: values

text: D

text: of

text: the

text: DM

text: mass,

text: namely

text: m

text: and

text: GeV,

text: assuming

text: pure

text: vectorial

text: (solid

text: lines),

text: namely

text: α

text: and

text: χ

text: substantially

text: pure

text: axial

text: (dashed

text: lines),

text: α

text: The

text: black

text: dash-dotted

text: line

text: represent

text: the

text: prediction

text: of

text: σB

text: for

text: the

text: SSM.

text: As

text: discussed

text: in

text: the

text: text

text: this

text: coincides

text: with

text: the

text: LUX

text: exclusion

text: for

text: m

text: GeV

text: and

text: pure

text: χ

text: vectorial

text: couplings

text: since

text: for

text: this

text: value

text: of

text: the

text: mass

text: only

text: a

text: very

text: small

text: invisible

text: branching

text: ratio

text: is

text: allowed.

text: limit

text: on

text: the

text: Z

text: mass.

text: On

text: the

text: contrary,

text: for

text: a

text: GeV

text: dark

text: matter,

text: the

text: LUX

text: experiment

text: substantially

text: disfavors

text: the

text: presence

text: of

text: an

text: invisible

text: branching

text: ratio,

text: in

text: the

text: case

text: of

text: purely

text: vectorial

text: couplings,

text: such

text: that

text: the

text: LUX

text: line

text: practically

text: overlaps

text: with

text: the

text: prediction

text: of

text: the

text: dilepton

text: production

text: cross

text: section

text: for

text: the

text: SSM

text: without

text: dark

text: matter.

text: In

text: all

text: cases,

text: the

text: al-

text: lowed

text: parameter

text: range,

text: for

text: a

text: given

text: Z

text: realization

text: and

text: DM

text: mass,

text: corresponds

text: to

text: the

text: region

text: which

text: is

text: simultaneously

text: below

text: the

text: LHC

text: observational

text: limit

text: (black

text: dashed

text: line

text: in

text: the

text: plots)

text: and

text: above

text: the

text: corresponding

text: LUX

text: exclusion

text: line.

text: It

text: is

text: of

text: interest

text: to

text: present

text: the

text: above

text: constraints

text: in

text: the

text: plane

text: σ

text: m

text: see

text: ﬁgure

text: SI

text: χ

text: There

text: we

text: show

text: again

text: the

text: fact

text: that,

text: for

text: a

text: given

text: Z

text: mass,

text: dilepton

text: searches

text: put

text: a

text: lower

text: bound

text: on

text: the

text: Z

text: coupling

text: to

text: dark

text: matter

text: (which

text: is

text: quantiﬁed

text: by

text: V

text: for

text: ﬁxed

text: g

text: By

text: the

text: χ

text: D

text: same

text: token,

text: a

text: larger

text: V

text: leads

text: to

text: a

text: larger

text: SI

text: cross

text: section,

text: which

text: may

text: be

text: excluded

text: by

text: direct

text: χ

text: searches.

text: This

text: is

text: illustrated

text: for

text: two

text: diﬀerent

text: (M

text: ,g

text: pairs.

text: The

text: features

text: in

text: this

text: ﬁgure

text: are

text: Z

text: D

text: pretty

text: clear.

text: Obviously

text: there

text: is

text: no

text: constraint

text: from

text: resonant

text: production

text: for

text: M

text: Z

text: χ

text: since

text: in

text: this

text: case

text: the

text: Z

text: is

text: fully

text: visible.

text: The

text: spike

text: for

text: m

text: M

text: is

text: due

text: to

text: phase-space

text: χ

text: Z

text: suppression,

text: which

text: requires

text: a

text: larger

text: value

text: of

text: the

text: coupling

text: to

text: dark

text: matter

text: to

text: be

text: compatible

text: with

text: dilepton

text: searches

text: (the

text: values

text: of

text: V

text: quoted

text: in

text: the

text: ﬁgure

text: are

text: for

text: m

text: M

text: Of

text: χ

text: χ

text: Z

text: course

text: there

text: are

text: no

text: constraints

text: from

text: dileptons

text: if

text: the

text: Z

text: is

text: too

text: heavy

text: to

text: be

text: produced

text: at

text: the

text: LHC

text: (e.g.

text: for

text: M

text: TeV

text: for

text: g

text: g),

text: but

text: a

text: lighter

text: Z

text: is

text: a

text: priori

text: possible

text: provided

text: Z

text: D

text: it

text: has

text: a

text: larger

text: coupling

text: to

text: an

text: invisible

text: sector.

text: However

text: this

text: coupling

text: cannot

text: be

text: arbitrarily

text: ##LTFigure##

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: ##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: ##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: ##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: ##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: ##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: ##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: ##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: ##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: ##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: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: g 0.3 D(cid:61) 1 m (cid:61)50 GeV, Α(cid:61)0 Χ 0.1 mΧ(cid:61)8 GeV, Α(cid:61)0 m (cid:61)50 GeV, Α(cid:61)103 Χ m (cid:61)8 GeV, Α(cid:61)103 (cid:68) 0.01 Χ b p (cid:64) B 0.001 Σ 10(cid:45)4 10(cid:45)5 500 1000 1500 2000 2500 3000 3500 (cid:72) (cid:76) M GeV Z' Figure 6. The same as Fig. (5) for g = 0.3. D 10 37  10 39  10 41 g 0.3 M 500GeV, V 2 7.8 2  D  Χ  m c  10 43 p  Χ Σ 10 45 gDg M2.75TeV, VΧ20.09  10 47  1 10 100 1000   m GeV Χ − Figure 7. Constraints from dilepton searches shown in the plane σ m together with the LUX SI χ exclusion limits. See text for details. (cid:46) (cid:48) large. Imposing g2 V 2 4π gives a lower bound on the Z mass, which we will refer to as D D a unitarity bound in the sequel. Combining all our preceding results, we give in the ﬁgure (8) the parameter space allowed when combining ATLAS and LUX limits in the plane (m , M (cid:48)) and in the case of χ Z the SSM. All the points below the lines are excluded by our analysis. We see that a large region does not survive the constraints, as expected from the discussion above. For instance – 11 – ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: g

text: m

text: GeV,

text: Χ

text: GeV,

text: m

text: GeV,

text: Χ

text: m

text: GeV,

text: Χ

text: b

text: p

text: B

text: Σ

text: M

text: GeV

text: Z'

text: Figure

text: The

text: same

text: as

text: Fig.

text: for

text: g

text: D

text: g

text: M

text: V

text: D

text: Χ

text: m

text: c

text: p

text: Χ

text: Σ

text: gDg

text: m

text: GeV

text: Χ

text: Figure

text: Constraints

text: from

text: dilepton

text: searches

text: shown

text: in

text: the

text: plane

text: σ

text: m

text: together

text: with

text: the

text: LUX

text: SI

text: χ

text: exclusion

text: limits.

text: See

text: text

text: for

text: details.

text: large.

text: Imposing

text: V

text: 4π

text: gives

text: a

text: lower

text: bound

text: on

text: the

text: Z

text: mass,

text: which

text: we

text: will

text: refer

text: to

text: as

text: D

text: D

text: a

text: unitarity

text: bound

text: in

text: the

text: sequel.

text: Combining

text: all

text: our

text: preceding

text: results,

text: we

text: give

text: in

text: the

text: ﬁgure

text: the

text: parameter

text: space

text: allowed

text: when

text: combining

text: ATLAS

text: and

text: LUX

text: limits

text: in

text: the

text: plane

text: (m

text: M

text: and

text: in

text: the

text: case

text: of

text: χ

text: Z

text: the

text: SSM.

text: All

text: the

text: points

text: below

text: the

text: lines

text: are

text: excluded

text: by

text: our

text: analysis.

text: We

text: see

text: that

text: a

text: large

text: region

text: does

text: not

text: survive

text: the

text: constraints,

text: as

text: expected

text: from

text: the

text: discussion

text: above.

text: For

text: instance

text: ##LTFigure##

text: ##LTFigure##

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: ##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: ##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: ##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: ##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: ##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: ##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: ##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: ##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: ##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: ##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: ##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: ##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: ##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: ##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: ##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: ##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: ##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: ##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: ##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: ##LTLine##

text: ##LTLine##


text: (cid:48) invisible Z in some speciﬁc frameworks can be found in [18] whereas some direct detection analysis can be found in [19]. The paper is organized as follows. After a summary of the model under consideration and its eﬀective low energy limit, we establish in section II the relation between the invisible (cid:48) branching ratio of a Z and the direct detection cross sections (spin-dependent and spin- independent). We combine the exclusion limits set by the direct detection experiments with (cid:48) the LHC bounds on Z mass and couplings in section III. Some prospects are discussed in the last section. (cid:48) 2 Invisible Z decay rates and direct detection cross sections 2.1 The model (cid:48) While the existence of extra U(1) gauge symmetries may be motivated in various ways [1], we will try to be as generic as possible in the present work. To do so, we parametrize (cid:48) as follows the couplings of a Z gauge bosons to the SM quarks and leptons on one hand and to a dark matter particle χ on the other hand, which we take to be fermionic for (cid:0) (cid:1) concreteness1, (cid:88) (cid:16) (cid:17) (cid:48) ∆L ⊃ g χ¯γµ V χ − Aχ γ5 χ Z D D D µ (cid:48) + g f¯γµ V f − Af γ5 f Z . (2.1) D D D µ f f χ f χ Here V and V (A and A ) are the vectorial (axial) couplings for the SM fermions f and D D D D χ DM particle χ respectively (V = 0 if χ is a Majorana particle) and we have introduced D an overall gauge coupling g . Since the gauge coupling g , as well as V f,χ and Af,χ are a D D D (cid:48) priori free parameters, our formalism can then describe all the possible Z realisations in f f terms of this ﬁve quantities. It is anyway possible to ﬁx the combinations g V and g A (cid:48) D D D D by specifying the Z model (e.g. SSM, E , B-L,...) as it is shown in table I. The partial 6 (cid:48) widths of the Z can be straightforwardly determined as function of these four fundamental (cid:115) parameters as: (cid:20)g2 c (cid:18) 4m2(cid:19) (cid:18) (cid:19)(cid:21) Γi (cid:48) = D i M (cid:48) 1 − i (2.2) Z 12π Z M2(cid:48) Z m2 m2 × (V i )2 1 + 2 i + (Ai )2 1 − 4 i D M2(cid:48) D M2(cid:48) Z Z where i = f or χ, c is the number of color of the SM fermion f and c = 1. f χ From the microscopic Lagrangian (2.1), we can deduce the eﬀective low energy inter- action of the dark matter to a nucleon. The XENON [14] or LUX [15] experiments are supposed to observe dark matter collisions on nuclei, which are translated as couplings to nucleons. These processes occur at velocities of the order of magnitude of that of the Sun 1Our results are similar for a scalar dark matter candidate and will be reported in a future work. – 2 – ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: invisible

text: Z

text: in

text: some

text: speciﬁc

text: frameworks

text: can

text: be

text: found

text: in

text: whereas

text: some

text: direct

text: detection

text: analysis

text: can

text: be

text: found

text: in

text: The

text: paper

text: is

text: organized

text: as

text: follows.

text: After

text: a

text: summary

text: of

text: the

text: model

text: under

text: consideration

text: and

text: its

text: eﬀective

text: low

text: energy

text: limit,

text: we

text: establish

text: in

text: section

text: II

text: the

text: relation

text: between

text: the

text: invisible

text: branching

text: ratio

text: of

text: a

text: Z

text: and

text: the

text: direct

text: detection

text: cross

text: sections

text: (spin-dependent

text: and

text: spin-

text: independent).

text: We

text: combine

text: the

text: exclusion

text: limits

text: set

text: by

text: the

text: direct

text: detection

text: experiments

text: with

text: the

text: LHC

text: bounds

text: on

text: Z

text: mass

text: and

text: couplings

text: in

text: section

text: III.

text: Some

text: prospects

text: are

text: discussed

text: in

text: the

text: last

text: section.

text: Invisible

text: Z

text: decay

text: rates

text: and

text: direct

text: detection

text: cross

text: sections

text: The

text: model

text: While

text: the

text: existence

text: of

text: extra

text: gauge

text: symmetries

text: may

text: be

text: motivated

text: in

text: various

text: ways

text: we

text: will

text: try

text: to

text: be

text: as

text: generic

text: as

text: possible

text: in

text: the

text: present

text: work.

text: To

text: do

text: so,

text: we

text: parametrize

text: as

text: follows

text: the

text: couplings

text: of

text: a

text: Z

text: gauge

text: bosons

text: to

text: the

text: SM

text: quarks

text: and

text: leptons

text: on

text: one

text: hand

text: and

text: to

text: a

text: dark

text: matter

text: particle

text: χ

text: on

text: the

text: other

text: hand,

text: which

text: we

text: take

text: to

text: be

text: fermionic

text: for

text: ∆L

text: g

text: χ¯γµ

text: V

text: χ

text: Aχ

text: γ5

text: χ

text: Z

text: D

text: D

text: D

text: µ

text: g

text: f¯γµ

text: V

text: f

text: Af

text: γ5

text: f

text: Z

text: D

text: D

text: D

text: µ

text: f

text: f

text: χ

text: f

text: χ

text: Here

text: V

text: and

text: V

text: (A

text: and

text: A

text: are

text: the

text: vectorial

text: (axial)

text: couplings

text: for

text: the

text: SM

text: fermions

text: f

text: and

text: D

text: D

text: D

text: D

text: χ

text: DM

text: particle

text: χ

text: respectively

text: (V

text: if

text: χ

text: is

text: a

text: Majorana

text: particle)

text: and

text: we

text: have

text: introduced

text: D

text: an

text: overall

text: gauge

text: coupling

text: g

text: Since

text: the

text: gauge

text: coupling

text: g

text: as

text: well

text: as

text: V

text: f,χ

text: and

text: Af,χ

text: are

text: a

text: D

text: D

text: D

text: priori

text: free

text: parameters,

text: our

text: formalism

text: can

text: then

text: describe

text: all

text: the

text: possible

text: Z

text: realisations

text: in

text: f

text: f

text: terms

text: of

text: this

text: ﬁve

text: quantities.

text: It

text: is

text: anyway

text: possible

text: to

text: ﬁx

text: the

text: combinations

text: g

text: V

text: and

text: g

text: A

text: D

text: D

text: D

text: D

text: by

text: specifying

text: the

text: Z

text: model

text: (e.g.

text: SSM,

text: E

text: B-L,...)

text: as

text: it

text: is

text: shown

text: in

text: table

text: I.

text: The

text: partial

text: widths

text: of

text: the

text: Z

text: can

text: be

text: straightforwardly

text: determined

text: as

text: function

text: of

text: these

text: four

text: fundamental

text: parameters

text: as:

text: c

text: Γi

text: D

text: i

text: M

text: i

text: Z

text: Z

text: Z

text: (V

text: i

text: i

text: (Ai

text: i

text: D

text: D

text: Z

text: Z

text: where

text: i

text: f

text: or

text: χ,

text: c

text: is

text: the

text: number

text: of

text: color

text: of

text: the

text: SM

text: fermion

text: f

text: and

text: c

text: f

text: χ

text: From

text: the

text: microscopic

text: Lagrangian

text: we

text: can

text: deduce

text: the

text: eﬀective

text: low

text: energy

text: inter-

text: action

text: of

text: the

text: dark

text: matter

text: to

text: a

text: nucleon.

text: The

text: XENON

text: or

text: LUX

text: experiments

text: are

text: supposed

text: to

text: observe

text: dark

text: matter

text: collisions

text: on

text: nuclei,

text: which

text: are

text: translated

text: as

text: couplings

text: to

text: nucleons.

text: These

text: processes

text: occur

text: at

text: velocities

text: of

text: the

text: order

text: of

text: magnitude

text: of

text: that

text: of

text: the

text: Sun

text: results

text: are

text: similar

text: for

text: a

text: scalar

text: dark

text: matter

text: candidate

text: and

text: will

text: be

text: reported

text: in

text: a

text: future

text: work.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: χ χ f g (V χ − Aχ γ5) D D D Z’ g (V f − Af γ5) Z’ D D D g (V q − Aq γ5) D D D f Γ f q q σ χq (cid:48) Figure 1. Feynman diagrams contributing to the width of the Z boson and the scattering cross section of the dark matter on a nucleon. in the galactic halo, i.e. (cid:39) 300 km/s so that the energy transferred in such collisions is (cid:48) below the MeV scale for typical dark matter masses. We can thus integrate out the Z from the Lagrangian (2.1) to get the eﬀective Lagrangian describing interactions between (cid:104) a χ and, say, a proton p, g2 (cid:105) L ⊃ D V χ(2V u + V d) χ¯γµχ p¯γ p (2.3) eﬀ M2(cid:48) D D D µ Z + Aχ (∆pAu + (∆p + ∆p)Ad )χ¯γµγ5χ p¯γ γ5p , D u D d s D µ p with a similar expression for the neutron. Here ∆ is the spin content of the quark i in the i proton, which may be extracted from lepton-proton scattering data. The values we use are taken from the latest determination of the light quark contributions [20], i.e. ∆p = 0.842, ∆p = −0.427, ∆p = −0.085. (2.4) u d s From Eq.(2.3), we can deduce the Lagrangian describing the interaction of DM with a neutron by isospin symmetry2: 2V u + V d → V u + 2V d and ∆n = ∆p, ∆n = ∆p, D D D D u d d u ∆n = ∆p. As already discussed above, the combinations g V f and g Af are ﬁxed in s s D D D D a given fundamental theory. For illustration, we report in Table I their values in some (cid:48) popular realizations of Z models, while a more exhaustive list can be found e.g. in [2]. For the sake of concreteness, we will mainly in this paper refer to the so-called sequen- (cid:48) tial model (noted SSM in the sequel) [1], for which the Z has the same couplings to SM fermions as the SM Z boson. A possible realization of the SSM appears in constructions with extra dimensions at the weak scale, but in the present work we merely take it as a (cid:48) benchmark model. Other realizations like (B-L) or E Z do not change drastically our 6 (cid:48) (cid:48) conclusion. Having set the Z model, the two parameters left free are the χ − Z couplings, χ χ χ namely V and A . We will show in the next section that V is severely constrained by D D D 2Another description of this formalism can be found in [21]. – 3 – ##LTFigure## ##LTLine## ##LTLine##

text: χ

text: χ

text: f

text: g

text: (V

text: χ

text: Aχ

text: D

text: D

text: D

text: Z’

text: g

text: (V

text: f

text: Af

text: Z’

text: D

text: D

text: D

text: g

text: (V

text: q

text: Aq

text: D

text: D

text: D

text: f

text: Γ

text: f

text: q

text: q

text: σ

text: χq

text: Figure

text: Feynman

text: diagrams

text: contributing

text: to

text: the

text: width

text: of

text: the

text: Z

text: boson

text: and

text: the

text: scattering

text: cross

text: section

text: of

text: the

text: dark

text: matter

text: on

text: a

text: nucleon.

text: in

text: the

text: galactic

text: halo,

text: i.e.

text: km/s

text: so

text: that

text: the

text: energy

text: transferred

text: in

text: such

text: collisions

text: is

text: below

text: the

text: MeV

text: scale

text: for

text: typical

text: dark

text: matter

text: masses.

text: We

text: can

text: thus

text: integrate

text: out

text: the

text: Z

text: from

text: the

text: Lagrangian

text: to

text: get

text: the

text: eﬀective

text: Lagrangian

text: describing

text: interactions

text: between

text: a

text: χ

text: and,

text: say,

text: a

text: proton

text: p,

text: L

text: D

text: V

text: u

text: V

text: d)

text: χ¯γµχ

text: p¯γ

text: p

text: eﬀ

text: D

text: D

text: D

text: µ

text: Z

text: Aχ

text: (∆pAu

text: (∆p

text: ∆p)Ad

text: )χ¯γµγ5χ

text: p¯γ

text: D

text: u

text: D

text: d

text: s

text: D

text: µ

text: p

text: with

text: a

text: similar

text: expression

text: for

text: the

text: neutron.

text: Here

text: is

text: the

text: spin

text: content

text: of

text: the

text: quark

text: i

text: in

text: the

text: i

text: proton,

text: which

text: may

text: be

text: extracted

text: from

text: lepton-proton

text: scattering

text: data.

text: The

text: values

text: we

text: use

text: are

text: taken

text: from

text: the

text: latest

text: determination

text: of

text: the

text: light

text: quark

text: contributions

text: i.e.

text: ∆p

text: ∆p

text: ∆p

text: u

text: d

text: s

text: From

text: we

text: can

text: deduce

text: the

text: Lagrangian

text: describing

text: the

text: interaction

text: of

text: DM

text: with

text: a

text: neutron

text: by

text: isospin

text: u

text: V

text: d

text: V

text: u

text: d

text: and

text: ∆n

text: ∆p,

text: ∆n

text: ∆p,

text: D

text: D

text: D

text: D

text: u

text: d

text: d

text: u

text: ∆n

text: ∆p.

text: As

text: already

text: discussed

text: above,

text: the

text: combinations

text: g

text: V

text: f

text: and

text: g

text: Af

text: are

text: ﬁxed

text: in

text: s

text: s

text: D

text: D

text: D

text: D

text: a

text: given

text: fundamental

text: theory.

text: For

text: illustration,

text: we

text: report

text: in

text: Table

text: I

text: their

text: values

text: in

text: some

text: popular

text: realizations

text: of

text: Z

text: models,

text: while

text: a

text: more

text: exhaustive

text: list

text: can

text: be

text: found

text: e.g.

text: in

text: For

text: the

text: sake

text: of

text: concreteness,

text: we

text: will

text: mainly

text: in

text: this

text: paper

text: refer

text: to

text: the

text: so-called

text: sequen-

text: tial

text: model

text: (noted

text: SSM

text: in

text: the

text: sequel)

text: for

text: which

text: the

text: Z

text: has

text: the

text: same

text: couplings

text: to

text: SM

text: fermions

text: as

text: the

text: SM

text: Z

text: boson.

text: A

text: possible

text: realization

text: of

text: the

text: SSM

text: appears

text: in

text: constructions

text: with

text: extra

text: dimensions

text: at

text: the

text: weak

text: scale,

text: but

text: in

text: the

text: present

text: work

text: we

text: merely

text: take

text: it

text: as

text: a

text: benchmark

text: model.

text: Other

text: realizations

text: like

text: (B-L)

text: or

text: E

text: Z

text: do

text: not

text: change

text: drastically

text: our

text: conclusion.

text: Having

text: set

text: the

text: Z

text: model,

text: the

text: two

text: parameters

text: left

text: free

text: are

text: the

text: χ

text: Z

text: couplings,

text: χ

text: χ

text: χ

text: namely

text: V

text: and

text: A

text: We

text: will

text: show

text: in

text: the

text: next

text: section

text: that

text: V

text: is

text: severely

text: constrained

text: by

text: D

text: D

text: D

text: description

text: of

text: this

text: formalism

text: can

text: be

text: found

text: in

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##