text: (cid:80) EQUIVARIANT LATTICE GENERATORS AND MARKOV BASES 5 ∈ Z ∩ with n . Every element in im(φ) ker(ψ) must satisfy n = 0 since im(A ) is i (cid:20) (cid:21) i i φ generated by matrices whose two non-zero entries have the same sign. The permutations of − · · · b b 0 w := − · · · a a 0 ∩ form an equivariant lattice generating set for such elements. Consequently im(φ) ker(ψ) is contained in the lattice generated up to symmetry by w. Now − − − − − φ(yb ya b yb ya b) = za b(zb za zb za ) 21 31 12 32 13 12 21 11 22 − − − which has lattice element w, so yb ya b yb ya b is the pullback of the generator of ∩ 21 31 12 32 (cid:3) im(φ) ker(ψ). Remark 2.2. A generating set in K[Y ] for the kernel of a map of width two requires − the 3-cycle cubic y y y y y y (see Proposition 4.1). However in the Laurent ± 12 23 31 21 32 13 − ring K[Y ], this binomial is redundant modulo the basic quadric y y y y . The 12 34 14 32 3-cycle cubic’s exponent is    −   0 1 1  − · · · 1 0 1 − c = , 1 1 0 ... ...       which can be expressed in terms of basic quadrics as          −   −   0 0 0 0  0 1 0 1  0 0 1 1  − · · · · · · − · · · 1 0 0 1 0 0 0 0 0 0 1 1 − − c = + + . 1 0 0 1 0 1 0 1 0 0 0 0 . . . . . . . . . We now generalize Proposition 2.1 to arbitrary k. When necessary, we write φ(k) (cid:76) instead of φ to emphasize the width of the image monomial but usually the level of generality is clear from the context and we avoid overloading the notation too much. Z Elements of Nk should be thought of as(cid:76)k-dimensional tables of inﬁnite size with integer entries. Our setup additionally requires that these tables be zero along their (cid:54) diagonals (deﬁned as entries indexed by (i , . . . , i ) with any i = i for j = l). Let 1 Zk j l ei1...ik denote the standard basis elements of Nk . Then Y consists of indeterminates yi1...ik = yei1...ik . The factorization (1.2) gives a map φ(k) as follows: ± → ± · · · φ(k) : K[Y ] K[Z ], φ(k)(y ) = z z z . i1...ik 1i1 2i2 kik Remark 2.3. In algebraic statistics, the independence model on k factors is (the (cid:55)→ · · · non-negative real part of) the image of the monomial map y z z z ∈ i1...ik 1i1 2i2 kik where i [l ] for some integers l [DSS09]. In algebraic geometry, this map represents j j j

text: EQUIVARIANT

text: LATTICE

text: GENERATORS

text: AND

text: MARKOV

text: BASES

text: Z

text: with

text: n

text: Every

text: element

text: in

text: im(φ)

text: ker(ψ)

text: must

text: satisfy

text: n

text: since

