text: Topological Spin Texture in a Quantum Anomalous Hall Insulator ∗ Jiansheng Wu,1 Jie Liu,1 and Xiong-Jun Liu 1,2,3 1Department of Physics, Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong, China 2International Center for Quantum Materials and School of Physics, Peking University, Beijing 100871, China 3Department of Physics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA (Dated: May 26, 2020) The quantum anomalous Hall (QAH) eﬀect has been recently discovered in experiment using thin-ﬁlm topological insulator with ferromagnetic ordering and strong spin-orbit coupling. Here we investigate the spin degree of freedom of a QAH insulator and uncover a fundamental phenomenon that the edge states exhibit topologically stable spin texture in the boundary when a chiral-like symmetry is present. This result shows that edge states are chiral in both the orbital and spin degrees of freedom, and the chiral edge spin texture corresponds to the bulk topological states of the QAH insulator. We also study the potential applications of the edge spin texture in designing topological-state-based spin devices which might be applicable to future spintronic technologies. Discovery of the quantum Hall eﬀect in 1980s brought takes the (cid:20)simple (2 + 1)D Dirac form (cid:21) about a fundamental concept, topological state of quan- tum matter, to condensed matter physics [1, 2]. In the H m + 2B(k2 + k2) 2A k + i2A k quantum Hall eﬀect an external magnetic ﬁeld drives the (k) = z − x y − 1−y 2 x , (1) 2A k i2A k m 2B(k2 + k2) electrons to ﬁll in discrete Landau levels. This leads to a 1 y 2 x z x y gap in the two-dimensional (2D) bulk, while the bound- ary exhibits 1D chiral gapless edge states. The Hall con- where for the realization with thin-ﬁlm FM topologi- ductance in the integer quantum Hall eﬀect is quantized cal insulators [10, 14] m depends on the Zeeman term z by Chern numbers, which are integers and characterize induced by the FM order, the B-term characterizes the the topology of the system [3]. The topological inter- hybridization between top and bottom thin-ﬁlm surfaces, pretation of the quantized Hall conductance implies that and 2A equal Fermi velocities of the surface Dirac 1,2 to obtain a quantum Hall state does not necessitate an cones of the parent topological insulator [15, 16]. The external magnetic ﬁeld. The theoretical idea for quan- QAH phase is obtained when m B < 0, with the Chern z tum Hall eﬀect without Landau levels, i.e. the quantum number C = sgn(m A A ) [10, 17]. In the solid-state 1 z 1 2 anomalous Hall (QAH) eﬀect, was ﬁrst introduced by experiment, the Cr-doped (Bi − Sb ) Te was used to 1 x x 2 3 Haldane in a honeycomb lattice over two decades ago [4]. achieve the above Hamiltonian and the QAH phase [14]. The recent interests in this topological state have been re- On the other hand, this model can also be realized in vived due to the great developments in the time-reversal- a square optical lattice [18] with SO coupling generated invariant topological insulators [5, 6], with many new the- based on the cold atom experiments [19–22]. | | | | oretical proposals having been introduced [7–13]. Impor- In the typical isotropic case A = A a chiral-like M 1 2 tantly, following the proposal in Ref. [10], the QAH state symmetry S = σ emerges in the Hamiltonian, ⊥ (cid:126)n1 (cid:126)n2 has been detected in a recent experiment using ferromag- with (cid:126)n (cid:126)n being arbitrary 2D orthogonal unit vec- 1 2 M netic (FM) thin-ﬁlm topological insulator by observing tors in the x-y plane. Here σ and represent the (cid:126)n1 (cid:126)n2 the quantized Hall conductance [14]. (cid:126)n -component of the Pauli matrix acting on the spin 1 space and the spatial reﬂection along the (cid:126)n direction, While in QAH eﬀect the spin is generically not con- 2 respectively. The symmetry transforms the fermion op- served, the recent experimental realization based on † † strongly spin-orbit (SO) coupled materials [14] motivates erat↑ors↓ via S(c(cid:48) ks, cks)T −= (σ(cid:126)n2)ss(cid:48)(ck(cid:48)s(cid:48), ck(cid:48)s(cid:48))T , with us to explore the spin degree of freedom of such QAH s = , , and k = (kn1, kn2). One can v†erify for the insulators. We show surprisingly that the edge states ex- second quantization Hamiltonian that SHS =HH, w†hile hibit topologically stable spin texture in the boundary t−hHe ﬁrst quantization Hamiltonian satisﬁes S (k)S = when a chiral-like symmetry is present, and such chi- (k(cid:80)). Consider two edges normal to (cid:126)n1 axis and we ral edge spin texture corresponds to the bulk topological can reexpress the Hamiltonian as a summation of 1D states of the QAH insulator. The potential applications Hamiltonian with ﬁxed momentum kn2 along the edge: of the edge spin texture are studie(cid:80)d. H = kn2 H1D(kˆn2), where (cid:26)(cid:2) (cid:3) The minimal model for the QAH insulator is described †H by a two-band Hamiltonian H = ψ (k)ψ , where − † (cid:27) k k k H H (k ) = dx ψ 2B∂2 + m(k ) σ the spin basis ψk = (ck↑, ck↓)T . Around the Γ point (k) 1D n2 n1 kn2,xn1 xn1 n2 z − +iA ∂ σ A k σ ψ , (2) 1 xn1 n2 2 n2 n1 kn2,xn1 ∗ Corresponding author: xiongjunliu@pku.edu.cn ##LTLine##

text: Topological

label: title

text: Spin

text: Texture

text: in

text: a

text: Quantum

text: Anomalous

text: Hall

text: Insulator

label: author

text: Jiansheng

text: Jie

text: and

text: Xiong-Jun

text: Liu

text: of

text: Physics,

text: Hong

text: Kong

text: University

text: of

text: Science

text: and

text: Technology,

text: Clear

text: Water

text: Bay,

text: Hong

text: Kong,

text: China

text: Center

text: for

text: Quantum

text: Materials

text: and

text: School

text: of

text: Physics,

text: Peking

text: University,

text: Beijing

text: China

text: of

text: Physics,

text: Massachusetts

text: Institute

text: of

text: Technology,

text: Cambridge,

text: Massachusetts

text: USA

