text: Hybrid PDE solver for data-driven problems and modern branching 9 a theoretical speedup observed speedup (approx.) 0 .04 13.93 15 .02 28.34 29 .01 57.42 60 .005 116.00 125 .0025 233.84 250 Table 2.1. Acceleration of the most current version of PDD (IterPDD), with improved stochastic numerics, over the previous PDD algorithm. a is the error tolerance on inter- 0 facing nodes. The BVP being solved is (2.10). [12]). IterPDD is a numerical suite which includes variance reduction techniques with iterative control variates based on nested, increasingly accurate global solutions. The speedup of a method A over a method B to solve a BVP is deﬁned as Time taken by method B S(A, B) = . (2.11) Time taken by method A Table 2.1 shows the speedup of IterPDD over the previous versions of PDD. Note that IterPDD retains all the advantages of any previous version of the PDD algorithm and hence it is not necessary to compare it against DDD solvers, since S(IterPDD, DDD) = × S(IterPDD, PDD) S(PDD, DDD). The theoretical speedup in Table 2.1 is the op- timal speedup predicted by a sensitivity algorithm presented in [12]. Importantly, the latter is designed in such a way that it relies on fast warm up Monte Carlo sampling, and runs in parallel so as not to defeat the purpose of PDD. The agreement with the experimentally observed speedup is consistently conservative. The acceleration (speedup) grows larger as the target nodal accuracy a (the largest 0 admissible error of the numerical solution on the interface nodes, obtained via the prob- abilistic representation) decreases, approximately in an inversely proportional way. In summary, nearly every previously reported result using PDD, which were already faster than deterministic solvers, could be additionally accelerated by one to two orders of mag- nitude thanks to improved numerics. Further acceleration improvements are expected to follow in combination with Multilevel formulations [34]. Some applications of PDD The initial undertaking of the PDD programme was due to J. A. Acebrón and his re- search group [1]-[5]. Some realistic large-scale simulations carried out in supercom- puters at the Barcelona Supercomputer Center and Rome’s CASPUR proved the superi- ority of PDD over ScaLAPACK in terms of both total time and observed scalability when solving a nonlinear equations including KPP [7], [8], [4]. Independently, Gobet and Mairé proposed a PDD-like domain decomposition scheme for the Poisson equation in [38]. Bihlo and Haynes have applied PDD to the generation of meshes for ﬁnite ele- ments, a PDE-based task very well suited to stochastic representations [15], [14], [16]. Moreover, in [5], the Vlasov-Poisson equations were tackled, which are of unquestion- ##LTLine## ##LTLine## ##LTLine##

text: Hybrid

text: PDE

text: solver

text: for

text: data-driven

text: problems

text: and

text: modern

text: branching

text: a

label: table

text: theoretical

text: speedup

text: observed

text: speedup

text: (approx.)

text: Table

text: Acceleration

label: caption

text: of

text: the

text: most

text: current

text: version

text: of

text: PDD

text: (IterPDD),

text: with

text: improved

text: stochastic

text: numerics,

text: over

text: the

text: previous

text: PDD

text: algorithm.

text: a

text: is

text: the

text: error

text: tolerance

text: on

text: inter-

text: facing

text: nodes.

text: The

text: BVP

text: being

text: solved

text: is

text: IterPDD

text: is

text: a

text: numerical

text: suite

text: which

text: includes

text: variance

text: reduction

text: techniques

text: with

text: iterative

text: control

text: variates

text: based

text: on

text: nested,

text: increasingly

text: accurate

text: global

text: solutions.

text: The

text: speedup

text: of

text: a

text: method

text: A

text: over

text: a

text: method

text: B

text: to

text: solve

text: a

text: BVP

text: is

text: deﬁned

text: as

text: Time

text: taken

text: by

text: method

text: B

text: S(A,

text: B)

text: Time

text: taken

text: by

text: method

text: A

text: Table

text: shows

text: the

text: speedup

text: of

text: IterPDD

text: over

text: the

text: previous

text: versions

text: of

text: PDD.

text: Note

text: that

text: IterPDD

text: retains

text: all

text: the

text: advantages

text: of

text: any

text: previous

text: version

text: of

text: the

text: PDD

text: algorithm

text: and

text: hence

text: it

text: is

text: not

text: necessary

text: to

text: compare

text: it

text: against

text: DDD

text: solvers,

text: since

text: S(IterPDD,

text: DDD)

text: S(IterPDD,

text: PDD)

text: S(PDD,

text: DDD).

text: The

text: theoretical

text: speedup

text: in

text: Table

text: is

text: the

text: op-

text: timal

text: speedup

text: predicted

text: by

text: a

text: sensitivity

text: algorithm

text: presented

text: in

text: Importantly,

text: the

text: latter

text: is

text: designed

text: in

text: such

text: a

text: way

text: that

text: it

text: relies

text: on

text: fast

text: warm

text: up

text: Monte

text: Carlo

text: sampling,

text: and

text: runs

text: in

text: parallel

text: so

text: as

text: not

text: to

text: defeat

text: the

text: purpose

text: of

text: PDD.

text: The

text: agreement

text: with

text: the

text: experimentally

text: observed

text: speedup

text: is

text: consistently

text: conservative.

text: The

text: acceleration

text: (speedup)

text: grows

text: larger

text: as

text: the

text: target

text: nodal

text: accuracy

text: a

text: (the

text: largest

text: admissible

text: error

text: of

text: the

text: numerical

text: solution

text: on

text: the

text: interface

text: nodes,

text: obtained

text: via

text: the

text: prob-

text: abilistic

text: representation)

text: decreases,

text: approximately

text: in

text: an

text: inversely

text: proportional

text: way.

text: In

text: summary,

text: nearly

text: every

text: previously

text: reported

text: result

text: using

text: PDD,

text: which

text: were

text: already

text: faster

text: than

text: deterministic

text: solvers,

text: could

text: be

text: additionally

text: accelerated

text: by

text: one

text: to

text: two

text: orders

text: of

text: mag-

text: nitude

text: thanks

text: to

text: improved

text: numerics.

text: Further

text: acceleration

text: improvements

text: are

text: expected

text: to

text: follow

text: in

text: combination

text: with

text: Multilevel

text: formulations

text: Some

text: applications

text: of

text: PDD

text: The

text: initial

text: undertaking

text: of

text: the

text: PDD

text: programme

text: was

text: due

text: to

text: J.

text: A.

text: Acebrón

text: and

text: his

text: re-

text: search

text: group

text: Some

text: realistic

text: large-scale

text: simulations

text: carried

text: out

text: in

text: supercom-

text: puters

text: at

text: the

text: Barcelona

text: Supercomputer

text: Center

text: and

text: Rome’s

text: CASPUR

text: proved

text: the

text: superi-

text: ority

text: of

text: PDD

text: over

text: ScaLAPACK

text: in

text: terms

text: of

text: both

text: total

text: time

text: and

text: observed

text: scalability

text: when

text: solving

text: a

text: nonlinear

text: equations

text: including

text: KPP

text: Independently,

text: Gobet

text: and

text: Mairé

text: proposed

text: a

text: PDD-like

text: domain

text: decomposition

text: scheme

text: for

text: the

text: Poisson

text: equation

text: in

text: Bihlo

text: and

text: Haynes

text: have

text: applied

text: PDD

text: to

text: the

text: generation

text: of

text: meshes

text: for

text: ﬁnite

text: ele-

text: ments,

text: a

text: PDE-based

text: task

text: very

text: well

text: suited

text: to

text: stochastic

text: representations

text: Moreover,

text: in

text: the

text: Vlasov-Poisson

text: equations

text: were

text: tackled,

text: which

text: are

text: of

text: unquestion-

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: − n 1 (cid:48) H . . . s t x w v (cid:48) (cid:48) Figure 3: Graph G obtained in Construction 4. The gray part represents the graph H . ≥ and directed planar graphs, even if the number k 0 of shared edges (arcs) or the ≥ ≥ maximum degree ∆ 5 (∆ 3) is constant. The reductions are slightly more i/o involved, because it is harder to force trails to take a certain way. 5.1 On Undirected Graphs In this section, we prove the following. ≥ Theorem 5. Trail-RCA on undirected planar graphs is NP-complete, even if k 0 ≥ is constant or ∆ 5 is constant. We provide two constructions supporting the two subresults for constants k, ∆. The reductions are again from Planar Cubic Hamiltonian Cycle (PCHC). | | Construction 4. Let G = (V, E) be an undirected planar cubic graph with n = V . (cid:48) Construct an undirected planar graph G as follows (refer to Figure 3 for an illustration (cid:48) of the constructed graph). Initially, let G be the empty graph. Add a copy of G (cid:48) to G and denote the copy by H. Subdivide each edge in H and denote the resulting (cid:48) (cid:48) (cid:48) (cid:48) graph H . Note that H is still planar. Consider a plane embedding φ(H ) of H and ∈ (cid:48) and let x V (H ) be a vertex incident to the outer face in the embedding. Next, add { } { } { } { } { } the vertex set s, v, w, t to G. Add the edges s, x , s, v , v, w , and w, t to G. − { } Finally, add n 1 vertices B = b , . . . , b − to G and connect each of them with s 1 n 1 { } { } by two edges (in the following, we distinguish these edges as s, b and s, b , for ∈ − i 1 i 2 each i [n 1]). Note that the graph is planar (see Figure 3 for an embedding, where (cid:48) (cid:48) H is embedded as φ(H )) but not simple. (cid:48) Lemma 7. Let G and G as in Construction 4. Then G admits a Hamiltonian cycle (cid:48) if and only if G admits 2n s-t trails with no shared edge. ⇒ (cid:48) (cid:48) Proof. ( ) Let G admit a Hamiltonian cycle C. Observe that H allows for a cycle C (cid:48) in H that contains each vertex corresponding to a vertex in H exactly once. We (cid:48) construct 2n trails in G as follows. We group the trails in two groups. The ﬁrst group of trails ﬁrst visits some of { } ∈ − the vertices b , . . . , b − by each time ﬁrst using the edge s, b , i [n 1], and 1 n 1 i 1 then proceeding to t via v. The second group of trails ﬁrst visits some of the ver- { } ∈ − tices b , . . . , b − by each time ﬁrst using the edge s, b , i [n 1], and then 1 n 1 (cid:48) i 2 proceeding via x, then following the cycle C , and ﬁnally again via x towards t. Let ∈ { } Ti, . . . , Ti denote the trails of group i 1, 2 . For each j < n, the trail Ti ﬁrst visits 1 n j the vertices b , . . . , b − in that order before proceeding as described above. The trails ∈ { }j n 1 Ti, i 1, 2 , do not contain any of the vertices b , . . . , b − , and directly approach t n 1 n 1 as described above. 14 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: paragraph

text: n

text: H

text: s

text: t

text: x

text: w

text: v

text: Figure

text: Graph

text: G

text: obtained

text: in

text: Construction

text: The

text: gray

text: part

text: represents

text: the

text: graph

text: H

text: and

text: directed

text: planar

text: graphs,

text: even

text: if

text: the

text: number

text: k

text: of

text: shared

text: edges

text: (arcs)

text: or

text: the

text: maximum

text: degree

text: is

text: constant.

text: The

text: reductions

text: are

text: slightly

text: more

text: i/o

text: involved,

text: because

text: it

text: is

text: harder

text: to

text: force

text: trails

text: to

text: take

text: a

text: certain

text: way.

label: section

text: On

text: Undirected

text: Graphs

text: In

text: this

text: section,

text: we

text: prove

text: the

text: following.

text: Theorem

text: Trail-RCA

text: on

text: undirected

text: planar

text: graphs

text: is

text: NP-complete,

text: even

text: if

text: k

text: is

text: constant

text: or

text: is

text: constant.

text: We

text: provide