text: im(A

text: is

text: i

text: i

text: i

text: φ

text: generated

text: by

text: matrices

text: whose

text: two

text: non-zero

text: entries

text: have

text: the

text: same

text: sign.

text: The

text: permutations

text: of

text: b

text: b

text: w

text: a

text: a

text: form

text: an

text: equivariant

text: lattice

text: generating

text: set

text: for

text: such

text: elements.

text: Consequently

text: im(φ)

text: ker(ψ)

text: is

text: contained

text: in

text: the

text: lattice

text: generated

text: up

text: to

text: symmetry

text: by

text: w.

text: Now

text: φ(yb

text: ya

text: b

text: yb

text: ya

text: b)

text: za

text: b(zb

text: za

text: zb

text: za

text: which

text: has

text: lattice

text: element

text: w,

text: so

text: yb

text: ya

text: b

text: yb

text: ya

text: b

text: is

text: the

text: pullback

text: of

text: the

text: generator

text: of

text: im(φ)

text: ker(ψ).

text: Remark

text: A

text: generating

text: set

text: in

text: K[Y

text: for

text: the

text: kernel

text: of

text: a

text: map

text: of

text: width

text: two

text: requires

text: the

text: cubic

text: y

text: y

text: y

text: y

text: y

text: y

text: (see

text: Proposition

text: However

text: in

text: the

text: Laurent

text: ring

text: K[Y

text: this

text: binomial

text: is

text: redundant

text: modulo

text: the

text: basic

text: quadric

text: y

text: y

text: y

text: y

text: The

text: cubic’s

text: exponent

text: is

text: c

text: which

text: can

text: be

text: expressed

text: in

text: terms

text: of

text: basic

text: quadrics

text: as

text: 0

text: 0

text: c

text: We

text: now

text: generalize

text: Proposition

text: to

text: arbitrary

text: k.

text: When

text: necessary,

text: we

text: write

text: φ(k)

text: instead

text: of

text: φ

text: to

text: emphasize

text: the

text: width

text: of

text: the

text: image

text: monomial

text: but

text: usually

text: the

text: level

text: of

text: generality

text: is

text: clear

text: from

text: the

text: context

text: and

text: we

text: avoid

text: overloading

text: the

text: notation

text: too

text: much.

text: Z

text: Elements

text: of

text: Nk

text: should

text: be

text: thought

text: of

text: tables

text: of

text: inﬁnite

text: size

text: with

text: integer

text: entries.

text: Our

text: setup

text: additionally

text: requires

text: that

text: these

text: tables

text: be

text: zero

text: along

text: their

text: diagonals

text: (deﬁned

text: as

text: entries

text: indexed

text: by

text: (i

text: i

text: with

text: any

text: i

text: i

text: for

text: j

text: l).

text: Let

text: Zk

text: j

text: l

text: denote

text: the

text: standard

text: basis

text: elements

text: of

text: Nk

text: Then

text: Y

text: consists

text: of

text: indeterminates

text: The

text: factorization

text: gives

text: a

text: map

text: φ(k)

text: as

text: follows:

text: φ(k)

text: K[Y

text: K[Z

text: φ(k)(y

text: z

text: z

text: z

text: kik

text: Remark

text: In

text: algebraic

text: statistics,

text: the

text: independence

text: model

text: on

text: k

text: factors

text: is

text: (the

text: non-negative

text: real

text: part

text: of)

text: the

text: image

text: of

text: the

text: monomial

text: map

text: y

text: z

text: z

text: z

text: kik

text: where

text: i

text: [l

text: for

text: some

text: integers

text: l

text: In

text: algebraic

text: geometry,

text: this

text: map

text: represents

text: j

text: j

text: j


text: TORUS MANIFOLDS AND NON-NEGATIVE CURVATURE 13 Proof. Assume that one of the cases 2a and 3a occurs at the factor Γ of F and j0 one of the cases 1a, 1b, 2a and 3a appears at another factor Γ of F. Then we ∩ j1 consider the intersection G G with j(k ) = j and j(k ) = j . It follows from the description of the combki0natorki1al type of0G g(cid:89)0iven in th1e Sub1lemmas 4.10 and k0 4.11, that there is an isomorphism of posets P → P × × (C) (Γ Γ˜ Γ ), j0 j1 (cid:54) i ∩ (cid:84) i∩=j0,j1∩ ∩ ∩ where C is a component of G G such that F G G and the G G G , k1 k0 k0 k1 k k0 k1 j(k) = j , correspond to the facets belonging to the factor Γ . Hence, it follows 0 ∩ j0 that the intersection of G G with G is non-empty (or connected) k0 k1 k; j(k)=j0 k if case 3a (or 2a, respectively) appears at the factor Γ of F. From the description of the combinatorial type of G(cid:89)j0 given in Sublemmas 4.10, k1 4.11, 4.12 and 4.13 it follows that there is an isomorphism of posets P ∩ → P × × (G G ) (Γ˜ Γ Γ ), k0 k1 j0 j1 (cid:54) i (cid:84) i=j0,j1 ∩ ∩ such that the G G G , j(k) = j , correspond to the facets belonging to the k k0 k1 0 ∩ factor Γ˜ . Hence, it follows that the intersection of G G with G j0 k0 k1 k; j(k)=j0 kj0 is empty (or non-connected) if case 3a (or 2a, respectively) appears at the factor Γ˜ of F. Therefore we have a contradiction. j0 Next assume that at one factor Γ of F the case 1a appears and at another factor j0 Γ the case 1b appears. Then it follows from the description of the combinatorial j1 ∩ type of G given in Sublemma 4.12 that the intersection G G is connected. k0 k0 k1 Here G is the facet belonging to the factor Γ and G is a facet belonging k0 j0 k1 to the factor Γ . But the description of the combinatorial type of G given in j1 k1 Sublemma 4.13 implies that this intersection is disconnected. Next assume that the case 1b occurs at two factors Γ and Γ . Let G and j0 j1 k0 G (cid:48) be the facets belonging to Γ . Moreover, let G be a facet of Q belonging k0 j0 k1 to Γ . Then it follows from the description of the combinatorial type of G given j1 ∩ ∩ k0 in Sublemma 4.13 that the intersection G G (cid:48) G is non-empty. But from k0 k0 k1 the description of the combinatorial type of G it follows that this intersection is k1 empty. Last we show that the case 1a occurs at at most one factor of F. Assume that (cid:84) (cid:84) the case 1a appears at the factors Γ with j < s and not at the factors Γ with ≥ ≥ j j j s. Then for each j s choose n facets G , . . . , G of Q belonging to j kj1 kjnj that factor. Consider a component K of ≥ nj G which meets F. Since at ≥ j s i=1 kji ∩ none of the factors Γ , j s, the cases 1a or 2a appear, the intersection F K j ∩ is connected. Therefore also the intersections G K, j(k) < s are connected by k Sublemma 4.12. By the description of the combinatorial type of the G given in Sublemma 4.12 ∩ k the intersections G K are combinatorially equivalent to cubes and have pairwise k non-connected intersection. Therefore it follows from Lemma 4.4, that K has di- mension two. Hence it follows that s is two, i.e. there is only one factor of F where the case 1a appears. Therefore there is at most one factor Γ of F where one of the cases 1a, 1b, 2a j0 (cid:3) and 3a appears. Sublemma 4.15. Assume that one of the cases 1a, 1b, 2a or 3a appears at the factor Γ of F. Let G be a facet of Q which meets F and belongs to Γ with (cid:54) j0 k1 j1 j = j . Then the following holds: 1 0 ∩ (1) The facets of G are given by the components of the intersections G G . ∩ k1 k k1 (2) G G is disconnected if and only if Γ = Σ2 and j(k) = j(k ) = j . k1 k j1 1 1

text: TORUS

label: paragraph

text: MANIFOLDS

text: AND

text: NON-NEGATIVE

text: CURVATURE

text: Proof.

text: Assume

text: that

text: one

text: of

text: the

text: cases

text: and

text: occurs

text: at

text: the

text: factor

text: Γ

text: of

text: F

text: and

text: one

text: of

text: the

text: cases

text: and

text: appears

text: at

text: another

text: factor

text: Γ

text: of

text: F.

text: Then

text: we

text: consider

text: the

text: intersection

text: G

text: G

text: with

text: j(k

text: j

text: and

text: j(k

text: j

text: It

text: follows

text: from

text: the

text: description

text: of

text: the

text: type

text: in

text: and

text: that

text: there

text: is

text: an

text: isomorphism

text: of

text: posets

text: P

text: P

text: (C)

text: (Γ

text: Γ˜

text: Γ

font: default

text: i

text: where

text: C

text: is

text: a

text: component

text: of

text: G

text: G

text: such

text: that

text: F

text: G

text: G

text: and

text: the

text: G

text: G

text: G

text: k

text: j(k)

text: j

text: correspond

text: to

text: the

text: facets

text: belonging

text: to

text: the

text: factor

text: Γ

text: Hence,

text: it

text: follows

text: that

text: the

text: intersection

text: of

text: G

text: G

text: with

text: G

text: is

text: non-empty

text: (or

text: connected)

text: k;

text: k

text: if

text: case

text: (or

text: respectively)

text: appears

text: at

text: the

text: factor

text: Γ

text: of

text: F.

text: From

text: the

text: description

text: of

text: the

text: combinatorial

text: type

text: of

text: given

text: in

text: Sublemmas

text: and

text: it

text: follows

text: that

text: there

text: is

text: an

text: isomorphism

text: of

text: posets

text: P

text: P

text: (G

text: G

text: (Γ˜

text: Γ

text: Γ

text: i

text: such

text: that

text: the

text: G

text: G

text: G

text: j(k)

text: j

text: correspond

text: to

text: the

text: facets

text: belonging

text: to

text: the

text: k

text: factor

text: Γ˜

text: Hence,

text: it

text: follows

text: that

text: the

text: intersection

text: of

text: G

text: G

text: with

text: G

text: k;

text: is

text: empty

text: (or

text: non-connected)

text: if

text: case

text: (or

text: respectively)

text: appears

text: at

text: the

text: factor

text: Γ˜

text: of

text: F.

text: Therefore

text: we

text: have

text: a

text: contradiction.

text: Next

text: assume

text: that

text: at

text: one

text: factor

text: Γ

text: of

text: F

text: the

text: case

text: appears

text: and

text: at

text: another

text: factor

text: Γ

text: the

text: case

text: appears.

text: Then

text: it

text: follows

text: from

text: the

text: description

text: of

text: the

text: combinatorial

text: type

text: of

text: G

text: given

text: in

text: Sublemma

text: that

text: the

text: intersection

text: G

text: G

text: is

text: connected.

text: Here

text: G

text: is

text: the

text: facet

text: belonging

text: to

text: the

text: factor

text: Γ

text: and

text: G

text: is

text: a

text: facet

text: belonging

text: to

text: the

text: factor

text: Γ

text: But

text: the

text: description

text: of

text: the

text: combinatorial

text: type

text: of

text: G

text: given

text: in

text: Sublemma

text: implies

text: that

text: this

text: intersection

text: is

text: disconnected.

text: Next

text: assume

text: that

text: the

text: case

text: occurs

text: at

text: two

text: factors

text: Γ

text: and

text: Γ

text: Let

text: G

text: and

text: G

text: be

text: the

text: facets

text: belonging

text: to

text: Γ

text: Moreover,

text: let

text: G

text: be

text: a

text: facet

text: of

text: Q

text: belonging

text: to

text: Γ

text: Then

text: it

text: follows

text: from

text: the

text: description

text: of

text: the

text: combinatorial

text: type

text: of

text: G

text: given

text: in

text: Sublemma

text: that

text: the

text: intersection

text: G

text: G

text: G

text: is

text: non-empty.

text: But

text: from

text: the

text: description

text: of

text: the

text: combinatorial

text: type

text: of

text: G

text: it

text: follows

text: that

text: this

text: intersection

text: is

text: empty.

text: Last

text: we

text: show

text: that

text: the

text: case

text: occurs

text: at

text: at

text: most

text: one

text: factor

text: of

text: F.

text: Assume

text: that

text: the

text: case

text: appears

text: at

text: the

text: factors

text: Γ

text: with

text: j

text: s

text: and

text: not

text: at

text: the

text: factors

text: Γ

text: with

text: j

text: j

text: j

text: s.

text: Then

text: for

text: each

text: j

text: s

text: choose

text: n

text: facets

text: G

text: G

text: of

text: Q

text: belonging

text: to

text: j

text: kjnj

text: that

text: factor.

text: Consider

text: a

text: component

text: K

text: of

text: nj

text: G

text: which

text: meets

text: F.

text: Since

text: at

text: j

text: s

text: kji

text: of

text: the

text: factors

text: Γ

text: j

text: s,

text: the

text: cases

text: or

text: appear,

text: the

text: intersection

text: F

text: K

text: j

text: is

text: connected.

text: Therefore

text: also

text: the

text: intersections

text: G

text: K,

text: j(k)

text: s

text: are

text: connected

text: by

text: k

text: Sublemma

text: By

text: the

text: description

text: of

text: the

text: combinatorial

text: type

text: of

text: the

text: G

text: given

text: in

text: Sublemma

text: k

text: the

text: intersections

text: G

text: K

text: are

text: combinatorially

text: equivalent

text: to

text: cubes

text: and

text: have

text: pairwise

text: k

text: non-connected

text: intersection.

text: Therefore

text: it

text: follows

text: from

text: Lemma

text: that

text: K

text: has

text: di-

text: mension

text: two.

text: Hence

text: it

text: follows

text: that

text: s

text: is

text: two,

text: i.e.

text: there

text: is

text: only

text: one

text: factor

text: of

text: F

text: where

text: the

text: case

text: appears.

text: Therefore

text: there

text: is

text: at

text: most

text: one

text: factor

text: Γ

text: of

text: F

text: where

text: one

text: of

text: the

text: cases

text: and

text: appears.

text: Sublemma

text: Assume

text: that

text: one

text: of

text: the

text: cases

text: or

text: appears

text: at

text: the

text: factor

text: Γ

text: of

text: F.

text: Let

text: G

text: be

text: a

text: facet

text: of

text: Q

text: which

text: meets

text: F

text: and

text: belongs

text: to

text: Γ

text: with

text: j

text: j

text: Then

text: the

text: following

text: holds:

text: The

text: facets

text: of

text: G

text: are

text: given

text: by

text: the

text: components

text: of

text: the

text: intersections

text: G

text: G

text: k

text: G

text: G

text: is

text: disconnected

text: if

text: and

text: only

text: if

text: Γ

text: Σ2

text: and

text: j(k)

text: j(k

text: j

text: k


text: (cid:84) 16 MICHAEL WIEMELER (cid:84) ∩ (cid:84) is a union of components of G G . In fact, the union of those com- (cid:84)k; j(k)=j k k0 ponents of B which meet F is equal to the union of those components k; j∩(k)=j k (cid:84) (cid:84) of G G which meet F. k; j(k)=j (cid:84)k k0 ∩ Since every component of G F contains exactly one component of ∩ ∩ k; j(k)=j k (cid:84) G G F, each component of G which meets F contains a k; j(k)=j k (cid:84)k0 k; j(k)=j k component of B which meets F. Because the union of those components k; j(k)=j k of G which meet F is disconnected, the same holds for the union of those k; j(k)=j k components of B which meet F. Hence, the case 2b appears at the factor ∩ k; j(k)=j k Γ of F G . j k0 Therefore it follows from the induction hypotheses that there is an isomorphism P → P ∩ × ∩ ×{ } of posets (G ) ((F G ) [0, 1]), such that F is mapped to (F G ) 0 k0 ∩k0 ∩ ×k0 and the component C of G G which meets F is mapped to (F C) [0, 1]. In k0 k∩ (cid:3) particular, all components of G G meet F. k0 k Sublemma 4.17. In the situation of Lemma 4.9, there is exactly one facet H of Q which does not meet F. Moreover, the following holds: ∩ (1) Under the isomorphism constructed in the previous sublemma, G H ∩ × { } k0 cPorresp∼onPds to (F Gk0) 1 . (2) (H) = (F). Proof. Let H be the facet of Q which intersects G in the facet of G which k0 ∩ × { } k0 k0 corresponds to (F G ) 1 . If q is a vertex of G corresponding to (p, 1), k0∩ k0 where p is a vertex of F G , then H is the facet of Q which is perpendicular k0 k0{ } × to the edge of G which corresponds to p [0, 1]. We claim that all H are the k0 k0 same. (cid:54) ∩ ∩ If j = j , then the intersection of G F and G F, where j(k ) = j and 1 2 k1 ∩ k2 ∩ 1 1 j(k ) = j , is non-empty. If j = j and dim G F = dim G F > 0, there is 2 2 ∩ ∩ 1 (cid:54) ∅2 k1 k2 a G (cid:48) such that G (cid:48) G F = for i = 1, 2. Hence, in these cases H = H k k ki ∩ ∩ k1 k2 because there is a vertex in G G F. Since dim Q > 2, F cannot be an k1 k2 interval. Hence, it follows that all H are equal, so that we can drop the indices. k Since the vertex-edge-graph of H is connected, every face of Q contains at least one − vertex and each vertex is contained in exactly n 1 facets of H, it follows that the ∩ facets of H are given by the G H. k Indeed, if there is another facet of H, then it contains a vertex v of H. Since the vertex-edge-graph of H is connected, we may assume that v is connected by an edge (cid:48) ∈ ∩ to a vertex v G H. It follows from the description of the combinatorial type (cid:48) k − ∩ of G that v is contained in n 1 facets of H of the form G (cid:48) H. Therefore each k (cid:48) k∩ ∈ edge which meets v is contained in a facet of the form G (cid:48) H. Hence, v G (cid:48). k k Therefore it follows from the description of the combinatorial type of G (cid:48) that all ∩ k facets of H which contain v are of the form G (cid:48)(cid:48) H. This is a contradiction to the k (cid:84) assumption that v is contained in a facet which is not of this form. P → P ∩ Therefore there is an isomorphism of posets φ : (F) (H), such that φ(C ∩ K F) = C H. Here C is a component of the intersection ∈ G . Since the K K k K k vertex-edge-graph of Q is connected, every face of Q contains at least one vertex and each vertex is contained in exactly n facets, F, H, G is a complete list of k (cid:3) facets of Q. Proof of Lemma 4.9. It follows from Sublemmas 4.16 and 4.17 that the face posets × of Q and F [0, 1] are isomorphic. An isomorphism is given by (cid:55)→ ∩ × ∩ (cid:55)→ ∩ × { } C (C F) [0, 1] (F C ) (F C ) 0 K K K K ∩ (cid:55)→ ∩ × { } (H C ) (F C ) 1 . K K

text: MICHAEL

text: WIEMELER

text: is

text: a

text: union

text: of

text: components

text: of

text: G

text: G

text: In

text: fact,

text: the

text: union

text: of

text: those

text: com-

text: j(k)=j

text: k

text: ponents

text: of

text: B

text: which

text: meet

text: F

text: is

text: equal

text: to

text: the

text: union

text: of

text: those

text: components

text: k;

text: j∩(k)=j

text: k

text: of

text: G

text: G

text: which

text: meet

text: F.

text: k;

text: j(k)=j

text: Since

text: every

text: component

text: of

text: G

text: F

text: contains

text: exactly

text: one

text: component

text: of

text: k;

text: j(k)=j

text: k

text: G

text: G

text: F,

text: each

text: component

text: of

text: G

text: which

text: meets

text: F

text: contains

text: a

text: k;

text: j(k)=j

text: k

text: k;

text: j(k)=j

text: k

text: component

text: of

text: B

text: which

text: meets

text: F.

text: Because

text: the

text: union

text: of

text: those

text: components

text: k;

text: j(k)=j

text: k

text: of

text: G

text: which

text: meet

text: F

text: is

text: disconnected,

text: the

text: same

text: holds

text: for

text: the

text: union

text: of

text: those

text: k;

text: j(k)=j

text: k

text: components

text: of

text: B

text: which

text: meet

text: F.

text: Hence,

text: the

text: case

text: appears

text: at

text: the

text: factor

text: k;

text: j(k)=j

text: k

text: Γ

text: of

text: F

text: G

text: j

text: Therefore

text: it

text: follows

text: from

text: the

text: induction

text: hypotheses

text: that

text: there

text: is

text: an

text: isomorphism

text: P

text: P

text: of

text: posets

text: (G

text: ((F

text: G

text: such

text: that

text: F

text: is

text: mapped

text: to

text: (F

text: G

text: and

text: the

text: component

text: C

text: of

text: G

text: G

text: which

text: meets

text: F

text: is

text: mapped

text: to

text: (F

text: C)

text: In

text: k∩

text: particular,

text: all

text: components

text: of

text: G

text: G

text: meet

text: F.

text: k

text: Sublemma

text: In

text: the

text: situation

text: of

text: Lemma

text: there

text: is

text: exactly

text: one

text: facet

text: H

text: of

text: Q

text: which

text: does

text: not

text: meet

text: F.

text: Moreover,

text: the

text: following

text: holds:

text: Under

text: the

text: isomorphism

text: constructed

text: in

text: the

text: previous

text: sublemma,

text: G

text: H

text: cPorresp∼onPds

text: to

text: (F

text: (H)

text: (F).

text: Proof.

text: Let

text: H

text: be

text: the

text: facet

text: of

text: Q

text: which

text: intersects

text: G

text: in

text: the

text: facet

text: of

text: G

text: which

text: corresponds

text: to

text: (F

text: G

text: If

text: q

text: is

text: a

text: vertex

text: of

text: G

text: corresponding

text: to

text: (p,

text: where

text: p

text: is

text: a

text: vertex

text: of

text: F

text: G

text: then

text: H

text: is

text: the

text: facet

text: of

text: Q

text: which

text: is

text: perpendicular

text: to

text: the

text: edge

text: of

text: G

text: which

text: corresponds

text: to

text: p

text: We

text: claim

text: that

text: all

text: H

text: are

text: the

text: same.

text: If

text: j

text: j

text: then

text: the

text: intersection

text: of

text: G

text: F

text: and

text: G

text: F,

text: where

text: j(k

text: j

text: and

text: j(k

text: j

text: is

text: non-empty.

text: If

text: j

text: j

text: and

text: dim

text: G

text: F

text: dim

text: G

text: F

text: there

text: is

text: ∅2

text: a

text: G

text: such

text: that

text: G

text: G

text: F

text: for

text: i

text: Hence,

text: in

text: these

text: cases

text: H

text: H

text: k

text: k

text: ki

text: because

text: there

text: is

text: a

text: vertex

text: in

text: G

text: G

text: F.

text: Since

text: dim

text: Q

text: F

text: cannot

text: be

text: an

text: interval.

text: Hence,

text: it

text: follows

text: that

text: all

text: H

text: are

text: equal,

text: so

text: that

text: we

text: can

text: drop

text: the

text: indices.

text: k

text: Since

text: the

text: vertex-edge-graph

text: of

text: H

text: is

text: connected,

text: every

text: face

text: of

text: Q

text: contains

text: at

text: least

text: one

text: vertex

text: and

text: each

text: vertex

text: is

text: contained

text: in

text: exactly

text: n

text: facets

text: of

text: H,

text: it

text: follows

text: that

text: the

text: facets

text: of

text: H

text: are

text: given

text: by

text: the

text: G

text: H.

text: k

text: Indeed,

text: if

text: there

text: is

text: another

text: facet

text: of

text: H,

text: then

text: it

text: contains

text: a

text: vertex

text: v

text: of

text: H.

text: Since

text: the

text: vertex-edge-graph

text: of

text: H

text: is

text: connected,

text: we

text: may

text: assume

text: that

text: v

text: is

text: connected

text: by

text: an

text: edge

text: to

text: a

text: vertex

text: v

text: G

text: H.

text: It

text: follows

text: from

text: the

text: description

text: of

text: the

text: combinatorial

text: type

text: k

text: of

text: G

text: that

text: v

text: is

text: contained

text: in

text: n

text: facets

text: of

text: H

text: of

text: the

text: form

text: G

text: H.

text: Therefore

text: each

text: k

text: k∩

text: edge

text: which

text: meets

text: v

text: is

text: contained

text: in

text: a

text: facet

text: of

text: the

text: form

text: G

text: H.

text: Hence,

text: v

text: G

text: k

text: k

text: Therefore

text: it

text: follows

text: from

text: the

text: description

text: of

text: the

text: combinatorial

text: type

text: of

text: G

text: that

text: all

text: k

text: facets

text: of

text: H

text: which

text: contain

text: v

text: are

text: of

text: the

text: form

text: G

text: H.

text: This

text: is

text: a

text: contradiction

text: to

text: the

text: k

text: assumption

text: that

text: v

text: is

text: contained

text: in

text: a

text: facet

text: which

text: is

text: not

text: of

text: this

text: form.

text: P

text: P

text: Therefore

text: there

text: is

text: an

text: isomorphism

text: of

text: posets

text: φ

text: (F)

text: (H),

text: such

text: that

text: φ(C

text: K

text: F)

text: C

text: H.

text: Here

text: C

text: is

text: a

text: component

text: of

text: the

text: intersection

text: G

text: Since

text: the

text: K

text: K

text: k

text: K

text: k

text: vertex-edge-graph

text: of

text: Q

text: is

text: connected,

text: every

text: face

text: of

text: Q

text: contains

text: at

text: least

text: one

text: vertex

text: and

text: each

text: vertex

text: is

text: contained

text: in

text: exactly

text: n

text: facets,

text: F,

text: H,

text: G

text: is

text: a

text: complete

text: list

text: of

text: k

text: facets

text: of

text: Q.

text: Proof

text: of

text: Lemma

text: It

text: follows

text: from

text: Sublemmas

text: and

text: that

text: the

text: face

text: posets

text: of

text: Q

text: and

text: F

text: are

text: isomorphic.

text: An

text: isomorphism

text: is

text: given

text: by

text: C

text: (C

text: F)

text: (F

text: C

text: (F

text: C

text: K

text: K

text: K

text: K

text: (H

text: C

text: (F

text: C

text: K

text: K


text: 22 MICHAEL WIEMELER × × Proof. We prove this lemma by induction on the dimension of Q Q . For dim Q 1 × 2 1 Q = 0 there is nothing to show. Therefore assume that dim Q Q > 0 and the 2 × 1 2 × lemma is proved for all products Q˜ Q˜ of dimension less than dim Q Q . 1 2 1 2 × (1) It follows from the induction hypothesis that F Q has a shelling. ≤ − 1 2 (2) For j s 1, we have (cid:91) (cid:91) − − j 1 j 1 × ∩ × ∩ × (6.4) (F(cid:83) Q ) (F Q ) = (F(cid:83) F ) Q . j 2 i 2 j i 2 i=1 i=1 ∩ − (cid:54) Because j F is contractible, F j 1 F = ∂F is the beginning of i=1 i j i=1 i j a shelling of F . By the induction hypothesis it follows that (6.4) is the j × beginning of a shelling of F Q . ≤ ≤ j 2 For 1 j r we have (cid:32) (cid:33) (cid:32) (cid:33) (cid:91) (cid:91) (cid:91) (cid:91) (6.5) − − − − × ∩ s 1 × ∪ j 1 × s 1 × ∪ × j 1 ∩ (Q G ) (F Q ) (Q G ) = F G Q ( G G ) . 1 j i 2 1 i i j 1 j i i=1 i=1 i=1 i=1 Therefore it follows from the induction hypothesis that (6.5) is the be- × ginning of a shelling of Q G . (cid:91) ×1 j (cid:91) The intersection of F Q with s 2 − s 1 × ∪ r × (F Q ) (Q G ) i 2 1 i i=1 i=1 × is the whole boundary of F Q . Since by assumption there are shellings s 2 (cid:83) (cid:83) for F and Q , it follows from the induction hypothesis that it is a beginning s 2 × of a shelling for F Q . s 2 × ∪ (cid:48) × ≤ − (3) The veriﬁcation that j F Q j Q G is contractible for j s 1 (cid:48) ≤ i=1 i 2 i=1 1 i and j r is left to the reader. (cid:81) (cid:81) (cid:3) × It follows from the above lemma that Σni ∆ni is shellable. Now we can i i prove the following lemma in the same way as Theorem 5.6 in [25]. Lemma 6.8. Let M be a locally standard torus manifold over a shellable nice manifold with corners Q. Then M is determined up to equivariant diﬀeomorphism by the characteristic function λ . M Now we can prove Theorem 6.1. P Proof of Theorem 6.1. As in the proof of Theorem 4.1, it follows that ( (M/T), λ) P (cid:48) (cid:48) (cid:48) is isomorphic to ( (M /T), λ ), where M is the quotient of a free linear torus action on a product of spheres. This quotient admits an invariant metric of non-negative curvature and is simply connected. Therefore, by Lemmas 6.3, 6.4 and 6.8, M and (cid:48) (cid:3) M are equivariantly diﬀeomorphic. 7. Non-simply connected non-negatively curved torus manifolds Now we discuss some results for non-simply connected non-negatively curved torus manifolds. Lemma 7.1. Let M be a 2n-dimensional torus manifold with an invariant metric | | ≤ ≤ of non-negative sectional curvature. Then we have π (M) = 2k for some 0 k − 1 n 1.

text: MICHAEL

text: WIEMELER

text: Proof.

text: We

text: prove

text: this

text: lemma

text: by

text: induction

text: on

text: the

text: dimension

text: of

text: Q

text: Q

text: For

text: dim

text: Q

text: Q

text: there

text: is

text: nothing

text: to

text: show.

text: Therefore

text: assume

text: that

text: dim

text: Q

text: Q

text: and

text: the

text: lemma

text: is

text: proved

text: for

text: all

text: products

text: Q˜

text: Q˜

text: of

text: dimension

text: less

text: than

text: dim

text: Q

text: Q

label: list

text: It

text: follows

text: from

text: the

text: induction

text: hypothesis

text: that

text: F

text: Q

text: has

text: a

text: shelling.

text: For

text: j

text: s

text: we

text: have

label: equation

text: j

text: j

text: Q

text: (F

text: Q

text: F

text: Q

text: j

text: i

text: j

text: i

text: Because

text: j

text: F

text: is

text: contractible,

text: F

text: j

text: F

text: ∂F

text: is

text: the

text: beginning

text: of

text: i

text: j

text: i

text: j

text: a

text: shelling

text: of

text: F

text: By

text: the

text: induction

text: hypothesis

text: it

text: follows

text: that

text: is

text: the

text: j

text: beginning

text: of

text: a

text: shelling

text: of

text: F

text: Q

text: j

text: For

text: j

text: r

text: we

text: have

text: s

text: j

text: s

text: j

text: (Q

text: G

text: (F

text: Q

text: (Q

text: G

text: F

text: G

text: Q

text: G

text: G

text: j

text: i

text: i

text: i

text: j

text: j

text: i

text: Therefore

text: it

text: follows

text: from

text: the

text: induction

text: hypothesis

text: that

text: is

text: the

text: be-

text: ginning

text: of

text: a

text: shelling

text: of

text: Q

text: G

text: ×1

text: j

text: The

text: intersection

text: of

text: F

text: Q

text: with

text: s

text: s

text: r

text: (F

text: Q

text: (Q

text: G

text: i

text: i

text: is

text: the

text: whole

text: boundary

text: of

text: F

text: Q

text: Since

text: by

text: assumption

text: there

text: are

text: shellings

text: s

text: for

text: F

text: and

text: Q

text: it

text: follows

text: from

text: the

text: induction

text: hypothesis

text: that

text: it

text: is

text: a

text: beginning

text: s

text: of

text: a

text: shelling

text: for

text: F

text: Q

text: s

text: The

text: veriﬁcation

text: that

text: j

text: F

text: Q

text: j

text: Q

text: G

text: is

text: contractible

text: for

text: j

text: s

text: i

text: i

text: and

text: j

text: r

text: is

text: left

text: to

text: the

text: reader.

text: It

text: follows

text: from

text: the

text: above

text: lemma

text: that

text: Σni

text: ∆ni

text: is

text: shellable.

text: Now

text: we

text: can

text: i

text: i

text: prove

text: the

text: following

text: lemma

text: in

text: the

text: same

text: way

text: as

text: Theorem

text: in

text: Lemma

text: Let

text: M

text: be

text: a

text: locally

text: standard

text: torus

text: manifold

text: over

text: a

text: shellable

text: nice

text: manifold

text: with

text: corners

text: Q.

text: Then

text: M

text: is

text: determined

text: up

text: to

text: equivariant

text: diﬀeomorphism

text: by

text: the

text: characteristic

text: function

text: λ

text: M

text: Now

text: we

text: can

text: prove

text: Theorem

text: P

text: Proof

text: of

text: Theorem

text: As

text: in

text: the

text: proof

text: of

text: Theorem

text: it

text: follows

text: that

text: (M/T),

text: λ)

text: P

text: is

text: isomorphic

text: to

text: (M

text: /T),

text: λ

text: where

text: M

text: is

text: the

text: quotient

text: of

text: a

text: free

text: linear

text: torus

text: action

text: on

text: a

text: product

text: of

text: spheres.

text: This

text: quotient

text: admits

text: an

text: invariant

text: metric

text: of

text: non-negative

text: curvature

text: and

text: is

text: simply

text: connected.

text: Therefore,

text: by

text: Lemmas

text: and

text: M

text: and

text: M

text: are

text: equivariantly

text: diﬀeomorphic.

text: Non-simply

text: connected

text: non-negatively

text: curved

text: torus

text: manifolds

text: Now

text: we

text: discuss

text: some

text: results

text: for

text: non-simply

text: connected

text: non-negatively

text: curved

text: torus

text: manifolds.

text: Lemma

text: Let

text: M

text: be

text: a

text: torus

text: manifold

text: with

text: an

text: invariant

text: metric

text: of

text: non-negative

text: sectional

text: curvature.

text: Then

text: we

text: have

text: π

text: (M)

text: for

text: some

text: k

text: n


text: 10 MICHAEL WIEMELER Lemma 4.9. If, in the above situation, at all factors Γ only the cases 1c, 2b and Pj → P × 3b appear, then there is an isomorphism of face posets (Q) (F [0, 1]) which ∩ × × { } sends each G to (G F) [0, 1] and F to F 0 . k k (cid:3) Now we prove by induction on the dimension of Q the lemmas from above. For dim Q = 2, these lemmas are obvious. Therefore we may assume that n = dim Q > 2 and that all the lemmas are proved in dimensions less than n. Sublemma 4.10. Assume that the case 2a appears at the factor Γ of F. Let G j0 k0 be a facet of Q which belongs to Γ . Then the following holds: j0 ∩ (1) The facets of G are given by the components of the intersections G G ∩ k0 k k0 and F G . ∩ k0 ∩ (2) G G is connected if and only if (cid:89)F G is connected. k k0 k (3) There is a combinatorial equivalence P → P (G ) ( Γ ), k0 i i ∩ such that F G corresponds to a facet of the j -th factor and the compo- ∩ k0 0 nents of G G correspond to facets of the j(k)-th factor. k k0 ∩ → Proof. We consider the inclusion of F G (cid:44) G , where G is a facet of Q ∩ k0 (cid:89)k0 k0 which belongs to Γ . Then F G is a facet of G and there is a combinatorial j0 k0 k0 equivalence ∩ ∼ − × F Gk0 = Σnj0 1 (cid:54) Γi ∩ ∩ i=j0 such that each component of G G F corresponds to a facet of the j(k)-th factor. k0 k ∩(cid:84) (cid:84) Moreover, the facets of G which meet F G are given by those components of ∩ k0 k0 the G G which meet F. Since the case 2a appears at the factor Γ of F it k k0 j0 ∩ follows that there is only one component of G = (G G ) k; j(k)=j0 k k; j(k)=j0 k k−0 which∩me(cid:81)ets F. Therefore one of the cases 2a or 1a appears at the factor Σnj0 1 of F G . k0 Hence, it follows from the induction hypothesis that G is combinatorially equiv- k0 ∩ alent to Γ in such a way that the component of G G which meets F is i i (cid:81) k0 ∩k mapped to a facet which belongs to the j(k)-th factor and F G is mapped to a k0 facet which belongs to the j -th factor. 0 ∩ Since all facets of Γ meet the facet which corresponds to F G it follows i i ∩ k0 that each facet of G is a component of some intersection G G . ∩ k0 k k0 Moreover, G G is connected for all k with n > 1 because for these k k0 j(k) k the facets of the factor Γ of G have pairwise non-trivial intersections. If (cid:54) (cid:81)j(k) ∩ k0 ∩ ∩ n = 1 and j(k) = j , then G G is disconnected if and only if G G F j(k) 0 ∩ k k0 ∩ k k0 is disconnected because∼F Gk0 and the components of Gk Gk0 are facets of diﬀerent factors of G = Γ . Since G and G belong to diﬀerent factors of F, k0 i i k k0 ∩ (cid:3) it follows that this last statement is true if and only if G F is disconnected. k Sublemma 4.11. Assume that the case 3a appears at the factor Γ of F. Let G j0 k0 be a facet of Q which belongs to Γ . Then the following holds: j0 ∩ (1) The facets of G are given by the components of the intersections G G ∩ k0 k k0 and F G . ∩ k0 ∩ (2) G G is connected if and only if (cid:89)F G is connected. k k0 k (3) There is a combinatorial equivalence P → P (G ) ( Γ ), k0 i i

text: MICHAEL

text: WIEMELER

text: Lemma

text: If,

text: in

text: the

text: above

text: situation,

text: at

text: all

text: factors

text: Γ

text: only

text: the

text: cases

text: and

text: Pj

text: P

text: appear,

text: then

text: there

text: is

text: an

text: isomorphism

text: of

text: face

text: posets

text: (Q)

text: (F

text: which

text: sends

text: each

text: G

text: to

text: (G

text: F)

text: and

text: F

text: to

text: F

text: k

text: k

text: Now

text: we

text: prove

text: by

text: induction

text: on

text: the

text: dimension

text: of

text: Q

text: the

text: lemmas

text: from

text: above.

text: For

text: dim

text: Q

text: these

text: lemmas

text: are

text: obvious.

text: Therefore

text: we

text: may

text: assume

text: that

text: n

text: dim

text: Q

text: and

text: that

text: all

text: the

text: lemmas

text: are

text: proved

text: in

text: dimensions

text: less

text: than

text: n.

text: Sublemma

text: Assume

text: that

text: the

text: case

text: appears

text: at

text: the

text: factor

text: Γ

text: of

text: F.

text: Let

text: G

text: be

text: a

text: facet

text: of

text: Q

text: which

text: belongs

text: to

text: Γ

text: Then

text: the

text: following

text: holds:

text: The

text: facets

text: of

text: G

text: are

text: given

text: by

text: the

text: components

text: of

text: the

text: intersections

text: G

text: G

text: k

text: and

text: F

text: G

text: G

text: G

text: is

text: connected

text: if

text: and

text: only

text: if

text: G

text: is

text: connected.

text: k

text: k

text: There

text: is

text: a

text: combinatorial

text: equivalence

text: P

text: P

text: (G

text: Γ

text: i

text: i

text: such

text: that

text: F

text: G

text: corresponds

text: to

text: a

text: facet

text: of

text: the

text: j

text: -th

text: factor

text: and

text: the

text: compo-

text: nents

text: of

text: G

text: G

text: correspond

text: to

text: facets

text: of

text: the

text: j(k)-th

text: factor.

text: k

text: Proof.

text: We

text: consider

text: the

text: inclusion

text: of

text: F

text: G

text: G

text: where

text: G

text: is

text: a

text: facet

text: of

text: Q

text: which

text: belongs

text: to

text: Γ

text: Then

text: F

text: G

text: is

text: a

text: facet

text: of

text: G

text: and

text: there

text: is

text: a

text: combinatorial

text: equivalence

text: F

text: Γi

text: such

text: that

text: each

text: component

text: of

text: G

text: G

text: F

text: corresponds

text: to

text: a

text: facet

text: of

text: the

text: j(k)-th

text: factor.

text: k

text: Moreover,

text: the

text: facets

text: of

text: G

text: which

text: meet

text: F

text: G

text: are

text: given

text: by

text: those

text: components

text: of

text: the

text: G

text: G

text: which

text: meet

text: F.

text: Since

text: the

text: case

text: appears

text: at

text: the

text: factor

text: Γ

text: of

text: F

text: it

text: k

text: follows

text: that

text: there

text: is

text: only

text: one

text: component

text: of

text: G

text: (G

text: G

text: k;

text: k

text: k;

text: k

text: F.

text: Therefore

text: one

text: of

text: the

text: cases

text: or

text: appears

text: at

text: the

text: factor

text: of

text: F

text: G

text: Hence,

text: it

text: follows

text: from

text: the

text: induction

text: hypothesis

text: that

text: G

text: is

text: combinatorially

text: equiv-

text: alent

text: to

text: Γ

text: in

text: such

text: a

text: way

text: that

text: the

text: component

text: of

text: G

text: G

text: which

text: meets

text: F

text: is

text: i

text: i

text: ∩k

text: mapped

text: to

text: a

text: facet

text: which

text: belongs

text: to

text: the

text: j(k)-th

text: factor

text: and

text: F

text: G

text: is

text: mapped

text: to

text: a

text: facet

text: which

text: belongs

text: to

text: the

text: j

text: -th

text: factor.

text: Since

text: all

text: facets

text: of

text: Γ

text: meet

text: the

text: facet

text: which

text: corresponds

text: to

text: F

text: G

text: it

text: follows

text: i

text: i

text: that

text: each

text: facet

text: of

text: G

text: is

text: a

text: component

text: of

text: some

text: intersection

text: G

text: G

text: k

text: Moreover,

text: G

text: G

text: is

text: connected

text: for

text: all

text: k

text: with

text: n

text: because

text: for

text: these

text: k

text: j(k)

text: k

text: the

text: facets

text: of

text: the

text: factor

text: Γ

text: of

text: G

text: have

text: pairwise

text: non-trivial

text: intersections.

text: If

text: n

text: and

text: j(k)

text: j

text: then

text: G

text: G

text: is

text: disconnected

text: if

text: and

text: only

text: if

text: G

text: G

text: F

text: j(k)

text: k

text: k

text: is

text: disconnected

text: because∼F

text: and

text: the

text: components

text: of

text: Gk

text: are

text: facets

text: of

text: diﬀerent

text: factors

text: of

text: G

text: Γ

text: Since

text: G

text: and

text: G

text: belong

text: to

text: diﬀerent

text: factors

text: of

text: F,

text: i

text: i

text: k

text: it

text: follows

text: that

text: this

text: last

text: statement

text: is

text: true

text: if

text: and

text: only

text: if

text: G

text: F

text: is

text: disconnected.

text: k

text: Sublemma

text: Assume

text: that

text: the

text: case

text: appears

text: at

text: the

text: factor

text: Γ

text: of

text: F.

text: Let

text: G

text: be

text: a

text: facet

text: of

text: Q

text: which

text: belongs

text: to

text: Γ

text: Then

text: the

text: following

text: holds:

text: The

text: facets

text: of

text: G

text: are

text: given

text: by

text: the

text: components

text: of

text: the

text: intersections

text: G

text: G

text: k

text: and

text: F

text: G

text: G

text: G

text: is

text: connected

text: if

text: and

text: only

text: if

text: G

text: is

text: connected.

text: k

text: k

text: There

text: is

text: a

text: combinatorial

text: equivalence

text: P

text: P

text: (G

text: Γ

text: i

text: i


text: EPITOPE PROFILING VIA MIXTURE MODELING OF RANKED DATA CRISTINA MOLLICA AND LUCA TARDELLA Abstract. We propose the use of probability models for ranked data as a useful alternative to a quantitative data analysis to investigate the outcome of bioassay experiments, when the preliminary choice of an appropriate nor- malization method for the raw numerical responses is diﬃcult or subject to criticism. We review standard distance-based and multistage ranking models and in this last context we propose an original generalization of the Plackett- Luce model to account for the order of the ranking elicitation process. The usefulness of the novel model is illustrated with its maximum likelihood es- timation for a real data set. Speciﬁcally, we address the heterogeneous na- ture of experimental units via model-based clustering and detail the necessary steps for a successful likelihood maximization through a hybrid version of the Expectation-Maximization algorithm. The performance of the mixture model using the new distribution as mixture components is compared with those rel- ative to alternative mixture models for random rankings. A discussion on the interpretation of the identiﬁed clusters and a comparison with more standard quantitative approaches are ﬁnally provided. Dipartimento di Scienze statistiche, Sapienza Universita` di Roma, Piazzale A. Moro 5, 00185 Roma, Italy Email address: cristina.mollica@uniroma1.it Dipartimento di Scienze statistiche, Sapienza Universita` di Roma, Piazzale A. Moro 5, 00185 Roma, Italy Email address: luca.tardella@uniroma1.it 1. Introduction Ranked data arise in several contexts, especially when objective and precise measurements of the phenomena of interest can be impossible or deemed unreliable and the observer gathers ordinal information in terms of orderings, preferences, judgments, relative or absolute ranking among competitors. Research ﬁelds where the analysis of ranked data are frequently required are the social and behavioral sciences, where studies often ask a sample of N people to rank a ﬁnite set of K items according to certain criteria, typically their personal preferences or attitudes. In marketing, political surveys or psychological experiments, items to rank can be consumer goods, political candidates or goals, words or topics considered to be more or less associated to a reference one according to the individual perception. Another typical context is sport, where teams, horses or cars compete, and the ﬁnal outcome is a ranking among competitors. A detailed and well-structured reference monograph concerning ranking data analysis and modeling is (Marden, 1995). Key words and phrases. Ranking data, Plackett-Luce model, Multistage ranking models, Mixture models, EM algorithm, Epitope mapping. Version May 26, 2020. 1 ##LTLine##

text: EPITOPE

text: PROFILING

text: VIA

text: MIXTURE

text: MODELING

text: OF

text: RANKED

text: DATA

text: CRISTINA

text: MOLLICA

text: AND

text: LUCA

text: TARDELLA

text: Abstract.

text: We

label: abstract

text: propose

text: the

text: use

text: of

text: probability

text: models

text: for

text: ranked

text: data

text: as

text: a

text: useful

text: alternative

text: to

text: a

text: quantitative

text: data

text: analysis

text: to

text: investigate

text: the

text: outcome

text: of

text: bioassay

text: experiments,

text: when

text: the

text: preliminary

text: choice

text: of

text: an

text: appropriate

text: nor-

text: malization

text: method

text: for

text: the

text: raw

text: numerical

text: responses

text: is

text: diﬃcult

text: or

text: subject

text: to

text: criticism.

text: We

text: review

text: standard

text: distance-based

text: and

text: multistage

text: ranking

text: models

text: and

text: in

text: this

text: last

text: context

text: we

text: propose

text: an

text: original

text: generalization

text: of

text: the

text: Plackett-

text: Luce

text: model

text: to

text: account

text: for

text: the

text: order

text: of

text: the

text: ranking

text: elicitation

text: process.

text: The

text: usefulness

text: of

text: the

text: novel

text: model

text: is

text: illustrated

text: with

text: its

text: maximum

text: likelihood

text: es-

text: timation

text: for

text: a

text: real

text: data

text: set.

text: Speciﬁcally,

text: we

text: address

text: the

text: heterogeneous

text: na-

text: ture

text: of

text: experimental

text: units

text: via

text: model-based

text: clustering

text: and

text: detail

text: the

text: necessary

text: steps

text: for

text: a

text: successful

text: likelihood

text: maximization

text: through

text: a

text: hybrid

text: version

text: of

text: the

text: Expectation-Maximization

text: algorithm.

text: The

text: performance

text: of

text: the

text: mixture

text: model

text: using

text: the

text: new

text: distribution

text: as

text: mixture

text: components

text: is

text: compared

text: with

text: those

text: rel-

text: ative

text: to

text: alternative

text: mixture

text: models

text: for

text: random

text: rankings.

text: A

text: discussion

text: on

text: the

text: interpretation

text: of

text: the

text: identiﬁed

text: clusters

text: and

text: a

text: comparison

text: with

text: more

text: standard

text: quantitative

text: approaches

text: are

text: ﬁnally

text: provided.

text: Dipartimento

text: di

text: Scienze

text: statistiche,

text: Sapienza

text: Universita`

text: di

text: Roma,

text: Piazzale

text: A.

text: Moro

text: Roma,

text: Italy

text: Email

text: address:

text: Dipartimento

text: di

text: Scienze

text: statistiche,

text: Sapienza

text: Universita`

text: di

text: Roma,

text: Piazzale

text: A.

text: Moro

text: Roma,

text: Italy

text: Email

text: address:

text: Introduction

text: Ranked

text: data

text: arise

text: in

text: several

text: contexts,

text: especially

text: when

text: objective

text: and

text: precise

text: measurements

text: of

text: the

text: phenomena

text: of

text: interest

text: can

text: be

text: impossible

text: or

text: deemed

text: unreliable

text: and

text: the

text: observer

text: gathers

text: ordinal

text: information

text: in

text: terms

text: of

text: orderings,

text: preferences,

text: judgments,

text: relative

text: or

text: absolute

text: ranking

text: among

text: competitors.

text: Research

text: ﬁelds

text: where

text: the

text: analysis

text: of

text: ranked

text: data

text: are

text: frequently

text: required

text: are

text: the

text: social

text: and

text: behavioral

text: sciences,

text: where

text: studies

text: often

text: ask

text: a

text: sample

text: of

text: N

text: people

text: to

text: rank

text: a

text: ﬁnite

text: set

text: of

text: K

text: items

text: according

text: to

text: certain

text: criteria,

text: typically

text: their

text: personal

text: preferences

text: or

text: attitudes.

text: In

text: marketing,

text: political

text: surveys

text: or

text: psychological

text: experiments,

text: items

text: to

text: rank

text: can

text: be

text: consumer

text: goods,

text: political

text: candidates

text: or

text: goals,

text: words

text: or

text: topics

text: considered

text: to

text: be

text: more

text: or

text: less

text: associated

text: to

text: a

text: reference

text: one

text: according

text: to

text: the

text: individual

text: perception.

text: Another

text: typical

text: context

text: is

text: sport,

text: where

text: teams,

text: horses

text: or

text: cars

text: compete,

text: and

text: the

text: ﬁnal

text: outcome

text: is

text: a

text: ranking

text: among

text: competitors.

text: A

text: detailed

text: and

text: well-structured

text: reference

text: monograph

text: concerning

text: ranking

text: data

text: analysis

text: and

text: modeling

text: is

text: (Marden,

text: Key

text: words

text: and

text: phrases.

text: Ranking

text: data,

text: Plackett-Luce

text: model,

text: Multistage

text: ranking

text: models,

text: Mixture

text: models,

text: EM

text: algorithm,

text: Epitope

text: mapping.

text: Version

text: May

text: ##LTLine##


text: EPITOPE PROFILING VIA MIXTURE MODELING OF RANKED DATA 23 of pre-experimental information in the analysis. This extension could beneﬁt from the conjugacy of the PL with the Gamma prior distribution, already exploited for the Bayesian inference in (Guiver and Snelson, 2009) and (Caron and Doucet, 2012) but restricted to the homogenous population case. Another interesting direction could be that of setting up a ﬂexible framework to integrate the use of mixed-type (ordinal and quantitative) data with the possible inclusion of individual covariates. Acknowledgements We are deeply grateful to Augusto Amici and his research group for providing LFPD data and many insightful discussions on the biological foundations of the experimental outcomes. We also thank prof. Thomas Brendan Murphy and Isobel Claire Gormley for providing their C code and helpful hints. Appendix We prove here the presence of distributions on orderings in our novel EPL family which are not members of the canonical PL. For this purpose, let us remind that the PL implies the independence of irrelevant alternatives (IIA), stating that the probability ratio to select an item over another is unaﬀected by the preferences towards the other alternatives in the choice set, see (Luce, 1959). Equivalently, one can say that in a PL the choice probability ratio between two items is constant over all stages as long as such alternatives are both still available. In the K = 3 case the IIA lemma translates into the following set of conditions on the probabilities − q − = P(π 1) of each possible ordering π 1 q q + q (1,2,3) (2,1,3) (2,3,1) = q q + q (1,3,2) (3,1,2) (3,2,1) q q + q (2,1,3) (1,2,3) (1,3,2) (5.1) = q q + q (2,3,1) (3,1,2) (3,2,1) q q + q (3,1,2) (1,2,3) (1,3,2) = q q + q (3,2,1) (2,1,3) (2,3,1) and they have to be simultaneously satisﬁed for a generic ranking distribution to belong to the forward PL. Now, let us consider the EPL with ﬁxed ρ = (2, 1, 3) and the generi(cid:32)c induced probability function on random orderings(cid:33)given by q q q q q q (1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1) (5.2) . p−2p1 p−3p1 p−1p2 p−3p2 p−1p3 p−2p3 1 p2 1 p3 1 p1 1 p3 1 p1 1 p2 Substituting (5.2) in (5.1) and solving w.r.t. p one obtains as unique solution p = (1/3, 1/3, 1/3), meaning that the two model classes can share only the UM. This formally shows what has been hinted at in (Fligner and Verducci, 1988) on the possibility to deﬁne new ranking models relaxing the forward hypothesis. To give an intuition about the types of ranking distributions that are not covered by the traditional PL, let us consider the EPL with parameter conﬁguration ρ = (2, 1, 3) − → and p = (1 2(cid:15), (cid:15), (cid:15)) where (cid:15) 0. The corresponding probability function over the six possible orderings has two equally supported modes on the sequences with ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: EPITOPE

text: PROFILING

text: VIA

text: MIXTURE

text: MODELING

text: OF

text: RANKED

text: DATA

text: of

text: pre-experimental

text: information

text: in

text: the

text: analysis.

text: This

text: extension

text: could

text: beneﬁt

text: from

text: the

text: conjugacy

text: of

text: the

text: PL

text: with

text: the

text: Gamma

text: prior

text: distribution,

text: already

text: exploited

text: for

text: the

text: Bayesian

text: inference

text: in

text: (Guiver

text: and

text: Snelson,

text: and

text: (Caron

text: and

text: Doucet,

text: but

text: restricted

text: to

text: the

text: homogenous

text: population

text: case.

text: Another

text: interesting

text: direction

text: could

text: be

text: that

text: of

text: setting

text: up

text: a

text: ﬂexible

text: framework

text: to

text: integrate

text: the

text: use

text: of

text: mixed-type

text: (ordinal

text: and

text: quantitative)

text: data

text: with

text: the

text: possible

text: inclusion

text: of

text: individual

text: covariates.

text: Acknowledgements

label: section

text: We

text: are

text: deeply

text: grateful

text: to

text: Augusto

text: Amici

text: and

text: his

text: research

text: group

text: for

text: providing

text: LFPD

text: data

text: and

text: many

text: insightful

text: discussions

text: on

text: the

text: biological

text: foundations

text: of

text: the

text: experimental

text: outcomes.

text: We

text: also

text: thank

text: prof.

text: Thomas

text: Brendan

text: Murphy

text: and

text: Isobel

text: Claire

text: Gormley

text: for

text: providing

text: their

text: C

text: code

text: and

text: helpful

text: hints.

text: Appendix

text: We

text: prove

text: here

text: the

text: presence

text: of

text: distributions

text: on

text: orderings

text: in

text: our

text: novel

text: EPL

text: family

text: which

text: are

text: not

text: members

text: of

text: the

text: canonical

text: PL.

text: For

text: this

text: purpose,

text: let

text: us

text: remind

text: that

text: the

text: PL

text: implies

text: the

text: independence

text: of

text: irrelevant

text: alternatives

text: (IIA),

text: stating

text: that

text: the

text: probability

text: ratio

text: to

text: select

text: an

text: item

text: over

text: another

text: is

text: unaﬀected

text: by

text: the

text: preferences

text: towards

text: the

text: other

text: alternatives

text: in

text: the

text: choice

text: set,

text: see

text: (Luce,

text: Equivalently,

text: one

text: can

text: say

text: that

text: in

text: a

text: PL

text: the

text: choice

text: probability

text: ratio

text: between

text: two

text: items

text: is

text: constant

text: over

text: all

text: stages

text: as

text: long

text: as

text: such

text: alternatives

text: are

text: both

text: still

text: available.

text: In

text: the

text: K

text: case

text: the

text: IIA

text: lemma

text: translates

text: into

text: the

text: following

text: set

text: of

text: conditions

text: on

text: the

text: probabilities

text: q

text: P(π

text: of

text: each

text: possible

text: ordering

text: π

text: q

text: q

text: q

text: q

text: q

text: q

text: q

text: q

text: q

text: q

text: q

text: q

text: q

text: q

text: q

text: q

text: q

text: q

text: and

text: they

text: have

text: to

text: be

text: simultaneously

text: satisﬁed

text: for

text: a

text: generic

text: ranking

text: distribution

text: to

text: belong

text: to

text: the

text: forward

text: PL.

text: Now,

text: let

text: us

text: consider

text: the

text: EPL

text: with

text: ﬁxed

text: ρ

text: and

text: the

text: induced

text: probability

text: function

text: on

text: random

text: by

text: q

text: q

text: q

text: q

text: q

text: q

text: Substituting

text: in

text: and

text: solving

text: w.r.t.

text: p

text: one

text: obtains

text: as

text: unique

text: solution

text: p

text: meaning

text: that

text: the

text: two

text: model

text: classes

text: can

text: share

text: only

text: the

text: UM.

text: This

text: formally

text: shows

text: what

text: has

text: been

text: hinted

text: at

text: in

text: (Fligner

text: and

text: Verducci,

text: on

text: the

text: possibility

text: to

text: deﬁne

text: new

text: ranking

text: models

text: relaxing

text: the

text: forward

text: hypothesis.

text: To

text: give

text: an

text: intuition

text: about

text: the

text: types

text: of

text: ranking

text: distributions

text: that

text: are

text: not

text: covered

text: by

text: the

text: traditional

text: PL,

text: let

text: us

text: consider

text: the

text: EPL

text: with

text: parameter

text: conﬁguration

text: ρ

text: and

text: p

text: where

text: The

text: corresponding

text: probability

text: function

text: over

text: the

text: six

text: possible

text: orderings

text: has

text: two

text: equally

text: supported

text: modes

text: on

text: the

text: sequences

text: with

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Tables 27 Table 1. BIC values resulting from the MLE of the PL (ρ = 1 forward and ρ = backward reference order) and of the EPL on 2 the three disease groups for a diﬀerent number K of binding probes included in the ranking. Groups of patients are deﬁned as follows: HD = healthy, EBC = diagnosed with early stage breast cancer, and MBC = diagnosed with metastatic breast cancer. K = 11 K = 13 Model HD EBC MBC HD EBC MBC PL-ρ 694.04 776.13 499.46 899.63 1025.71 658.44 1 PL-ρ 685.85 804.61 498.67 894.44 1039.45 652.15 2 EPL 676.93 773.17 473.90 873.71 1026.61 630.05 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Tables

text: Table

text: BIC

label: caption

text: values

text: resulting

text: from

text: the

text: MLE

text: of

text: the

text: PL

text: (ρ

text: forward

text: and

text: ρ

text: backward

text: reference

text: order)

text: and

text: of

text: the

text: EPL

text: on

text: the

text: three

text: disease

text: groups

text: for

text: a

text: diﬀerent

text: number

text: K

text: of

text: binding

text: probes

text: included

text: in

text: the

text: ranking.

text: Groups

text: of

text: patients

text: are

text: deﬁned

text: as

text: follows:

text: HD

text: healthy,

text: EBC

text: diagnosed

text: with

text: early

text: stage

text: breast

text: cancer,

text: and

text: MBC

text: diagnosed

text: with

text: metastatic

text: breast

text: cancer.

text: K

label: table

text: K

text: Model

text: HD

text: EBC

text: MBC

text: HD

text: EBC

text: MBC

text: PL-ρ

text: PL-ρ

text: EPL

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 30 Tables Table 4. Correspondence between the model-based clustering de- rived by the MLE of the EPLmix and the true disease status of the LFPD experimental units: HD = healthy, EBC = diagnosed with early stage breast cancer and MBC = diagnosed with metastatic breast cancer. (a) K = 11 (b) K = 13 Group Group Disease Status 1 2 3 4 Disease Status 1 2 3 4 5 HD 0 2 10 8 HD 1 10 0 1 8 EBC 13 12 2 1 EBC 12 0 9 7 0 MBC 0 15 3 1 MBC 14 2 0 3 0 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Tables

text: Table

text: Correspondence

text: between

text: the

text: model-based

text: clustering

text: de-

text: rived

text: by

text: the

text: MLE

text: of

text: the

text: EPLmix

text: and

text: the

text: true

text: disease

text: status

text: of

text: the

text: LFPD

text: experimental

text: units:

text: HD

text: healthy,

text: EBC

text: diagnosed

text: with

text: early

text: stage

text: breast

text: cancer

text: and

text: MBC

text: diagnosed

text: with

text: metastatic

text: breast

text: cancer.

text: (a)

text: K

text: (b)

text: K

text: Group

text: Group

text: Disease

text: Status

text: Disease

text: Status

text: HD

text: HD

text: EBC

text: EBC

text: MBC

text: MBC

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: • Linked particles tend to have common friends. This is called the “clustering property”. • The degree distribution, that is, the distribution of the number of links of a given particle, is heavy-tailed, i.e. its survival probability has a power law decay. It is observed that in real-life networks the (power law) tail parameter τ is often between 1 and 2, for instance, for the movie actor network τ is estimated to be around 1.3. For more explicit examples we refer to [15]. Z A well studied model in the literature is the homogeneous long-range percolation model on d, ≥ Z ∈ Z d 1. In this model, the particles are the vertices of d. Any two particles x, y d are | − |− | − | → ∞ linked with probability p which behaves as λ x y α for x y . This model has xy ∈ by deﬁnition of p a local clustering property. Moreover, if α (d, 2d) the graph distance xy ∈ Z between x, y d, that is, the minimal number of links that connect x and y, behaves roughly | − | | − | → ∞ as (log x y )1/log2(2d/α) as x y , see [8]. This behavior can be interpreted as a version of the small-world eﬀect. But homogeneous long-range percolation does not fulﬁll the stylized fact of having a heavy-tailed degree distribution. Therefore, [13] introduced the inhomogeneous Z long-range percolation model (also known as scale-free percolation model) on d which extends the homogeneous model in such a way that the degree distribution turns out to be heavy-tailed. ∈ Z In the inhomogeneous long-range percolation model one assigns to each particle x d a positive random weight W whose distribution is heavy-tailed with tail parameter β > 0. These weights x make particles more or less attractive, i.e. if a given particle x has a large weight W then it plays x ∈ Z the role of a hub in the network. Given these weights, two particles x, y d are then linked with | − |− | − | { } probability p which is approximately λW W x y α for large x y . For min α, βα > d xy x y the degree distribution is heavy-tailed with tail parameter τ = βα/d > 1, see Theorem 2.2 in [13]. Hence, this model fulﬁlls the stylized fact of having a heavy-tailed degree distribution. For ∈ real-life applications the interesting case is τ = βα/d (1, 2), and in this case, if in addition ∈ Z | − | | − | → ∞ α > d, the graph distance between x, y d is of order log log x y as x y , see [13] and Theorem 8 below. This is again a version of the small-world eﬀect. One goal of this paper is to complement the picture about graph distances of [13] by providing analogous results to [6, 8, 9, 21] for inhomogeneous long-range percolation. In homogeneous long-range percolation it is known that there is a critical constant λ = λ (α, d) c c such that there is an inﬁnite connected component of particles for λ > λ and there is no such c Z component for λ < λ , i.e. in the former case there is an inﬁnite connected network in d. This c phase transition picture in homogeneous long-range percolation can be traced back to the work of [2, 18, 20]. Later work concentrated more on the geometrical properties of percolation like graph distances, see [4, 8, 9, 12, 21]. A good overview of the literature for long-range percolation ≤ is provided in [8, 10]. For homogeneous long-range percolation it is known that for α d there is an inﬁnite connected component for all λ > 0, and therefore λ = 0. This inﬁnite connected c Z component contains all particles of d, a.s., i.e. in that case we have a completely connected Z ∈ network of all particles of d. The case α (d, 2d) is treated in [5]. In that case there is no 2

text: Linked

text: particles

text: tend

text: to

text: have

text: common

text: friends.

text: This

text: is

text: called

text: the

text: “clustering

text: property”.

text: The

text: degree

text: distribution,

text: that

text: is,

text: the

text: distribution

text: of

text: the

text: number

text: of

text: links

text: of

text: a

text: given

text: particle,

text: is

text: heavy-tailed,

text: i.e.

text: its

text: survival

text: probability

text: has

text: a

text: power

text: law

text: decay.

text: It

text: is

text: observed

text: that

text: in

text: real-life

text: networks

text: the

text: (power

text: law)

text: tail

text: parameter

text: τ

text: is

text: often

text: between

text: and

text: for

text: instance,

text: for

text: the

text: movie

text: actor

text: network

text: τ

text: is

text: estimated

text: to

text: be

text: around

text: For

text: more

text: explicit

text: examples

text: we

text: refer

text: to

text: Z

text: A

text: well

text: studied

text: model

text: in

text: the

text: literature

text: is

text: the

text: homogeneous

text: long-range

text: percolation

text: model

text: on

text: d,

text: Z

text: Z

text: d

text: In

text: this

text: model,

text: the

text: particles

text: are

text: the

text: vertices

text: of

text: d.

text: Any

text: two

text: particles

text: x,

text: y

text: d

text: are

text: linked

text: with

text: probability

text: p

text: which

text: behaves

text: as

text: λ

text: x

text: y

text: α

text: for

text: x

text: y

text: This

text: model

text: has

text: xy

text: by

text: deﬁnition

text: of

text: p

text: a

text: local

text: clustering

text: property.

text: Moreover,

text: if

text: α

text: (d,

text: the

text: graph

text: distance

text: xy

text: Z

text: between

text: x,

text: y

text: d,

text: that

text: is,

text: the

text: minimal

text: number

text: of

text: links

text: that

text: connect

text: x

text: and

text: y,

text: behaves

text: roughly

text: as

text: (log

text: x

text: y

text: as

text: x

text: y

text: see

text: This

text: behavior

text: can

text: be

text: interpreted

text: as

text: a

text: version

text: of

text: the

text: small-world

text: eﬀect.

text: But

text: homogeneous

text: long-range

text: percolation

text: does

text: not

text: fulﬁll

text: the

text: stylized

text: fact

text: of

text: having

text: a

text: heavy-tailed

text: degree

text: distribution.

text: Therefore,

text: introduced

text: the

text: inhomogeneous

text: Z

text: long-range

text: percolation

text: model

text: (also

text: known

text: as

text: scale-free

text: percolation

text: model)

text: on

text: d

text: which

text: extends

text: the

text: homogeneous

text: model

text: in

text: such

text: a

text: way

text: that

text: the

text: degree

text: distribution

text: turns

text: out

text: to

text: be

text: heavy-tailed.

text: Z

text: In

text: the

text: inhomogeneous

text: long-range

text: percolation

text: model

text: one

text: assigns

text: to

text: each

text: particle

text: x

text: d

text: a

text: positive

text: random

text: weight

text: W

text: whose

text: distribution

text: is

text: heavy-tailed

text: with

text: tail

text: parameter

text: β

text: These

text: weights

text: x

text: make

text: particles

text: more

text: or

text: less

text: attractive,

text: i.e.

text: if

text: a

text: given

text: particle

text: x

text: has

text: a

text: large

text: weight

text: W

text: then

text: it

text: plays

text: x

text: Z

text: the

text: role

text: of

text: a

text: hub

text: in

text: the

text: network.

text: Given

text: these

text: weights,

text: two

text: particles

text: x,

text: y

text: d

text: are

text: then

text: linked

text: with

text: probability

text: p

text: which

text: is

text: approximately

text: λW

text: W

text: x

text: y

text: α

text: for

text: large

text: x

text: y

text: For

text: min

text: α,

text: βα

text: d

text: xy

text: x

text: y

text: the

text: degree

text: distribution

text: is

text: heavy-tailed

text: with

text: tail

text: parameter

text: τ

text: βα/d

text: see

text: Theorem

text: in

text: Hence,

text: this

text: model

text: fulﬁlls

text: the

text: stylized

text: fact

text: of

text: having

text: a

text: heavy-tailed

text: degree

text: distribution.

text: For

text: real-life

text: applications

text: the

text: interesting

text: case

text: is

text: τ

text: βα/d

text: and

text: in

text: this

text: case,

text: if

text: in

text: addition

text: Z

text: α

text: d,

text: the

text: graph

text: distance

text: between

text: x,

text: y

text: d

text: is

text: of

text: order

text: log

text: log

text: x

text: y

text: as

text: x

text: y

text: see

text: and

text: Theorem

text: below.

text: This

text: is

text: again

text: a

text: version

text: of

text: the

text: small-world

text: eﬀect.

text: One

text: goal

text: of

text: this

text: paper

text: is

text: to

text: complement

text: the

text: picture

text: about

text: graph

text: distances

text: of

text: by

text: providing

text: analogous

text: results

text: to

text: for

text: inhomogeneous

text: long-range

text: percolation.

text: In

text: homogeneous

text: long-range

text: percolation

text: it

text: is

text: known

text: that

text: there

text: is

text: a

text: critical

text: constant

text: λ

text: λ

text: (α,

text: d)

text: c

text: c

text: such

text: that

text: there

text: is

text: an

text: inﬁnite

text: connected

text: component

text: of

text: particles

text: for

text: λ

text: λ

text: and

text: there

text: is

text: no

text: such

text: c

text: Z

text: component

text: for

text: λ

text: λ

text: i.e.

text: in

text: the

text: former

text: case

text: there

text: is

text: an

text: inﬁnite

text: connected

text: network

text: in

text: d.

text: This

text: c

text: phase

text: transition

text: picture

text: in

text: homogeneous

text: long-range

text: percolation

text: can

text: be

text: traced

text: back

text: to

text: the

text: work

text: of

text: Later

text: work

text: concentrated

text: more

text: on

text: the

text: geometrical

text: properties

text: of

text: percolation

text: like

text: graph

text: distances,

text: see

text: A

text: good

text: overview

text: of

text: the

text: literature

text: for

text: long-range

text: percolation

text: is

text: provided

text: in

text: For

text: homogeneous

text: long-range

text: percolation

text: it

text: is

text: known

text: that

text: for

text: α

text: d

text: there

text: is

text: an

text: inﬁnite

text: connected

text: component

text: for

text: all

text: λ

text: and

text: therefore

text: λ

text: This

text: inﬁnite

text: connected

text: c

text: Z

text: component

text: contains

text: all

text: particles

text: of

text: d,

text: a.s.,

text: i.e.

text: in

text: that

text: case

text: we

text: have

text: a

text: completely

text: connected

text: Z

text: network

text: of

text: all

text: particles

text: of

text: d.

text: The

text: case

text: α

text: (d,

text: is

text: treated

text: in

text: In

text: that

text: case

text: there

text: is

text: no


text: exactly the occupied edges in this coupling (note that the exponential distribution (4) is absolutely continuous). This implies for (cid:96) = λ P |C | ∞ | | ∞ θ(λ, α) = [ (0) = ] = P [ C (0) = ] . λ (cid:2) (cid:3) By countable subadditivity of P and the increasing property of C (0) in (cid:96) we have (cid:96) (cid:48) | | ∞ (cid:48) lim θ(λ , α) = P C (cid:48)(0) = for some λ < λ . (cid:48)↑ λ λ λ {| | ∞ (cid:48) } ⊂ {| | ∞} Moreover, the increasing property of C (0) in (cid:96) provides C (cid:48)(0) = for some λ < λ C (0) = . (cid:2) (cid:96) λ (cid:3) λ Therefore, to prove (3) it suﬃces to show that {| | ∞ (cid:48) } ∩ {| | ∞} P C (cid:48)(0) < for all λ < λ C (0) = = 0. λ λ ∈ Choose λ (λ , λ). Since there is a unique inﬁnite cluster for λ > λ , a.s., there exists an inﬁnite cluster 0 c 0 c ⊂ {| | ∞} C C (0) on the set C (0) = . If the origin belongs to C then the proof is done. Otherwise, because λ0 λ λ λ0 C is a subgraph of C (0), there exists a ﬁnite path π of λ-open edges connecting the origin with an edge in C . λ0 λ ∈ λ0 By the deﬁnition of λ-open edges we have φ < λ for all edges (x, y) π. Since π is ﬁnite we obtain the strict (x,y)(cid:48) ∈ ∨ | | ∞ inequality λ = max ∈ φ < λ. Choose λ (λ λ , λ) and it follows that C (cid:48)(0) = . This completes 1 (x,y) π (x,y) 0 1 λ the proof for the left-continuity in λ. (cid:55)→ ≥ (iii) Finally, we need to prove right-continuity of λ θ(λ, α) on λ λ . For integers n > 1 we consider the boxes c − {C ∩ (cid:54) ∅} Λ = [ n, n]d centered at the origin, see also Corollary 7. We deﬁne the events A = (0) Λc = , i.e., the n C − n n connected component (0) of the origin leaves the box Λ = [ n, n]d. Note that θ(λ, α) is the decreasing limit n P → ∞ P P P of [A ] as n . Therefore, it suﬃces to show that [A ] is a continuous function in λ. We write = to n n λ C indicate on which parameter λ the probability law depends. We again denote by (0) the connected component n of the origin connected within box Λ , see Corollary 7. Then, we have n {C ∩ (cid:54) ∅} {C ⇔ } A = (0) Λc = = (0) Λc . n n n n ∈ (cid:48) ∈ − (cid:48) Choose δ (0, λ), then we have for all λ (λ δ , λ + δ ) and all n > n 0 0 0 |P [A ] − P (cid:48) [A ]| = |P [C (0) ⇔ Λc ] − P (cid:48) [C (0) ⇔ Λc ]| λ n λ n λ n n λ n n ≤ |P [C (0) ⇔ (Λc ∩ Λ (cid:48))] − P (cid:48) [C (0) ⇔ (Λc ∩ Λ (cid:48))]| λ n n n λ n n n +2 P [C (0) ⇔ Λc(cid:48)] λ+δ0 n n ≤ |P [C (0) ⇔ (Λc ∩ Λ (cid:48))] − P (cid:48) [C (0) ⇔ (Λc ∩ Λ (cid:48))]| λ n n n λ n n n + 2(2n + 1)d sup P [x ⇔ Λc(cid:48)] . (5) ∈ λ+δ0 n x Λn We bound the two terms on the right-hand side of (5). (cid:48) ∈ (a) First we prove that for all ε > 0 there exists n > n such that for all x Λ n P [x ⇔ Λc(cid:48)] < ε(2n + 1)−d/4. (6) λ+δ0 n This is done as follows. For m > n we deﬁne the following events { ⇔ } { ⇔ \ } L = x ∂Λ = x (Λ Λ ) . m m+1 (cid:91)m+1 m (cid:48) This implies for n > n that { ⇔ } E (cid:48) d=ef. x Λc(cid:48) = L . n n m ≥ (cid:48) (cid:48) (cid:34) m n (cid:35)    Moreover, note that E (cid:48) is decreasing in n , (cid:92) (cid:92) (cid:91) n    P P P P lim sup [E (cid:48)] = lim [E (cid:48)] = E (cid:48) = L . n(cid:48)→∞ λ+δ0 n n(cid:48)→∞ λ+δ0 n λ+δ0 (cid:48) n λ+δ0 (cid:48) ≥ (cid:48) m n >n n >n m n 13

text: exactly

text: the

text: occupied

text: edges

text: in

text: this

text: coupling

text: (note

text: that

text: the

text: exponential

text: distribution

text: is

text: absolutely

text: continuous).

text: This

text: implies

text: for

text: λ

text: P

text: |C

text: θ(λ,

text: α)

text: P

text: C

text: λ

text: By

text: countable

text: subadditivity

text: of

text: P

text: and

text: the

text: increasing

text: property

text: of

text: C

text: in

text: we

text: have

text: lim

text: θ(λ

text: α)

text: P

text: C

text: for

text: some

text: λ

text: λ

text: λ

text: λ

text: λ

text: Moreover,

text: the

text: increasing

text: property

text: of

text: C

text: in

text: provides

text: C

text: for

text: some

text: λ

text: λ

text: C

text: λ

text: λ

text: Therefore,

text: to

text: prove

text: it

text: suﬃces

text: to

text: show

text: that

text: P

text: C

text: for

text: all

text: λ

text: λ

text: C

text: λ

text: λ

text: Choose

text: λ

text: (λ

text: λ).

text: Since

text: there

text: is

text: a

text: unique

text: inﬁnite

text: cluster

text: for

text: λ

text: λ

text: a.s.,

text: there

text: exists

text: an

text: inﬁnite

text: cluster

text: c

text: c

text: C

text: C

text: on

text: the

text: set

text: C

text: If

text: the

text: origin

text: belongs

text: to

text: C

text: then

text: the

text: proof

text: is

text: done.

text: Otherwise,

text: because

text: λ0

text: λ

text: λ

text: λ0

text: C

text: is

text: a

text: subgraph

text: of

text: C

text: there

text: exists

text: a

text: ﬁnite

text: path

text: π

text: of

text: λ-open

text: edges

text: connecting

text: the

text: origin

text: with

text: an

text: edge

text: in

text: C

text: λ0

text: λ

text: λ0

text: By

text: the

text: deﬁnition

text: of

text: λ-open

text: edges

text: we

text: have

text: φ

text: λ

text: for

text: all

text: edges

text: (x,

text: y)

text: π.

text: Since

text: π

text: is

text: ﬁnite

text: we

text: obtain

text: the

text: strict

text: inequality

text: λ

text: max

text: φ

text: λ.

text: Choose

text: λ

text: (λ

text: λ

text: λ)

text: and

text: it

text: follows

text: that

text: C

text: This

text: completes

text: (x,y)

text: π

text: (x,y)

text: λ

text: the

text: proof

text: for

text: the

text: left-continuity

text: in

text: λ.

text: (iii)

text: Finally,

text: we

text: need

text: to

text: prove

text: right-continuity

text: of

text: λ

text: θ(λ,

text: α)

text: on

text: λ

text: λ

text: For

text: integers

text: n

text: we

text: consider

text: the

text: boxes

text: c

text: {C

text: Λ

text: n,

text: n]d

text: centered

text: at

text: the

text: origin,

text: see

text: also

text: Corollary

text: We

text: deﬁne

text: the

text: events

text: A

text: Λc

text: i.e.,

text: the

text: n

text: C

text: n

text: n

text: connected

text: component

text: of

text: the

text: origin

text: leaves

text: the

text: box

text: Λ

text: n,

text: n]d.

text: Note

text: that

text: θ(λ,

text: α)

text: is

text: the

text: decreasing

text: limit

text: n

text: P

text: P

text: P

text: P

text: of

text: [A

text: as

text: n

text: Therefore,

text: it

text: suﬃces

text: to

text: show

text: that

text: [A

text: is

text: a

text: continuous

text: function

text: in

text: λ.

text: We

text: write

text: to

text: n

text: n

text: λ

text: C

text: indicate

text: on

text: which

text: parameter

text: λ

text: the

text: probability

text: law

text: depends.

text: We

text: again

text: denote

text: by

text: the

text: connected

text: component

text: n

text: of

text: the

text: origin

text: connected

text: within

text: box

text: Λ

text: see

text: Corollary

text: Then,

text: we

text: have

text: n

text: {C

text: {C

text: A

text: Λc

text: Λc

text: n

text: n

text: n

text: n

text: Choose

text: δ

text: λ),

text: then

text: we

text: have

text: for

text: all

text: λ

text: (λ

text: δ

text: λ

text: δ

text: and

text: all

text: n

text: n

text: |P

text: [A

text: P

text: [A

text: |P

text: [C

text: Λc

text: P

text: [C

text: Λc

text: λ

text: n

text: λ

text: n

text: λ

text: n

text: n

text: λ

text: n

text: n

text: |P

text: [C

text: (Λc

text: Λ

text: P

text: [C

text: (Λc

text: Λ

text: λ

text: n

text: n

text: n

text: λ

text: n

text: n

text: n

text: P

text: [C

text: λ+δ0

text: n

text: n

text: |P

text: [C

text: (Λc

text: Λ

text: P

text: [C

text: (Λc

text: Λ

text: λ

text: n

text: n

text: n

text: λ

text: n

text: n

text: n

text: sup

text: P

text: [x

text: λ+δ0

text: n

text: x

text: Λn

text: We

text: bound

text: the

text: two

text: terms

text: on

text: the

text: right-hand

text: side

text: of

text: (a)

text: First

text: we

text: prove

text: that

text: for

text: all

text: ε

text: there

text: exists

text: n

text: n

text: such

text: that

text: for

text: all

text: x

text: Λ

text: n

text: P

text: [x

text: λ+δ0

text: n

text: This

text: is

text: done

text: as

text: follows.

text: For

text: m

text: n

text: we

text: deﬁne

text: the

text: following

text: events

text: L

text: x

text: ∂Λ

text: x

text: (Λ

text: Λ

text: m

text: m

text: This

text: implies

text: for

text: n

text: n

text: that

text: E

text: d=ef.

text: x

text: L

text: n

text: n

text: m

text: m

text: n

text: Moreover,

text: note

text: that

text: E

text: is

text: decreasing

text: in

text: n

text: n

text: P

text: P

text: P

text: P

text: lim

text: sup

text: [E

text: lim

text: [E

text: E

text: L

text: λ+δ0

text: n

text: λ+δ0

text: n

text: λ+δ0

text: n

text: λ+δ0

text: m

text: n

text: >n

text: n

text: >n

text: m

text: n


text: [14] J. Ding and A. Sly. Distances in critical long range percolation. arXiv:1303.3995, 2013. [15] R. Durrett. Random Graph Dynamics. Cambridge University Press, 2007. [16] G. R. Grimmett. Percolation. Springer, 2nd edition, 1999. [17] T. Hara and G. Slade. Mean-ﬁeld critical behavior for percolation in high dimensions. Comm. Math. Phys., 128(2):333–391, 1990. | − | [18] C. M. Newman and L. S. Schulman. One dimensional 1/ j i s percolation models: the ≤ existence of a transition for s 2. Comm. Math. Phys., 104(4):547–571, 1986. [19] M. E. J. Newman, D. J. Watts, and S. H. Strogatz. Random graph models of social networks. Proc. Natl. Acad. Sci., 99:2566–2572, 2002. [20] L. S. Schulman. Long-range percolation in one dimension. J. Phys. A, 16(17):L639–L641, 1983. [21] P. Trapman. The growth of the inﬁnite long-range percolation cluster. Ann. Probab., 38(4):1583–1608, 2010. [22] J. Van den Berg and M. Keane. On the continuity of the percolation probability function. Contemp. Math., 26:61–65, 1984. [23] D. J. Watts. Six Degrees: The Science of a Connected Age. W.W. Norton, 2003. 19

label: reference

text: J.

text: Ding

text: and

text: A.

text: Sly.

text: Distances

text: in

text: critical

text: long

text: range

text: percolation.

text: R.

text: Durrett.

text: Random

text: Graph

text: Dynamics.

text: Cambridge

text: University

text: Press,

text: G.

text: R.

text: Grimmett.

text: Percolation.

text: Springer,

text: edition,

text: T.

text: Hara

text: and

text: G.

text: Slade.

text: Mean-ﬁeld

text: critical

text: behavior

text: for

text: percolation

text: in

text: high

text: dimensions.

text: Comm.

text: Math.

text: Phys.,

text: C.

text: M.

text: Newman

text: and

text: L.

text: S.

text: Schulman.

text: One

text: dimensional

text: j

text: i

text: s

text: percolation

text: models:

text: the

text: existence

text: of

text: a

text: transition

text: for

text: s

text: Comm.

text: Math.

text: Phys.,

text: M.

text: E.

text: J.

text: Newman,

text: D.

text: J.

text: Watts,

text: and

text: S.

text: H.

text: Strogatz.

text: Random

text: graph

text: models

text: of

text: social

text: networks.

text: Proc.

text: Natl.

text: Acad.

text: Sci.,

text: L.

text: S.

text: Schulman.

text: Long-range

text: percolation

text: in

text: one

text: dimension.

text: J.

text: Phys.

text: A,

text: P.

text: Trapman.

text: The

text: growth

text: of

text: the

text: inﬁnite

text: long-range

text: percolation

text: cluster.

text: Ann.

text: Probab.,

text: J.

text: Van

text: den

text: Berg

text: and

text: M.

text: Keane.

text: On

text: the

text: continuity

text: of

text: the

text: percolation

text: probability

text: function.

text: Contemp.

text: Math.,

text: D.

text: J.

text: Watts.

text: Six

text: Degrees:

text: The

text: Science

text: of

text: a

text: Connected

text: Age.

text: W.W.

text: Norton,


text: | · | For we choose the Euclidean norm. If there is an occupied edge between x and y we write ⇔ ↔ x y; if there is a ﬁnite connected path of occupied edges between x and y we write x y { ⇔ } ⊂ { ↔ } and we say that x and y are connected. Clearly x y x y . We deﬁne the cluster of ∈ Z x d to be the connected component C { ∈ Z ↔ } (x) = y d; x y . C Our aim is to study the size of the cluster (x) and to investigate its percolation properties as (cid:55)→ a function of λ > 0 and α > 0, that is, as a function of the edge probabilities (λ, α) p = xy C ∈ Z p (λ, α). Note that (x) exactly denotes all particles y d which can be reached within the xy network whose links are described by the occupied edges. The percolation probability is deﬁned by P |C | ∞ θ(λ, α) = [ (0) = ] . This is non-decreasing in λ and non-increasing in α. For given α > 0, the critical value λ (α) is c deﬁned as { } λ = λ (α) = inf λ > 0; θ(λ, α) > 0 . c c Note that θ(λ, α) and λ (α) also depend on β, but this parameter will be kept ﬁxed. c (cid:104) (cid:105) { } ≤ Trivial case. For min α, βα d, we have λ = 0. This comes from the fact that for any λ > 0 c P |{ ∈ Z ⇔ }| ∞ y d; 0 y = = 1, see Theorem 2.1 in [13]. This says that the degree distribution of a given vertex is inﬁnite, a.s., and therefore there is an inﬁnite connected component, a.s. For this reason we only consider the { } non-trivial case min α, βα > d (where a phase transition may occur). In this latter case the degree distribution is heavy-tailed with tail parameter τ = βα/d > 1, see Theorem 2.2 of [13]. ≥ { } Theorem 1 (upper bounds) Fix d 1. Assume min α, βα > d. ≥ ∞ (a) If d 2, then λ < . c ∈ ∞ (b) If d = 1 and α (1, 2], then λ < . c { } ∞ (c) If d = 1 and min α, βα > 2, then λ = . c ≥ Since W 1 , a.s., the edge probability stochastically dominates a conﬁguration with indepen- x − − | − |− dent edges being occupied with probabilities 1 exp( λ x y α). The latter is the homogeneous Z ≥ long-range percolation model on d and it is well known that this model percolates (for d 2 ∈ see [5]; for d = 1 and α (1, 2] see [18]). For part (c) of the theorem we refer to Theorem 3.1 of [13]. The next theorem follows from Theorems 4.2 and 4.4 of [13]. ≥ { } Theorem 2 (lower bounds) Fix d 1. Assume min α, βα > d. (a) If βα < 2d, then λ = 0. c (b) If βα > 2d, then λ > 0. c 4

text: For

text: we

text: choose

text: the

text: Euclidean

text: norm.

text: If

text: there

text: is

text: an

text: occupied

text: edge

text: between

text: x

text: and

text: y

text: we

text: write

text: x

text: y;

text: if

text: there

text: is

text: a

text: ﬁnite

text: connected

text: path

text: of

text: occupied

text: edges

text: between

text: x

text: and

text: y

text: we

text: write

text: x

text: y

text: and

text: we

text: say

text: that

text: x

text: and

text: y

text: are

text: connected.

text: Clearly

text: x

text: y

text: x

text: y

text: We

text: deﬁne

text: the

text: cluster

text: of

text: Z

text: x

text: d

text: to

text: be

text: the

text: connected

text: component

text: C

text: Z

text: (x)

text: y

text: d;

text: x

text: y

text: C

text: Our

text: aim

text: is

text: to

text: study

text: the

text: size

text: of

text: the

text: cluster

text: (x)

text: and

text: to

text: investigate

text: its

text: percolation

text: properties

text: as

text: a

text: function

text: of

text: λ

text: and

text: α

text: that

text: is,

text: as

text: a

text: function

text: of

text: the

text: edge

text: probabilities

text: (λ,

text: α)

text: p

text: xy

text: C

text: Z

text: p

text: (λ,

text: α).

text: Note

text: that

text: (x)

text: exactly

text: denotes

text: all

text: particles

text: y

text: d

text: which

text: can

text: be

text: reached

text: within

text: the

text: xy

text: network

text: whose

text: links

text: are

text: described

text: by

text: the

text: occupied

text: edges.

text: The

text: percolation

text: probability

text: is

text: deﬁned

text: by

text: P

text: |C

text: θ(λ,

text: α)

text: This

text: is

text: non-decreasing

text: in

text: λ

text: and

text: non-increasing

text: in

text: α.

text: For

text: given

text: α

text: the

text: critical

text: value

text: λ

text: (α)

text: is

text: c

text: deﬁned

text: as

text: λ

text: λ

text: (α)

text: inf

text: λ

text: θ(λ,

text: α)

text: c

text: c

text: Note

text: that

text: θ(λ,

text: α)

text: and

text: λ

text: (α)

text: also

text: depend

text: on

text: β,

text: but

text: this

text: parameter

text: will

text: be

text: kept

text: ﬁxed.

text: c

text: Trivial

text: case.

text: For

text: min

text: α,

text: βα

text: d,

text: we

text: have

text: λ

text: This

text: comes

text: from

text: the

text: fact

text: that

text: for

text: any

text: λ

text: c

text: P

text: Z

text: y

text: d;

text: y

text: see

text: Theorem

text: in

text: This

text: says

text: that

text: the

text: degree

text: distribution

text: of

text: a

text: given

text: vertex

text: is

text: inﬁnite,

text: a.s.,

text: and

text: therefore

text: there

text: is

text: an

text: inﬁnite

text: connected

text: component,

text: a.s.

text: For

text: this

text: reason

text: we

text: only

text: consider

text: the

text: non-trivial

text: case

text: min

text: α,

text: βα

text: d

text: (where

text: a

text: phase

text: transition

text: may

text: occur).

text: In

text: this

text: latter

text: case

text: the

text: degree

text: distribution

text: is

text: heavy-tailed

text: with

text: tail

text: parameter

text: τ

text: βα/d

text: see

text: Theorem

text: of

text: Theorem

text: (upper

text: bounds)

text: Fix

text: d

text: Assume

text: min

text: α,

text: βα

text: d.

text: (a)

text: If

text: d

text: then

text: λ

text: c

text: (b)

text: If

text: d

text: and

text: α

text: then

text: λ

text: c

text: (c)

text: If

text: d

text: and

text: min

text: α,

text: βα

text: then

text: λ

text: c

text: Since

text: W

text: a.s.,

text: the

text: edge

text: probability

text: stochastically

text: dominates

text: a

text: conﬁguration

text: with

text: indepen-

text: x

text: dent

text: edges

text: being

text: occupied

text: with

text: probabilities

text: exp(

text: λ

text: x

text: y

text: α).

text: The

text: latter

text: is

text: the

text: homogeneous

text: Z

text: long-range

text: percolation

text: model

text: on

text: d

text: and

text: it

text: is

text: well

text: known

text: that

text: this

text: model

text: percolates

text: (for

text: d

text: see

text: for

text: d

text: and

text: α

text: see

text: For

text: part

text: (c)

text: of

text: the

text: theorem

text: we

text: refer

text: to

text: Theorem

text: of

text: The

text: next

text: theorem

text: follows

text: from

text: Theorems

text: and

text: of

text: Theorem

text: (lower

text: bounds)

text: Fix

text: d

text: Assume

text: min

text: α,

text: βα

text: d.

text: (a)

text: If

text: βα

text: then

text: λ

text: c

text: (b)

text: If

text: βα

text: then

text: λ

text: c