text: (Dated:

text: May

label: date

text: The

text: quantum

text: anomalous

text: Hall

text: (QAH)

text: eﬀect

text: has

text: been

text: recently

text: discovered

text: in

text: experiment

text: using

text: thin-ﬁlm

text: topological

text: insulator

text: with

text: ferromagnetic

text: ordering

text: and

text: strong

text: spin-orbit

text: coupling.

text: Here

text: we

text: investigate

text: the

text: spin

text: degree

text: of

text: freedom

text: of

text: a

text: QAH

text: insulator

text: and

text: uncover

text: a

text: fundamental

text: phenomenon

text: that

text: the

text: edge

text: states

text: exhibit

text: topologically

text: stable

text: spin

text: texture

text: in

text: the

text: boundary

text: when

text: a

text: chiral-like

text: symmetry

text: is

text: present.

text: This

text: result

text: shows

text: that

text: edge

text: states

text: are

text: chiral

text: in

text: both

text: the

text: orbital

text: and

text: spin

text: degrees

text: of

text: freedom,

text: and

text: the

text: chiral

text: edge

text: spin

text: texture

text: corresponds

text: to

text: the

text: bulk

text: topological

text: states

text: of

text: the

text: QAH

text: insulator.

text: We

text: also

text: study

text: the

text: potential

text: applications

text: of

text: the

text: edge

text: spin

text: texture

text: in

text: designing

text: topological-state-based

text: spin

text: devices

text: which

text: might

text: be

text: applicable

text: to

text: future

text: spintronic

text: technologies.

text: Discovery

text: of

text: the

text: quantum

text: Hall

text: eﬀect

text: in

text: brought

text: takes

text: the

text: Dirac

text: form

text: about

text: a

text: fundamental

text: concept,

text: topological

text: state

text: of

text: quan-

text: tum

text: matter,

text: to

text: condensed

text: matter

text: physics

text: In

text: the

text: H

text: m

text: k

text: k

text: quantum

text: Hall

text: eﬀect

text: an

text: external

text: magnetic

text: ﬁeld

text: drives

text: the

text: (k)

text: z

text: x

text: y

text: x

text: k

text: k

text: m

text: electrons

text: to

text: ﬁll

text: in

text: discrete

text: Landau

text: levels.

text: This

text: leads

text: to

text: a

text: y

text: x

text: z

text: x

text: y

text: gap

text: in

text: the

text: two-dimensional

text: bulk,

text: while

text: the

text: bound-

text: ary

text: exhibits

text: chiral

text: gapless

text: edge

text: states.

text: The

text: Hall

text: con-

text: where

text: for

text: the

text: realization

text: with

text: thin-ﬁlm

text: FM

text: topologi-

text: ductance

text: in

text: the

text: integer

text: quantum

text: Hall

text: eﬀect

text: is

text: quantized

text: cal

text: insulators

text: m

text: depends

text: on

text: the

text: Zeeman

text: term

text: z

text: by

text: Chern

text: numbers,

text: which

text: are

text: integers

text: and

text: characterize

text: induced

text: by

text: the

text: FM

text: order,

text: the

text: B-term

text: characterizes

text: the

text: the

text: topology

text: of

text: the

text: system

text: The

text: topological

text: inter-

text: hybridization

text: between

text: top

text: and

text: bottom

text: thin-ﬁlm

text: surfaces,

text: pretation

text: of

text: the

text: quantized

text: Hall

text: conductance

text: implies

text: that

text: and

text: equal

text: Fermi

text: velocities

text: of

text: the

text: surface

text: Dirac

text: to

text: obtain

text: a

text: quantum

text: Hall

text: state

text: does

text: not

text: necessitate

text: an

text: cones

text: of

text: the

text: parent

text: topological

text: insulator

text: The

text: external

text: magnetic

text: ﬁeld.

text: The

text: theoretical

text: idea

text: for

text: quan-

text: QAH

text: phase

text: is

text: obtained

text: when

text: m

text: B

text: with

text: the

text: Chern

text: z

text: tum

text: Hall

text: eﬀect

text: without

text: Landau

text: levels,

text: i.e.

text: the

text: quantum

text: number

text: C

text: sgn(m

text: A

text: A

text: In

text: the

text: solid-state

text: z

text: anomalous

text: Hall

text: (QAH)

text: eﬀect,

text: was

text: ﬁrst

text: introduced

text: by

text: experiment,

text: the

text: Cr-doped

text: (Bi

text: Sb

text: Te

text: was

text: used

text: to

text: x

text: x

text: Haldane

text: in

text: a

text: honeycomb

text: lattice

text: over

text: two

text: decades

text: ago

text: achieve

text: the

text: above

text: Hamiltonian

text: and

text: the

text: QAH

text: phase

text: The

text: recent

text: interests

text: in

text: this

text: topological

text: state

text: have

text: been

text: re-

text: On

text: the

text: other

text: hand,

text: this

text: model

text: can

text: also

text: be

text: realized

text: in

text: vived

text: due

text: to

text: the

text: great

text: developments

text: in

text: the

text: time-reversal-

text: a

text: square

text: optical

text: lattice

text: with

text: SO

text: coupling

text: generated

text: invariant

text: topological

text: insulators

text: with

text: many

text: new

text: the-

text: based

text: on

text: the

text: cold

text: atom

text: experiments

text: oretical

text: proposals

text: having

text: been

text: introduced

text: Impor-

text: In

text: the

text: typical

text: isotropic

text: case

text: A

text: A

text: a

text: chiral-like

text: M

text: tantly,

text: following

text: the

text: proposal

text: in

text: Ref.

text: the

text: QAH

text: state

text: symmetry

text: S

text: σ

text: emerges

text: in

text: the

text: Hamiltonian,

text: has

text: been

text: detected

text: in

text: a

text: recent

text: experiment

text: using

text: ferromag-

text: with

text: being

text: arbitrary

text: orthogonal

text: unit

text: vec-

text: M

text: netic

text: (FM)

text: thin-ﬁlm

text: topological

text: insulator

text: by

text: observing

text: tors

text: in

text: the

text: x-y

text: plane.

text: Here

text: σ

text: and

text: represent

text: the

text: the

text: quantized

text: Hall

text: conductance

text: -component

text: of

text: the

text: Pauli

text: matrix

text: acting

text: on

text: the

text: spin

text: space

text: and

text: the

text: spatial

text: reﬂection

text: along

text: the

text: direction,

text: While

text: in

text: QAH

text: eﬀect

text: the

text: spin

text: is

text: generically

text: not

text: con-

text: respectively.

text: The

text: symmetry

text: transforms

text: the

text: fermion

text: op-

text: served,

text: the

text: recent

text: experimental

text: realization

text: based

text: on

text: strongly

text: spin-orbit

text: (SO)

text: coupled

text: materials

text: motivates

text: erat↑ors↓

text: via

text: ks,

text: cks)T

text: with

text: us

text: to

text: explore

text: the

text: spin

text: degree

text: of

text: freedom

text: of

text: such

text: QAH

text: s

text: and

text: k

text: One

text: can

text: v†erify

text: for

text: the

text: insulators.

text: We

text: show

text: surprisingly

text: that

text: the

text: edge

text: states

text: ex-

text: second

text: quantization

text: Hamiltonian

text: that

text: SHS

text: =HH,

text: w†hile

text: hibit

text: topologically

text: stable

text: spin

text: texture

text: in

text: the

text: boundary

text: t−hHe

text: ﬁrst

text: quantization

text: Hamiltonian

text: satisﬁes

text: S

text: (k)S

text: when

text: a

text: chiral-like

text: symmetry

text: is

text: present,

text: and

text: such

text: chi-

text: Consider

text: two

text: edges

text: normal

text: to

text: axis

text: and

text: we

text: ral

text: edge

text: spin

text: texture

text: corresponds

text: to

text: the

text: bulk

text: topological

text: can

text: reexpress

text: the

text: Hamiltonian

text: as

text: a

text: summation

text: of

text: states

text: of

text: the

text: QAH

text: insulator.

text: The

text: potential

text: applications

text: Hamiltonian

text: with

text: ﬁxed

text: momentum

text: along

text: the

text: edge:

text: of

text: the

text: edge

text: spin

text: texture

text: are

text: H

text: where

text: The

text: minimal

text: model

text: for

text: the

text: QAH

text: insulator

text: is

text: described

text: †H

text: by

text: a

text: two-band

text: Hamiltonian

text: H

text: ψ

text: (k)ψ

text: where

text: k

text: k

text: k

text: H

text: H

text: (k

text: dx

text: ψ

text: m(k

text: σ

text: the

text: spin

text: basis

text: ψk

text: (ck↑,

text: ck↓)T

text: Around

text: the

text: Γ

text: point

text: (k)

text: z

text: +iA

text: σ

text: A

text: k

text: σ

text: ψ

text: Corresponding

text: author:

text: xiongjunliu@pku.edu.cn

text: ##LTLine##


text: MEAN VALUE THEOREMS FOR L–FUNCTIONS OVER PRIME POLYNOMIALS 5 Theorem 2.1 (Prime Polynomial Theorem). If π (n) denotes the number A (cid:32) (cid:33) of monic irreducible polynomials in A of degree n, then, n qn q 2 (2.7) π (n) = + O . A n n ∈ Let P A be a monic irreducible polynomial. We denote by χ the P quadratic character deﬁned in terms of the quadratic residue symbol for F (cid:18) (cid:19) [T ] q P (2.8) χ (f) = , P f ∈ where f A. For more details see [10, Chapters 3, 4]. We will make use of the quadratic reciprocity law for polynomials in A ∈ F Theorem 2.2 (Quadratic reciprocity). Let A, B [T ] be relatively prime (cid:54) (cid:54) q and A = 0 and B = 0. Then, (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19) (2.9) A B − − B − | |− | |− = ( 1)((q 1)/2)deg(A)deg(B) = ( 1)(( A 1)/2)(( B 1)/2). B A A (cid:18) (cid:19) The L–function at(cid:88)tached to the cha(cid:89)racter χ is deﬁned by P − χ (f) − χ (Q) 1 (2.10) L(s, χ ) := |P | = 1 |P | , R(s) > 1. P ∈ f s Q s f A Q monic f monic irreducible Henceforth we consider P to be a monic irreducible polynomial such that ≡ deg(P ) is odd and q 1( mod 4). Then [10, Propositions 4.3, 14.6 and 17.7] − − L(s, χ ) is a polynomial in u = q s of degree deg(P ) 1 and P L (2.11) L(s, χ ) = (u, χ ) = L (u), P P CP where L (u) is the numerator of the zeta function associated to the CP hyperelliptic curve given in aﬃne form by (2.12) C : y2 = P (T ) P ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: MEAN

label: paragraph

text: VALUE

text: THEOREMS

text: FOR

text: L–FUNCTIONS

text: OVER

text: PRIME

text: POLYNOMIALS

text: Theorem

text: (Prime

text: Polynomial

text: Theorem).

text: If

text: π

text: (n)

text: denotes

text: the

text: number

text: A

label: equation

text: of

text: monic

text: irreducible

text: polynomials

text: in

text: A

text: of

text: degree

text: n,

text: then,

text: n

text: qn

text: q

text: π

text: (n)

text: O

text: A

text: n

text: n

text: Let

text: P

text: A

text: be

text: a

text: monic

text: irreducible

text: polynomial.

text: We

text: denote

text: by

text: χ

text: the

text: P

text: quadratic

text: character

text: deﬁned

text: in

text: terms

text: of

text: the

text: quadratic

text: residue

text: symbol

text: for

text: F

text: [T

text: q

text: P

text: χ

text: (f)

text: P

text: f

text: where

text: f

text: A.

text: For

text: more

text: details

text: see

text: Chapters

text: We

text: will

text: make

text: use

text: of

text: the

text: quadratic

text: reciprocity

text: law

text: for

text: polynomials

text: in

text: A

text: F

text: Theorem

text: (Quadratic

text: reciprocity).

text: Let

text: A,

text: B

text: [T

text: be

text: relatively

text: prime

text: q

text: and

text: A

text: and

text: B

text: Then,

text: A

text: B

text: B

text: A

text: B

text: B

text: A

text: A

text: The

text: L–function

text: to

text: the

text: χ

text: is

text: deﬁned

text: by

text: P

text: χ

text: (f)

text: χ

text: (Q)

text: L(s,

text: χ

text: |P

text: |P

text: R(s)

text: P

text: f

text: s

text: Q

text: s

text: f

text: A

text: Q

text: monic

text: f

text: monic

text: irreducible

text: Henceforth

text: we

text: consider

text: P

text: to

text: be

text: a

text: monic

text: irreducible

text: polynomial

text: such

text: that

text: deg(P

text: is

text: odd

text: and

text: q

text: mod

text: Then

text: Propositions

text: and

text: L(s,

text: χ

text: is

text: a

text: polynomial

text: in

text: u

text: q

text: s

text: of

text: degree

text: deg(P

text: and

text: P

text: L

text: L(s,

text: χ

text: (u,

text: χ

text: L

text: (u),

text: P

text: P

text: CP

text: where

text: L

text: (u)

text: is

text: the

text: numerator

text: of

text: the

text: zeta

text: function

text: associated

text: to

text: the

text: CP

text: hyperelliptic

text: curve

text: given

text: in

text: aﬃne

text: form

text: by

text: C

text: P

text: (T

text: P

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 8 JULIO C. ANDRADE AND JONATHAN P. KEATING in (3.1). We can write this as (cid:88) (cid:88) g −n (3.2) χP (f1)q 2 (cid:88) (cid:88) (cid:88) (cid:88) n=0 f1 monic deg(f1)=n g g −n −n = χP (f1)q 2 + χP (f1)q 2 . n=0 f1 monic n=0 f1 monic deg(f1(cid:3))=n deg(f(cid:54) 1(cid:3))=n f1= f1= In this section we focus our attention on the average of the ﬁrst double sum in the right hand side of (3.2). The main result is Proposition 3.1. We have that, (cid:32) (cid:112) (cid:33) (cid:88) (cid:88) (cid:88) (cid:16)(cid:104) (cid:105) (cid:17) | | | | g −n P g P χP (f1)q 2 = | | + 1 + O | |g , log P 2 log P P monic n=0 f1 monic q q deigrr(ePd)u=ci2bgl+e 1 deg(f1(cid:3))=n f1= where [x] denotes the integer part of x. Proof. We have, (cid:88) (cid:88) (cid:88) g −n χP (f1)q 2 d(cid:88)eigrPr(ePdm)u=ocni2bigcl+e 1(cid:88)n=0 dfe1g(mf1o(cid:3)(cid:88))n=icn (cid:88) (cid:88) (cid:88) f1= g g −n −n = q 2 χP (l2) = q 2 1 n=| 0 l monic P monic n=| 0 l monic P monic (cid:88)2 n deg(cid:88)(l)=n2 deigrr(eP(cid:88)d)u=ci2bgl+e 1 2 n deg(l)=n2 deigrr(ePd)u=ci2bgl+e 1 (P,l)=1 g −n = q 2 1, n=| 0 l monic P monic 2 n deg(l)=n irreducible 2 deg(P)=2g+1 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: JULIO

text: C.

text: ANDRADE

text: AND

text: JONATHAN

text: P.

text: KEATING

text: in

text: We

text: can

text: write

text: this

text: as

text: g

text: −n

text: χP

text: monic

text: g

text: g

text: −n

text: −n

text: χP

text: χP

text: monic

text: monic

text: In

text: this

text: section

text: we

text: focus

text: our

text: attention

text: on

text: the

text: average

text: of

text: the

text: ﬁrst

text: double

text: sum

text: in

text: the

text: right

text: hand

text: side

text: of

text: The

text: main

text: result

text: is

text: Proposition

text: We

text: have

text: that,

text: g

text: −n

text: P

text: g

text: P

text: χP

text: O

text: |g

text: log

text: P

text: log

text: P

text: P

text: monic

text: monic

text: q

text: q

text: where

text: [x]

text: denotes

text: the

text: integer

text: part

text: of

text: x.

text: Proof.

text: We

text: have,

text: g

text: −n

text: χP

text: g

text: g

text: −n

text: −n

text: q

text: χP

text: q

text: n=|

text: l

text: monic

text: P

text: monic

text: n=|

text: l

text: monic

text: P

text: monic

text: n

text: n

text: g

text: −n

text: q

text: n=|

text: l

text: monic

text: P

text: monic

text: n

text: deg(l)=n

text: irreducible

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: { (cid:48) (cid:48)} { (cid:48) (cid:48)} from A(S) by replacing A(x) by xx , xz, zz , A(y) by yy , yz, zz , but leaving other A(u) ∈ − { } { (cid:48) (cid:48)} { (cid:48) (cid:48)} with u S x, y unchanged, in (4). Since xx , xz, zz and yy , yz, zz have one arc in | | | | − common, we have A (S) = A(S) 1. If deg(z) = 2, then let A (S) be obtained from A(S) 1 1 { } { } ∈ − { } by replacing A(x) by xz, zy , A(y) by yz, zx , but leaving other A(u) with u S x, y | | | | − unchanged, in (4). Then A (S) = A(S) 2. Set A (D) := A(D) regardless of the degree of 1 1 | ∪ | ≤ | ∪ | − ∪ z. Then A (S) A (D) A(S) A(D) 1 and A (S) A (D) is a dominating set of X(G). 1 1 1 1 ∅ − (cid:54) ∅ | | ≥ Case 3: S is an independent set of G and U = . Then W = V (G) S = , A(D) 1 and | − | ≥ ∈ − W D 1. Choose a vertex z W D. Since S is a dominating set of G, we may choose a ∈ ∈ neighbour x S of z. Similarly, we may choose a neighbour v D of z in H and a neighbour ∈ u S of v in G. It may happen that u = x, but this will not aﬀect our subsequent proof. { } Let A (S) be obtained from A(S) by replacing A(x) by xz, zv, vu , but leaving other A(y) 1 ∈ − { } ∈ (cid:48) (cid:48) ∈ ∩ with y S x unchanged, in (4). Since v D, A(D) contains an arc vv with v N(v) S. (cid:48) (cid:54) (cid:48) If vv = vu, then let A (D) be obtained from A(D) by replacing this particular arc vv by vu 1 (cid:48) ∈ but retaining all other yy A(D) in (8); otherwise, let A (D) := A(D). Since vu appears in 1 | ∪ | | ∪ | − both A (D) and A (S), we have A (S) A (D) = A(S) A(D) 1. We now show that 1 1 1 1 ∪ A (S) A (D) is a dominating set of X(G). In fact, by the deﬁnition of A (D) and A (S) one 1 1 1 1 ∪ can see that every arc with tail not in N[x] that is dominated by A(S) A(D) is now dominated ∪ ∈ ∈ by A (S) A (D). Let ab be an arc with a N[x]. If a = x, then ab = xz A (S) or ab is 1 1 1 ∈ ∈ dominated by zv A (S). Suppose that a N(x). If a = z, then ab = zv or ab is dominated 1 ∈ ∈ − { } (cid:54) ∈ by vu A (S). Suppose that a N(x) z . If b = x, then ab is dominated by xz A (S). 1 1 ∈ ∈ (cid:48) ∈ If b = x, then either ab A (D) when a D, or ab is dominated by yy A (D), where y is a 1 1 ∪ vertex in D that dominates a in H. Therefore, A (S) A (D) is a dominating set of X(G). 1 1 So far we have completed the proof of Claim 2. By this claim (and the discussion before it) ≤ | ∪ | ≤ | ∪ |− ≤ − and (9), we obtain γ(X(G)) A (S) A (D) A(S) A(D) 1 3γ(G)+γ(H : V − (H)) 1. 1 1 δ 1 Since this holds for any γ(G)-set S of G and since H = G , we obtain (2) immediately. S It is easy to see that the bound in (2) is achieved by the 3-cycle C and in general by any 3 friendship graph (that is, a graph obtained from a number of copies of C by identifying one 3 vertex from each copy to form a single vertex). (cid:50) ≥ It was proved in [8] that, for any connected graph G of order n 4 and minimum degree at ≤ ≤ least 2, we have γ(X(G)) n. Combining this with n/(1 + ∆(G)) γ(G) [3], we then have ≤ γ(X(G)) (1 + ∆(G))γ(G). (10) ≥ The following theorem improves this bound for any graph G with ∆(G) δ(G) = 2, 3 or 4. In Theorem 7 we will give a further improved bound for any claw-free graph with minimum degree at least two. (cid:18) (cid:19) Theorem 6 Let G be a graph. ≤ ∆(G) − (a) If δ(G) = 2, then γ(X(G)) (cid:18) + 3 (cid:19)γ(G) 1; 2 ≤ 2∆(G) − (b) if δ(G) = 3, then γ(X(G)) + 3 γ(G) 1; 5 9 ##LTLine## ##LTLine##

text: from

text: A(S)

text: by

text: replacing

text: A(x)

text: by

text: xx

text: xz,

text: zz

text: A(y)

text: by

text: yy

text: yz,

text: zz

text: but

text: leaving

text: other

text: A(u)

text: with

text: u

text: S

text: x,

text: y

text: unchanged,

text: in

text: Since

text: xx

text: xz,

text: zz

text: and

text: yy

text: yz,

text: zz

text: have

text: one

text: arc

text: in

text: common,

text: we

text: have

text: A

text: (S)

text: A(S)

text: If

text: deg(z)

text: then

text: let

text: A

text: (S)

text: be

text: obtained

text: from

text: A(S)

text: by

text: replacing

text: A(x)

text: by

text: xz,

text: zy

text: A(y)

text: by

text: yz,

text: zx

text: but

text: leaving

text: other

text: A(u)

text: with

text: u

text: S

text: x,

text: y

text: unchanged,

text: in

text: Then

text: A

text: (S)

text: A(S)

text: Set

text: A

text: (D)

text: A(D)

text: regardless

text: of

text: the

text: degree

text: of

text: z.

text: Then

text: A

text: (S)

text: A

text: (D)

text: A(S)

text: A(D)

text: and

text: A

text: (S)

text: A

text: (D)

text: is

text: a

text: dominating

text: set

text: of

text: X(G).

text: Case

text: S

text: is

text: an

text: independent

text: set

text: of

text: G

text: and

text: U

text: Then

text: W

text: V

text: (G)

text: S

text: A(D)

text: and

text: W

text: D

text: Choose

text: a

text: vertex

text: z

text: W

text: D.

text: Since

text: S

text: is

text: a

text: dominating

text: set

text: of

text: G,

text: we

text: may

text: choose

text: a

text: neighbour

text: x

text: S

text: of

text: z.

text: Similarly,

text: we

text: may

text: choose

text: a

text: neighbour

text: v

text: D

text: of

text: z

text: in

text: H

text: and

text: a

text: neighbour

text: u

text: S

text: of

text: v

text: in

text: G.

text: It

text: may

text: happen

text: that

text: u

text: x,

text: but

text: this

text: will

text: not

text: aﬀect

text: our

text: subsequent

text: proof.

text: Let

text: A

text: (S)

text: be

text: obtained

text: from

text: A(S)

text: by

text: replacing

text: A(x)

text: by

text: xz,

text: zv,

text: vu

text: but

text: leaving

text: other

text: A(y)

text: with

text: y

text: S

text: x

text: unchanged,

text: in

text: Since

text: v

text: D,

text: A(D)

text: contains

text: an

text: arc

text: vv

text: with

text: v

text: N(v)

text: S.

text: If

text: vv

text: vu,

text: then

text: let

text: A

text: (D)

text: be

text: obtained

text: from

text: A(D)

text: by

text: replacing

text: this

text: particular

text: arc

text: vv

text: by

text: vu

text: but

text: retaining

text: all

text: other

text: yy

text: A(D)

text: in

text: otherwise,

text: let

text: A

text: (D)

text: A(D).

text: Since

text: vu

text: appears

text: in

text: both

text: A

text: (D)

text: and

text: A

text: (S),

text: we

text: have

text: A

text: (S)

text: A

text: (D)

text: A(S)

text: A(D)

text: We

text: now

text: show

text: that

text: A

text: (S)

text: A

text: (D)

text: is

text: a

text: dominating

text: set

text: of

text: X(G).

text: In

text: fact,

text: by

text: the

text: deﬁnition

text: of

text: A

text: (D)

text: and

text: A

text: (S)

text: one

text: can

text: see

text: that

text: every

text: arc

text: with

text: tail

text: not

text: in

text: N[x]

text: that

text: is

text: dominated

text: by

text: A(S)

text: A(D)

text: is

text: now

text: dominated

text: by

text: A

text: (S)

text: A

text: (D).

text: Let

text: ab

text: be

text: an

text: arc

text: with

text: a

text: N[x].

text: If

text: a

text: x,

text: then

text: ab

text: xz

text: A

text: (S)

text: or

text: ab

text: is

text: dominated

text: by

text: zv

text: A

text: (S).

text: Suppose

text: that

text: a

text: N(x).

text: If

text: a

text: z,

text: then

text: ab

text: zv

text: or

text: ab

text: is

text: dominated

text: by

text: vu

text: A

text: (S).

text: Suppose

text: that

text: a

text: N(x)

text: z

text: If

text: b

text: x,

text: then

text: ab

text: is

text: dominated

text: by

text: xz

text: A

text: (S).

text: If

text: b

text: x,

text: then

text: either

text: ab

text: A

text: (D)

text: when

text: a

text: D,

text: or

text: ab

text: is

text: dominated

text: by

text: yy

text: A

text: (D),

text: where

text: y

text: is

text: a

text: vertex

text: in

text: D

text: that

text: dominates

text: a

text: in

text: H.

text: Therefore,

text: A

text: (S)

text: A

text: (D)

text: is

text: a

text: dominating

text: set

text: of

text: X(G).

text: So

text: far

text: we

text: have

text: completed

text: the

text: proof

text: of

text: Claim

text: By

text: this

text: claim

text: (and

text: the

text: discussion

text: before

text: it)

text: and

text: we

text: obtain

text: γ(X(G))

text: A

text: (S)

text: A

text: (D)

text: A(S)

text: A(D)

text: V

text: (H))

text: δ

text: Since

text: this

text: holds

text: for

text: any

text: γ(G)-set

text: S

text: of

text: G

text: and

text: since

text: H

text: G

text: we

text: obtain

text: immediately.

text: S

text: It

text: is

text: easy

text: to

text: see

text: that

text: the

text: bound

text: in

text: is

text: achieved

text: by

text: the

text: C

text: and

text: in

text: general

text: by

text: any

text: friendship

text: graph

text: (that

text: is,

text: a

text: graph

text: obtained

text: from

text: a

text: number

text: of

text: copies

text: of

text: C

text: by

text: identifying

text: one

text: vertex

text: from

text: each

text: copy

text: to

text: form

text: a

text: single

text: vertex).

text: It

text: was

text: proved

text: in

text: that,

text: for

text: any

text: connected

text: graph

text: G

text: of

text: order

text: n

text: and

text: minimum

text: degree

text: at

text: least

text: we

text: have

text: γ(X(G))

text: n.

text: Combining

text: this

text: with

text: ∆(G))

text: γ(G)

text: we

text: then

text: have

text: γ(X(G))

text: ∆(G))γ(G).

text: The

text: following

text: theorem

text: improves

text: this

text: bound

text: for

text: any

text: graph

text: G

text: with

text: ∆(G)

text: δ(G)

text: or

text: In

text: Theorem

text: we

text: will

text: give

text: a

text: further

text: improved

text: bound

text: for

text: any

text: claw-free

text: graph

text: with

text: minimum

text: degree

text: at

text: least

text: two.

text: Theorem

text: Let

text: G

text: be

text: a

text: graph.

text: ∆(G)

text: (a)

text: If

text: δ(G)

text: then

text: γ(X(G))

text: (b)

text: if

text: δ(G)

text: then

text: γ(X(G))

text: γ(G)

text: ##LTLine##

text: ##LTLine##


text: (cid:18) (cid:19) ≤ 3(∆(G) + 2) − (c) if δ(G) = 4, then γ(X(G)) + 3 γ(G) 1. 8 Moreover, the bounds in (a) and (b) are attainable. Proof Denote δ := δ(G). As in the proof of Theorem 5, let S be a γ(G)-set of G and − (cid:48) denote H := G S. Let H be obtained from H by deleting all isolated vertices. Then ≤ (cid:48) γ(H : V (H)) γ(H ). 1 | | ≤ (a) If δ = 2, then by Theorems 5, Lemma 4(a) and the fact that V (G) (∆(G) + 1)γ(G), we have ≤ − γ(X(G)) 3γ(G) + γ(H : V (H)) 1 1 − ≤ n γ(G) − 3γ(G) + 1 2 − (cid:18) (cid:19) ≤ (∆(G) + 1)γ(G) γ(G) − 3γ(G) + 1 2 ∆(G) − = + 3 γ(G) 1. 2 (b) Assume δ = 3. Let A(S) and W be deﬁned by (4) and (5), respectively, with A(x) as ∈ ⊆ given in (3) for each x S. By (6), we have W V (H). 2 (cid:48) Let R , R , . . . , R be the set of components of H , and let r be the order of R . We are 1 2 s j j going to prove that we can choose an appropriate subset D of V (R ) for each j such that j j | | ≤ ∪ ∪ D 2r /5 and A(S) A( s D ) is a dominating set of X(G). j j j=1 j A In fact, if R is not isomorphic to any graph in the family (see Figure 1), then we choose j | | D to be a minimum (R : V (R ))-dominating set. By Lemma 4(b), we have D = γ(R : j j 2 j j j ≤ V (R )) 2r /5. 2 j j A Suppose that a component R is isomorphic to some graph in . If R contains a vertex j j − { } z which is not in W , then we choose D to be a minimum dominating set of R z . Since j j ∩ ∩ ≤ in this case D is also an (R : W V (R ))-dominating set, we have γ(R : W V (R )) j j j j j − { } | | γ(R z ) = D < 2r /5 by noting that r = 4 or 7. j j j j Now assume that all vertices of R are in W . Let z be an arbitrary vertex of R and D a j j j − { } (cid:48) ∈ minimum dominating set of R z . Let A(D ) be the set of arcs xx of G such that x D j j j (cid:48) | | and x is the unique neighbour of x in S. It is not hard to verify that D < 2r /5. Let u j j be a neighbour of z in R . Since δ(R ) = 2 (see Figure 1), we can choose a neighbour y of u j j (cid:48) (cid:48) in G other than u and z (so that y is in R ), where u is the unique neighbour of u in S. In j { (cid:48) (cid:48) } (cid:48) forming A(S) by (4), we choose A(u) to be u u, uy, u v , where v is a neighbour of u other than u. Similar to what we did in the proof of Theorem 5, when necessary we may modify A(S) to obtain a new set A(S) (also denoted by A(S)) such that every arc of G with tail z is (cid:48) (cid:48) dominated in X(G) by either uy or an arc in A(z ), where z is the unique neighbour of z in S. It can be veriﬁed that we can always choose an appropriate pair of vertices z, u such that this happens. In this way we ensure that all arcs emanating from vertices of R are dominated by j ∪ A(S) A(D ) in X(G). j 10 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: list

text: (c)

text: if

text: δ(G)

text: then

text: γ(X(G))

text: γ(G)

text: Moreover,

text: the

text: bounds

text: in

text: (a)

text: and

text: (b)

text: are

text: attainable.

text: Proof

text: Denote

text: δ

text: δ(G).

text: As

text: in

text: the

text: proof

text: of

text: Theorem

text: let

text: S

text: be

text: a

text: γ(G)-set

text: of

text: G

text: and

text: denote

text: H

text: G

text: S.

text: Let

text: H

text: be

text: obtained

text: from

text: H

text: by

text: deleting

text: all

text: isolated

text: vertices.

text: Then

text: γ(H

text: V

text: (H))

text: γ(H

text: (a)

text: If

text: δ

text: then

text: by

text: Theorems

text: Lemma

text: and

text: the

text: fact

text: that

text: V

text: (G)

text: (∆(G)

text: we

text: have

text: γ(X(G))

text: γ(H

text: V

text: (H))

text: n

text: γ(G)

text: (∆(G)

text: γ(G)

text: ∆(G)

text: γ(G)

text: (b)

text: Assume

text: δ

text: Let

text: A(S)

text: and

text: W

text: be

text: deﬁned

text: by

text: and

text: respectively,

text: with

text: A(x)

text: as

text: given

text: in

text: for

text: each

text: x

text: S.

text: By

text: we

text: have

text: W

text: V

text: (H).

text: Let

text: R

text: R

text: R

text: be

text: the

text: set

text: of

text: components

text: of

text: H

text: and

text: let

text: r

text: be

text: the

text: order

text: of

text: R

text: We

text: are

text: s

text: j

text: j

text: going

text: to

text: prove

text: that

text: we

text: can

text: choose

text: an

text: appropriate

text: subset

text: D

text: of

text: V

text: (R

text: for

text: each

text: j

text: such

text: that

text: j

text: j

text: D

text: and

text: A(S)

text: A(

text: s

text: D

text: is

text: a

text: dominating

text: set

text: of

text: X(G).

text: j

text: j

text: j

text: A

text: In

text: fact,

text: if

text: R

text: is

text: not

text: isomorphic

text: to

text: any

text: graph

text: in

text: the

text: family

text: (see

text: Figure

text: then

text: we

text: choose

text: j

text: D

text: to

text: be

text: a

text: minimum

text: (R

text: V

text: (R

text: ))-dominating

text: set.

text: By

text: Lemma

text: we

text: have

text: D

text: γ(R

text: j

text: j

text: j

text: j

text: j

text: V

text: (R

text: j

text: j

text: A

text: Suppose

text: that

text: a

text: component

text: R

text: is

text: isomorphic

text: to

text: some

text: graph

text: in

text: If

text: R

text: contains

text: a

text: vertex

text: j

text: j

text: z

text: which

text: is

text: not

text: in

text: W

text: then

text: we

text: choose

text: D

text: to

text: be

text: a

text: minimum

text: dominating

text: set

text: of

text: R

text: z

text: Since

text: j

text: j

text: in

text: this

text: case

text: D

text: is

text: also

text: an

text: (R

text: W

text: V

text: (R

text: ))-dominating

text: set,

text: we

text: have

text: γ(R

text: W

text: V

text: (R

text: j

text: j

text: j

text: j

text: j

text: γ(R

text: z

text: D

text: by

text: noting

text: that

text: r

text: or

text: j

text: j

text: j

text: j

text: Now

text: assume

text: that

text: all

text: vertices

text: of

text: R

text: are

text: in

text: W

text: Let

text: z

text: be

text: an

text: arbitrary

text: vertex

text: of

text: R

text: and

text: D

text: a

text: j

text: j

text: j

text: minimum

text: dominating

text: set

text: of

text: R

text: z

text: Let

text: A(D

text: be

text: the

text: set

text: of

text: arcs

text: xx

text: of

text: G

text: such

text: that

text: x

text: D

text: j

text: j

text: j

text: and

text: x

text: is

text: the

text: unique

text: neighbour

text: of

text: x

text: in

text: S.

text: It

text: is

text: not

text: hard

text: to

text: verify

text: that

text: D

text: Let

text: u

text: j

text: j

text: be

text: a

text: neighbour

text: of

text: z

text: in

text: R

text: Since

text: δ(R

text: (see

text: Figure

text: we

text: can

text: choose

text: a

text: neighbour

text: y

text: of

text: u

text: j

text: j

text: in

text: G

text: other

text: than

text: u

text: and

text: z

text: (so

text: that

text: y

text: is

text: in

text: R

text: where

text: u

text: is

text: the

text: unique

text: neighbour

text: of

text: u

text: in

text: S.

text: In

text: j

text: forming

text: A(S)

text: by

text: we

text: choose

text: A(u)

text: to

text: be

text: u

text: u,

text: uy,

text: u

text: v

text: where

text: v

text: is

text: a

text: neighbour

text: of

text: u

text: other

text: than

text: u.

text: Similar

text: to

text: what

text: we

text: did

text: in

text: the

text: proof

text: of

text: Theorem

text: when

text: necessary

text: we

text: may

text: modify

text: A(S)

text: to

text: obtain

text: a

text: new

text: set

text: A(S)

text: (also

text: denoted

text: by

text: A(S))

text: such

text: that

text: every

text: arc

text: of

text: G

text: with

text: tail

text: z

text: is

text: dominated

text: in

text: X(G)

text: by

text: either

text: uy

text: or

text: an

text: arc

text: in

text: A(z

text: where

text: z

text: is

text: the

text: unique

text: neighbour

text: of

text: z

text: in

text: S.

text: It

text: can

text: be

text: veriﬁed

text: that

text: we

text: can

text: always

text: choose

text: an

text: appropriate

text: pair

text: of

text: vertices

text: z,

text: u

text: such

text: that

text: this

text: happens.

text: In

text: this

text: way

text: we

text: ensure

text: that

text: all

text: arcs

text: emanating

text: from

text: vertices

text: of

text: R

text: are

text: dominated

text: by

text: j

text: A(S)

text: A(D

text: in

text: X(G).

text: j

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: The number of ends of critical branching random walks ∗ † Elisabetta Candellero and Matthew I. Roberts May 26, 2020 Abstract We investigate the number of topological ends of the trace of branching random walk (BRW) on a graph, showing that in many symmetric cases there are inﬁnitely many ends. We then describe some BRWs which have just one end, and conclude with some open problems. 1 Introduction Consider a branching random walk (BRW) on a graph described as follows. We are given ∈ ≥ a graph G and a vertex i V (G). We begin with one particle at i at time 0. For each n 0, each particle alive at time n dies and gives birth to an independent random number of oﬀspring particles according to some probability distribution µ, each of which independently takes a step according to a speciﬁed random walk on the graph with transition kernel P . We write BRW(G, µ, P ) for such a branching random walk. We assume throughout that G ≥ is inﬁnite, P is irreducible, µ has ﬁnite mean m = m and µ(0) = 0. We write (X , n 0) for a µ n P random walk on G with transition kernel P , and for a probability measure under which the i BRW and the random walk are independent and begin at vertex i. Let ρ = ρ(P ) be the spectral P radius of P , ρ = lim sup →∞ (X = i)1/n (which is independent of the choice of i). n i n We say that a BRW is recurrent if every vertex of the graph is visited inﬁnitely often by the particles of the BRW. Otherwise it is transient. Benjamini and Peres (see [BP94]) gave a characterization for transience of the process in terms of the spectral radius ρ of the underlying − − walk: they showed that if m < ρ 1 then the BRW is transient, while if m > ρ 1 then the BRW − is recurrent. We call a BRW(G, µ, P ) critical if m = ρ 1. µ Gantert and Mu¨ller [GM06] and Bertacchi and Zucca [BZ08] proved that any critical BRW is transient. The trace of the critical process (the subgraph induced by edges that are traversed by particles of the BRW) is then an interesting random structure in its own right. Benjamini and Mu¨ller [BM12] showed that on Cayley graphs, simple random walk on the trace of any transient BRW is itself almost surely transient, but any non-trivial branching random walk on the trace is strongly recurrent. In this work we investigate the number of topological ends of the trace. That is, if we remove a large ball about the origin, how many connected components do we see? We prove the following theorem, which shows that on many graphs the trace has inﬁnitely ≥ many ends. We say that a random walk X , n 0 is quasi-symmetric if there exists C such that ≥ n for all vertices i and j, and all n 0, P ≤ P (X = j) C (X = i). i n j n ∗ Department of Statistics, University of Warwick, Coventry CV4 7AL, UK. Email: elisabetta.candellero@gmail.com † Department of Mathematical Sciences, University of Bath, Bath BA2 7AY, UK. Email: mattiroberts@gmail.com 1 ##LTLine##

text: The

text: number

text: of

text: ends

text: of

text: critical

text: branching

text: random

text: walks

text: Elisabetta

text: Candellero

text: and

text: Matthew

text: I.

text: Roberts

text: May

text: Abstract

text: We

label: abstract

text: investigate

text: the

text: number

text: of

text: topological

text: ends

text: of

text: the

text: trace

text: of

text: branching

text: random

text: walk

text: (BRW)

text: on

text: a

text: graph,

text: showing

text: that

text: in

text: many

text: symmetric

text: cases

text: there

text: are

text: inﬁnitely

text: many

text: ends.

text: We

text: then

text: describe

text: some

text: BRWs

text: which

text: have

text: just

text: one

text: end,

text: and

text: conclude

text: with

text: some

text: open

text: problems.

label: section

text: Introduction

text: Consider

text: a

text: branching

text: random

text: walk

text: (BRW)

text: on

text: a

text: graph

text: described

text: as

text: follows.

text: We

text: are

text: given

text: a

text: graph

text: G

text: and

text: a

text: vertex

text: i

text: V

text: (G).

text: We

text: begin

text: with

text: one

text: particle

text: at

text: i

text: at

text: time

text: For

text: each

text: n

text: each

text: particle

text: alive

text: at

text: time

text: n

text: dies

text: and

text: gives

text: birth

text: to

text: an

text: independent

text: random

text: number

text: of

text: oﬀspring

text: particles

text: according

text: to

text: some

text: probability

text: distribution

text: µ,

text: each

text: of

text: which

text: independently

text: takes

text: a

text: step

text: according

text: to

text: a

text: speciﬁed

text: random

text: walk

text: on

text: the

text: graph

text: with

text: transition

text: kernel

text: P

text: We

text: write

text: BRW(G,

text: µ,

text: P

text: for

text: such

text: a

text: branching

text: random

text: walk.

text: We

text: assume

text: throughout

text: that

text: G

text: is

text: inﬁnite,

text: P

text: is

text: irreducible,

text: µ

text: has

text: ﬁnite

text: mean

text: m

text: m

text: and

text: We

text: write

text: (X

text: n

text: for

text: a

text: µ

text: n

text: P

text: random

text: walk

text: on

text: G

text: with

text: transition

text: kernel

text: P

text: and

text: for

text: a

text: probability

text: measure

text: under

text: which

text: the

text: i

text: BRW

text: and

text: the

text: random

text: walk

text: are

text: independent

text: and

text: begin

text: at

text: vertex

text: i.

text: Let

text: ρ

text: ρ(P

text: be

text: the

text: spectral

text: P

text: radius

text: of

text: P

text: ρ

text: lim

text: sup

text: (X

text: (which

text: is

text: independent

text: of

text: the

text: choice

text: of

text: i).

text: n

text: i

text: n

text: We

text: say

text: that

text: a

text: BRW

text: is

text: recurrent

text: if

text: every

text: vertex

text: of

text: the

text: graph

text: is

text: visited

text: inﬁnitely

text: often

text: by

text: the

text: particles

text: of

text: the

text: BRW.

text: Otherwise

text: it

text: is

text: transient.

text: Benjamini

text: and

text: Peres

text: (see

text: gave

text: a

text: characterization

text: for

text: transience

text: of

text: the

text: process

text: in

text: terms

text: of

text: the

text: spectral

text: radius

text: ρ

text: of

text: the

text: underlying

text: walk:

text: they

text: showed

text: that

text: if

text: m

text: ρ

text: then

text: the

text: BRW

text: is

text: transient,

text: while

text: if

text: m

text: ρ

text: then

text: the

text: BRW

text: is

text: recurrent.

text: We

text: call

text: a

text: BRW(G,

text: µ,

text: P

text: critical

text: if

text: m

text: ρ

text: µ

text: Gantert

text: and

text: Mu¨ller

text: and

text: Bertacchi

text: and

text: Zucca

text: proved

text: that

text: any

text: critical

text: BRW

text: is

text: transient.

text: The

text: trace

text: of

text: the

text: critical

text: process

text: (the

text: subgraph

text: induced

text: by

text: edges

text: that

text: are

text: traversed

text: by

text: particles

text: of

text: the

text: BRW)

text: is

text: then

text: an

text: interesting

text: random

text: structure

text: in

text: its

text: own

text: right.

text: Benjamini

text: and

text: Mu¨ller

text: showed

text: that

text: on

text: Cayley

text: graphs,

text: simple

text: random

text: walk

text: on

text: the

text: trace

text: of

text: any

text: transient

text: BRW

text: is

text: itself

text: almost

text: surely

text: transient,

text: but

text: any

text: non-trivial

text: branching

text: random

text: walk

text: on

text: the

text: trace

text: is

text: strongly

text: recurrent.

text: In

text: this

text: work

text: we

text: investigate

text: the

text: number

text: of

text: topological

text: ends

text: of

text: the

text: trace.

text: That

text: is,

text: if

text: we

text: remove

text: a

text: large

text: ball

text: about

text: the

text: origin,

text: how

text: many

text: connected

text: components

text: do

text: we

text: see?

text: We

text: prove

text: the

text: following

text: theorem,

text: which

text: shows

text: that

text: on

text: many

text: graphs

text: the

text: trace

text: has

text: inﬁnitely

text: many

text: ends.

text: We

text: say

text: that

text: a

text: random

text: walk

text: X

text: n

text: is

text: quasi-symmetric

text: if

text: there

text: exists

text: C

text: such

text: that

text: n

text: for

text: all

text: vertices

text: i

text: and

text: j,

text: and

text: all

text: n

text: P

text: P

text: (X

text: j)

text: C

text: (X

text: i).

text: i

text: n

text: j

text: n

text: Department

text: of

text: Statistics,

text: University

text: of

text: Warwick,

text: Coventry

text: UK.

text: Email:

text: elisabetta.candellero@gmail.com

text: Department

text: of

text: Mathematical

text: Sciences,

text: University

text: of

text: Bath,

text: Bath

text: UK.

text: Email:

text: mattiroberts@gmail.com

text: ##LTLine##


text: so ρ(P ) > 0. H Showing that the critical BRW is one-ended can be done in a very similar way to the proof of Proposition 5.1. Choose any two particles in the BRW, and colour their descendants red and blue respectively; any site hit by both a red and a blue particle is coloured purple. Clearly a N N random walk on H eventually hits almost surely, so is hit inﬁnitely often by red particles 0 0 and inﬁnitely often by blue particles. We can ensure (for example by constructing embedded Galton-Watson processes as in the proof of Proposition 5.1) that there are almost surely inﬁnitely many red-blue pairs within distance at most k of each other. Each of these pairs has at least N a ﬁxed probability δ > 0 of creating a purple dot (since this time does not have bounded 0 N T degree, we have to allow particles to bounce back and forth between and ). Thus we have 0 inﬁnitely many purple dots almost surely, and since our initial choice of red and blue particles was arbitrary, this guarantees that we have only one end. Remark 5.4. By gluing together various copies of graphs already constructed, it is easy to construct graphs on which critical BRW has any number of ends. For example, if we glue two × copies of H and one copy of T T at a single vertex, then we have a graph on which critical 3 3 BRW has one end, two ends, or inﬁnitely many ends, each with positive probability. Open problem. Does there exist a quasi-symmetric random walk such that the corresponding critical BRW is one-ended almost surely? Another possibility for future research is to investigate the Cayley graphs of co-compact Fuchsian groups. These graphs correspond to tilings of the hyperbolic plane. Lalley and Sellke [LS97] showed that critical branching Brownian motion on the hyperbolic plane has a limit set that does not have full measure, and by analogy one might expect that critical branching random walks on co-compact Fuchsian groups have inﬁnitely many ends. Finally, we relay a conjecture from Itai Benjamini. Conjecture 5.5 (Itai Benjamini, private communication). On any vertex-transitive graph G, the trace of simple critical BRW has inﬁnitely many ends. 6 Appendix on product random walks As we mentioned brieﬂy in Section , given random walks on d graphs G , . . . , G , there is × × 1 d more than one natural random walk on G . . . G . Rather than overcomplicate matters with 1 d general deﬁnitions in the earlier sections, we concentrated on one such natural choice. Here we give more details, and see that in fact our results hold regardless of the choice. ≥ Given random walks X(1), . . . , X(d) on G , . . . , G respectively, and α , . . . , α 0 with 1 d 1 ×d × α1 + . . . + αd = 1, we deﬁne the (α1, . . . , αd)-product random walk X on G = G1 . . . Gd by setting  (cid:80) α P(X(l) = j |X(l) = i ) if j = i ∀k (cid:54)= l, j (cid:54)= i l 1 l 0 l k k l l P (X = (j , . . . , j )) = d α P(X(k) = i |X(k) = i ) if j = i ∀k (i1,...,id) 1 1 d k=1 k 1 k 0 k k k 0 otherwise. (cid:80) We write P = α P (1) + . . . + α P (d) for the transition kernel of this random walk. For vertex- 1 d transitive graphs, there are at least two natural choices for α : we could take α = 1/d for each i i i, or α = deg(G )/ deg(G ) where deg(G ) is the degree of an arbitrary vertex in G . The i i j j j × × j latter choice corresponds to simple isotropic random walk on G . . . G . 1 d The following lemma, due to Cartwright and Soardi [CS87], tells us how to translate results about return probabilities on certain graphs into results about return probabilities on their Cartesian products. We recall that the Cayley graph G(Y ) of a group Y with generating set S 8 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: so

text: ρ(P

text: H

text: Showing

text: that

text: the

text: critical

text: BRW

text: is

text: one-ended

text: can

text: be

text: done

text: in

text: a

text: very

text: similar

text: way

text: to

text: the

text: proof

text: of

text: Proposition

text: Choose

text: any

text: two

text: particles

text: in

text: the

text: BRW,

text: and

text: colour

text: their

text: descendants

text: red

text: and

text: blue

text: respectively;

text: any

text: site

text: hit

text: by

text: both

text: a

text: red

text: and

text: a

text: blue

text: particle

text: is

text: coloured

text: purple.

text: Clearly

text: a

text: N

text: N

text: random

text: walk

text: on

text: H

text: eventually

text: hits

text: almost

text: surely,

text: so

text: is

text: hit

text: inﬁnitely

text: often

text: by

text: red

text: particles

text: and

text: inﬁnitely

text: often

text: by

text: blue

text: particles.

text: We

text: can

text: ensure

text: (for

text: example

text: by

text: constructing

text: embedded

text: Galton-Watson

text: processes

text: as

text: in

text: the

text: proof

text: of

text: Proposition

text: that

text: there

text: are

text: almost

text: surely

text: inﬁnitely

text: many

text: red-blue

text: pairs

text: within

text: distance

text: at

text: most

text: k

text: of

text: each

text: other.

text: Each

text: of

text: these

text: pairs

text: has

text: at

text: least

text: N

text: a

text: ﬁxed

text: probability

text: δ

text: of

text: creating

text: a

text: purple

text: dot

text: (since

text: this

text: time

text: does

text: not

text: have

text: bounded

text: N

text: T

text: degree,

text: we

text: have

text: to

text: allow

text: particles

text: to

text: bounce

text: back

text: and

text: forth

text: between

text: and

text: Thus

text: we

text: have

text: inﬁnitely

text: many

text: purple

text: dots

text: almost

text: surely,

text: and

text: since

text: our

text: initial

text: choice

text: of

text: red

text: and

text: blue

text: particles

text: was

text: arbitrary,

text: this

text: guarantees

text: that

text: we

text: have

text: only

text: one

text: end.

text: Remark

text: By

text: gluing

text: together

text: various

text: copies

text: of

text: graphs

text: already

text: constructed,

text: it

text: is

text: easy

text: to

text: construct

text: graphs

text: on

text: which

text: critical

text: BRW

text: has

text: any

text: number

text: of

text: ends.

text: For

text: example,

text: if

text: we

text: glue

text: two

text: copies

text: of

text: H

text: and

text: one

text: copy

text: of

text: T

text: T

text: at

text: a

text: single

text: vertex,

text: then

text: we

text: have

text: a

text: graph

text: on

text: which

text: critical

text: BRW

text: has

text: one

text: end,

text: two

text: ends,

text: or

text: inﬁnitely

text: many

text: ends,

text: each

text: with

text: positive

text: probability.

text: Open

text: problem.

text: Does

text: there

text: exist

text: a

text: quasi-symmetric

text: random

text: walk

text: such

text: that

text: the

text: corresponding

text: critical

text: BRW

text: is

text: one-ended

text: almost

text: surely?

text: Another

text: possibility

text: for

text: future

text: research

text: is

text: to

text: investigate

text: the

text: Cayley

text: graphs

text: of

text: co-compact

text: Fuchsian

text: groups.

text: These

text: graphs

text: correspond

text: to

text: tilings

text: of

text: the

text: hyperbolic

text: plane.

text: Lalley

text: and

text: Sellke

text: showed

text: that

text: critical

text: branching

text: Brownian

text: motion

text: on

text: the

text: hyperbolic

text: plane

text: has

text: a

text: limit

text: set

text: that

text: does

text: not

text: have

text: full

text: measure,

text: and

text: by

text: analogy

text: one

text: might

text: expect

text: that

text: critical

text: branching

text: random

text: walks

text: on

text: co-compact

text: Fuchsian

text: groups

text: have

text: inﬁnitely

text: many

text: ends.

text: Finally,

text: we

text: relay

text: a

text: conjecture

text: from

text: Itai

text: Benjamini.

text: Conjecture

text: (Itai

text: Benjamini,

text: private

text: communication).

text: On

text: any

text: vertex-transitive

text: graph

text: G,

text: the

text: trace

text: of

text: simple

text: critical

text: BRW

text: has

text: inﬁnitely

text: many

text: ends.

text: Appendix

text: on

text: product

text: random

text: walks

text: As

text: we

text: mentioned

text: brieﬂy

text: in

text: Section

text: given

text: random

text: walks

text: on

text: d

text: graphs

text: G

text: G

text: there

text: is

text: d

text: more

text: than

text: one

text: natural

text: random

text: walk

text: on

text: G

text: G

text: Rather

text: than

text: overcomplicate

text: matters

text: with

text: d

text: general

text: deﬁnitions

text: in

text: the

text: earlier

text: sections,

text: we

text: concentrated

text: on

text: one

text: such

text: natural

text: choice.

text: Here

text: we

text: give

text: more

text: details,

text: and

text: see

text: that

text: in

text: fact

text: our

text: results

text: hold

text: regardless

text: of

text: the

text: choice.

text: Given

text: random

text: walks

text: X(d)

text: on

text: G

text: G

text: respectively,

text: and

text: α

text: α

text: with

text: d

text: ×d

text: α1

text: αd

text: we

text: deﬁne

text: the

text: αd)-product

text: random

text: walk

text: X

text: on

text: G

text: Gd

text: by

text: setting

text: α

text: P(X(l)

text: j

text: |X(l)

text: i

text: if

text: j

text: i

text: ∀k

text: l,

text: j

text: i

text: l

text: l

text: l

text: k

text: k

text: l

text: l

text: P

text: (X

text: (j

text: j

text: d

text: α

text: P(X(k)

text: i

text: |X(k)

text: i

text: if

text: j

text: i

text: ∀k

text: d

text: k

text: k

text: k

text: k

text: k

text: otherwise.

text: We

text: write

text: P

text: α

text: P

text: α

text: P

text: (d)

text: for

text: the

text: transition

text: kernel

text: of

text: this

text: random

text: walk.

text: For

text: vertex-

text: d

text: transitive

text: graphs,

text: there

text: are

text: at

text: least

text: two

text: natural

text: choices

text: for

text: α

text: we

text: could

text: take

text: α

text: for

text: each

text: i

text: i

text: i,

text: or

text: α

text: deg(G

text: deg(G

text: where

text: deg(G

text: is

text: the

text: degree

text: of

text: an

text: arbitrary

text: vertex

text: in

text: G

text: The

text: i

text: i

text: j

text: j

text: j

text: j

text: latter

text: choice

text: corresponds

text: to

text: simple

text: isotropic

text: random

text: walk

text: on

text: G

text: G

text: d

text: The

text: following

text: lemma,

text: due

text: to

text: Cartwright

text: and

text: Soardi

text: tells

text: us

text: how

text: to

text: translate

text: results

text: about

text: return

text: probabilities

text: on

text: certain

text: graphs

text: into

text: results

text: about

text: return

text: probabilities

text: on

text: their

text: Cartesian

text: products.

text: We

text: recall

text: that

text: the

text: Cayley

text: graph

text: G(Y

text: of

text: a

text: group

text: Y

text: with

text: generating

text: set

text: S

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ∈ has as its vertex set the elements of Y , with two vertices i, j Y joined by an edge if i = js for ∈ P ∼ P → → ∞ some s S. We write that (X = i) b if (X = i)/b 1 as n through values such n n n n P that (X = i) > 0. n Lemma 6.1. Suppose that G , . . . , G are Cayley graphs with associated random walks X(1), . . . , X(d). 1 d × × ∈ Let X be the (α , . . . , α )-product random walk on G = G . . . G . Fix i = (i , . . . , i ) G. 1 d 1 d 1 d Suppose that there exist constants C , . . . , C > 0 and a , . . . , a such that for each k = 1, . . . , d, 1 d 1 d P ∼ ρn (X(k) = i ) C k . ik n k j nak Then there exists C such that P ∼ (α1ρ1 + . . . + αdρd)n (X = i) C . i n na1+...+ad Note in particular that the choice of α , . . . , α aﬀects the spectral radius in the obvious way, 1 d and has no eﬀect on the polynomial terms. Thus the proofs in earlier sections are unaﬀected × Z by choosing diﬀerent α , . . . , α . For example, the results on T where we used 1P + 1PZ 1 d 3 2×TZ3 2 hold also for 3P + 2PZ, which corresponds to simple isotropic random walk on T . 5 T3 5 3 Acknowledgements We would like to thank Itai Benjamini for asking us these questions, and for several helpful discussions. We are also grateful to Steven Lalley, Yuval Peres and Yehuda Pinchover. Dur- ing this project EC received support from the Austrian Academy of Science (DOC-fFORTE fellowship, project number D-1503000014); Microsoft Research; Austrian Science Fund (FWF): S09606, part of the Austrian National Research Network “Analytic Combinatorics and Proba- bilistic Number Theory”; and Project DK plus, funded by FWF, Austrian Science Fund (project number E-1503W01230). MR was supported by a CRM-ISM postdoctoral fellowship, McGill University, the University of Warwick, and EPSRC Fellowship EP/K007440/1. References [BM12] Itai Benjamini and Sebastian Mu¨ller, On the trace of branching random walks, Groups Geom. Dyn. 2 (2012), no. 2, 231–247. [BP94] Itai Benjamini and Yuval Peres, Markov chains indexed by trees, Ann. Probab. 22 (1994), no. 1, 219–243. [BZ08] Daniela Bertacchi and Fabio Zucca, Critical behaviors and critical values of branching random walks on multigraphs, J. Appl. Probab. 45 (2008), no. 2, 481–497. [CS86] Donald I. Cartwright and P. M. Soardi, Random walks on free products, quotients and amalgams, Nagoya Math. J. 102 (1986), 163–180. [CS87] Donald I. Cartwright and P. M. Soardi, A local limit theorem for random walks on the Cartesian product of discrete groups, Boll. Unione Mat. Ital. A (7) 1 (1987), no. 1, 107–115. [GM06] N. Gantert and S. Mu¨ller, The critical branching Markov chain is transient, Markov Process. Related Fields 12 (2006), no. 4, 805–814. [GW86] Peter Gerl and Wolfgang Woess, Local limits and harmonic functions for nonisotropic random walks on free groups, Probab. Theory Related Fields 71 (1986), no. 3, 341–355. [Kes59] Harry Kesten, Symmetric random walks on groups, Trans. Amer. Math. Soc. 92 (1959), no. 2, 336–354. 9 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: has

text: as

text: its

text: vertex

text: set

text: the

text: elements

text: of

text: Y

text: with

text: two

text: vertices

text: i,

text: j

text: Y

text: joined

text: by

text: an

text: edge

text: if

text: i

text: js

text: for

text: P

text: P

text: some

text: s

text: S.

text: We

text: write

text: that

text: (X

text: i)

text: b

text: if

text: (X

text: i)/b

text: as

text: n

text: through

text: values

text: such

text: n

text: n

text: n

text: n

text: P

text: that

text: (X

text: i)

text: n

text: Lemma

text: Suppose

text: that

text: G

text: G

text: are

text: Cayley

text: graphs

text: with

text: associated

text: random

text: walks

text: X(d).

text: d

text: Let

text: X

text: be

text: the

text: (α

text: α

text: )-product

text: random

text: walk

text: on

text: G

text: G

text: G

text: Fix

text: i

text: (i

text: i

text: G.

text: d

text: d

text: d

text: Suppose

text: that

text: there

text: exist

text: constants

text: C

text: C

text: and

text: a

text: a

text: such

text: that

text: for

text: each

text: k

text: d,

text: d

text: d

text: P

text: ρn

text: (X(k)

text: i

text: C

text: k

text: ik

text: n

text: k

text: j

text: nak

text: Then

text: there

text: exists

text: C

text: such

text: that

text: P

text: αdρd)n

text: (X

text: i)

text: C

text: i

text: n

text: Note

text: in

text: particular

text: that

text: the

text: choice

text: of

text: α

text: α

text: aﬀects

text: the

text: spectral

text: radius

text: in

text: the

text: obvious

text: way,

text: d

text: and

text: has

text: no

text: eﬀect

text: on

text: the

text: polynomial

text: terms.

text: Thus

text: the

text: proofs

text: in

text: earlier

text: sections

text: are

text: unaﬀected

text: Z

text: by

text: choosing

text: diﬀerent

text: α

text: α

text: For

text: example,

text: the

text: results

text: on

text: T

text: where

text: we

text: used

text: d

text: hold

text: also

text: for

text: which

text: corresponds

text: to

text: simple

text: isotropic

text: random

text: walk

text: on

text: T

text: Acknowledgements

text: We

text: would

text: like

text: to

text: thank

text: Itai

text: Benjamini

text: for

text: asking

text: us

text: these

text: questions,

text: and

text: for

text: several

text: helpful

text: discussions.

text: We

text: are

text: also

text: grateful

text: to

text: Steven

text: Lalley,

text: Yuval

text: Peres

text: and

text: Yehuda

text: Pinchover.

text: Dur-

text: ing

text: this

text: project

text: EC

text: received

text: support

text: from

text: the

text: Austrian

text: Academy

text: of

text: Science

text: (DOC-fFORTE

text: fellowship,

text: project

text: number

text: Microsoft

text: Research;

text: Austrian

text: Science

text: Fund

text: (FWF):

text: part

text: of

text: the

text: Austrian

text: National

text: Research

text: Network

text: “Analytic

text: Combinatorics

text: and

text: Proba-

text: bilistic

text: Number

text: Theory”;

text: and

text: Project

text: DK

text: plus,

text: funded

text: by

text: FWF,

text: Austrian

text: Science

text: Fund

text: (project

text: number

text: MR

text: was

text: supported

text: by

text: a

text: CRM-ISM

text: postdoctoral

text: fellowship,

text: McGill

text: University,

text: the

text: University

text: of

text: Warwick,

text: and

text: EPSRC

text: Fellowship

text: References

text: Itai

text: Benjamini

text: and

text: Sebastian

text: Mu¨ller,

text: On

text: the

text: trace

text: of

text: branching

text: random

text: walks,

text: Groups

text: Geom.

text: Dyn.

text: no.

text: Itai

text: Benjamini

text: and

text: Yuval

text: Peres,

text: Markov

text: chains

text: indexed

text: by

text: trees,

text: Ann.

text: Probab.

text: no.

text: Daniela

text: Bertacchi

text: and

text: Fabio

text: Zucca,

text: Critical

text: behaviors

text: and

text: critical

text: values

text: of

text: branching

text: random

text: walks

text: on

text: multigraphs,

text: J.

text: Appl.

text: Probab.

text: no.

text: Donald

text: I.

text: Cartwright

text: and

text: P.

text: M.

text: Soardi,

text: Random

text: walks

text: on

text: free

text: products,

text: quotients

text: and

text: amalgams,

text: Nagoya

text: Math.

text: J.

text: Donald

text: I.

text: Cartwright

text: and

text: P.

text: M.

text: Soardi,

text: A

text: local

text: limit

text: theorem

text: for

text: random

text: walks

text: on

text: the

text: Cartesian

text: product

text: of

text: discrete

text: groups,

text: Boll.

text: Unione

text: Mat.

text: Ital.

text: A

text: no.

text: N.

text: Gantert

text: and

text: S.

text: Mu¨ller,

text: The

text: critical

text: branching

text: Markov

text: chain

text: is

text: transient,

text: Markov

text: Process.

text: Related

text: Fields

text: no.

text: Peter

text: Gerl

text: and

text: Wolfgang

text: Woess,

text: Local

text: limits

text: and

text: harmonic

text: functions

text: for

text: nonisotropic

text: random

text: walks

text: on

text: free

text: groups,

text: Probab.

text: Theory

text: Related

text: Fields

text: no.

text: Harry

text: Kesten,

text: Symmetric

text: random

text: walks

text: on

text: groups,

text: Trans.

text: Amer.

text: Math.

text: Soc.

text: no.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: A GLOBAL MINIMIZATION ALGORITHM FOR TIKHONOV FUNCTIONALS WITH SPARSITY CONSTRAINTS WEI WANG, STEPHAN W. ANZENGRUBER, RONNY RAMLAU, AND BO HAN Abstract. In this paper we present a globally convergent algorithm for the computation of a minimizer of the Tikhonov functional with sparsity promoting penalty term for nonlinear forward operators in Banach space. The dual TIGRA method uses a gradient descent iteration in the dual space at decreasing values of the regularization parameter α , where the approximation obtained with α j j serves as the starting value for the dual iteration with parameter α . With j+1 the discrepancy principle as a global stopping rule the method further yields an automatic parameter choice. We prove convergence of the algorithm under suitable step-size selection and stopping rules and illustrate our theoretic results with numerical experiments for the nonlinear autoconvolution problem. 1. Introduction Tikhonov regularization has become a well-established and widely used method for the stable solution of ill-posed problems. Its regularizing properties as well as convergence and rates of convergence of the approximate solutions have been studied in great detail. In particular, the theory for the classical formulation, where the penalty term is the square of the norm in a Hilbert space, is well developed (see, e.g. [12]). Over the last decade, there has been a growing interest in more general convex penalty terms in Banach spaces as well. Using a total variation type penalty [1, 9, 24, 31], for example, allows for the reconstruction of sharp edges in images, whereas (cid:96)p-norms of basis coeﬃcients with p < 2 [10, 29, 27] are known to promote sparsity in the solution – a desireable eﬀect in many applications. We refer the interested reader to the monographs [33, 34] and to the incomplete list [2, 3, 4, 6, 14, 16, 17, 30] for further information in this direction. Open questions remain, however, concerning the computational aspects of ﬁnd- ing a minimizer of the Tikhonov functional. Especially, if the forward operator is non-linear many optimization routines will only converge locally and it may not be possible to obtain a global minimizer. Several attempts have been made to tackle this problem in the classical Hilbert space setting. In [25, 26] the TIGRA (TIkhonov-GRAdient) algorithm was introduced which applies a gradient descent method to the Tikhonov functional at a decreasing sequence of regularization pa- rameters α = q¯jα . This algorithm was further studied in [20, 21, 22]. Another j 0 approach to obtain a global minimizer are multi-level methods [18, 19, 11], which Date: 2010 Mathematics Subject Classiﬁcation. 65J20, 47J06, 47A52, 49J40. Key words and phrases. Inverse problems, Tikhonov regularization, global optimization, gra- dient descent method, TIGRA, parameter choice rules. 1 ##LTLine##

text: A

text: GLOBAL

text: MINIMIZATION

text: ALGORITHM

text: FOR

text: TIKHONOV

text: FUNCTIONALS

text: WITH

text: SPARSITY

text: CONSTRAINTS

text: WEI

text: WANG,

text: STEPHAN

text: W.

text: ANZENGRUBER,

text: RONNY

text: RAMLAU,

text: AND

text: BO

text: HAN

text: Abstract.

text: In

text: this

text: paper

text: we

text: present

text: a

text: globally

text: convergent

text: algorithm

text: for

text: the

text: computation

text: of

text: a

text: minimizer

text: of

text: the

text: Tikhonov

text: functional

text: with

text: sparsity

text: promoting

text: penalty

text: term

text: for

text: nonlinear

text: forward

text: operators

text: in

text: Banach

text: space.

text: The

text: dual

text: TIGRA

text: method

text: uses

text: a

text: gradient

text: descent

text: iteration

text: in

text: the

text: dual

text: space

text: at

text: decreasing

text: values

text: of

text: the

text: regularization

text: parameter

text: α

text: where

text: the

text: approximation

text: obtained

text: with

text: α

text: j

text: j

text: serves

text: as

text: the

text: starting

text: value

text: for

text: the

text: dual

text: iteration

text: with

text: parameter

text: α

text: With

text: the

text: discrepancy

text: principle

text: as

text: a

text: global

text: stopping

text: rule

text: the

text: method

text: further

text: yields

text: an

text: automatic

text: parameter

text: choice.

text: We

text: prove

text: convergence

text: of

text: the

text: algorithm

text: under

text: suitable

text: step-size

text: selection

text: and

text: stopping

text: rules

text: and

text: illustrate

text: our

text: theoretic

text: results

text: with

text: numerical

text: experiments

text: for

text: the

text: nonlinear

text: autoconvolution

text: problem.

text: Introduction

text: Tikhonov

text: regularization

text: has

text: become

text: a

text: well-established

text: and

text: widely

text: used

text: method

text: for

text: the

text: stable

text: solution

text: of

text: ill-posed

text: problems.

text: Its

text: regularizing

text: properties

text: as

text: well

text: as

text: convergence

text: and

text: rates

text: of

text: convergence

text: of

text: the

text: approximate

text: solutions

text: have

text: been

text: studied

text: in

text: great

text: detail.

text: In

text: particular,

text: the

text: theory

text: for

text: the

text: classical

text: formulation,

text: where

text: the

text: penalty

text: term

text: is

text: the

text: square

text: of

text: the

text: norm

text: in

text: a

text: Hilbert

text: space,

text: is

text: well

text: developed

text: (see,

text: e.g.

text: Over

text: the

text: last

text: decade,

text: there

text: has

text: been

text: a

text: growing

text: interest

text: in

text: more

text: general

text: convex

text: penalty

text: terms

text: in

text: Banach

text: spaces

text: as

text: well.

text: Using

text: a

text: total

text: variation

text: type

text: penalty

text: for

text: example,

text: allows

text: for

text: the

text: reconstruction

text: of

text: sharp

text: edges

text: in

text: images,

text: whereas

text: of

text: basis

text: coeﬃcients

text: with

text: p

text: are

text: known

text: to

text: promote

text: sparsity

text: in

text: the

text: solution

text: a

text: desireable

text: eﬀect

text: in

text: many

text: applications.

text: We

text: refer

text: the

text: interested

text: reader

text: to

text: the

text: monographs

text: and

text: to

text: the

text: incomplete

text: list

text: for

text: further

text: information

text: in

text: this

text: direction.

text: Open

text: questions

text: remain,

text: however,

text: concerning

text: the

text: computational

text: aspects

text: of

text: ﬁnd-

text: ing

text: a

text: minimizer

text: of

text: the

text: Tikhonov

text: functional.

text: Especially,

text: if

text: the

text: forward

text: operator

text: is

text: non-linear

text: many

text: optimization

text: routines

text: will

text: only

text: converge

text: locally

text: and

text: it

text: may

text: not

text: be

text: possible

text: to

text: obtain

text: a

text: global

text: minimizer.

text: Several

text: attempts

text: have

text: been

text: made

text: to

text: tackle

text: this

text: problem

text: in

text: the

text: classical

text: Hilbert

text: space

text: setting.

text: In

text: the

text: TIGRA

text: (TIkhonov-GRAdient)

text: algorithm

text: was

text: introduced

text: which

text: applies

text: a

text: gradient

text: descent

text: method

text: to

text: the

text: Tikhonov

text: functional

text: at

text: a

text: decreasing

text: sequence

text: of

text: regularization

text: pa-

text: rameters

text: α

text: q¯jα

text: This

text: algorithm

text: was

text: further

text: studied

text: in

text: Another

text: j

text: approach

text: to

text: obtain

text: a

text: global

text: minimizer

text: are

text: multi-level

text: methods

text: which

text: Date:

text: Mathematics

text: Subject

text: Classiﬁcation.

text: Key

text: words

text: and

text: phrases.

text: Inverse

text: problems,

text: Tikhonov

text: regularization,

text: global

text: optimization,

text: gra-

text: dient

text: descent

text: method,

text: TIGRA,

text: parameter

text: choice

text: rules.

text: ##LTLine##


text: 12 WEI WANG, STEPHAN W. ANZENGRUBER, RONNY RAMLAU, AND BO HAN (cid:54) Theorem 3.7. Let Assumption 2.5 hold and suppose that D (xδ , x ) d with ∇ (cid:54) fp αj j,k α d as in Lemma 3.5 and that Φ (x ) = 0. Then x from (3.6) is at least α αj j,k j,k+1 as close to xδ as x with respect to the Bregman distance, i.e. αj j,k (cid:54) D (xδ , x ) D (xδ , x ), fp αj j,k+1 fp αj j,k if the step-size β is chosen such that j,k (cid:54) γ c¯ α (3.7) β (cid:107)∇ j,k j (cid:107) , j,k Φ (x ) 2 αj j,k   holds, where    −  8c¯ (Φ (x ) φ ) (3.8) c¯j,k := min 1, A αj j,k j,k 2−p 4K2 + 4Ls(cid:37)α + 4LKr + L2r 2 + 8α c˜ c¯ 2 j αj αj j p A − − with c¯ := p 1(2r + A)p 2 and A 2 α { ∇ ∈ R } φ := min Φ (J (J (x ) + t Φ (x ))) : t + . j,k αj q p j,k αj j,k Using the decay with respect to the Bregman distance, we also obtain mono- (cid:107)∇ (cid:107) → tonicity in the Tikhonov functional values Φ (x ) and that Φ (x ) 0 → ∞ αj j,k αj j,k as k . It is worth noting that the latter also ensures that the inner stopping (cid:107)∇ (cid:107) (cid:54) rule Φ (x ) C is well-deﬁned for any value C > 0. For the proof, αj j,k αj αj which goes along the lines of Theorem 2.9 in [25], we refer to Section 12, where the constants M are explicitely given as well. αj (cid:54) Proposition 3.8. Let Assumption 2.5 hold and suppose that D (xδ , x ) d fp αj 0 α with d as in Lemma 3.5. Then there exists a constant M > 0 such that the sequenαce {x } ∈N generated by ((cid:26)3.6) with step-sizes (cid:27) αj j,k k 0 γ c¯ α 1 (3.9) β := min (cid:107)∇ j,k j (cid:107) , j,k Φ (x ) 2 2M αj j,k αj satisﬁes (cid:54) (cid:54) Φ (x ) Φ (x ) and R (x , x ) M D (x , x ) αj j,k+1 αj j,k Φαj j,k+1 j,k αj fp j,k+1 j,k (cid:62) for all k 0, as well as (cid:107)∇ (cid:107) → → ∞ Φ (x ) 0 as k . αj j,k Now we can give the convergence result for the dual gradient descent method (cid:62) ∗ with ﬁxed α α . j ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: WEI

text: WANG,

text: STEPHAN

text: W.

text: ANZENGRUBER,

text: RONNY

text: RAMLAU,

text: AND

text: BO

text: HAN

text: Theorem

text: Let

text: Assumption

text: hold

text: and

text: suppose

text: that

text: D

text: (xδ

text: x

text: d

text: with

font: default

text: fp

text: αj

text: j,k

text: α

text: d

text: as

text: in

text: Lemma

text: and

text: that

text: Φ

text: (x

text: Then

text: x

text: from

text: is

text: at

text: least

text: α

text: αj

text: j,k

text: as

text: close

text: to

text: xδ

text: as

text: x

text: with

text: respect

text: to

text: the

text: Bregman

text: distance,

text: i.e.

text: αj

text: j,k

text: D

text: (xδ

text: x

text: D

text: (xδ

text: x

text: fp

text: αj

text: fp

text: αj

text: j,k

text: if

text: the

text: step-size

text: β

text: is

text: chosen

text: such

text: that

text: j,k

text: γ

text: c¯

text: α

text: β

text: j,k

text: j

text: j,k

text: Φ

text: (x

text: αj

text: j,k

text: holds,

text: where

text: (Φ

text: (x

text: φ

text: c¯j,k

text: min

text: A

text: αj

text: j,k

text: j,k

text: 8α

text: c˜

text: c¯

text: j

text: αj

text: αj

text: j

text: p

text: A

text: with

text: c¯

text: p

text: A)p

text: and

text: A

text: α

text: R

text: φ

text: min

text: Φ

text: (J

text: (J

text: (x

text: t

text: Φ

text: (x

text: t

text: j,k

text: αj

text: q

text: p

text: j,k

text: αj

text: j,k

text: Using

text: the

text: decay

text: with

text: respect

text: to

text: the

text: Bregman

text: distance,

text: we

text: also

text: obtain

text: mono-

text: tonicity

text: in

text: the

text: Tikhonov

text: functional

text: values

text: Φ

text: (x

text: and

text: that

text: Φ

text: (x

text: αj

text: j,k

text: αj

text: j,k

text: as

text: k

text: It

text: is

text: worth

text: noting

text: that

text: the

text: latter

text: also

text: ensures

text: that

text: the

text: inner

text: stopping

text: rule

text: Φ

text: (x

text: C

text: is

text: well-deﬁned

text: for

text: any

text: value

text: C

text: For

text: the

text: proof,

text: αj

text: j,k

text: αj

text: αj

text: which

text: goes

text: along

text: the

text: lines

text: of

text: Theorem

text: in

text: we

text: refer

text: to

text: Section

text: where

text: the

text: constants

text: M

text: are

text: explicitely

text: given

text: as

text: well.

text: αj

text: Proposition

text: Let

text: Assumption

text: hold

text: and

text: suppose

text: that

text: D

text: (xδ

text: x

text: d

text: fp

text: αj

text: α

text: with

text: d

text: as

text: in

text: Lemma

text: Then

text: there

text: exists

text: a

text: constant

text: M

text: such

text: that

text: the

text: sequenαce

text: {x

text: ∈N

text: generated

text: by

text: with

text: step-sizes

text: αj

text: j,k

text: k

text: γ

text: c¯

text: α

text: β

text: min

text: j,k

text: j

text: j,k

text: Φ

text: (x

text: αj

text: j,k

text: αj

text: satisﬁes

text: Φ

text: (x

text: Φ

text: (x

text: and

text: R

text: (x

text: x

text: M

text: D

text: (x

text: x

text: αj

text: αj

text: j,k

text: Φαj

text: j,k

text: αj

text: fp

text: j,k

text: for

text: all

text: k

text: as

text: well

text: as

text: Φ

text: (x

text: as

text: k

text: αj

text: j,k

text: Now

text: we

text: can

text: give

text: the

text: convergence

text: result

text: for

text: the

text: dual

text: gradient

text: descent

text: method

text: with

text: ﬁxed

text: α

text: α

text: j

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 16 WEI WANG, STEPHAN W. ANZENGRUBER, RONNY RAMLAU, AND BO HAN the ﬁnal iterate with index j, and using an induction argument the assertion follows ∈ N (cid:54) (cid:54) ∗ for all j and 0 k k (j). According to Lemma 3.5 it thus holds that 0 (cid:54) (cid:107) − (cid:107) (cid:54) D (xδ , x ) d and xδ x r . fp αj j,k αj αj j,k (cid:62)αj ∗ To prove that the dual TIGRA algorithm stops with α ∗ α , we proceed j by contradiction. Note that the sequence α = q¯jα is monotonically decreasing j 0 and converges to zero since q¯ < 1. Let now j denote the unique index such that (cid:62) ∗ ∗ ∗ (cid:62) α α and α = q¯α < α and suppose that j j + 1. Due to Lemma 2.3 j j+−1 j − (cid:107)∇ (cid:107) (cid:54) with c = c¯ = p 1(A + 2r )p 2, the inner stopping rule Φ (x ∗) C and p A 2 αj αj j,k αj Proposition 3.3 we obtain (cid:107) − (cid:107) (cid:54) 1 (cid:54) 1 (cid:104)∇ − (cid:105) xδ x ∗ 2 D (xδ , x ∗) Φ (x ∗), x ∗ xδ αj j,k c¯ fp αj j,k c¯ γα αj j,k j,k αj A A j (cid:54) C (cid:107) − (cid:107) αj xδ x ∗ . c¯ γα αj j,k A j (cid:107) − (cid:107) (cid:54) Using a boot-strap argument on the one hand, and that xδ x ∗ r on the αj j,k αj other hand, it follows that (cid:107) − (cid:107) (cid:54) C (cid:54) C r xδ x ∗ αj and D (xδ , x ∗) αj αj . αj j,k c¯ γα fp αj j,k γα A j j Thus, Assumption 2.5, Lemma 2.8 and Assumption 4.1 (iv) yield (cid:107) − (cid:107) F (x ∗) F (xδ ) (cid:54)j,k(cid:107) α−j − (cid:48) − (cid:107) (cid:107) (cid:48) (cid:107)(cid:107) − (cid:107) F (x ∗) F (xδ ) F (x ∗)(xδ x ∗) + F (x ∗) xδ x ∗ (cid:54) j,k(cid:0) αj (cid:1)j,k (cid:107) αj− j,k (cid:107) j,k αj j,k cD (xδ , x ∗) + (Lr + K) xδ x ∗ fp αj j,k αj αj j,k (cid:54) C (cid:54) αj r (c c¯ + L) + K δ. c¯ γα αj A A j (cid:107) − (cid:107) (cid:54) ∗ In combination with F (xδ ) yδ 2(cid:37)α + δ from (2.11) and α < α = −δ αj j j+1 (s 2)(cid:37) we obtain (cid:107) − (cid:107) (cid:54) (cid:107) − (cid:107) (cid:107) − (cid:107) (cid:54) α F (x ∗) yδ F (x ∗) F (xδ ) + F (xδ ) yδ 2(cid:37) j+1 + 2δ j,k j,k αj αj q¯ (cid:54) 2δ (cid:54) − + 2δ τδ. q¯(s 2) Thus the discrepancy principle with τ from Assumption 4.1 (v) is satisﬁed for x ∗, ∗ (cid:62) j,k which contradicts our assumption j j + 1. Hence, the iteration terminates with (cid:62) ∗ (cid:3) a regularization parameter α ∗ α . j 5. Numerical examples In this section we compare numerical results for the d-TIGRA method to a dual version of the modiﬁed Landweber method [32]. Both methods are applied to the nonlinear ill-posed auto-convolution problem (compare also [3]), where the forward operator is given by ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: WEI

text: WANG,

text: STEPHAN

text: W.

text: ANZENGRUBER,

text: RONNY

text: RAMLAU,

text: AND

text: BO

text: HAN

text: the

text: ﬁnal

text: iterate

text: with

text: index

text: j,

text: and

text: using

text: an

text: induction

text: argument

text: the

text: assertion

text: follows

text: N

text: for

text: all

text: j

text: and

text: k

text: k

text: (j).

text: According

text: to

text: Lemma

text: it

text: thus

text: holds

text: that

text: D

text: (xδ

text: x

text: d

text: and

text: xδ

text: x

text: r

text: fp

text: αj

text: j,k

text: αj

text: αj

text: j,k

text: To

text: prove

text: that

text: the

text: dual

text: TIGRA

text: algorithm

text: stops

text: with

text: α

text: α

text: we

text: proceed

text: j

text: by

text: contradiction.

text: Note

text: that

text: the

text: sequence

text: α

text: q¯jα

text: is

text: monotonically

text: decreasing

text: j

text: and

text: converges

text: to

text: zero

text: since

text: q¯

text: Let

text: now

text: j

text: denote

text: the

text: unique

text: index

text: such

text: that

text: α

text: α

text: and

text: α

text: q¯α

text: α

text: and

text: suppose

text: that

text: j

text: j

text: Due

text: to

text: Lemma

text: j

text: j

text: with

text: c

text: c¯

text: p

text: )p

text: the

text: inner

text: stopping

text: rule

text: Φ

text: (x

text: C

text: and

text: p

text: A

text: αj

text: αj

text: j,k

text: αj

text: Proposition

text: we

text: obtain

text: xδ

text: x

text: D

text: (xδ

text: x

text: Φ

text: (x

text: x

text: xδ

text: αj

text: j,k

text: c¯

text: fp

text: αj

text: j,k

text: c¯

text: γα

text: αj

text: j,k

text: j,k

text: αj

text: A

text: A

text: j

text: C

text: αj

text: xδ

text: x

text: c¯

text: γα

text: αj

text: j,k

text: A

text: j

text: Using

text: a

text: boot-strap

text: argument

text: on

text: the

text: one

text: hand,

text: and

text: that

text: xδ

text: x

text: r

text: on

text: the

text: αj

text: j,k

text: αj

text: other

text: hand,

text: it

text: follows

text: that

text: C

text: C

text: r

text: xδ

text: x

text: αj

text: and

text: D

text: (xδ

text: x

text: αj

text: αj

text: αj

text: j,k

text: c¯

text: γα

text: fp

text: αj

text: j,k

text: γα

text: A

text: j

text: j

text: Thus,

text: Assumption

text: Lemma

text: and

text: Assumption

text: (iv)

text: yield

text: F

text: (x

text: F

text: (xδ

text: α−j

text: F

text: (x

text: F

text: (xδ

text: F

text: (x

text: ∗)(xδ

text: x

text: F

text: (x

text: xδ

text: x

text: αj

text: αj−

text: j,k

text: j,k

text: αj

text: j,k

text: cD

text: (xδ

text: x

text: (Lr

text: K)

text: xδ

text: x

text: fp

text: αj

text: j,k

text: αj

text: αj

text: j,k

text: C

text: αj

text: r

text: (c

text: c¯

text: L)

text: K

text: δ.

text: c¯

text: γα

text: αj

text: A

text: A

text: j

text: In

text: combination

text: with

text: F

text: (xδ

text: yδ

text: δ

text: from

text: and

text: α

text: α

text: −δ

text: αj

text: j

text: (s

text: we

text: obtain

text: α

text: F

text: (x

text: yδ

text: F

text: (x

text: F

text: (xδ

text: F

text: (xδ

text: yδ

text: 2δ

text: j,k

text: j,k

text: αj

text: αj

text: q¯

text: 2δ

text: 2δ

text: τδ.

text: q¯(s

text: Thus

text: the

text: discrepancy

text: principle

text: with

text: τ

text: from

text: Assumption

text: (v)

text: is

text: satisﬁed

text: for

text: x

text: j,k

text: which

text: contradicts

text: our

text: assumption

text: j

text: j

text: Hence,

text: the

text: iteration

text: terminates

text: with

text: a

text: regularization

text: parameter

text: α

text: α

text: j

text: Numerical

text: examples

text: In

text: this

text: section

text: we

text: compare

text: numerical

text: results

text: for

text: the

text: d-TIGRA

text: method

text: to

text: a

text: dual

text: version

text: of

text: the

text: modiﬁed

text: Landweber

text: method

text: Both

text: methods

text: are

text: applied

text: to

text: the

text: nonlinear

text: ill-posed

text: auto-convolution

text: problem

text: (compare

text: also

text: where

text: the

text: forward

text: operator

text: is

text: given

text: by

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: GLOBAL MINIMIZATION OF TIKHONOV FUNCTIONALS 31 c Asmp. 2.5 (ii) − p 1 − c = (3A)p 2 Prop. 2.9 A 2 − (cid:26) (cid:27) p 1 − c¯ = (2r + A)p 2 Theorem 3.7 A α 2 − 2c¯ (√Φ (x ) φ ) c¯ = min 1, A αj j,k min,k Theorem 3.7 j,k (cid:16) K2 + 2c c¯ K + c2c¯ +(cid:17) 4c¯ α A A A j c , c˜ Lemma 2.3 p p − − p 1 − p 2 cp(α) = 2 (cid:40) 3(rα + A(cid:18)) + 2(Tακα)p 1 (cid:19) (cid:41) Prop. 6.5 c , c˜ Lemma 2.4 q q − − q 1 − q 2 c˜ (α) = max 1, 2(r + A)p 1 + r Prop. 6.3 q α α 2 d Lemma 3.5 α q¯ Lemma 3.10 2sc(cid:37) (cid:40) (cid:114) (cid:41) q¯ = Prop. 2.9 0 1 + sc(cid:37) 2 √ 2γα 9c r = min , γα Theorem 3.2 α sc(1 + 2) 3K 10L s Asmp. 2.5 (iii) (cid:16) (cid:17) (cid:26) (cid:27) p 1/p (cid:107) − (cid:107) A = ∗ F (0) yδ 2/p Lemma 2.8 2α (cid:54) d δ c¯ C γα min αj+1 , A Prop. 4.2 αj j 3r K + r (c c¯ + L) (cid:107) (cid:48) (cid:107)αj αj A K = LA + F (0) Lemma 2.8 L Asmp. 2.5 (i) T 2κ2 Lr + K M = c2 α α + α + c(cd + (Lr + K)r + s(cid:37)α) + α Prop. 6.5 α α α α 2c (α) c (α) p p r α T = Prop. 6.5 α c˜ (α)C q α ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: GLOBAL

text: MINIMIZATION

text: OF

text: TIKHONOV

text: FUNCTIONALS

text: c

text: Asmp.

text: (ii)

text: p

text: c

text: Prop.

text: A

text: p

text: c¯

text: A)p

text: Theorem

text: A

text: α

text: (√Φ

text: (x

text: φ

text: c¯

text: min

text: A

text: αj

text: j,k

text: min,k

text: Theorem

text: j,k

text: c¯

text: K

text: α

text: A

text: A

text: A

text: j

text: c

text: c˜

text: Lemma

text: p

text: p

text: p

text: p

text: cp(α)

text: Prop.

text: c

text: c˜

text: Lemma

text: q

text: q

text: q

text: q

text: c˜

text: (α)

text: max

text: A)p

text: r

text: Prop.

text: q

text: α

text: α

text: d

text: Lemma

text: α

text: q¯

text: Lemma

text: q¯

text: Prop.

text: 2γα

text: r

text: min

text: γα

text: Theorem

text: α

text: s

text: Asmp.

text: (iii)

text: p

text: A

text: F

text: yδ

text: Lemma

text: 2α

text: d

text: δ

text: c¯

text: C

text: γα

text: min

text: A

text: Prop.

text: αj

text: j

text: K

text: r

text: (c

text: c¯

text: L)

text: αj

text: A

text: K

text: LA

text: F

text: Lemma

text: L

text: Asmp.

text: (i)

text: T

text: Lr

text: K

text: M

text: α

text: α

text: α

text: c(cd

text: (Lr

text: K)r

text: α

text: Prop.

text: α

text: α

text: α

text: α

text: (α)

text: c

text: (α)

text: p

text: p

text: r

text: α

text: T

text: Prop.

text: α

text: c˜

text: (α)C

text: q

text: α

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##