text: two

text: constructions

text: supporting

text: the

text: two

text: subresults

text: for

text: constants

text: k,

text: The

text: reductions

text: are

text: again

text: from

text: Planar

text: Cubic

text: Hamiltonian

text: Cycle

text: (PCHC).

text: Construction

text: Let

text: G

text: (V,

text: E)

text: be

text: an

text: undirected

text: planar

text: cubic

text: graph

text: with

text: n

text: V

text: Construct

text: an

text: undirected

text: planar

text: graph

text: G

text: as

text: follows

text: (refer

text: to

text: Figure

text: for

text: an

text: illustration

text: of

text: the

text: constructed

text: graph).

text: Initially,

text: let

text: G

text: be

text: the

text: empty

text: graph.

text: Add

text: a

text: copy

text: of

text: G

text: to

text: G

text: and

text: denote

text: the

text: copy

text: by

text: H.

text: Subdivide

text: each

text: edge

text: in

text: H

text: and

text: denote

text: the

text: resulting

text: graph

text: H

text: Note

text: that

text: H

text: is

text: still

text: planar.

text: Consider

text: a

text: plane

text: embedding

text: φ(H

text: of

text: H

text: and

text: and

text: let

text: x

text: V

text: (H

text: be

text: a

text: vertex

text: incident

text: to

text: the

text: outer

text: face

text: in

text: the

text: embedding.

text: Next,

text: add

text: the

text: vertex

text: set

text: s,

text: v,

text: w,

text: t

text: to

text: G.

text: Add

text: the

text: edges

text: s,

text: x

text: s,

text: v

text: v,

text: w

text: and

text: w,

text: t

text: to

text: G.

text: Finally,

text: add

text: n

text: vertices

text: B

text: b

text: b

text: to

text: G

text: and

text: connect

text: each

text: of

text: them

text: with

text: s

text: n

text: by

text: two

text: edges

text: (in

text: the

text: following,

text: we

text: distinguish

text: these

text: edges

text: as

text: s,

text: b

text: and

text: s,

text: b

text: for

text: i

text: i

text: each

text: i

text: [n

text: Note

text: that

text: the

text: graph

text: is

text: planar

text: (see

text: Figure

text: for

text: an

text: embedding,

text: where

text: H

text: is

text: embedded

text: as

text: φ(H

text: but

text: not

text: simple.

text: Lemma

text: Let

text: G

text: and

text: G

text: as

text: in

text: Construction

text: Then

text: G

text: admits

text: a

text: Hamiltonian

text: cycle

text: if

text: and

text: only

text: if

text: G

text: admits

text: s-t

text: trails

text: with

text: no

text: shared

text: edge.

text: Proof.

text: Let

text: G

text: admit

text: a

text: Hamiltonian

text: cycle

text: C.

text: Observe

text: that

text: H

text: allows

text: for

text: a

text: cycle

text: C

text: in

text: H

text: that

text: contains

text: each

text: vertex

text: corresponding

text: to

text: a

text: vertex

text: in

text: H

text: exactly

text: once.

text: We

text: construct

text: trails

text: in

text: G

text: as

text: follows.

text: We

text: group

text: the

text: trails

text: in

text: two

text: groups.

text: The

text: ﬁrst

text: group

text: of

text: trails

text: ﬁrst

text: visits

text: some

text: of

text: the

text: vertices

text: b

text: b

text: by

text: each

text: time

text: ﬁrst

text: using

text: the

text: edge

text: s,

text: b

text: i

text: [n

text: and

text: n

text: i

text: then

text: proceeding

text: to

text: t

text: via

text: v.

text: The

text: second

text: group

text: of

text: trails

text: ﬁrst

text: visits

text: some

text: of

text: the

text: ver-

text: tices

text: b

text: b

text: by

text: each

text: time

text: ﬁrst

text: using

text: the

text: edge

text: s,

text: b

text: i

text: [n

text: and

text: then

text: n

text: i

text: proceeding

text: via

text: x,

text: then

text: following

text: the

text: cycle

text: C

text: and

text: ﬁnally

text: again

text: via

text: x

text: towards

text: t.

text: Let

text: Ti,

text: Ti

text: denote

text: the

text: trails

text: of

text: group

text: i

text: For

text: each

text: j

text: n,

text: the

text: trail

text: Ti

text: ﬁrst

text: visits

text: n

text: j

text: the

text: vertices

text: b

text: b

text: in

text: that

text: order

text: before

text: proceeding

text: as

text: described

text: above.

text: The

text: trails

text: }j

text: n

text: Ti,

text: i

text: do

text: not

text: contain

text: any

text: of

text: the

text: vertices

text: b

text: b

text: and

text: directly

text: approach

text: t

text: n

text: n

text: as

text: described

text: above.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 7 Conclusion and Outlook Some of our results can be seen as a parameterized complexity study of RCA focusing on the number k of shared edges. It is interesting to study the problem with respect to other parameters. Herein, the ﬁrst natural parameterization is the number of routes. Recall that the Minimum Shared Edges problem is ﬁxed-parameter tractable with respect to the number of path [6]. A second parameterization we consider as interesting is the combined parameter maximum degree plus k. In our NP- completeness results for Path-RCA and Trail-RCA it seemed diﬃcult to achieve constant k and maximum degree at the same time. Another research direction is to further investigate on which graph classes Path- RCA and Trail-RCA become tractable. We proved that that both problems remain NP-complete even on planar graphs. Do both Path-RCA and Trail-RCA remain NP-complete on graphs of bounded treewidth? Recall that the Minimum Shared Edges problem is tractable on this graph class [20, 1]. Finally, we proved that on undirected graphs, Walk-RCA is solvable in polyno- mial time while Walk-FRCA is NP-complete. However, we left open whether Walk- FRCA on undirected graphs is NP-complete or polynomial-time solvable when k is constant. References [1] Yusuke Aoki, Bjarni V. Halldórsson, Magnús M. Halldórsson, Takehiro Ito, Chris- tian Konrad, and Xiao Zhou. The minimum vulnerability problem on graphs. In Proc. 8th International Conference on Combinatorial Optimization and Applica- tions (COCOA ’14), volume 8881 of LNCS, pages 299–313. Springer, 2014. 4, 25 [2] Sepehr Assadi, Ehsan Emamjomeh-Zadeh, Ashkan Norouzi-Fard, Sadra Yazdan- bod, and Hamid Zarrabi-Zadeh. The minimum vulnerability problem. Algorith- mica, 70(4):718–731, 2014. 1 [3] Kenneth A. Berman. Vulnerability of scheduled networks and a generalization of Menger’s theorem. Networks, 28(3):125–134, 1996. 4 [4] Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. 7 [5] Till Fluschnik. The parameterized complexity of ﬁnding paths with shared edges. Master thesis, Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, 2015. 3 [6] Till Fluschnik, Stefan Kratsch, Rolf Niedermeier, and Manuel Sorge. The param- eterized complexity of the minimum shared edges problem. In Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and The- oretical Computer Science (FSTTCS’15), volume 45 of LIPIcs, pages 448–462. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. 2, 3, 24 25

text: Conclusion

text: and

text: Outlook

text: Some

text: of

text: our

text: results

text: can

text: be

text: seen

text: as

text: a

text: parameterized

text: complexity

text: study

text: of

text: RCA

text: focusing

text: on

text: the

text: number

text: k

text: of

text: shared

text: edges.

text: It

text: is

text: interesting

text: to

text: study

text: the

text: problem

text: with

text: respect

text: to

text: other

text: parameters.

text: Herein,

text: the

text: ﬁrst

text: natural

text: parameterization

text: is

text: the

text: number

text: of

text: routes.

text: Recall

text: that

text: the

text: Minimum

text: Shared

text: Edges

text: problem

text: is

text: ﬁxed-parameter

text: tractable

text: with

text: respect

text: to

text: the

text: number

text: of

text: path

text: A

text: second

text: parameterization

text: we

text: consider

text: as

text: interesting

text: is

text: the

text: combined

text: parameter

text: maximum

text: degree

text: plus

text: k.

text: In

text: our

text: NP-

text: completeness

text: results

text: for

text: Path-RCA

text: and

text: Trail-RCA

text: it

text: seemed

text: diﬃcult

text: to

text: achieve

text: constant

text: k

text: and

text: maximum

text: degree

text: at

text: the

text: same

text: time.

text: Another

text: research

text: direction

text: is

text: to

text: further

text: investigate

text: on

text: which

text: graph

text: classes

text: Path-

text: RCA

text: and

text: Trail-RCA

text: become

text: tractable.

text: We

text: proved

text: that

text: that

text: both

text: problems

text: remain

text: NP-complete

text: even

text: on

text: planar

text: graphs.

text: Do

text: both

text: Path-RCA

text: and

text: Trail-RCA

text: remain

text: NP-complete

text: on

text: graphs

text: of

text: bounded

text: treewidth?

text: Recall

text: that

text: the

text: Minimum

text: Shared

text: Edges

text: problem

text: is

text: tractable

text: on

text: this

text: graph

text: class

text: Finally,

text: we

text: proved

text: that

text: on

text: undirected

text: graphs,

text: Walk-RCA

text: is

text: solvable

text: in

text: polyno-

text: mial

text: time

text: while

text: Walk-FRCA

text: is

text: NP-complete.

text: However,

text: we

text: left

text: open

text: whether

text: Walk-

text: FRCA

text: on

text: undirected

text: graphs

text: is

text: NP-complete

text: or

text: polynomial-time

text: solvable

text: when

text: k

text: is

text: constant.

text: References

text: Yusuke

text: Aoki,

text: Bjarni

text: V.

text: Halldórsson,

text: Magnús

text: M.

text: Halldórsson,

text: Takehiro

text: Ito,

text: Chris-

text: tian

text: Konrad,

text: and

text: Xiao

text: Zhou.

text: The

text: minimum

text: vulnerability

text: problem

text: on

text: graphs.

text: In

text: Proc.

text: International

text: Conference

text: on

text: Combinatorial

text: Optimization

text: and

text: Applica-

text: tions

text: (COCOA

text: volume

text: of

text: LNCS,

text: pages

text: Springer,

text: Sepehr

text: Assadi,

text: Ehsan

text: Emamjomeh-Zadeh,

text: Ashkan

text: Norouzi-Fard,

text: Sadra

text: Yazdan-

text: bod,

text: and

text: Hamid

text: Zarrabi-Zadeh.

text: The

text: minimum

text: vulnerability

text: problem.

text: Algorith-

text: mica,

text: Kenneth

text: A.

text: Berman.

text: Vulnerability

text: of

text: scheduled

text: networks

text: and

text: a

text: generalization

text: of

text: Menger’s

text: theorem.

text: Networks,

text: Rodney

text: G.

text: Downey

text: and

text: Michael

text: R.

text: Fellows.

text: Fundamentals

text: of

text: Parameterized

text: Complexity.

text: Texts

text: in

text: Computer

text: Science.

text: Springer,

text: Till

text: Fluschnik.

text: The

text: parameterized

text: complexity

text: of

text: ﬁnding

text: paths

text: with

text: shared

text: edges.

text: Master

text: thesis,

text: Institut

text: für

text: Softwaretechnik

text: und

text: Theoretische

text: Informatik,

text: TU

text: Berlin,

text: Till

text: Fluschnik,

text: Stefan

text: Kratsch,

text: Rolf

text: Niedermeier,

text: and

text: Manuel

text: Sorge.

text: The

text: param-

text: eterized

text: complexity

text: of

text: the

text: minimum

text: shared

text: edges

text: problem.

text: In

text: Proceedings

text: of

text: the

text: IARCS

text: Annual

text: Conference

text: on

text: Foundation

text: of

text: Software

text: Technology

text: and

text: The-

text: oretical

text: Computer

text: Science

text: volume

text: of

text: LIPIcs,

text: pages

text: Schloss

text: Dagstuhl

text: Leibniz-Zentrum

text: fuer

text: Informatik,


text: polynomial-time solvable on graphs of bounded treewidth [20, 1]. There are various tractability and hardness results for problems related to RCA with k = 0 in temporal graphs, in which edges are only available at predeﬁned time steps [3, 10, 14, 13]. The goal herein is to ﬁnd a number of edge or vertex-disjoint time-respecting paths connecting two ﬁxed terminal vertices. Time-respecting means that the time steps of the edges in the paths are nondecreasing. Apart from the fact that all graphs that we study are static, the crucial diﬀerence is in the type of routes: vehicles moving along time-respecting paths may wait an arbitrary number of time steps at each vertex, while we require them to move at least one edge per time step (unless they already arrived at the target vertex). Our work is related to ﬂows over time, a concept already introduced by Ford and Fulkerson [7] to measure the maximal throughput in a network over a ﬁxed time period. This and similar problems were studied continually, see Skutella [19] and Köhler et al. [12] for surveys. In contrast, our throughput is ﬁxed, our ﬂow may not stand still or go in circles arbitrarily, and we want to augment the network to allow for our throughput. 2 Preliminaries We deﬁne [n] := {1, . . . , n} for every n ∈ N. Let G = (V, E) be an undirected (directed) graph. Let the sequence P = (v , . . . , v ) of vertices in G be a walk, trail, 1 (cid:96) ∈ or path. We call v and v the start and end of P. For i [(cid:96)], we denote by P[i] 1 (cid:96) ∈ the vertex v at position i in P. Moreover, for i, j [(cid:96)], i < j, we denote by P[i, j] i the subsequence (v , . . . , v ) of P. By deﬁnition, P has an alternative representation i j { } as sequence of edges (arcs) P = (e , . . . , e − ) with e := v , v (e := (v , v )) ∈ − 1 (cid:96) 1 i i i+1 i i i+1 for i [(cid:96) 1]. Along this representation, we say that P contains/uses edge (arc) e at time step i if edge (arc) e appears at the ith position in P represented as sequence of edges (arcs) (analogue for vertices). We call an edge/arc shared if two routes uses the edge/arc at the same time step. We say that a walk/trail/path Q is an s- t walk/trail/path, if s is the start and t is the end of Q. The length of a walk/trail/path is the number of edges (arcs) contained, where we also count multiple occurrences of an edge (arc) (we refer to a path of length m as an m-chain). (We deﬁne the maximum { } over in- and outdegrees in G by ∆ (G) := max ∈ outdeg(v), indeg(v) .) A parameterized problem P is ia/oset of tuplesv (Vx,(G(cid:96))) ∈ Σ∗ × N, where Σ denotes a ﬁnite alphabet. A parameterized problem P is ﬁxed-parameter tractable if it admits an ·| | algorithm that decides every input (x, (cid:96)) in f((cid:96)) x O(1) time (FPT-time), where f is a computable function. The class FPT is the class of ﬁxed-parameter tractable problems. ≥ The classes W[q], q 1, contain parameterized problems that are presumably not (cid:48) ﬁxed-parameter tractable. For two parameterized problems P and P , a parameterized (cid:48) (cid:48) (cid:48) reduction from P to P is an algorithm that maps each input (x, (cid:96)) to (x , (cid:96) ) in FPT- ∈ (cid:48) (cid:48) ∈ (cid:48) (cid:48) ≤ time such that (x, (cid:96)) P if and only if (x , (cid:96) ) P , and (cid:96) g((cid:96)) for some function g. A parameterized problem P is W[q]-hard if for every problem contained in W[q] there is a parameterized reduction to P. Preliminary Observations on RCA and FRCA. We state some preliminary observations on RCA and FRCA. If there is a shortest path between the terminals s 4

text: polynomial-time

text: solvable

text: on

text: graphs

text: of

text: bounded

text: treewidth

text: There

text: are

text: various

text: tractability

text: and

text: hardness

text: results

text: for

text: problems

text: related

text: to

text: RCA

text: with

text: k

text: in

text: temporal

text: graphs,

text: in

text: which

text: edges

text: are

text: only

text: available

text: at

text: predeﬁned

text: time

text: steps

text: The

text: goal

text: herein

text: is

text: to

text: ﬁnd

text: a

text: number

text: of

text: edge

text: or

text: vertex-disjoint

text: time-respecting

text: paths

text: connecting

text: two

text: ﬁxed

text: terminal

text: vertices.

text: Time-respecting

text: means

text: that

text: the

text: time

text: steps

text: of

text: the

text: edges

text: in

text: the

text: paths

text: are

text: nondecreasing.

text: Apart

text: from

text: the

text: fact

text: that

text: all

text: graphs

text: that

text: we

text: study

text: are

text: static,

text: the

text: crucial

text: diﬀerence

text: is

text: in

text: the

text: type

text: of

text: routes:

text: vehicles

text: moving

text: along

text: time-respecting

text: paths

text: may

text: wait

text: an

text: arbitrary

text: number

text: of

text: time

text: steps

text: at

text: each

text: vertex,

text: while

text: we

text: require

text: them

text: to

text: move

text: at

text: least

text: one

text: edge

text: per

text: time

text: step

text: (unless

text: they

text: already

text: arrived

text: at

text: the

text: target

text: vertex).

text: Our

text: work

text: is

text: related

text: to

text: ﬂows

text: over

text: time,

text: a

text: concept

text: already

text: introduced

text: by

text: Ford

text: and

text: Fulkerson

text: to

text: measure

text: the

text: maximal

text: throughput

text: in

text: a

text: network

text: over

text: a

text: ﬁxed

text: time

text: period.

text: This

text: and

text: similar

text: problems

text: were

text: studied

text: continually,

text: see

text: Skutella

text: and

text: Köhler

text: et

text: al.

text: for

text: surveys.

text: In

text: contrast,

text: our

text: throughput

text: is

text: ﬁxed,

text: our

text: ﬂow

text: may

text: not

text: stand

text: still

text: or

text: go

text: in

text: circles

text: arbitrarily,

text: and

text: we

text: want

text: to

text: augment

text: the

text: network

text: to

text: allow

text: for

text: our

text: throughput.

text: Preliminaries

text: We

text: deﬁne

text: [n]

text: n}

text: for

text: every

text: n

text: N.

text: Let

text: G

text: (V,

text: E)

text: be

text: an

text: undirected

text: (directed)

text: graph.

text: Let

text: the

text: sequence

text: P

text: (v

text: v

text: of

text: vertices

text: in

text: G

text: be

text: a

text: walk,

text: trail,

text: or

text: path.

text: We

text: call

text: v

text: and

text: v

text: the

text: start

text: and

text: end

text: of

text: P.

text: For

text: i

text: we

text: denote

text: by

text: P[i]

text: the

text: vertex

text: v

text: at

text: position

text: i

text: in

text: P.

text: Moreover,

text: for

text: i,

text: j

text: i

text: j,

text: we

text: denote

text: by

text: P[i,

text: j]

text: i

text: the

text: subsequence

text: (v

text: v

text: of

text: P.

text: By

text: deﬁnition,

text: P

text: has

text: an

text: alternative

text: representation

text: i

text: j

text: as

text: sequence

text: of

text: edges

text: (arcs)

text: P

text: (e

text: e

text: with

text: e

text: v

text: v

text: (e

text: (v

text: v

text: i

text: i

text: i

text: i

text: for

text: i

text: Along

text: this

text: representation,

text: we

text: say

text: that

text: P

text: contains/uses

text: edge

text: (arc)

text: e

text: at

text: time

text: step

text: i

text: if

text: edge

text: (arc)

text: e

text: appears

text: at

text: the

text: ith

text: position

text: in

text: P

text: represented

text: as

text: sequence

text: of

text: edges

text: (arcs)

text: (analogue

text: for

text: vertices).

text: We

text: call

text: an

text: edge/arc

text: shared

text: if

text: two

text: routes

text: uses

text: the

text: edge/arc

text: at

text: the

text: same

text: time

text: step.

text: We

text: say

text: that

text: a

text: walk/trail/path

text: Q

text: is

text: an

text: s-

text: t

text: walk/trail/path,

text: if

text: s

text: is

text: the

text: start

text: and

text: t

text: is

text: the

text: end

text: of

text: Q.

text: The

text: length

text: of

text: a

text: walk/trail/path

text: is

text: the

text: number

text: of

text: edges

text: (arcs)

text: contained,

text: where

text: we

text: also

text: count

text: multiple

text: occurrences

text: of

text: an

text: edge

text: (arc)

text: (we

text: refer

text: to

text: a

text: path

text: of

text: length

text: m

text: as

text: an

text: m-chain).

text: (We

text: deﬁne

text: the

text: maximum

text: over

text: in-

text: and

text: outdegrees

text: in

text: G

text: by

text: (G)

text: max

text: outdeg(v),

text: indeg(v)

text: A

text: parameterized

text: problem

text: P

text: is

text: ia/oset

text: of

text: tuplesv

text: Σ∗

text: N,

text: where

text: Σ

text: denotes

text: a

text: ﬁnite

text: alphabet.

text: A

text: parameterized

text: problem

text: P

text: is

text: ﬁxed-parameter

text: tractable

text: if

text: it

text: admits

text: an

text: algorithm

text: that

text: decides

text: every

text: input

text: (x,

text: in

text: x

text: time

text: (FPT-time),

text: where

text: f

text: is

text: a

text: computable

text: function.

text: The

text: class

text: FPT

text: is

text: the

text: class

text: of

text: ﬁxed-parameter

text: tractable

text: problems.

text: The

text: classes

text: W[q],

text: q

text: contain

text: parameterized

text: problems

text: that

text: are

text: presumably

text: not

text: ﬁxed-parameter

text: tractable.

text: For

text: two

text: parameterized

text: problems

text: P

text: and

text: P

text: a

text: parameterized

text: reduction

text: from

text: P

text: to

text: P

text: is

text: an

text: algorithm

text: that

text: maps

text: each

text: input

text: (x,

text: to

text: (x

text: in

text: FPT-

text: time

text: such

text: that

text: (x,

text: P

text: if

text: and

text: only

text: if

text: (x

text: P

text: and

text: for

text: some

text: function

text: g.

text: A

text: parameterized

text: problem

text: P

text: is

text: W[q]-hard

text: if

text: for

text: every

text: problem

text: contained

text: in

text: W[q]

text: there

text: is

text: a

text: parameterized

text: reduction

text: to

text: P.

text: Preliminary

text: Observations

text: on

text: RCA

text: and

text: FRCA.

text: We

text: state

text: some

text: preliminary

text: observations

text: on

text: RCA

text: and

text: FRCA.

text: If

text: there

text: is

text: a

text: shortest

text: path

text: between

text: the

text: terminals

text: s


text: - c h a i n ( n + 1 )- c h a i n ... 5 t - c h a i n x2 w 4 s H v x 1 x 3 (cid:48) Figure 1: Graph G obtained in Construction 2. The gray part represents the graph H. Dashed lines represent chains. Corollary 2. FRCA on DAGs is NP-complete and W[2]-hard with respect to k + α. 4 Path-RCA In this section, we prove the following theorem. Theorem 4. Path-RCA both on undirected planar and directed planar graphs is ≥ ≥ NP-complete, even if k 0 is constant or ∆ 4 is constant. In the proof of Theorem 4, we reduce from the following NP-complete [8] problem (a cubic graph is a graph where every vertex has degree exactly three): Planar Cubic Hamiltonian Cycle (PCHC) Input: An undirected, planar, cubic graph G. Question: Is there a cycle in G that visits each vertex exactly once? Roughly, the instance of Path-RCA obtained in the reduction consists of the original graph G connected to the terminals s, t via a bridge (see Figure 1). We ask for constructing roughly n paths connecting the terminals, where n is the number of vertices in the input graph of PCHC. All but one of these paths will use the bridge to t in the constructed graph for n time steps in total, each in a diﬀerent time step. Thus, this bridge is occupied for roughly n time steps, and the ﬁnal path is forced to stay in the input graph of PCHC for n time steps. For a path, this is only possible by visiting each of the n vertices in the graph exactly once, and hence it corresponds to a Hamiltonian cycle. The reduction to prove Theorem 4 uses the following Construction 2. | | Construction 2. Let G = (V, E) be an undirected, planar, cubic graph with n = V . (cid:48) Construct in time polynomial in the size of G an undirected planar graph G as follows (cid:48) (refer to Figure 1 for an illustration of the constructed graph). Let initially G be the (cid:48) (cid:48) empty graph. Add a copy of G to G . Denote the copy of G in G by H. Next, add the new vertices s, t, v, w to G. Connect s with v, and w with t by an edge. For ∈ { } each m 4, 5, . . . , n+1 , add an m-chain connecting s with w. Next, consider a ﬁxed plane embedding φ(G) of G. Let x denote a vertex incident to the outer face in φ(G). 1 9 ##LTLine## ##LTLine## ##LTLine##

text: c

text: h

text: a

text: i

text: n

text: n

text: c

text: h

text: a

text: i

text: n

text: t

text: c

text: h

text: a

text: i

text: n

text: w

text: s

text: H

text: v

text: x

text: x

text: Figure

text: Graph

text: G

text: obtained

text: in

text: Construction

text: The

text: gray

text: part

text: represents

text: the

text: graph

text: H.

text: Dashed

text: lines

text: represent

text: chains.

text: Corollary

text: FRCA

text: on

text: DAGs

text: is

text: NP-complete

text: and

text: with

text: respect

text: to

text: k

text: α.

text: Path-RCA

text: In

text: this

text: section,

text: we

text: prove

text: the

text: following

text: theorem.

text: Theorem

text: Path-RCA

text: both

text: on

text: undirected

text: planar

text: and

text: directed

text: planar

text: graphs

text: is

text: NP-complete,

text: even

text: if

text: k

text: is

text: constant

text: or

text: is

text: constant.

text: In

text: the

text: proof

text: of

text: Theorem

text: we

text: reduce

text: from

text: the

text: following

text: NP-complete

text: problem

text: (a

text: cubic

text: graph

text: is

text: a

text: graph

text: where

text: every

text: vertex

text: has

text: degree

text: exactly

text: three):

text: Planar

text: Cubic

text: Hamiltonian

text: Cycle

text: (PCHC)

text: Input:

text: An

text: undirected,

text: planar,

text: cubic

text: graph

text: G.

text: Question:

text: Is

text: there

text: a

text: cycle

text: in

text: G

text: that

text: visits

text: each

text: vertex

text: exactly

text: once?

text: Roughly,

text: the

text: instance

text: of

text: Path-RCA

text: obtained

text: in

text: the

text: reduction

text: consists

text: of

text: the

text: original

text: graph

text: G

text: connected

text: to

text: the

text: terminals

text: s,

text: t

text: via

text: a

text: bridge

text: (see

text: Figure

text: We

text: ask

text: for

text: constructing

text: roughly

text: n

text: paths

text: connecting

text: the

text: terminals,

text: where

text: n

text: is

text: the

text: number

text: of

text: vertices

text: in

text: the

text: input

text: graph

text: of

text: PCHC.

text: All

text: but

text: one

text: of

text: these

text: paths

text: will

text: use

text: the

text: bridge

text: to

text: t

text: in

text: the

text: constructed

text: graph

text: for

text: n

text: time

text: steps

text: in

text: total,

text: each

text: in

text: a

text: diﬀerent

text: time

text: step.

text: Thus,

text: this

text: bridge

text: is

text: occupied

text: for

text: roughly

text: n

text: time

text: steps,

text: and

text: the

text: ﬁnal

text: path

text: is

text: forced

text: to

text: stay

text: in

text: the

text: input

text: graph

text: of

text: PCHC

text: for

text: n

text: time

text: steps.

text: For

text: a

text: path,

text: this

text: is

text: only

text: possible

text: by

text: visiting

text: each

text: of

text: the

text: n

text: vertices

text: in

text: the

text: graph

text: exactly

text: once,

text: and

text: hence

text: it

text: corresponds

text: to

text: a

text: Hamiltonian

text: cycle.

text: The

text: reduction

text: to

text: prove

text: Theorem

text: uses

text: the

text: following

text: Construction

text: Construction

text: Let

text: G

text: (V,

text: E)

text: be

text: an

text: undirected,

text: planar,

text: cubic

text: graph

text: with

text: n

text: V

text: Construct

text: in

text: time

text: polynomial

text: in

text: the

text: size

text: of

text: G

text: an

text: undirected

text: planar

text: graph

text: G

text: as

text: follows

text: (refer

text: to

text: Figure

text: for

text: an

text: illustration

text: of

text: the

text: constructed

text: graph).

text: Let

text: initially

text: G

text: be

text: the

text: empty

text: graph.

text: Add

text: a

text: copy

text: of

text: G

text: to

text: G

text: Denote

text: the

text: copy

text: of

text: G

text: in

text: G

text: by

text: H.

text: Next,

text: add

text: the

text: new

text: vertices

text: s,

text: t,

text: v,

text: w

text: to

text: G.

text: Connect

text: s

text: with

text: v,

text: and

text: w

text: with

text: t

text: by

text: an

text: edge.

text: For

text: each

text: m

text: add

text: an

text: m-chain

text: connecting

text: s

text: with

text: w.

text: Next,

text: consider

text: a

text: ﬁxed

text: plane

text: embedding

text: φ(G)

text: of

text: G.

text: Let

text: x

text: denote

text: a

text: vertex

text: incident

text: to

text: the

text: outer

text: face

text: in

text: φ(G).

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: CMC FOLIATION WITH PARTICLES 3 u : Σ → R is the solution of an elliptic PDE, which translates the fact that the p − operator B = I 1II must satisfy the Gauss equation. We then prove the following: ∗ → Theorem 0.2. The map Φ : T T (Σ ) GH0(Σ ) is a homeomorphism for every ∈ −∞ H θ p θ p H ( , 0). We thus deduce the existence of a unique H-surface S orthogonal to the singular H lines in every CGHM Minkowki manifolds with particles. Moreover, by studying the relation between K-surfaces and H-surfaces in Minkowski manifolds, we obtain that { } the family S provides a foliation of the whole manifold as a consequence of H H<0 the following result: Theorem 0.3. Let M be a CGHM Minkowski manifold with particles. Then it admits a unique foliation by constant Gauss curvature surfaces orthogonal to the singular lines. We also underline the fact that the existence of surfaces with prescribed Gauss or mean curvature is obtained in this paper without using the classical barrier arguments or exploiting the results of the non-singular case, thus our techniques provide also a new proof of the results in [BBZ11]. In Section and Section we recall the main deﬁnitions and well-known results about hyperbolic metrics with cone singularities on surfaces and (2 + 1)-dimensional spacetimes with particles. Section is dedicated to the proof of Theorem 0.2 and to the study of constant Gauss curvature and constant mean curvature foliations of CGHM Minkowski manifolds with particles. Theorem 0.1 is proved for the anti-de Sitter manifolds in Section and for de Sitter manifolds in Section . 1. Teichmüller space of hyperbolic metrics with cone singularities In this section we introduce hyperbolic metrics with cone singularities and their deformation space. The material covered here is classical, the main purpose being ﬁxing the notation and recalling the main results that we are going to use in the sequel. Let Σ be a closed oriented surface of genus τ with n marked points p , . . . , p . 1 n Let p = (p , . . . , p ). We will denote by Σ the surface Σ with the marked points p 1 n p ∈ removed. Let us ﬁx an n-tuple of angles θ = (θ , . . . , θ ) (0, π)n. ∈ 1 n Let θ (0, 2π). We ﬁrst recall the local model of a hyperbolic metric with a cone singularity of angle θ. Let H2 be the Poincaré model of the hyperbolic plane. The local model is constructed in the following way: consider two half-lines in H2 which intersect at the center O and bound a wedge of angle θ at O, and then glue the two half-lines by a rotation ﬁxing O. The resulting space is denoted by H , called θ the hyperbolic disk with cone singularity of angle θ, endowed with the metric that in polar coordinates assumes the form: ∈ R ∈ R Z gH = dr2 + sinh2(r)dφ2, r + , φ /θ . θ

text: CMC

text: FOLIATION

text: WITH

text: PARTICLES

text: u

text: Σ

text: R

text: is

text: the

text: solution

text: of

text: an

text: elliptic

text: PDE,

text: which

text: translates

text: the

text: fact

text: that

text: the

text: p

text: operator

text: B

text: I

text: must

text: satisfy

text: the

text: Gauss

text: equation.

text: We

text: then

text: prove

text: the

text: following:

text: Theorem

text: The

text: map

text: Φ

text: T

text: T

font: UQBTSW+URWChanceryL-MediItal

text: (Σ

text: is

text: a

text: homeomorphism

text: for

text: every

text: H

text: θ

text: p

text: θ

text: p

text: H

text: We

text: thus

text: deduce

text: the

text: existence

text: of

text: a

text: unique

text: H-surface

text: S

text: orthogonal

text: to

text: the

text: singular

text: H

text: lines

text: in

text: every

text: CGHM

text: Minkowki

text: manifolds

text: with

text: particles.

text: Moreover,

text: by

text: studying

text: the

text: relation

text: between

text: K-surfaces

text: and

text: H-surfaces

text: in

text: Minkowski

text: manifolds,

text: we

text: obtain

text: that

text: the

text: family

text: S

text: provides

text: a

text: foliation

text: of

text: the

text: whole

text: manifold

text: as

text: a

text: consequence

text: of

text: H

text: the

text: following

text: result:

text: Theorem

text: Let

text: M

text: be

text: a

text: CGHM

text: Minkowski

text: manifold

text: with

text: particles.

text: Then

text: it

text: admits

text: a

text: unique

text: foliation

text: by

text: constant

text: Gauss

text: curvature

text: surfaces

text: orthogonal

text: to

text: the

text: singular

text: lines.

text: We

text: also

text: underline

text: the

text: fact

text: that

text: the

text: existence

text: of

text: surfaces

text: with

text: prescribed

text: Gauss

text: or

text: mean

text: curvature

text: is

text: obtained

text: in

text: this

text: paper

text: without

text: using

text: the

text: classical

text: barrier

text: arguments

text: or

text: exploiting

text: the

text: results

text: of

text: the

text: non-singular

text: case,

text: thus

text: our

text: techniques

text: provide

text: also

text: a

text: new

text: proof

text: of

text: the

text: results

text: in

text: In

text: Section

text: and

text: Section

text: we

text: recall

text: the

text: main

text: deﬁnitions

text: and

text: well-known

text: results

text: about

text: hyperbolic

text: metrics

text: with

text: cone

text: singularities

text: on

text: surfaces

text: and

text: spacetimes

text: with

text: particles.

text: Section

text: is

text: dedicated

text: to

text: the

text: proof

text: of

text: Theorem

text: and

text: to

text: the

text: study

text: of

text: constant

text: Gauss

text: curvature

text: and

text: constant

text: mean

text: curvature

text: foliations

text: of

text: CGHM

text: Minkowski

text: manifolds

text: with

text: particles.

text: Theorem

text: is

text: proved

text: for

text: the

text: anti-de

text: Sitter

text: manifolds

text: in

text: Section

text: and

text: for

text: de

text: Sitter

text: manifolds

text: in

text: Section

text: Teichmüller

text: space

text: of

text: hyperbolic

text: metrics

text: with

text: cone

text: singularities

text: In

text: this

text: section

text: we

text: introduce

text: hyperbolic

text: metrics

text: with

text: cone

text: singularities

text: and

text: their

text: deformation

text: space.

text: The

text: material

text: covered

text: here

text: is

text: classical,

text: the

text: main

text: purpose

text: being

text: ﬁxing

text: the

text: notation

text: and

text: recalling

text: the

text: main

text: results

text: that

text: we

text: are

text: going

text: to

text: use

text: in

text: the

text: sequel.

text: Let

text: Σ

text: be

text: a

text: closed

text: oriented

text: surface

text: of

text: genus

text: τ

text: with

text: n

text: marked

text: points

text: p

text: p

text: n

text: Let

text: p

text: (p

text: p

text: We

text: will

text: denote

text: by

text: Σ

text: the

text: surface

text: Σ

text: with

text: the

text: marked

text: points

text: p

text: n

text: p

text: removed.

text: Let

text: us

text: ﬁx

text: an

text: n-tuple

text: of

text: angles

text: θ

text: (θ

text: θ

text: π)n.

text: n

text: Let

text: θ

text: We

text: ﬁrst

text: recall

text: the

text: local

text: model

text: of

text: a

text: hyperbolic

text: metric

text: with

text: a

text: cone

text: singularity

text: of

text: angle

text: θ.

text: Let

text: be

text: the

text: Poincaré

text: model

text: of

text: the

text: hyperbolic

text: plane.

text: The

text: local

text: model

text: is

text: constructed

text: in

text: the

text: following

text: way:

text: consider

text: two

text: half-lines

text: in

text: which

text: intersect

text: at

text: the

text: center

text: O

text: and

text: bound

text: a

text: wedge

text: of

text: angle

text: θ

text: at

text: O,

text: and

text: then

text: glue

text: the

text: two

text: half-lines

text: by

text: a

text: rotation

text: ﬁxing

text: O.

text: The

text: resulting

text: space

text: is

text: denoted

text: by

text: H

text: called

text: θ

text: the

text: hyperbolic

text: disk

text: with

text: cone

text: singularity

text: of

text: angle

text: θ,

text: endowed

text: with

text: the

text: metric

text: that

text: in

text: polar

text: coordinates

text: assumes

text: the

text: form:

text: R

text: R

text: Z

text: gH

text: r

text: φ

text: /θ

text: θ


text: CMC FOLIATION WITH PARTICLES 25 A direct consequence of Theorem 3.10 is the following: Corollary 3.20. Let M be a CGHM Minkowski manifold with particles. Then for every H < 0, there exists a convex space-like surface S orthogonal to the singular H lines with constant mean curvature H. We deduce then from Lemma 3.5 also the existence of surfaces with constant Gauss curvature. Corollary 3.21. Let M be a CGHM Minkowski manifold with particles. Then for every K < 0, there exists a convex space-like surface Σ orthogonal to the singular K lines with constant Gauss curvature K. { } { } The aim of this section is proving that these two families S and Σ H H<0 K K<0 provide a foliation of the whole manifold M. Let us start with the family of surfaces with constant Gauss curvature. Theorem 3.22. Every CGHM Minkowski manifold with particles M has a unique { } foliation by constant Gauss curvature surfaces Σ orthogonal to the singular K K<0 lines. Proof. We already know that in M we can ﬁnd a family of constant Gauss curvature surfaces Σ for K < 0. Let us ﬁrst prove uniqueness. Suppose that M contains two K (cid:48) convex space-like surfaces Σ and Σ orthogonal to the singular lines with constant K K (cid:48) Gauss curvature K. Up to changing the role of Σ and Σ only three mutual (cid:48) K K(cid:48) position are possible: Σ is disjoint from Σ in the future of Σ ; Σ is tangent to (cid:48) K (cid:48) K (cid:48) K K Σ and lies in the future of Σ ; or Σ and Σ intersect transversely. In any case, K K (cid:48) K K since the surfaces equidistant to Σ in the future provide a well-deﬁned foliation of (cid:48) K (cid:48) the future of Σ , there exists a time t > 0 such that the surface ψt(Σ ) obtained (cid:48) K K by pushing Σ along the normal ﬂow is tangent to Σ at a point p and lies in the K K future of Σ . We distinguish two cases: K • if p is a regular point, by the Maximum Principle and Lemma 3.3 we deduce that ≥ K K (p) > K ψt(ΣK) and we obtain a contradiction. • If p is a singular point, since K-surfaces are umbilical at the intersection with the singular lines, we can apply again Lemma 3.3 and the Maximum Principle for umbilical surfaces ([CS16, Lemma 3.12]) and conclude as above. { } We are left to prove that the family Σ foliates the manifold. Let us ﬁrst K K<0 prove that the union of Σ over all K < 0 foliates a domain in M, called Ω. To K this aim, it is suﬃcient to show that if K converges to K, then Σ converges to n Kn

text: CMC

text: FOLIATION

text: WITH

text: PARTICLES

text: A

text: direct

text: consequence

text: of

text: Theorem

text: is

text: the

text: following:

text: Corollary

text: Let

text: M

text: be

text: a

text: CGHM

text: Minkowski

text: manifold

text: with

text: particles.

text: Then

text: for

text: every

text: H

text: there

text: exists

text: a

text: convex

text: space-like

text: surface

text: S

text: orthogonal

text: to

text: the

text: singular

text: H

text: lines

text: with

text: constant

text: mean

text: curvature

text: H.

text: We

text: deduce

text: then

text: from

text: Lemma

text: also

text: the

text: existence

text: of

text: surfaces

text: with

text: constant

text: Gauss

text: curvature.

text: Corollary

text: Let

text: M

text: be

text: a

text: CGHM

text: Minkowski

text: manifold

text: with

text: particles.

text: Then

text: for

text: every

text: K

text: there

text: exists

text: a

text: convex

text: space-like

text: surface

text: Σ

text: orthogonal

text: to

text: the

text: singular

text: K

text: lines

text: with

text: constant

text: Gauss

text: curvature

text: K.

text: The

text: aim

text: of

text: this

text: section

text: is

text: proving

text: that

text: these

text: two

text: families

text: S

text: and

text: Σ

text: H

text: K

text: provide

text: a

text: foliation

text: of

text: the

text: whole

text: manifold

text: M.

text: Let

text: us

text: start

text: with

text: the

text: family

text: of

text: surfaces

text: with

text: constant

text: Gauss

text: curvature.

text: Theorem

text: Every

text: CGHM

text: Minkowski

text: manifold

text: with

text: particles

text: M

text: has

text: a

text: unique

text: foliation

text: by

text: constant

text: Gauss

text: curvature

text: surfaces

text: Σ

text: orthogonal

text: to

text: the

text: singular

text: K

text: lines.

text: Proof.

text: We

text: already

text: know

text: that

text: in

text: M

text: we

text: can

text: ﬁnd

text: a

text: family

text: of

text: constant

text: Gauss

text: curvature

text: surfaces

text: Σ

text: for

text: K

text: Let

text: us

text: ﬁrst

text: prove

text: uniqueness.

text: Suppose

text: that

text: M

text: contains

text: two

text: K

text: convex

text: space-like

text: surfaces

text: Σ

text: and

text: Σ

text: orthogonal

text: to

text: the

text: singular

text: lines

text: with

text: constant

text: K

text: K

text: Gauss

text: curvature

text: K.

text: Up

text: to

text: changing

text: the

text: role

text: of

text: Σ

text: and

text: Σ

text: only

text: three

text: mutual

text: K

text: position

text: are

text: possible:

text: Σ

text: is

text: disjoint

text: from

text: Σ

text: in

text: the

text: future

text: of

text: Σ

text: Σ

text: is

text: tangent

text: to

text: K

text: K

text: K

text: K

text: Σ

text: and

text: lies

text: in

text: the

text: future

text: of

text: Σ

text: or

text: Σ

text: and

text: Σ

text: intersect

text: transversely.

text: In

text: any

text: case,

text: K

text: K

text: K

text: K

text: since

text: the

text: surfaces

text: equidistant

text: to

text: Σ

text: in

text: the

text: future

text: provide

text: a

text: well-deﬁned

text: foliation

text: of

text: K

text: the

text: future

text: of

text: Σ

text: there

text: exists

text: a

text: time

text: t

text: such

text: that

text: the

text: surface

text: ψt(Σ

text: obtained

text: K

text: K

text: by

text: pushing

text: Σ

text: along

text: the

text: normal

text: ﬂow

text: is

text: tangent

text: to

text: Σ

text: at

text: a

text: point

text: p

text: and

text: lies

text: in

text: the

text: K

text: K

text: future

text: of

text: Σ

text: We

text: distinguish

text: two

text: cases:

text: K

text: if

text: p

text: is

text: a

text: regular

text: point,

text: by

text: the

text: Maximum

text: Principle

text: and

text: Lemma

text: we

text: deduce

text: that

text: K

text: K

text: (p)

text: K

text: ψt(ΣK)

text: and

text: we

text: obtain

text: a

text: contradiction.

text: If

text: p

text: is

text: a

text: singular

text: point,

text: since

text: K-surfaces

text: are

text: umbilical

text: at

text: the

text: intersection

text: with

text: the

text: singular

text: lines,

text: we

text: can

text: apply

text: again

text: Lemma

text: and

text: the

text: Maximum

text: Principle

text: for

text: umbilical

text: surfaces

text: Lemma

text: and

text: conclude

text: as

text: above.

text: We

text: are

text: left

text: to

text: prove

text: that

text: the

text: family

text: Σ

text: foliates

text: the

text: manifold.

text: Let

text: us

text: ﬁrst

text: K

text: prove

text: that

text: the

text: union

text: of

text: Σ

text: over

text: all

text: K

text: foliates

text: a

text: domain

text: in

text: M,

text: called

text: Ω.

text: To

text: K

text: this

text: aim,

text: it

text: is

text: suﬃcient

text: to

text: show

text: that

text: if

text: K

text: converges

text: to

text: K,

text: then

text: Σ

text: converges

text: to

text: n

text: Kn


text: CMC FOLIATION WITH PARTICLES 26 Σ uniformly. We will actually prove more: we will show that the convergence is K also smooth outside the singular lines. Without loss of generality we can suppose that K is decreasing and converging to K. This implies that the surface Σ lies n Kn in the future of Σ and they all lie in the future of the surface Σ (cid:48) for some (cid:48) Kn+1 K K < K. This kind of sequence of convex space-like surfaces has already been studied in [BBZ11]. In particular, the authors proved (Theorem 3.6 and Corollary 3.8 in [BBZ11]) that the boundary of the closure of the union of I+(Σ ) over all n → Kn is a convex space-like surface Σ∞. Let us denote by σ∞ : Σ M the embedding → p such that σ∞(Σ ) = Σ∞. Let ψ : Σ∞ Σ be the homeomorphisms obtained by p n Kn ◦ following the normal ﬂow. We deﬁne σ = ψ σ∞. We claim that σ converges to ∞ n n n σ∞ in the C topology outside the singular locus and that Σ∞ has constant Gauss curvature K. The induced metrics on Σ can be written as n 1 g = | |h n n K n where h is a hyperbolic metric with cone singularities at p of angles θ, since all n surfaces Σ are orthogonal to the singular locus. Since the metrics induced on Kn convex space-like surfaces embedded in Minkowski manifold increase when moving towards the future ([Bel14, Proposition 4.2]) we have that ≤ (cid:96) ((σ (γ)) (cid:96) (σ (γ)) , gn n g1 1(cid:115) for every simple closed curve (cid:112)γ on Σ . Therefore, we have p | | | | ≤ K (cid:96) (σ (γ)) = K (cid:96) (σ (γ)) | n| (cid:96) (σ (γ)) , hn n n gn n K h1 1 1 ∗ which implies that the metrics σ h are contained in a compact set of T (Σ ). Thus, n n ∗ θ p up to extracting a subsequence, the metrics σ h converges to a hyperbolic metric ∈ n n h∞ T (Σ ) smoothly outside the singular locus. Following again [BBZ11], for each θ p ∈ ∈ regular point x Σ∞ there exists a sequence x Σ , such that x converges to n Kn n x and the unit normal of Σ at x converges to the unit normal of Σ∞ at x. This Kn n implies that the sequence of 1-jets of σ converges. Now, from the proof of Theorem n ∞ 5.6 in [Sch96] it follows that if σ were not convergent to σ∞ in the C topology, the n surface Σ∞ would be pleated along a geodesic γ (which may be a geodesic segment between singular points) and tangent to a light-like plane somewhere outside γ. This implies that Σ∞ admits a light-like unit normal, which contradicts the fact that Σ∞ ∞ is space-like. Therefore, σ converges to σ∞ in the C topology outside the singular n locus and the induced metric on Σ∞ is 1 g∞ = | |(σ∞)∗h∞ , K which has constant curvature K. Then Σ∞ must coincide with Σ by uniqueness. K→ −∞ We now claim that Ω = M. It is suﬃcient to show that if K , then the (cid:48) → n − union of I+(Σ ) is the whole manifold and if K 0 then the union of I (Σ (cid:48) ) is exactly M. KWn e will do the proof for the ﬁrstncase, the other being analogoKuns. ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: CMC

text: FOLIATION

text: WITH

text: PARTICLES

text: Σ

text: uniformly.

text: We

text: will

text: actually

text: prove

text: more:

text: we

text: will

text: show

text: that

text: the

text: convergence

text: is

text: K

text: also

text: smooth

text: outside

text: the

text: singular

text: lines.

text: Without

text: loss

text: of

text: generality

text: we

text: can

text: suppose

text: that

text: K

text: is

text: decreasing

text: and

text: converging

text: to

text: K.

text: This

text: implies

text: that

text: the

text: surface

text: Σ

text: lies

text: n

text: Kn

text: in

text: the

text: future

text: of

text: Σ

text: and

text: they

text: all

text: lie

text: in

text: the

text: future

text: of

text: the

text: surface

text: Σ

text: for

text: some

text: K

text: K

text: K.

text: This

text: kind

text: of

text: sequence

text: of

text: convex

text: space-like

text: surfaces

text: has

text: already

text: been

text: studied

text: in

text: In

text: particular,

text: the

text: authors

text: proved

text: (Theorem

text: and

text: Corollary

text: in

text: that

text: the

text: boundary

text: of

text: the

text: closure

text: of

text: the

text: union

text: of

text: I+(Σ

text: over

text: all

text: n

text: Kn

text: is

text: a

text: convex

text: space-like

text: surface

text: Σ∞.

text: Let

text: us

text: denote

text: by

text: σ∞

text: Σ

text: M

text: the

text: embedding

text: p

text: such

text: that

text: σ∞(Σ

text: Σ∞.

text: Let

text: ψ

text: Σ∞

text: Σ

text: be

text: the

text: homeomorphisms

text: obtained

text: by

text: p

text: n

text: Kn

text: following

text: the

text: normal

text: ﬂow.

text: We

text: deﬁne

text: σ

text: ψ

text: σ∞.

text: We

text: claim

text: that

text: σ

text: converges

text: to

text: n

text: n

text: n

text: σ∞

text: in

text: the

text: C

text: topology

text: outside

text: the

text: singular

text: locus

text: and

text: that

text: Σ∞

text: has

text: constant

text: Gauss

text: curvature

text: K.

text: The

text: induced

text: metrics

text: on

text: Σ

text: can

text: be

text: written

text: as

text: n

text: g

text: |h

text: n

text: n

text: K

text: n

text: where

text: h

text: is

text: a

text: hyperbolic

text: metric

text: with

text: cone

text: singularities

text: at

text: p

text: of

text: angles

text: θ,

text: since

text: all

text: n

text: surfaces

text: Σ

text: are

text: orthogonal

text: to

text: the

text: singular

text: locus.

text: Since

text: the

text: metrics

text: induced

text: on

text: Kn

text: convex

text: space-like

text: surfaces

text: embedded

text: in

text: Minkowski

text: manifold

text: increase

text: when

text: moving

text: towards

text: the

text: future

text: Proposition

text: we

text: have

text: that

text: ((σ

text: (γ))

text: (σ

text: (γ))

text: gn

text: n

text: for

text: every

text: simple

text: closed

text: curve

text: on

text: Σ

text: Therefore,

text: we

text: have

text: p

text: K

text: (σ

text: (γ))

text: K

text: (σ

text: (γ))

text: n|

text: (σ

text: (γ))

text: hn

text: n

text: n

text: gn

text: n

text: K

text: which

text: implies

text: that

text: the

text: metrics

text: σ

text: h

text: are

text: contained

text: in

text: a

text: compact

text: set

text: of

text: T

text: (Σ

text: Thus,

text: n

text: n

text: θ

text: p

text: up

text: to

text: extracting

text: a

text: subsequence,

text: the

text: metrics

text: σ

text: h

text: converges

text: to

text: a

text: hyperbolic

text: metric

text: n

text: n

text: h∞

text: T

text: (Σ

text: smoothly

text: outside

text: the

text: singular

text: locus.

text: Following

text: again

text: for

text: each

text: θ

text: p

text: regular

text: point

text: x

text: Σ∞

text: there

text: exists

text: a

text: sequence

text: x

text: Σ

text: such

text: that

text: x

text: converges

text: to

text: n

text: Kn

text: n

text: x

text: and

text: the

text: unit

text: normal

text: of

text: Σ

text: at

text: x

text: converges

text: to

text: the

text: unit

text: normal

text: of

text: Σ∞

text: at

text: x.

text: This

text: Kn

text: n

text: implies

text: that

text: the

text: sequence

text: of

text: of

text: σ

text: converges.

text: Now,

text: from

text: the

text: proof

text: of

text: Theorem

text: n

text: in

text: it

text: follows

text: that

text: if

text: σ

text: were

text: not

text: convergent

text: to

text: σ∞

text: in

text: the

text: C

text: topology,

text: the

text: n

text: surface

text: Σ∞

text: would

text: be

text: pleated

text: along

text: a

text: geodesic

text: γ

text: (which

text: may

text: be

text: a

text: geodesic

text: segment

text: between

text: singular

text: points)

text: and

text: tangent

text: to

text: a

text: light-like

text: plane

text: somewhere

text: outside

text: γ.

text: This

text: implies

text: that

text: Σ∞

text: admits

text: a

text: light-like

text: unit

text: normal,

text: which

text: contradicts

text: the

text: fact

text: that

text: Σ∞

text: is

text: space-like.

text: Therefore,

text: σ

text: converges

text: to

text: σ∞

text: in

text: the

text: C

text: topology

text: outside

text: the

text: singular

text: n

text: locus

text: and

text: the

text: induced

text: metric

text: on

text: Σ∞

text: is

text: g∞

text: |(σ∞)∗h∞

text: K

text: which

text: has

text: constant

text: curvature

text: K.

text: Then

text: Σ∞

text: must

text: coincide

text: with

text: Σ

text: by

text: uniqueness.

text: K→

text: We

text: now

text: claim

text: that

text: Ω

text: M.

text: It

text: is

text: suﬃcient

text: to

text: show

text: that

text: if

text: K

text: then

text: the

text: n

text: union

text: of

text: I+(Σ

text: is

text: the

text: whole

text: manifold

text: and

text: if

text: K

text: then

text: the

text: union

text: of

text: I

text: (Σ

text: is

text: exactly

text: M.

text: KWn

text: e

text: will

text: do

text: the

text: proof

text: for

text: the

text: ﬁrstncase,

text: the

text: other

text: being

text: analogoKuns.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: CMC FOLIATION WITH PARTICLES 34 → (cid:48) → (cid:48) the identity (ﬁxing the marked points) g : (Σ , c) (Σ , h) and g : (Σ , c) (Σ , h ) p p p p such that (cid:48) ◦ − (cid:48) f = g g 1 and Hopf(g ) = e2iαHopf(g) . × Landslides are related to the aforementioned S1-action on T (Σ ) T (Σ ) in (cid:48) ∈ × θ p θ p the following way. Given a couple (h, h ) T (Σ ) T (Σ ), there exists a unique θ p θ p → conformal class c on Σ such that the unique harmonic maps g : (Σ , c) (Σ , h) (cid:48) → p (cid:48) p p and g : (Σ , c) (Σ , h ) isotopic to the identity have opposite Hopf diﬀerentials. p p ∈ For every eiα S1 we can thus deﬁne × → × L : T (Σ ) T (Σ ) T (Σ ) T (Σ ) eiα θ p θ p θ p θ p (cid:48) (cid:55)→ (h, h ) (h , h− ) α α ∈ × where (h , h− ) T (Σ ) T (Σ ) are characterised by the fact that the unique α α θ p θ p → → harmonic maps isotopic to the identity g : (Σ , c) (Σ , h ) and g− : (Σ , c) α p p α α p (Σ , h− ) satisfy p α ± Hopf(g± ) = e iαHopf(g) , α ◦ − i.e. g g−1 is an α-landslide with the center c. α α A natural way to construct diﬀeomorphisms between hyperbolic surfaces is pro- vided by AdS geometry (see for instance [BS10], [BS16a], [Tam16a] for more details). ⊂ Let S M be a space-like surface embedded into a CGHM AdS manifolds with par- ticles, orthogonal to the singular lines. We can construct two hyperbolic metrics on Σ from the embedding data of S: p · · − · − · h = I((E + JB) , (E + JB) ) h = I((E JB) , (E JB) ) l r where J is the unique complex structure compatible with the induced metric on S → and E : T S T S is the identity operator. It was veriﬁed ([KS07]) that h and h l r carry cone singularities of the same angle θ at the points p as the surface S. Let us i i denote by → π : (Σ , I) (Σ , h ) l,r p p l,r the identity maps. In [BMS13] the authors proved that if S is a space-like surface − ◦ − with constant Gauss curvature 1 , then π π 1 is an α-landslide. This result cos2(α/2) l r was then extended to the case with conical singularities in [CS16]. We prove that landslides between hyperbolic metrics with cone singularities (of angles less than π) can also be constructed in terms of constant mean curvature surfaces embedded in CGHM AdS manifolds with particles. ⊂ Proposition 4.11. Let S M be a space-like surface embedded in a CGHM AdS manifold orthogonal to the singular lines. If S has constant mean curvature H, then ◦ − the map π π 1 is an α-landslide, where l r − π α = arctan(H) + . 2 ##LTLine## ##LTLine##

text: CMC

text: FOLIATION

text: WITH

text: PARTICLES

text: the

text: identity

text: (ﬁxing

text: the

text: marked

text: points)

text: g

text: (Σ

text: c)

text: (Σ

text: h)

text: and

text: g

text: (Σ

text: c)

text: (Σ

text: h

text: p

text: p

text: p

text: p

text: such

text: that

text: f

text: g

text: g

text: and

text: Hopf(g

text: Landslides

text: are

text: related

text: to

text: the

text: aforementioned

text: on

text: T

text: (Σ

text: T

text: (Σ

text: in

text: θ

text: p

text: θ

text: p

text: the

text: following

text: way.

text: Given

text: a

text: couple

text: (h,

text: h

text: T

text: (Σ

text: T

text: (Σ

text: there

text: exists

text: a

text: unique

text: θ

text: p

text: θ

text: p

text: conformal

text: class

text: c

text: on

text: Σ

text: such

text: that

text: the

text: unique

text: harmonic

text: maps

text: g

text: (Σ

text: c)

text: (Σ

text: h)

text: p

text: p

text: p

text: and

text: g

text: (Σ

text: c)

text: (Σ

text: h

text: isotopic

text: to

text: the

text: identity

text: have

text: opposite

text: Hopf

text: diﬀerentials.

text: p

text: p

text: For

text: every

text: eiα

text: we

text: can

text: thus

text: deﬁne

text: L

text: T

text: (Σ

text: T

text: (Σ

text: T

text: (Σ

text: T

text: (Σ

text: eiα

text: θ

text: p

text: θ

text: p

text: θ

text: p

text: θ

text: p

text: (h,

text: h

text: (h

text: h−

text: α

text: α

text: where

text: (h

text: h−

text: T

text: (Σ

text: T

text: (Σ

text: are

text: characterised

text: by

text: the

text: fact

text: that

text: the

text: unique

text: α

text: α

text: θ

text: p

text: θ

text: p

text: harmonic

text: maps

text: isotopic

text: to

text: the

text: identity

text: g

text: (Σ

text: c)

text: (Σ

text: h

text: and

text: g−

text: (Σ

text: c)

text: α

text: p

text: p

text: α

text: α

text: p

text: (Σ

text: h−

text: satisfy

text: p

text: α

text: Hopf(g±

text: e

text: iαHopf(g)

text: α

text: i.e.

text: g

text: is

text: an

text: α-landslide

text: with

text: the

text: center

text: c.

text: α

text: α

text: A

text: natural

text: way

text: to

text: construct

text: diﬀeomorphisms

text: between

text: hyperbolic

text: surfaces

text: is

text: pro-

text: vided

text: by

text: AdS

text: geometry

text: (see

text: for

text: instance

text: for

text: more

text: details).

text: Let

text: S

text: M

text: be

text: a

text: space-like

text: surface

text: embedded

text: into

text: a

text: CGHM

text: AdS

text: manifolds

text: with

text: par-

text: ticles,

text: orthogonal

text: to

text: the

text: singular

text: lines.

text: We

text: can

text: construct

text: two

text: hyperbolic

text: metrics

text: on

text: Σ

text: from

text: the

text: embedding

text: data

text: of

text: S:

text: p

text: h

text: I((E

text: JB)

text: (E

text: JB)

text: h

text: I((E

text: JB)

text: (E

text: JB)

text: l

text: r

text: where

text: J

text: is

text: the

text: unique

text: complex

text: structure

text: compatible

text: with

text: the

text: induced

text: metric

text: on

text: S

text: and

text: E

text: T

text: S

text: T

text: S

text: is

text: the

text: identity

text: operator.

text: It

text: was

text: veriﬁed

text: that

text: h

text: and

text: h

text: l

text: r

text: carry

text: cone

text: singularities

text: of

text: the

text: same

text: angle

text: θ

text: at

text: the

text: points

text: p

text: as

text: the

text: surface

text: S.

text: Let

text: us

text: i

text: i

text: denote

text: by

text: π

text: (Σ

text: I)

text: (Σ

text: h

text: l,r

text: p

text: p

text: l,r

text: the

text: identity

text: maps.

text: In

text: the

text: authors

text: proved

text: that

text: if

text: S

text: is

text: a

text: space-like

text: surface

text: with

text: constant

text: Gauss

text: curvature

text: then

text: π

text: π

text: is

text: an

text: α-landslide.

text: This

text: result

text: l

text: r

text: was

text: then

text: extended

text: to

text: the

text: case

text: with

text: conical

text: singularities

text: in

text: We

text: prove

text: that

text: landslides

text: between

text: hyperbolic

text: metrics

text: with

text: cone

text: singularities

text: (of

text: angles

text: less

text: than

text: π)

text: can

text: also

text: be

text: constructed

text: in

text: terms

text: of

text: constant

text: mean

text: curvature

text: surfaces

text: embedded

text: in

text: CGHM

text: AdS

text: manifolds

text: with

text: particles.

text: Proposition

text: Let

text: S

text: M

text: be

text: a

text: space-like

text: surface

text: embedded

text: in

text: a

text: CGHM

text: AdS

text: manifold

text: orthogonal

text: to

text: the

text: singular

text: lines.

text: If

text: S

text: has

text: constant

text: mean

text: curvature

text: H,

text: then

text: the

text: map

text: π

text: π

text: is

text: an

text: α-landslide,

text: where

text: l

text: r

text: π

text: α

text: arctan(H)

text: ##LTLine##

text: ##LTLine##


text: CMC FOLIATION WITH PARTICLES 40 for any n. Let D be the maximal distance from x to the initial singularity of M. (cid:16)(cid:113) (cid:17) Theorem 5.2 implies that there exists a surface Σ of constant Gauss curvature KN K for N large enough such that δ(K ) < D/2 (this is ensured by the fact that N N −∞ δ(K ) = arctanh −1 tends to 0 as K tends to ), lying within a time-like n 1 Kn n distance less than D/2 from the initial singularity of M. Therefore, the equidistant surface S in the future at a distance δ(K ) from Σ , lies within a time-like HN N KN distance strictly less than D from the initial singularity. This implies that x is in the future of S , which leads to contradiction. HN (cid:48) (cid:54) ∈ −∞ Note that Σ is disjoint from any other Σ (cid:48) for all K = K ( , 0) (see K K Theorem 5.2). Combined with the construction of S , it follows that S is disjoint (cid:54) (cid:48) ∈ −∞ − H H from any other S (cid:48) for all H = H ( , 1). H Combining all the results above, the proposition follows. (cid:3) Note that the argument using the Maximum Principle in Proposition 4.9 for the AdS case is also adapted to the de Sitter case. We have the following result. Proposition 5.9. The foliation of a CGHM de Sitter manifold with particles by constant mean curvature surfaces is unique. Combined with Proposition 5.8 and Proposition 5.9, we complete the proof of Theorem 5.1. References [BBS11] Thierry Barbot, Francesco Bonsante, and Jean-Marc Schlenker. Collisions of particles in locally AdS spacetimes I. Local description and global examples. Comm. Math. Phys., 308(1):147–200, 2011. [BBZ03] Thierry Barbot, François Béguin, and Abdelghani Zeghib. Feuilletages des espaces temps globalement hyperboliques par des hypersurfaces à courbure moyenne constante. C. R. Math. Acad. Sci. Paris, 336(3):245–250, 2003. [BBZ07] Thierry Barbot, François Béguin, and Abdelghani Zeghib. Constant mean curvature fo- liations of globally hyperbolic spacetimes locally modelled on AdS . Geom. Dedicata, 3 126:71–129, 2007. [BBZ11] Thierry Barbot, François Béguin, and Abdelghani Zeghib. Prescribing Gauss curvature of surfaces in 3-dimensional spacetimes: application to the Minkowski problem in the Minkowski space. Ann. Inst. Fourier (Grenoble), 61(2):511–591, 2011. [Bel14] Mehdi Belraouti. Sur la géométrie de la singularité initiale des espaces-temps plats glob- alement hyperboliques. Annales de l’Institut Fourier, 64(2):457–466, 2014. [BMS13] Francesco Bonsante, Gabriele Mondello, and Jean-Marc Schlenker. A cyclic extension of the earthquake ﬂow I. Geom. Topol., 17(1):157–234, 2013. [BS10] Francesco Bonsante and Jean-Marc Schlenker. Maximal surfaces and the universal Te- ichmüller space. Invent. Math., 182(2):279–333, 2010. [BS16a] Francesco Bonsante and Andrea Seppi. Area-preserving diﬀeomorphism of the hyperbolic plane and K-surfaces in Anti-de Sitter space. Preprint arXiv:1610.05701, 2016. ##LTLine## ##LTLine##

text: CMC

text: FOLIATION

text: WITH

text: PARTICLES

text: for

text: any

text: n.

text: Let

text: D

text: be

text: the

text: maximal

text: distance

text: from

text: x

text: to

text: the

text: initial

text: singularity

text: of

text: M.

text: Theorem

text: implies

text: that

text: there

text: exists

text: a

text: surface

text: Σ

text: of

text: constant

text: Gauss

text: curvature

text: KN

text: K

text: for

text: N

text: large

text: enough

text: such

text: that

text: δ(K

text: (this

text: is

text: ensured

text: by

text: the

text: fact

text: that

text: N

text: N

text: δ(K

text: arctanh

text: −1

text: tends

text: to

text: as

text: K

text: tends

text: to

text: lying

text: within

text: a

text: time-like

text: n

text: Kn

text: n

text: distance

text: less

text: than

text: from

text: the

text: initial

text: singularity

text: of

text: M.

text: Therefore,

text: the

text: equidistant

text: surface

text: S

text: in

text: the

text: future

text: at

text: a

text: distance

text: δ(K

text: from

text: Σ

text: lies

text: within

text: a

text: time-like

text: HN

text: N

text: KN

text: distance

text: strictly

text: less

text: than

text: D

text: from

text: the

text: initial

text: singularity.

text: This

text: implies

text: that

text: x

text: is

text: in

text: the

text: future

text: of

text: S

text: which

text: leads

text: to

text: contradiction.

text: HN

text: Note

text: that

text: Σ

text: is

text: disjoint

text: from

text: any

text: other

text: Σ

text: for

text: all

text: K

text: K

text: (see

text: K

text: K

text: Theorem

text: Combined

text: with

text: the

text: construction

text: of

text: S

text: it

text: follows

text: that

text: S

text: is

text: disjoint

text: H

text: H

text: from

text: any

text: other

text: S

text: for

text: all

text: H

text: H

text: H

text: Combining

text: all

text: the

text: results

text: above,

text: the

text: proposition

text: follows.

text: Note

text: that

text: the

text: argument

text: using

text: the

text: Maximum

text: Principle

text: in

text: Proposition

text: for

text: the

text: AdS

text: case

text: is

text: also

text: adapted

text: to

text: the

text: de

text: Sitter

text: case.

text: We

text: have

text: the

text: following

text: result.

text: Proposition

text: The

text: foliation

text: of

text: a

text: CGHM

text: de

text: Sitter

text: manifold

text: with

text: particles

text: by

text: constant

text: mean

text: curvature

text: surfaces

text: is

text: unique.

text: Combined

text: with

text: Proposition

text: and

text: Proposition

text: we

text: complete

text: the

text: proof

text: of

text: Theorem

text: References

text: Thierry

text: Barbot,

text: Francesco

text: Bonsante,

text: and

text: Jean-Marc

text: Schlenker.

text: Collisions

text: of

text: particles

text: in

text: locally

text: AdS

text: spacetimes

text: I.

text: Local

text: description

text: and

text: global

text: examples.

text: Comm.

text: Math.

text: Phys.,

text: Thierry

text: Barbot,

text: François

text: Béguin,

text: and

text: Abdelghani

text: Zeghib.

text: Feuilletages

text: des

text: espaces

text: temps

text: globalement

text: hyperboliques

text: par

text: des

text: hypersurfaces

text: à

text: courbure

text: moyenne

text: constante.

text: C.

text: R.

text: Math.

text: Acad.

text: Sci.

text: Paris,

text: Thierry

text: Barbot,

text: François

text: Béguin,

text: and

text: Abdelghani

text: Zeghib.

text: Constant

text: mean

text: curvature

text: fo-

text: liations

text: of

text: globally

text: hyperbolic

text: spacetimes

text: locally

text: modelled

text: on

text: AdS

text: Geom.

text: Dedicata,

text: Thierry

text: Barbot,

text: François

text: Béguin,

text: and

text: Abdelghani

text: Zeghib.

text: Prescribing

text: Gauss

text: curvature

text: of

text: surfaces

text: in

text: spacetimes:

text: application

text: to

text: the

text: Minkowski

text: problem

text: in

text: the

text: Minkowski

text: space.

text: Ann.

text: Inst.

text: Fourier

text: (Grenoble),

text: Mehdi

text: Belraouti.

text: Sur

text: la

text: géométrie

text: de

text: la

text: singularité

text: initiale

text: des

text: espaces-temps

text: plats

text: glob-

text: alement

text: hyperboliques.

text: Annales

text: de

text: l’Institut

text: Fourier,

text: Francesco

text: Bonsante,

text: Gabriele

text: Mondello,

text: and

text: Jean-Marc

text: Schlenker.

text: A

text: cyclic

text: extension

text: of

text: the

text: earthquake

text: ﬂow

text: I.

text: Geom.

text: Topol.,

text: Francesco

text: Bonsante

text: and

text: Jean-Marc

text: Schlenker.

text: Maximal

text: surfaces

text: and

text: the

text: universal

text: Te-

text: ichmüller

text: space.

text: Invent.

text: Math.,

text: Francesco

text: Bonsante

text: and

text: Andrea

text: Seppi.

text: Area-preserving

text: diﬀeomorphism

text: of

text: the

text: hyperbolic

text: plane

text: and

text: K-surfaces

text: in

text: Anti-de

text: Sitter

text: space.

text: Preprint

text: ##LTLine##

text: ##LTLine##


text: 4 Tree Loop r Stable Unstable UFB 15,975 9,157 6,818 57.3% Meta 51 48 3 94.1 % Stable 6,369 6,116 253 4.0 % TABLE I. Summary of our parameter set. r is the misidenti- ﬁcation rate when using tree-level constraints. ’Unstable’ at loop level includes UFB and metastability, i.e. ’stable’ means absolutely stable. checks [59, 60]. The remaining 22,395 points can be categorised as shown in Tab. I. Thus, more than half of the points which are ruled out by the tree-level UFB checks are valid at the loop-level. In general, there is a correlation between the size of the quartic couplings and the mass splitting between m , m and m . Conse- H A H+ quently, we ﬁnd also a correlation between the maximal splitting between the heavy Higgs state and the size of λ which can be stabilised via loop corrections5. This 1,2 is shown in Fig. 4 where the misidentiﬁcation rate r is given as function of min(λ , λ ) and the maximal mass 1 2 diﬀerence. r gives for the UFB and metastability check the ratio of points for which the result ’unstable’ changes to ’stable’ at the loop-level, while for stable tree-level − points it is vice versa. For small (> 0.2) negative val- ≈ ues of λ , we ﬁnd r 1 for the entire range of mass 1,2 diﬀerences. Only for a small island with very large mass diﬀerences points stay unstable at the loop-level. These points have in common that λ is O(4π), i.e. the loop 3 corrections might not be under control any more. If we | | FIG. 3. The scalar potential at tree- (top) and one-loop would have applied a stronger cut on λ as it might i (bottom) for the parameter point λ = 2.4, λ = 0.03, be necessary to really keep perturbativity under control − 1− 2 | | λ = 9.8, λ = 4.1, λ = 0.7, m = 0.81 TeV2. Shown is [61], e.g. λ < 2π, this island wouldn’t appear and ∆th3Ve c=or[rVec(tv41e,wv2V)E−VVs(vve15eww,=v2e1w6)0].×111G20e−V8, ivnewun=its18o4f.G3 eGVe4Vw. ith rth=e u1sewfuolunledsishoofldthuepchteockmfionr(λm1,eλta2s)ta(cid:38)bi−lit0y.,1t5h.e Tsaomtpeslet 1 2 of points is signiﬁcantly lower than for UFB, i.e. there is a non-negligible uncertainty in the misidentiﬁcation eﬀective potential. As data sample we have generated rate. Nevertheless, the obtained results suggest that in 400,000 points using the following parameter ranges4: most cases it rules out points which are viable. On the other side, the fraction of points which is stable at tree- level but becomes unstable at loop-level is quite low. We 200 GeV < m , m < 1000 GeV H A show the distribution of points without UFB directions 500−GeV < mH+ < 1000 GeV in Fig. 5. One can see that only for small |m12| and large 106 GeV2 < m < 0 mass diﬀerences between the heavy Higgs states, a point 12 − stable at tree-level can become unstable at loop-level. 1 < tan α < 0, 1 < tan β < 1.5 Up to now, we have only studied the overall stability Afterwards, points are discarded which violate the of the potential. However, even a meta-stable vacuum is tree-level unitarity limits or which fail the HiggsBounds 5 This implies, of course, that the rate of misidentiﬁed points de- 4 We use small values of tanβ to improve the eﬃciency of the pends on the chosen parameter ranges and gets enhanced by random scan. For larger values, it is more likely the the quar- the diﬀerent lower limit of mH+ compared to mH, mA. Never- tic couplings violate the tree-level unitarity limits unless ﬁne- theless, we think that the results are representative, because in tuned cancellations between diﬀerent mass terms are present, see literature often even bigger diﬀerences between the charged and eqs. (3)–(7). The overall results are not aﬀected by this choice. heavy neutral masses are considered. ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Tree

text: Loop

text: r

text: Stable

text: Unstable

text: UFB

text: Meta

text: Stable

text: TABLE

text: I.

text: Summary

text: of

text: our

text: parameter

text: set.

text: r

text: is

text: the

text: misidenti-

text: ﬁcation

text: rate

text: when

text: using

text: tree-level

text: constraints.

text: ’Unstable’

text: at

text: loop

text: level

text: includes

text: UFB

text: and

text: metastability,

text: i.e.

text: ’stable’

text: means

text: absolutely

text: stable.

text: checks

text: The

text: remaining

text: points

text: can

text: be

text: categorised

text: as

text: shown

text: in

text: Tab.

text: I.

text: Thus,

text: more

text: than

text: half

text: of

text: the

text: points

text: which

text: are

text: ruled

text: out

text: by

text: the

text: tree-level

text: UFB

text: checks

text: are

text: valid

text: at

text: the

text: loop-level.

text: In

text: general,

text: there

text: is

text: a

text: correlation

text: between

text: the

text: size

text: of

text: the

text: quartic

text: couplings

text: and

text: the

text: mass

text: splitting

text: between

text: m

text: m

text: and

text: m

text: Conse-

text: H

text: A

text: H+

text: quently,

text: we

text: ﬁnd

text: also

text: a

text: correlation

text: between

text: the

text: maximal

text: splitting

text: between

text: the

text: heavy

text: Higgs

text: state

text: and

text: the

text: size

text: of

text: λ

text: which

text: can

text: be

text: stabilised

text: via

text: loop

text: This

text: is

text: shown

text: in

text: Fig.

text: where

text: the

text: misidentiﬁcation

text: rate

text: r

text: is

text: given

text: as

text: function

text: of

text: min(λ

text: λ

text: and

text: the

text: maximal

text: mass

text: diﬀerence.

text: r

text: gives

text: for

text: the

text: UFB

text: and

text: metastability

text: check

text: the

text: ratio

text: of

text: points

text: for

text: which

text: the

text: result

text: ’unstable’

text: changes

text: to

text: ’stable’

text: at

text: the

text: loop-level,

text: while

text: for

text: stable

text: tree-level

text: points

text: it

text: is

text: vice

text: versa.

text: For

text: small

text: negative

text: val-

text: ues

text: of

text: λ

text: we

text: ﬁnd

text: r

text: for

text: the

text: entire

text: range

text: of

text: mass

text: diﬀerences.

text: Only

text: for

text: a

text: small

text: island

text: with

text: very

text: large

text: mass

text: diﬀerences

text: points

text: stay

text: unstable

text: at

text: the

text: loop-level.

text: These

text: points

text: have

text: in

text: common

text: that

text: λ

text: is

text: i.e.

text: the

text: loop

text: corrections

text: might

text: not

text: be

text: under

text: control

text: any

text: more.

text: If

text: we

text: FIG.

text: The

text: scalar

text: potential

text: at

text: tree-

text: (top)

text: and

text: one-loop

text: would

text: have

text: applied

text: a

text: stronger

text: cut

text: on

text: λ

text: as

text: it

text: might

text: i

text: (bottom)

text: for

text: the

text: parameter

text: point

text: λ

text: λ

text: be

text: necessary

text: to

text: really

text: keep

text: perturbativity

text: under

text: control

text: 1−

text: λ

text: λ

text: λ

text: m

text: Shown

text: is

text: e.g.

text: λ

text: this

text: island

text: wouldn’t

text: appear

text: and

text: ith

text: rth=e

text: Tsaomtpeslet

text: of

text: points

text: is

text: signiﬁcantly

text: lower

text: than

text: for

text: UFB,

text: i.e.

text: there

text: is

text: a

text: non-negligible

text: uncertainty

text: in

text: the

text: misidentiﬁcation

text: eﬀective

text: potential.

text: As

text: data

text: sample

text: we

text: have

text: generated

text: rate.

text: Nevertheless,

text: the

text: obtained

text: results

text: suggest

text: that

text: in

text: points

text: using

text: the

text: following

text: parameter

text: most

text: cases

text: it

text: rules

text: out

text: points

text: which

text: are

text: viable.

text: On

text: the

text: other

text: side,

text: the

text: fraction

text: of

text: points

text: which

text: is

text: stable

text: at

text: tree-

text: level

text: but

text: becomes

text: unstable

text: at

text: loop-level

text: is

text: quite

text: low.

text: We

text: GeV

text: m

text: m

text: GeV

text: H

text: A

text: show

text: the

text: distribution

text: of

text: points

text: without

text: UFB

text: directions

text: mH+

text: GeV

text: in

text: Fig.

text: One

text: can

text: see

text: that

text: only

text: for

text: small

text: and

text: large

text: m

text: mass

text: diﬀerences

text: between

text: the

text: heavy

text: Higgs

text: states,

text: a

text: point

text: stable

text: at

text: tree-level

text: can

text: become

text: unstable

text: at

text: loop-level.

text: tan

text: α

text: tan

text: β

text: Up

text: to

text: now,

text: we

text: have

text: only

text: studied

text: the

text: overall

text: stability

text: Afterwards,

text: points

text: are

text: discarded

text: which

text: violate

text: the

text: of

text: the

text: potential.

text: However,

text: even

text: a

text: meta-stable

text: vacuum

text: is

text: tree-level

text: unitarity

text: limits

text: or

text: which

text: fail

text: the

text: HiggsBounds

text: This

text: implies,

text: of

text: course,

text: that

text: the

text: rate

text: of

text: misidentiﬁed

text: points

text: de-

text: We

text: use

text: small

text: values

text: of

text: tanβ

text: to

text: improve

text: the

text: eﬃciency

text: of

text: the

text: pends

text: on

text: the

text: chosen

text: parameter

text: ranges

text: and

text: gets

text: enhanced

text: by

text: random

text: scan.

text: For

text: larger

text: values,

text: it

text: is

text: more

text: likely

text: the

text: the

text: quar-

text: the

text: diﬀerent

text: lower

text: limit

text: of

text: mH+

text: compared

text: to

text: mH,

text: mA.

text: Never-

text: tic

text: couplings

text: violate

text: the

text: tree-level

text: unitarity

text: limits

text: unless

text: ﬁne-

text: theless,

text: we

text: think

text: that

text: the

text: results

text: are

text: representative,

text: because

text: in

text: tuned

text: cancellations

text: between

text: diﬀerent

text: mass

text: terms

text: are

text: present,

text: see

text: literature

text: often

text: even

text: bigger

text: diﬀerences

text: between

text: the

text: charged

text: and

text: eqs.

text: The

text: overall

text: results

text: are

text: not

text: aﬀected

text: by

text: this

text: choice.

text: heavy

text: neutral

text: masses

text: are

text: considered.

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##