text: { } such that End(x ) = u − , u . The initial vertex is v , v is the terminal vertex, and i i 1 i 0 n v , . . . , v − are internal vertices of W . We write 1 n 1 − · · · W 1 = v e v − e v e v n n n 1 2 1 1 0 for the same walk in the reverse direction; its initial vertex is v and its terminal vertex is v . · ·n· 0 A subwalk of W is a subsequence of the form v e v e v − e v . A walk is closed if ≥ i i+1 i+1 i+2 k 1 k k n 1 and v = v and open otherwise. A walk is a trail if it has no repeating edges, and an 0 n open path if it has no repeating vertices (and consequently no repeating edges), and a closed path if it has no repeating vertices except that v = v . The graph of a closed path is a circle. 0 n (The diﬀerence is that a closed path has an initial and terminal vertex and a direction.) Note that every walk, including a closed walk, has an initial vertex and a terminal vertex, which are identical if the walk is closed. A signed graph Σ = (G, σ) consists of an unsigned graph G together with a sign function → { − } σ : E(G) +1, 1 . We usually write V (G) and E(G) as V (Σ) and E(Σ), respectively. Subgraphs of Σ inherit the edge signs from Σ. · · · (cid:89) The sign of a walk W = v e v e v − e v is the product 0 1 1 2 n 1 n n n σ(W ) = σ(e ). i i=1 In particular, the sign of a circle is the product of the signs of its edges. A subgraph (or its edge set) is balanced if every circle in it has positive sign. A signed-graph circuit is a subgraph (or its edge set) of the following three types: (1) A positive circle, said to be of Type I. (2) A pair of negative circles whose intersection is a single vertex, said to be of Type II. (3) A pair of vertex-disjoint negative circles together with a path of positive length that connects the two circles and is internally disjoint from the two circles, said to be of Type III. The connecting path in Type III and the common vertex in Type II are called the circuit path of the circuit. The circuits of a signed graph Σ form the circuit system of a matroid on the edge set of Σ [?], the frame matroid of the signed graph Σ; such a matroid is called a signed-graphic matroid. (Type II and Type III circuits are named contrabalanced tight handcuﬀs and contrabalanced loose handcuﬀs respectively by Zaslavsky [?]. We do not use these names here.) An ordinary unsigned graph is viewed as a signed graph whose edges are all positive; so all of its circles have positive sign and the frame matroid of an unsigned graph coincides with the graphic matroid. A bidirection of a graph (a concept introduced by Edmonds [?]) is a function ω from the {− } set of all edge ends to the sign group, 1, +1 . We view a positive value ω(u, e) as denoting an arrow at the end (u, e) directed along the edge e toward the endpoint u, and a negative value as an arrow directed away from the endpoint. Recall that we treat a loop e = uv (with u = v) as having distinguishable ends (u, e) and (v, e). 3

text: such

text: that

text: End(x

text: u

text: u

text: The

text: initial

text: vertex

text: is

text: v

text: v

text: is

text: the

text: terminal

text: vertex,

text: and

text: i

text: i

text: i

text: n

text: v

text: v

text: are

text: internal

text: vertices

text: of

text: W

text: We

text: write

text: n

text: W

text: v

text: e

text: v

text: e

text: v

text: e

text: v

text: n

text: n

text: n

text: for

text: the

text: same

text: walk

text: in

text: the

text: reverse

text: direction;

text: its

text: initial

text: vertex

text: is

text: v

text: and

text: its

text: terminal

text: vertex

text: is

text: v

text: ·n·

text: A

text: subwalk

text: of

text: W

text: is

text: a

text: subsequence

text: of

text: the

text: form

text: v

text: e

text: v

text: e

text: v

text: e

text: v

text: A

text: walk

text: is

text: closed

text: if

text: i

text: k

text: k

text: k

text: n

text: and

text: v

text: v

text: and

text: open

text: otherwise.

text: A

text: walk

text: is

text: a

text: trail

text: if

text: it

text: has

text: no

text: repeating

text: edges,

text: and

text: an

text: n

text: open

text: path

text: if

text: it

text: has

text: no

text: repeating

text: vertices

text: (and

text: consequently

text: no

text: repeating

text: edges),

text: and

text: a

text: closed

text: path

text: if

text: it

text: has

text: no

text: repeating

text: vertices

text: except

text: that

text: v

text: v

text: The

text: graph

text: of

text: a

text: closed

text: path

text: is

text: a

text: circle.

text: n

text: (The

text: diﬀerence

text: is

text: that

text: a

text: closed

text: path

text: has

text: an

text: initial

text: and

text: terminal

text: vertex

text: and

text: a

text: direction.)

text: Note

text: that

text: every

text: walk,

text: including

text: a

text: closed

text: walk,

text: has

text: an

text: initial

text: vertex

text: and

text: a

text: terminal

text: vertex,

text: which

text: are

text: identical

text: if

text: the

text: walk

text: is

text: closed.

text: A

text: signed

text: graph

text: Σ

text: (G,

text: σ)

text: consists

text: of

text: an

text: unsigned

text: graph

text: G

text: together

text: with

text: a

text: sign

text: function

text: σ

text: E(G)

text: We

text: usually

text: write

text: V

text: (G)

text: and

text: E(G)

text: as

text: V

text: (Σ)

text: and

text: E(Σ),

text: respectively.

text: Subgraphs

text: of

text: Σ

text: inherit

text: the

text: edge

text: signs

text: from

text: Σ.

text: The

text: sign

text: of

text: a

text: walk

text: W

text: v

text: e

text: v

text: e

text: v

text: e

text: v

text: is

text: the

text: product

text: n

text: n

text: n

text: n

text: σ(W

text: σ(e

text: i

text: In

text: particular,

text: the

text: sign

text: of

text: a

text: circle

text: is

text: the

text: product

text: of

text: the

text: signs

text: of

text: its

text: edges.

text: A

text: subgraph

text: (or

text: its

text: edge

text: set)

text: is

text: balanced

text: if

text: every

text: circle

text: in

text: it

text: has

text: positive

text: sign.

text: A

text: signed-graph

text: circuit

text: is

text: a

text: subgraph

text: (or

text: its

text: edge

text: set)

text: of

text: the

text: following

text: three

text: types:

text: A

text: positive

text: circle,

text: said

text: to

text: be

text: of

text: Type

text: I.

text: A

text: pair

text: of

text: negative

text: circles

text: whose

text: intersection

text: is

text: a

text: single

text: vertex,

text: said

text: to

text: be

text: of

text: Type

text: II.

text: A

text: pair

text: of

text: vertex-disjoint

text: negative

text: circles

text: together

text: with

text: a

text: path

text: of

text: positive

text: length

text: that

text: connects

text: the

text: two

text: circles

text: and

text: is

text: internally

text: disjoint

text: from

text: the

text: two

text: circles,

text: said

text: to

text: be

text: of

text: Type

text: III.

text: The

text: connecting

text: path

text: in

text: Type

text: III

text: and

text: the

text: common

text: vertex

text: in

text: Type

text: II

text: are

text: called

text: the

text: circuit

text: path

text: of

text: the

text: circuit.

text: The

text: circuits

text: of

text: a

text: signed

text: graph

text: Σ

text: form

text: the

text: circuit

text: system

text: of

text: a

text: matroid

text: on

text: the

text: edge

text: set

text: of

text: Σ

text: the

text: frame

text: matroid

text: of

text: the

text: signed

text: graph

text: Σ;

text: such

text: a

text: matroid

text: is

text: called

text: a

text: signed-graphic

text: matroid.

text: (Type

text: II

text: and

text: Type

text: III

text: circuits

text: are

text: named

text: contrabalanced

text: tight

text: handcuﬀs

text: and

text: contrabalanced

text: loose

text: handcuﬀs

text: respectively

text: by

text: Zaslavsky

text: We

text: do

text: not

text: use

text: these

text: names

text: here.)

text: An

text: ordinary

text: unsigned

text: graph

text: is

text: viewed

text: as

text: a

text: signed

text: graph

text: whose

text: edges

text: are

text: all

text: positive;

text: so

text: all

text: of

text: its

text: circles

text: have

text: positive

text: sign

text: and

text: the

text: frame

text: matroid

text: of

text: an

text: unsigned

text: graph

text: coincides

text: with

text: the

text: graphic

text: matroid.

text: A

text: bidirection

text: of

text: a

text: graph

text: (a

text: concept

text: introduced

text: by

text: Edmonds

text: is

text: a

text: function

text: ω

text: from

text: the

text: set

text: of

text: all

text: edge

text: ends

text: to

text: the

text: sign

text: group,

text: We

text: view

text: a

text: positive

text: value

text: ω(u,

text: e)

text: as

text: denoting

text: an

text: arrow

text: at

text: the

text: end

text: (u,

text: e)

text: directed

text: along

text: the

text: edge

text: e

text: toward

text: the

text: endpoint

text: u,

text: and

text: a

text: negative

text: value

text: as

text: an

text: arrow

text: directed

text: away

text: from

text: the

text: endpoint.

text: Recall

text: that

text: we

text: treat

text: a

text: loop

text: e

text: uv

text: (with

text: u

text: v)

text: as

text: having

text: distinguishable

text: ends

text: (u,

text: e)

text: and

text: (v,

text: e).


text: (cid:102) Proof. Parts (a) and (cid:101)(b) are by deﬁnition of the projection. · · · For part (c), let W = v e v e v − e v be a walk in Σ, lifted to a walk W = · · · 0 1 1 2(cid:89) n 1 n (cid:89)n vα0e˜ vα1 e˜ vαn in Σ. Since σ(e ) = α − α by (??), 0 1 1 n n i i 1 i n n σ(W ) = σ(ei) = αi−1αi = α0αn. (cid:102) i=1 i=1 Thus, σ(W ) = +1 if and only if α = α . It follows that the walk W is closed if and only if n 0 (cid:3) W has positive sign. 3. Flows × The incidence matrix [?] of an orientedsigned graph (Σ, ω) is the V E matrix M = × → Z M(Σ, ω) = [m(v, e)], wher(cid:88)e m is a function m : V E deﬁned by  ω(v, e) if e is a link, m(v, e) = ω(v, e) = 2 ω(v, e) if e is a negative loop, (3.1) ∈ v End(e) 0 otherwise. { } When e is a loop with End(e) = v, v we add ω(v, e) for each end of e, so the sum is 0 when e is a positive loop and is 2 ω(v, e) when e is a negative loop. → Z An integral ﬂow on an oriented signed graph (Σ, ω) is a function f : E(Σ) which is conservative at every vertex, meaning that the net contribution to each vertex is zero. The (cid:88)Z → Z (cid:88) boundary operator of (Σ, ω), ∂ : E(Σ) V (Σ), is deﬁned by ∂f(v) = m(v, e)f(e) = ω(v, e)f(e). (3.2) ∈ ∈ e E (v,e) End(v) → Z Thus a function f : E(Σ) is a ﬂow if and only if ∂f is identically zero. Z The set of all integral ﬂows on (Σ, ω) forms a -module, called the ﬂow lattice by Chen and Wang, who developed its basic theory in [?]. One can deﬁne ﬂows with values in an arbitrary abelian group, for example, the additive group of real numbers and ﬁnitely generated abelian groups. Many of the following remarks are applicable for such ﬂows. We omit the word “integral” when mentioning integral ﬂows. The theory of ﬂows on signed graphs depends essentially on the graph and the sign func- tion but not on the orientation, since only the notation changes when edges are reoriented. Speciﬁcally, a ﬂow f on Σ with respect to an orientation ω represents the same ﬂow on Σ as [ω, ρ]f on Σ with respect to another orientation ρ. (Therefore it is correct to speak of “ﬂows on signed graphs”.) → Z (cid:54) The support of a function f : E(Σ) is the set of edges e such that f(e) = 0; it is denoted by supp f. We denote by Σ(f) the subgraph of Σ whose edge set is supp f and whose vertex set consists of vertices incident with edges in supp f. The zero ﬂow is the ﬂow that is zero on all edges. Flows other than the zero ﬂow are referred to as nonzero ﬂows. A 8

label: paragraph

text: Proof.

text: Parts

text: (a)

text: and

text: are

text: by

text: deﬁnition

text: of

text: the

text: projection.

text: For

text: part

text: (c),

text: let

text: W

text: v

text: e

text: v

text: e

text: v

text: e

text: v

text: be

text: a

text: walk

text: in

text: Σ,

text: lifted

text: to

text: a

text: walk

text: W

text: n

text: n

text: e˜

text: vαn

text: in

text: Σ.

text: Since

text: σ(e

text: α

text: α

text: by

text: n

text: n

text: i

text: i

text: i

text: n

text: n

text: σ(W

text: σ(ei)

text: αi−1αi

text: Thus,

text: σ(W

text: if

text: and

text: only

text: if

text: α

text: α

text: It

text: follows

text: that

text: the

text: walk

text: W

text: is

text: closed

text: if

text: and

text: only

text: if

text: n

text: W

text: has

text: positive

text: sign.

text: Flows

text: The

text: incidence

text: matrix

text: of

text: an

text: orientedsigned

text: graph

text: (Σ,

text: ω)

text: is

text: the

text: V

text: E

text: matrix

text: M

text: Z

text: M(Σ,

text: ω)

text: [m(v,

text: e)],

text: m

text: is

text: a

text: function

text: m

text: V

text: E

text: deﬁned

text: by

text: ω(v,

text: e)

text: if

text: e

text: is

text: a

text: link,

text: m(v,

text: e)

text: ω(v,

text: e)

text: ω(v,

text: e)

text: if

text: e

text: is

text: a

text: negative

text: loop,

text: v

text: End(e)

text: otherwise.

text: When

text: e

text: is

text: a

text: loop

text: with

text: End(e)

text: v,

text: v

text: we

text: add

text: ω(v,

text: e)

text: for

text: each

text: end

text: of

text: e,

text: so

text: the

text: sum

text: is

text: when

text: e

text: is

text: a

text: positive

text: loop

text: and

text: is

text: ω(v,

text: e)

text: when

text: e

text: is

text: a

text: negative

text: loop.

text: Z

text: An

text: integral

text: ﬂow

text: on

text: an

text: oriented

text: signed

text: graph

text: (Σ,

text: ω)

text: is

text: a

text: function

text: f

text: E(Σ)

text: which

text: is

text: conservative

text: at

text: every

text: vertex,

text: meaning

text: that

text: the

text: net

text: contribution

text: to

text: each

text: vertex

text: is

text: zero.

text: The

text: Z

text: boundary

text: operator

text: of

text: (Σ,

text: ω),

text: E(Σ)

text: V

text: (Σ),

text: is

text: deﬁned

text: by

text: ∂f(v)

text: m(v,

text: e)f(e)

text: ω(v,

text: e)f(e).

text: e

text: E

text: (v,e)

text: End(v)

text: Z

text: Thus

text: a

text: function

text: f

text: E(Σ)

text: is

text: a

text: ﬂow

text: if

text: and

text: only

text: if

text: ∂f

text: is

text: identically

text: zero.

text: Z

text: The

text: set

text: of

text: all

text: integral

text: ﬂows

text: on

text: (Σ,

text: ω)

text: forms

text: a

text: -module,

text: called

text: the

text: ﬂow

text: lattice

text: by

text: Chen

text: and

text: Wang,

text: who

text: developed

text: its

text: basic

text: theory

text: in

text: One

text: can

text: deﬁne

text: ﬂows

text: with

text: values

text: in

text: an

text: arbitrary

text: abelian

text: group,

text: for

text: example,

text: the

text: additive

text: group

text: of

text: real

text: numbers

text: and

text: ﬁnitely

text: generated

text: abelian

text: groups.

text: Many

text: of

text: the

text: following

text: remarks

text: are

text: applicable

text: for

text: such

text: ﬂows.

text: We

text: omit

text: the

text: word

text: “integral”

text: when

text: mentioning

text: integral

text: ﬂows.

text: The

text: theory

text: of

text: ﬂows

text: on

text: signed

text: graphs

text: depends

text: essentially

text: on

text: the

text: graph

text: and

text: the

text: sign

text: func-

text: tion

text: but

text: not

text: on

text: the

text: orientation,

text: since

text: only

text: the

text: notation

text: changes

text: when

text: edges

text: are

text: reoriented.

text: Speciﬁcally,

text: a

text: ﬂow

text: f

text: on

text: Σ

text: with

text: respect

text: to

text: an

text: orientation

text: ω

text: represents

text: the

text: same

text: ﬂow

text: on

text: Σ

text: as

text: [ω,

text: ρ]f

text: on

text: Σ

text: with

text: respect

text: to

text: another

text: orientation

text: ρ.

text: (Therefore

text: it

text: is

text: correct

text: to

text: speak

text: of

text: “ﬂows

text: on

text: signed

text: graphs”.)

text: Z

text: The

text: support

text: of

text: a

text: function

text: f

text: E(Σ)

text: is

text: the

text: set

text: of

text: edges

text: e

text: such

text: that

text: f(e)

text: it

text: is

text: denoted

text: by

text: supp

text: f.

text: We

text: denote

text: by

text: Σ(f)

text: the

text: subgraph

text: of

text: Σ

text: whose

text: edge

text: set

text: is

text: supp

text: f

text: and

text: whose

text: vertex

text: set

text: consists

text: of

text: vertices

text: incident

text: with

text: edges

text: in

text: supp

text: f.

text: The

text: zero

text: ﬂow

text: is

text: the

text: ﬂow

text: that

text: is

text: zero

text: on

text: all

text: edges.

text: Flows

text: other

text: than

text: the

text: zero

text: ﬂow

text: are

text: referred

text: to

text: as

text: nonzero

text: ﬂows.

text: A


text: Classiﬁcation of Minimal Separating Sets in Low Genus Surfaces ∗ † ‡ § J. J. P. Veerman, William Maxwell, Victor Rielly, Austin K. Williams May 29, 2020 Abstract ⊂ \ Consider a surface S and let M S. If S M is not connected, then we say M separates S, and we refer to M as a separating set of S. If M separates S, and no proper subset of M separates S, then we say M is a minimal separating set of S. In this paper we use computational methods of combinatorial topology to classify the minimal separating sets of the orientable surfaces of genus g = 2 and g = 3. The classiﬁcation for genus 0 and 1 was done in earlier work, using methods of algebraic topology. Keywords: Combinatorial Topology, Graph Embeddings, Minimal Separating Sets, Rotation Systems. Surfaces and Separating Sets We begin with some basic deﬁnitions. Deﬁnition 1. When we say surface we are referring to a closed, connected, triangulated, orientable, 2-manifold. ⊂ Let S be a surface and let M S. \ Deﬁnition 2. If S M is not connected, then we say M separates S, and we refer to M as a separating set of S. Deﬁnition 3. If M separates S, and no proper subset of M separates S, then we say M is a minimal separating set of S. In this paper we will not consider pathological separating sets, such as the common boundary of the Lakes of Wada. To that end, when we refer to subsets of a surface it will be understood that we are referring to ﬁnitely triangulated subsets. Such subsets may be thought of as ﬁnite simplicial subcomplexes of the triangulated surface. Such sets occur naturally in the following geometric context. Let S be a connected compact surface whose distance d(., .) is inherited from a Riemannian metric. Given two distinct points p and q in S, the mediatrix is the set of points x such that d(x, q) = d(x, p). Brillouin zones were introduced by Brillouin in the 30s and play an important role in physics [1] and computational geometry [10]. Their boundaries are formed by pieces of of mediatrices[9]. Mediatrices also play an important role in the study of focal decomposition [6]. In [3] and [8] it is proved that mediatrices are closed simplicial 1-complexes. Vice versa, as we will argue in the concluding remarks of this paper, every minimal separating simplicial 1-complex can be realized as a mediatrix. In the cited papers, the topological classiﬁcation of minimally (triangulable) sets up to graph isomorphism was given for the (oriented) surfaces with genus 0 and 1. Namely, the 2-sphere admits only one minimal separating set (a simple, closed loop), and the torus admits 5 topologically distinct minimal separating sets. Here we carry out the classiﬁcation up to graph isomorphism for the (oriented) genus 2 and 3 surfaces. Our proofs diﬀer substantially from those in [3] and [8] where methods of algebraic topology were used. In this paper we use combinatorial topology and combine it with a substantial computational eﬀort to complete the classiﬁcation. ∗ Fariborz Maseeh Dept. of Math. and Stat., Portland State Univ., Portland, OR, USA; e-mail: veerman@pdx.edu † Fariborz Maseeh Dept. of Math. and Stat., Portland State Univ., Portland, OR, USA ‡ Fariborz Maseeh Dept. of Math. and Stat., Portland State Univ., Portland, OR, USA § Fariborz Maseeh Dept. of Math. and Stat., Portland State Univ., Portland, OR, USA 1 ##LTLine##

text: Classiﬁcation

label: title

text: of

text: Minimal

text: Separating

text: Sets

text: in

text: Low

text: Genus

text: Surfaces

label: author

text: J.

text: J.

text: P.

text: Veerman,

text: William

text: Maxwell,

text: Victor

text: Rielly,

text: Austin

text: K.

text: Williams

text: May

text: Abstract

label: abstract

text: Consider

text: a

text: surface

text: S

text: and

text: let

text: M

text: S.

text: If

text: S

text: M

text: is

text: not

text: connected,

text: then

text: we

text: say

text: M

text: separates

text: S,

text: and

text: we

text: refer

text: to

text: M

text: as

text: a

text: separating

text: set

text: of

text: S.

text: If

text: M

text: separates

text: S,

text: and

text: no

text: proper

text: subset

text: of

text: M

text: separates

text: S,

text: then

text: we

text: say

text: M

text: is

text: a

text: minimal

text: separating

text: set

text: of

text: S.

text: In

text: this

text: paper

text: we

text: use

text: computational

text: methods

text: of

text: combinatorial

text: topology

text: to

text: classify

text: the

text: minimal

text: separating

text: sets

text: of

text: the

text: orientable

text: surfaces

text: of

text: genus

text: g

text: and

text: g

text: The

text: classiﬁcation

text: for

text: genus

text: and

text: was

text: done

text: in

text: earlier

text: work,

text: using

text: methods

text: of

text: algebraic

text: topology.

text: Keywords:

text: Combinatorial

text: Topology,

text: Graph

text: Embeddings,

text: Minimal

text: Separating

text: Sets,

text: Rotation

text: Systems.

text: Surfaces

text: and

text: Separating

text: Sets

text: We

text: begin

text: with

text: some

text: basic

text: deﬁnitions.

text: Deﬁnition

text: When

text: we

text: say

text: surface

text: we

text: are

text: referring

text: to

text: a

text: closed,

text: connected,

text: triangulated,

text: orientable,

text: Let

text: S

text: be

text: a

text: surface

text: and

text: let

text: M

text: S.

text: Deﬁnition

text: If

text: S

text: M

text: is

text: not

text: connected,

text: then

text: we

text: say

text: M

text: separates

text: S,

text: and

text: we

text: refer

text: to

text: M

text: as

text: a

text: separating

text: set

text: of

text: S.

text: Deﬁnition

text: If

text: M

text: separates

text: S,

text: and

text: no

text: proper

text: subset

text: of

text: M

text: separates

text: S,

text: then

text: we

text: say

text: M

text: is

text: a

text: minimal

text: separating

text: set

text: of

text: S.

text: In

text: this

text: paper

text: we

text: will

text: not

text: consider

text: pathological

text: separating

text: sets,

text: such

text: as

text: the

text: common

text: boundary

text: of

text: the

text: Lakes

text: of

text: Wada.

text: To

text: that

text: end,

text: when

text: we

text: refer

text: to

text: subsets

text: of

text: a

text: surface

text: it

text: will

text: be

text: understood

text: that

text: we

text: are

text: referring

text: to

text: ﬁnitely

text: triangulated

text: subsets.

text: Such

text: subsets

text: may

text: be

text: thought

text: of

text: as

text: ﬁnite

text: simplicial

text: subcomplexes

text: of

text: the

text: triangulated

text: surface.

text: Such

text: sets

text: occur

text: naturally

text: in

text: the

text: following

text: geometric

text: context.

text: Let

text: S

text: be

text: a

text: connected

text: compact

text: surface

text: whose

text: distance

text: d(.,

text: is

text: inherited

text: from

text: a

text: Riemannian

text: metric.

text: Given

text: two

text: distinct

text: points

text: p

text: and

text: q

text: in

text: S,

text: the

text: mediatrix

text: is

text: the

text: set

text: of

text: points

text: x

text: such

text: that

text: d(x,

text: q)

text: d(x,

text: p).

text: Brillouin

text: zones

text: were

text: introduced

text: by

text: Brillouin

text: in

text: the

text: and

text: play

text: an

text: important

text: role

text: in

text: physics

text: and

text: computational

text: geometry

text: Their

text: boundaries

text: are

text: formed

text: by

text: pieces

text: of

text: of

text: Mediatrices

text: also

text: play

text: an

text: important

text: role

text: in

text: the

text: study

text: of

text: focal

text: decomposition

text: In

text: and

text: it

text: is

text: proved

text: that

text: mediatrices

text: are

text: closed

text: simplicial

text: Vice

text: versa,

text: as

text: we

text: will

text: argue

text: in

text: the

text: concluding

text: remarks

text: of

text: this

text: paper,

text: every

text: minimal

text: separating

text: simplicial

text: can

text: be

text: realized

text: as

text: a

text: mediatrix.

text: In

text: the

text: cited

text: papers,

text: the

text: topological

text: classiﬁcation

text: of

text: minimally

text: (triangulable)

text: sets

text: up

text: to

text: graph

text: isomorphism

text: was

text: given

text: for

text: the

text: (oriented)

text: surfaces

text: with

text: genus

text: and

text: Namely,

text: the

text: admits

text: only

text: one

text: minimal

text: separating

text: set

text: (a

text: simple,

text: closed

text: loop),

text: and

text: the

text: torus

text: admits

text: topologically

text: distinct

text: minimal

text: separating

text: sets.

text: Here

text: we

text: carry

text: out

text: the

text: classiﬁcation

text: up

text: to

text: graph

text: isomorphism

text: for

text: the

text: (oriented)

text: genus

text: and

text: surfaces.

text: Our

text: proofs

text: diﬀer

text: substantially

text: from

text: those

text: in

text: and

text: where

text: methods

text: of

text: algebraic

text: topology

text: were

text: used.

text: In

text: this

text: paper

text: we

text: use

text: combinatorial

text: topology

text: and

text: combine

text: it

text: with

text: a

text: substantial

text: computational

text: eﬀort

text: to

text: complete

text: the

text: classiﬁcation.

text: Fariborz

text: Maseeh

text: Dept.

text: of

text: Math.

text: and

text: Stat.,

text: Portland

text: State

text: Univ.,

text: Portland,

text: OR,

text: USA;

text: e-mail:

text: veerman@pdx.edu

text: Fariborz

text: Maseeh

text: Dept.

text: of

text: Math.

text: and

text: Stat.,

text: Portland

text: State

text: Univ.,

text: Portland,

text: OR,

text: USA

text: Fariborz

text: Maseeh

text: Dept.

text: of

text: Math.

text: and

text: Stat.,

text: Portland

text: State

text: Univ.,

text: Portland,

text: OR,

text: USA

text: Fariborz

text: Maseeh

text: Dept.

text: of

text: Math.

text: and

text: Stat.,

text: Portland

text: State

text: Univ.,

text: Portland,

text: OR,

text: USA

text: ##LTLine##


text: Table 2.3 # of Graph Rotation System (n , n ) # of Graph Rotation System (n , n ) 1 2 1 2 v : 0, 1, 2, 3 v : 0, 1, 2, 3 0 0 1 v : 0, 4, 4, 1 (1,4) 17 v : 0, 4, 5, 1 (1,2) 1 1 v : 2, 5, 5, 3 v : 2, 6, 7, 3, 4, 5, 6, 7 2 2 v : 0, 0, 1, 2 v : 0, 1, 2, 3 0 0 2 v : 1, 3, 3, 4 (2,3) 18 v : 0, 4, 5, 6, 7, 1 (1,2) 1 1 v : 2, 5, 5, 4 v : 2, 3, 4, 5, 6, 7 2 2 v : 0, 1, 2, 3 v : 0, 1, 2, 3 0 0 3 v : 4, 4, 5, 6 (2,2) 19 v : 0, 4, 5, 6, 4, 1 (1,2) 1 1 v : 0, 1, 2, 3, 5, 6 v : 2, 7, 6, 3, 7, 5 2 2 v : 0, 1, 2, 3 v : 0, 1, 2, 3 0 0 4 v : 0, 4, 4, 5 (1,3) 20 v : 0, 4, 5, 1, 4, 5 (1,2) 1 1 v : 1, 6, 3, 4, 2, 6, 5 v : 2, 6, 7, 3, 6, 7 2 2 v : 0, 1, 2, 3 v : 0, 2, 3, 1, 4, 5 0 0 5 v : 0, 4, 4, 1 (2,2) 21 v : 0, 6, 6, 1 (1,2) 1 1 v : 2, 5, 6, 3, 5, 6 v : 27, 5, 3, 7, 4 2 2 v : 0012 v : 0, 0, 1, 2 0 0 6 v : 3, 3, 4, 5 (1,3) 22 v : 3, 4, 5, 3, 4, 6 (1,2) 1 1 v : 1, 6, 4, 2, 6, 5 v : 1, 7, 5, 2, 7, 6 2 2 v : 0, 0, 1, 2 v : 0, 0, 1, 2 0 0 7 v : 1, 3, 3, 4 (1,3) 23 v : 1, 3, 4, 5, 3, 6 (1,2) 1 1 v : 2, 5, 6, 4, 5, 6 v : 2, 7, 4, 6, 7, 5 2 2 v : 0, 1, 2, 3 v : 0, 0, 1, 2 0 0 8 v : 4, 5, 6, 7 (1,2) 24 v : 1, 3, 4, 5, 3, 6 (1,2) 1 1 v : 0, 1, 2, 3, 4, 5, 6, 7 v : 2, 6, 7, 5, 6, 7 2 2 v : 0, 1, 2, 3 v : 0, 1, 2, 3 0 0 9 v : 4, 4, 5, 6 (1,2) 25 v : 4, 5, 6, 7 (1,1) 1 1 v : 0, 7, 2, 3, 5, 1, 7, 6 v : 0, 8, 2, 3, 4, 1, 6, 7, 8, 5 2 2 v : 0, 1, 2, 3 v : 0, 1, 2, 3 0 0 10 v : 4, 5, 6, 4, 5, 7 (1,2) 26 v : 4, 5, 6, 4, 7, 8 (1,1) 1 1 v : 0, 1, 2, 3, 6, 7 v : 0, 1, 2, 5, 7, 3, 6, 8 2 2 v : 0, 1, 2, 3 v : 0, 1, 2, 3 0 0 11 v : 0, 4, 5, 6 (1,2) 27 v : 4, 5, 6, 4, 5, 7 (1,1) 1 1 v : 1, 7, 3, 2, 5, 6, 7, 4 v : 0, 8, 2, 3, 6, 1, 8, 7 2 2 v : 0, 1, 2, 3 v : 0, 1, 2, 3 0 0 12 v : 0, 4, 4, 5 (1,2) 28 v : 0, 4, 5, 6 (1,1) 1 1 v : 1, 6, 7, 2, 3, 5, 6, 7 v : 1, 7, 8, 2, 3, 4, 5, 6, 7, 8 2 2 v : 0, 1, 2, 3 v : 0, 1, 2, 3 0 0 13 v : 0, 4, 5, 6, 4, 7 (1,2) 29 v : 0, 4, 5, 6, 7, 8 (1,1) 1 1 v : 1, 2, 3, 6, 5, 7 v : 1, 2, 3, 4, 5, 6, 7, 8 2 2 v : 0, 1, 2, 3 v : 0, 1, 2, 3 0 0 14 v : 0, 4, 5, 6, 4, 5 (1,2) 30 v : 0, 4, 5, 6, 4, 7 (1,1) 1 1 v : 1, 7, 3, 2, 7, 6 v : 1, 8, 3, 6, 8, 2, 5, 7 2 2 v : 0, 1, 2, 3 v : 0, 1, 2, 3 0 0 15 v : 0, 4, 5, 6, 4, 7, 6, 5 (1,2) 31 v : 0, 4, 5, 6, 4, 5 (1,1) 1 1 v : 1, 2, 3, 7 v : 1, 7, 8, 2, 3, 6, 7, 8 2 2 v : 0, 1, 2, 3, 4, 5 v : 0, 1, 2, 3 0 0 16 v : 0, 6, 6, 7 (1,2) 32 v : 0, 4, 6, 7, 8, 4, 5 (1,1) 1 1 v : 1, 2, 3, 4, 5, 7 v : 1, 2, 3, 6, 7, 8 2 2 17 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Table

label: table

text: of

text: Graph

text: Rotation

text: System

text: (n

text: n

text: of

text: Graph

text: Rotation

text: System

text: (n

text: n

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Table 2.4 continued # of Graph Rotation System (n , n ) # of Graph Rotation System (n , n ) 1 2 1 2 v : 0, 1, 2, 3 v : 0, 1, 2, 3 0 0 v : 0, 4, 5, 6 v : 0, 4, 5, 6, 4, 7 49 1 (1,1) 52 1 (1,1) v : 1, 7, 8, 4, 5, 9 v : 1, 8, 5, 9, 8, 6 2 2 v : 2, 3, 6, 7, 8, 9 v : 2, 3, 7, 9 3 3 v : 0, 1, 2, 3 v : 0, 1, 2, 3 0 0 v : 0, 4, 5, 6 v : 0, 4, 5, 6, 4, 5 50 1 (1,1) 53 1 (1,1) v : 1, 7, 5, 8, 7, 4 v : 1, 7, 8, 9, 7, 8 2 2 v : 2, 9, 6, 3, 9, 8 v : 2, 3, 6, 9 3 3 v : 0, 1, 2, 3 0 v : 0, 4, 5, 6, 7, 8 51 1 (1,1) v : 1, 4, 5, 6, 7, 9 2 v : 2, 3, 8, 9 3 21 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Table

text: continued

text: of

text: Graph

text: Rotation

text: System

text: (n

text: n

text: of

text: Graph

text: Rotation

text: System

text: (n

text: n

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Table 2.5 # of Graph Rotation System (n , n ) # of Graph Rotation System (n , n ) 1 2 1 2 v : 0, 1, 2, 3 v : 0, 1, 2, 3 0 0 v : 4, 5, 6, 7 v : 4, 4, 5, 6 1 1 1 v : 4, 8, 8, 9 (1,2) 10 v : 0, 7, 8, 5 (1,2) 2 2 v : 0, 9, 5, 6 v : 1, 7, 9, 6 3 3 v : 1, 2, 3, 7 v : 2, 3, 9, 8 4 4 v : 0, 1, 2, 3 v : 0, 1, 2, 3 0 0 v : 4, 5, 6, 7 v : 0, 4, 5, 6 1 1 2 v : 4, 8, 8, 9 (1,2) 11 v : 1, 7, 8, 4 (1,2) 2 2 v : 0, 5, 6, 7 v : 2, 5, 9, 7 3 3 v : 1, 2, 3, 9 v : 3, 6, 9, 8 4 4 v : 0, 1, 2, 3 v : 0, 1, 2, 3 0 0 v : 4, 5, 6, 7 v : 4, 5, 6, 7 1 1 3 v : 4, 8, 9, 5 (1,2) 12 v : 4, 8, 9, 10 (1,1) 2 2 v : 0, 8, 9, 6 v : 0, 8, 9, 10 3 3 v : 1, 2, 3, 7 v : 1, 2, 3, 5, 6, 7 4 4 v : 0, 1, 2, 3 v : 0, 1, 2, 3 0 0 v : 4, 5, 6, 7 v : 4, 5, 6, 7 1 1 4 v : 4, 5, 6, 8 (1,2) 13 v : 4, 8, 9, 10 (1,1) 2 2 v : 0, 9, 7, 8 v : 0, 5, 8, 9 3 3 v : 1, 2, 3, 9 v : 1, 2, 3, 6, 7, 10 4 4 v : 0, 2, 1, 3 v : 0, 1, 2, 3 0 0 v : 4, 6, 5, 7 v : 4, 5, 6, 7 1 1 5 v : 4, 8, 8, 9 (1,2) 14 v : 4, 8, 9, 10 (1,1) 2 2 v : 0, 5, 1, 9 v : 0, 8, 5, 6, 9, 10 3 3 v : 2, 6, 3, 7 v : 1, 2, 3, 7 4 4 v : 0, 2, 1, 3 v : 0, 1, 2, 3 0 0 v : 4, 6, 5, 7 v : 4, 5, 6, 7 1 1 6 v : 4, 8, 5, 9 (1,2) 15 v : 4, 8, 9, 10, 8, 9 (1,1) 2 2 v : 0, 8, 1, 9 v : 0, 10, 5, 6 3 3 v : 2, 6, 3, 7 v : 1, 2, 3, 7 4 4 v : 0, 1, 2, 3 v : 0, 1, 2, 3 0 0 v : 4, 5, 6, 7 v : 4, 5, 6, 7 1 1 7 v : 4, 5, 8, 9 (1,2) 16 v : 4, 8, 9, 10, 8, 9 (1,1) 2 2 v : 0, 1, 6, 8 v : 0, 5, 6, 7 3 3 v : 2, 3, 9, 7 v : 1, 2, 3, 10 4 4 v : 0, 1, 2, 3 v : 0, 1, 2, 3 0 0 v : 4, 5, 6, 7 v : 4, 6, 5, 7 1 1 8 v : 0, 8, 9, 4 (1,2) 17 v : 4, 8, 5, 9 (1,1) 2 2 v : 1, 5, 6, 8 v : 0, 8, 10, 9 3 3 v : 2, 3, 7, 9 v : 1, 2, 3, 7, 10, 6 4 4 v : 0, 1, 2, 3 v : 0, 1, 2, 3 0 0 v : 4, 5, 6, 7 v : 4, 5, 6, 7 1 1 9 v : 0, 8, 8, 4 (1,2) 18 v : 4, 5, 8, 9 (1,1) 2 2 v : 1, 5, 6, 9 v : 0, 10, 6, 8 3 3 v : 2, 3, 7, 9 v : 1, 2, 3, 10, 7, 9 4 4 22 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Table

text: of

text: Graph

text: Rotation

text: System

text: (n

text: n

text: of

text: Graph

text: Rotation

text: System

text: (n

text: n

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: v

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 2. The embedding has exactly two regions. 3. The image of each edge is in the boundary of both regions of the embedding. Proof. Suppose φ is a minimal separating embedding of G into S. Condition 1 is immediate. Lemmas 1 and 2 demonstrate conditions 2 and 3, respectively. So the forward direction is proved. Now suppose φ is an embedding of G into S that satisﬁes the three conditions. Since condition 2 is satisﬁed, ∈ we know φ[G] separates S. To show that φ[G] is a minimal separating set, let x φ[G]. Condition 1 implies that ∈ ∈ x φ[e] for some e V . By condition 3 we know that x is in the boundary of both regions of the embedding. \ \ { } It follows that S (φ[G] x ) is connected. | | − | | ≤ Lemma 3. Suppose φ is a minimal separating embedding of G into S. Then E V 2g where g is the genus of S. | | − | | ≥ − | | − | | ≤ Proof. By Euler’s theorem and lemma 1, V E + 2 2 2g. Thus E V 2g as desired. Deﬁnition 20. A graph homeomorphic to the graph consisting of one vertex with degree 2 and one edge (the cycle on one vertex) is called an isolated loop. ∈ G Lemma 4. For all g, and for all G , if v is a vertex of G and deg(v) = 2, then v is an isolated loop. g ≥ ∈ G Proof. Suppose g 0, and that G . Let v be a vertex of G such that deg(v) = 2, and suppose that v g is not an isolated loop. Then v is incident to precisely two edges, and so v can be smoothed. Thus G is not ∈ G homeomorphically irreducible. Hence G / . g ∈ G Lemma 5. If G , then by Lemma all vertices of G have even degree. Proof. Let v be a vertex and consider a neighborhood around φ(v). The edge-ends emanating from v divide the neighborhood into deg(v) subdivisions. By Lemma 1, there are exactly 2 regions of φ and each of these subdivisions must be a subset of exactly one of the two regions. By Lemma 2, each of the edge ends must be in the boundary of both regions. If deg(v) were odd then there would exist an edge end emanating from v that was in the boundary of only one of the two regions. Hence deg(v) is not odd. ∅ In what follows we denote the set of isolated loops of a graph G by B. If G has no isolated loops then B = . \ The graph G minus the isolated loops is denoted by G B, and its set of vertices and set of edges are denoted \ \ | | by V (G B) and E(G B), respectively. The number of components of B will be denoted by B . ≥ ∈ G | \ | ≤ | \ | Lemma 6. For all g 0, and for all G , 2 V (G B) E(G B) . g ≥ ∈ G (cid:104)(cid:80) (cid:105) Proof. Let g 0, and let G . Let B be the set of isolated loops of G. By Lemmas 4 and 5, and the g ≥ observation that minimal separating graphs do not contain vertices of degree zero, we have that deg(v) 4 for ∈ \ | \ | | | ≤ | | | \ | | | all v V (G B). Thus we have 4 V (G B) + 2 B ∈ \ deg(v) + 2 B = 2 E(G B) + 2 B . Thus | \ | ≤ | \ | v V B 2 V (G B) E(G B) . ∈ G \ Lemma 7. Let B be the set of isolated loops of a graph G . Either the graph G B is empty or it is a − | | | g| minimal separating graph of a surface of genus g B , where B is the number of components of B. Proof. Suppose G is a minimal separating graph for a surface S of genus g, and let φ be a minimal separating \ embedding of G into S. It will suﬃce to show that if L is any isolated loop of G, and G L is not empty, then \ − there exists an embedding of G L into a surface of genus g 1. Let L be any isolated loop of G. Either φ[L] is simple (ie contractible to a point), or it is not. If φ[L] is \ contractible to a point, then L separates S, and it follows that G L is empty. \ Suppose G L is not empty. Then φ[L] is not simple. So φ[L] must circumnavigate a handle of S. We will \ − construct a minimal separating embedding of the graph G L into a surface of genus g 1 using surgery. Note that φ satisﬁes the three conditions of theorem 1. A closed neighborhood of φ[L] is a cylinder C. Remove C from S. Since the Euler characteristic of a cylinder is zero, we have χ = χ \ . Note that by S S C condition 3 of theorem 1, this has the result of creating exactly two boundary components (one in each region of Sφ[G]. Glue one disk into each of the two components. Gluing in a disk adds 1 to the characteristic of the \ − surface. What remains is an embedding of the graph G L into a surface of surface of genus g 1. Note that this embedding is a minimal separating embedding because it satisﬁes the three requirements of theorem 1 – for it inherited these properties from φ. 4 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: list

text: The

text: embedding

text: has

text: exactly

text: two

text: regions.

text: The

text: image

text: of

text: each

text: edge

text: is

text: in

text: the

text: boundary

text: of

text: both

text: regions

text: of

text: the

text: embedding.

text: Proof.

text: Suppose

text: φ

text: is

text: a

text: minimal

text: separating

text: embedding

text: of

text: G

text: into

text: S.

text: Condition

text: is

text: immediate.

text: Lemmas

text: and

text: demonstrate

text: conditions

text: and

text: respectively.

text: So

text: the

text: forward

text: direction

text: is

text: proved.

text: Now

text: suppose

text: φ

text: is

text: an

text: embedding

text: of

text: G

text: into

text: S

text: that

text: satisﬁes

text: the

text: three

text: conditions.

text: Since

text: condition

text: is

text: satisﬁed,

text: we

text: know

text: φ[G]

text: separates

text: S.

text: To

text: show

text: that

text: φ[G]

text: is

text: a

text: minimal

text: separating

text: set,

text: let

text: x

text: φ[G].

text: Condition

text: implies

text: that

text: x

text: φ[e]

text: for

text: some

text: e

text: V

text: By

text: condition

text: we

text: know

text: that

text: x

text: is

text: in

text: the

text: boundary

text: of

text: both

text: regions

text: of

text: the

text: embedding.

text: It

text: follows

text: that

text: S

text: (φ[G]

text: x

text: is

text: connected.

text: Lemma

text: Suppose

text: φ

text: is

text: a

text: minimal

text: separating

text: embedding

text: of

text: G

text: into

text: S.

text: Then

text: E

text: V

text: where

text: g

text: is

text: the

text: genus

text: of

text: S.

text: Proof.

text: By

text: Euler’s

text: theorem

text: and

text: lemma

text: V

text: E

text: Thus

text: E

text: V

text: as

text: desired.

text: Deﬁnition

text: A

text: graph

text: homeomorphic

text: to

text: the

text: graph

text: consisting

text: of

text: one

text: vertex

text: with

text: degree

text: and

text: one

text: edge

text: (the

text: cycle

text: on

text: one

text: vertex)

text: is

text: called

text: an

text: isolated

text: loop.

text: G

text: Lemma

text: For

text: all

text: g,

text: and

text: for

text: all

text: G

text: if

text: v

text: is

text: a

text: vertex

text: of

text: G

text: and

text: deg(v)

text: then

text: v

text: is

text: an

text: isolated

text: loop.

text: g

text: G

text: Proof.

text: Suppose

text: g

text: and

text: that

text: G

text: Let

text: v

text: be

text: a

text: vertex

text: of

text: G

text: such

text: that

text: deg(v)

text: and

text: suppose

text: that

text: v

text: g

text: is

text: not

text: an

text: isolated

text: loop.

text: Then

text: v

text: is

text: incident

text: to

text: precisely

text: two

text: edges,

text: and

text: so

text: v

text: can

text: be

text: smoothed.

text: Thus

text: G

text: is

text: not

text: G

text: homeomorphically

text: irreducible.

text: Hence

text: G

text: g

text: G

text: Lemma

text: If

text: G

text: then

text: by

text: Lemma

text: all

text: vertices

text: of

text: G

text: have

text: even

text: degree.

text: Proof.

text: Let

text: v

text: be

text: a

text: vertex

text: and

text: consider

text: a

text: neighborhood

text: around

text: φ(v).

text: The

text: edge-ends

text: emanating

text: from

text: v

text: divide

text: the

text: neighborhood

text: into

text: deg(v)

text: subdivisions.

text: By

text: Lemma

text: there

text: are

text: exactly

text: regions

text: of

text: φ

text: and

text: each

text: of

text: these

text: subdivisions

text: must

text: be

text: a

text: subset

text: of

text: exactly

text: one

text: of

text: the

text: two

text: regions.

text: By

text: Lemma

text: each

text: of

text: the

text: edge

text: ends

text: must

text: be

text: in

text: the

text: boundary

text: of

text: both

text: regions.

text: If

text: deg(v)

text: were

text: odd

text: then

text: there

text: would

text: exist

text: an

text: edge

text: end

text: emanating

text: from

text: v

text: that

text: was

text: in

text: the

text: boundary

text: of

text: only

text: one

text: of

text: the

text: two

text: regions.

text: Hence

text: deg(v)

text: is

text: not

text: odd.

text: In

text: what

text: follows

text: we

text: denote

text: the

text: set

text: of

text: isolated

text: loops

text: of

text: a

text: graph

text: G

text: by

text: B.

text: If

text: G

text: has

text: no

text: isolated

text: loops

text: then

text: B

text: The

text: graph

text: G

text: minus

text: the

text: isolated

text: loops

text: is

text: denoted

text: by

text: G

text: B,

text: and

text: its

text: set

text: of

text: vertices

text: and

text: set

text: of

text: edges

text: are

text: denoted

text: by

text: V

text: (G

text: B)

text: and

text: E(G

text: B),

text: respectively.

text: The

text: number

text: of

text: components

text: of

text: B

text: will

text: be

text: denoted

text: by

text: B

text: G

text: Lemma

text: For

text: all

text: g

text: and

text: for

text: all

text: G

text: V

text: (G

text: B)

text: E(G

text: B)

text: g

text: G

text: Proof.

text: Let

text: g

text: and

text: let

text: G

text: Let

text: B

text: be

text: the

text: set

text: of

text: isolated

text: loops

text: of

text: G.

text: By

text: Lemmas

text: and

text: and

text: the

text: g

text: observation

text: that

text: minimal

text: separating

text: graphs

text: do

text: not

text: contain

text: vertices

text: of

text: degree

text: zero,

text: we

text: have

text: that

text: deg(v)

text: for

text: all

text: v

text: V

text: (G

text: B).

text: Thus

text: we

text: have

text: V

text: (G

text: B)

text: B

text: deg(v)

text: B

text: E(G

text: B)

text: B

text: Thus

text: v

text: V

text: B

text: V

text: (G

text: B)

text: E(G

text: B)

text: G

text: Lemma

text: Let

text: B

text: be

text: the

text: set

text: of

text: isolated

text: loops

text: of

text: a

text: graph

text: G

text: Either

text: the

text: graph

text: G

text: B

text: is

text: empty

text: or

text: it

text: is

text: a

text: g|

text: minimal

text: separating

text: graph

text: of

text: a

text: surface

text: of

text: genus

text: g

text: B

text: where

text: B

text: is

text: the

text: number

text: of

text: components

text: of

text: B.

text: Proof.

text: Suppose

text: G

text: is

text: a

text: minimal

text: separating

text: graph

text: for

text: a

text: surface

text: S

text: of

text: genus

text: g,

text: and

text: let

text: φ

text: be

text: a

text: minimal

text: separating

text: embedding

text: of

text: G

text: into

text: S.

text: It

text: will

text: suﬃce

text: to

text: show

text: that

text: if

text: L

text: is

text: any

text: isolated

text: loop

text: of

text: G,

text: and

text: G

text: L

text: is

text: not

text: empty,

text: then

text: there

text: exists

text: an

text: embedding

text: of

text: G

text: L

text: into

text: a

text: surface

text: of

text: genus

text: g

text: Let

text: L

text: be

text: any

text: isolated

text: loop

text: of

text: G.

text: Either

text: φ[L]

text: is

text: simple

text: (ie

text: contractible

text: to

text: a

text: point),

text: or

text: it

text: is

text: not.

text: If

text: φ[L]

text: is

text: contractible

text: to

text: a

text: point,

text: then

text: L

text: separates

text: S,

text: and

text: it

text: follows

text: that

text: G

text: L

text: is

text: empty.

text: Suppose

text: G

text: L

text: is

text: not

text: empty.

text: Then

text: φ[L]

text: is

text: not

text: simple.

text: So

text: φ[L]

text: must

text: circumnavigate

text: a

text: handle

text: of

text: S.

text: We

text: will

text: construct

text: a

text: minimal

text: separating

text: embedding

text: of

text: the

text: graph

text: G

text: L

text: into

text: a

text: surface

text: of

text: genus

text: g

text: using

text: surgery.

text: Note

text: that

text: φ

text: satisﬁes

text: the

text: three

text: conditions

text: of

text: theorem

text: A

text: closed

text: neighborhood

text: of

text: φ[L]

text: is

text: a

text: cylinder

text: C.

text: Remove

text: C

text: from

text: S.

text: Since

text: the

text: Euler

text: characteristic

text: of

text: a

text: cylinder

text: is

text: zero,

text: we

text: have

text: χ

text: χ

text: Note

text: that

text: by

text: S

text: S

text: C

text: condition

text: of

text: theorem

text: this

text: has

text: the

text: result

text: of

text: creating

text: exactly

text: two

text: boundary

text: components

text: (one

text: in

text: each

text: region

text: of

text: Sφ[G].

text: Glue

text: one

text: disk

text: into

text: each

text: of

text: the

text: two

text: components.

text: Gluing

text: in

text: a

text: disk

text: adds

text: to

text: the

text: characteristic

text: of

text: the

text: surface.

text: What

text: remains

text: is

text: an

text: embedding

text: of

text: the

text: graph

text: G

text: L

text: into

text: a

text: surface

text: of

text: surface

text: of

text: genus

text: g

text: Note

text: that

text: this

text: embedding

text: is

text: a

text: minimal

text: separating

text: embedding

text: because

text: it

text: satisﬁes

text: the

text: three

text: requirements

text: of

text: theorem

text: for

text: it

text: inherited

text: these

text: properties

text: from

text: φ.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Proof. By Lemma 5, p is even iﬀ k is even. We show that p is even. ∈ In the embedding edge a must separate a boundary component b B from a boundary component ∈ 1 1 b B . Orient edge a and travel with the orientation along a. The boundary component at your right side 2 2 (with respect to the orientation) must always point towards the same component. It follows that the corner (x , a) corresponds to the same boundary component as the corner (a, x ). The same is true for the other k p+1 two corners involving edge ends of a. Since the corners belonging to boundary component in B must alternate 1 with those belonging to B , we conclude that p is even. 2 G R Theorem 5. A graph G is in for some g if and only if there exists a two-sided rotation system on G ≥ | |−| | − g such that g E V +n1+n2 1 (where n and n are the numbers of boundary components corresponding to 2 1 2 R regions 1 and 2 of the reduced band decomposition corresponding to ). G R Proof. G is in if and only if there exists a two-sided rotation system by theorem 4. Equivalently the g D embedding in the surface S with genus g admits a reduced band decomposition with n bordering on the \D 1 component A of S and n boundary components bordering of the component A . Each of these components 1 2 2 A has itself genus g . i i The genus of S is the genus of the connected sum in Equation 2 in the proof of theorem 4. Thus χ = − − S χ(A ) + χ(A ) + χ(D). Since the characteristic of an n-punctured surface of genus g equals 2 2g n , we 1 2 i i i have − − − − | | − | | χ = 2 2g n + 2 2g n + V E (3) S 1 1 2 2 Solving for the genus g of S gives: S | | − | | E V + n + n − g = 1 2 1 + g + g (4) S 2 1 2 Clearly g is minimized when g = g = 0. 1 2 Deﬁnition 29. The minimally separating embedding of G is irreducible if equality holds in Theorem 5 holds (ie if g = g(cid:83)= 0 in Equation 4. 1 2 ∈ G Lemma 12. If G consists of two disjoint nonempty subgraphs G and G we have each of the subgraphs as G g elements of g(cid:48)<g g(cid:48). Proof. It is suﬃcient to prove the lemma for G. Suppose G embeds as a minimal separating set in the surface S. | | Denote the quantities corresponding to the disjoint subgraphs by underbars and overbars, ie E is the number of edges in G and so forth. Let C be a closed neighborhood of φ[G]. Then φ restricted to C satisﬁes theorem 1. Remove C from S. Let A and A be the n and n punctured spheres. We denote by S the connected sum 1 2 1 2 S = C#A #A 1 2 The genus of this surface according to equation 4 equals | | − | | E V + n + n − g = 1 2 1 S 2 By the same reasoning the genus of the original surface S equals | | − | | E V + n + n − g = 1 2 1 + g + g S 2 1 2 | | − | | | | − | | E V + n + n + E V + n + n − = 1 2 1 2 1 + g + g 2 1 2 | | − | | ≥ ≥ Lemma 4 implies that E V 0 and lemma 2 that n and n are at least 1. Thus g g + 1. 1 2 S S Lemma 13. If G and G have least separated genus g and g, respectively, then their disjoint union has least separated genus g + g + 1 8 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Proof.

text: By

text: Lemma

text: p

text: is

text: even

text: iﬀ

text: k

text: is

text: even.

text: We

text: show

text: that

text: p

text: is

text: even.

text: In

text: the

text: embedding

text: edge

text: a

text: must

text: separate

text: a

text: boundary

text: component

text: b

text: B

text: from

text: a

text: boundary

text: component

text: b

text: B

text: Orient

text: edge

text: a

text: and

text: travel

text: with

text: the

text: orientation

text: along

text: a.

text: The

text: boundary

text: component

text: at

text: your

text: right

text: side

text: (with

text: respect

text: to

text: the

text: orientation)

text: must

text: always

text: point

text: towards

text: the

text: same

text: component.

text: It

text: follows

text: that

text: the

text: corner

text: (x

text: a)

text: corresponds

text: to

text: the

text: same

text: boundary

text: component

text: as

text: the

text: corner

text: (a,

text: x

text: The

text: same

text: is

text: true

text: for

text: the

text: other

text: k

text: two

text: corners

text: involving

text: edge

text: ends

text: of

text: a.

text: Since

text: the

text: corners

text: belonging

text: to

text: boundary

text: component

text: in

text: B

text: must

text: alternate

text: with

text: those

text: belonging

text: to

text: B

text: we

text: conclude

text: that

text: p

text: is

text: even.

text: G

text: R

text: Theorem

text: A

text: graph

text: G

text: is

text: in

text: for

text: some

text: g

text: if

text: and

text: only

text: if

text: there

text: exists

text: a

text: two-sided

text: rotation

text: system

text: on

text: G

text: g

text: such

text: that

text: g

text: E

text: V

text: (where

text: n

text: and

text: n

text: are

text: the

text: numbers

text: of

text: boundary

text: components

text: corresponding

text: to

text: R

text: regions

text: and

text: of

text: the

text: reduced

text: band

text: decomposition

text: corresponding

text: to

text: G

text: R

text: Proof.

text: G

text: is

text: in

text: if

text: and

text: only

text: if

text: there

text: exists

text: a

text: two-sided

text: rotation

text: system

text: by

text: theorem

text: Equivalently

text: the

text: g

text: D

text: embedding

text: in

text: the

text: surface

text: S

text: with

text: genus

text: g

text: admits

text: a

text: reduced

text: band

text: decomposition

text: with

text: n

text: bordering

text: on

text: the

text: \D

text: component

text: A

text: of

text: S

text: and

text: n

text: boundary

text: components

text: bordering

text: of

text: the

text: component

text: A

text: Each

text: of

text: these

text: components

text: A

text: has

text: itself

text: genus

text: g

text: i

text: i

text: The

text: genus

text: of

text: S

text: is

text: the

text: genus

text: of

text: the

text: connected

text: sum

text: in

text: Equation

text: in

text: the

text: proof

text: of

text: theorem

text: Thus

text: χ

text: S

text: χ(A

text: χ(A

text: χ(D).

text: Since

text: the

text: characteristic

text: of

text: an

text: n-punctured

text: surface

text: of

text: genus

text: g

text: equals

text: n

text: we

text: i

text: i

text: i

text: have

text: χ

text: n

text: n

text: V

text: E

text: S

text: Solving

text: for

text: the

text: genus

text: g

text: of

text: S

text: gives:

text: S

text: E

text: V

text: n

text: n

text: g

text: g

text: g

text: S

text: Clearly

text: g

text: is

text: minimized

text: when

text: g

text: g

text: Deﬁnition

text: The

text: minimally

text: separating

text: embedding

text: of

text: G

text: is

text: irreducible

text: if

text: equality

text: holds

text: in

text: Theorem

text: holds

text: (ie

text: if

text: g

text: in

text: Equation

text: G

text: Lemma

text: If

text: G

text: consists

text: of

text: two

text: disjoint

text: nonempty

text: subgraphs

text: G

text: and

text: G

text: we

text: have

text: each

text: of

text: the

text: subgraphs

text: as

text: G

text: g

text: elements

text: of

text: Proof.

text: It

text: is

text: suﬃcient

text: to

text: prove

text: the

text: lemma

text: for

text: G.

text: Suppose

text: G

text: embeds

text: as

text: a

text: minimal

text: separating

text: set

text: in

text: the

text: surface

text: S.

text: Denote

text: the

text: quantities

text: corresponding

text: to

text: the

text: disjoint

text: subgraphs

text: by

text: underbars

text: and

text: overbars,

text: ie

text: E

text: is

text: the

text: number

text: of

text: edges

text: in

text: G

text: and

text: so

text: forth.

text: Let

text: C

text: be

text: a

text: closed

text: neighborhood

text: of

text: φ[G].

text: Then

text: φ

text: restricted

text: to

text: C

text: satisﬁes

text: theorem

text: Remove

text: C

text: from

text: S.

text: Let

text: A

text: and

text: A

text: be

text: the

text: n

text: and

text: n

text: punctured

text: spheres.

text: We

text: denote

text: by

text: S

text: the

text: connected

text: sum

text: S

text: C#A

text: #A

text: The

text: genus

text: of

text: this

text: surface

text: according

text: to

text: equation

text: equals

text: E

text: V

text: n

text: n

text: g

text: S

text: By

text: the

text: same

text: reasoning

text: the

text: genus

text: of

text: the

text: original

text: surface

text: S

text: equals

text: E

text: V

text: n

text: n

text: g

text: g

text: g

text: S

text: E

text: V

text: n

text: n

text: E

text: V

text: n

text: n

text: g

text: g

text: Lemma

text: implies

text: that

text: E

text: V

text: and

text: lemma

text: that

text: n

text: and

text: n

text: are

text: at

text: least

text: Thus

text: g

text: g

text: S

text: S

text: Lemma

text: If

text: G

text: and

text: G

text: have

text: least

text: separated

text: genus

text: g

text: and

text: g,

text: respectively,

text: then

text: their

text: disjoint

text: union

text: has

text: least

text: separated

text: genus

text: g

text: g

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: R Proof. Let be the rotation system for G that minimizes the number of boundary walks n + n . The least 1 2 separated genus g satisﬁes: | | − | | E V + n + n − g = 1 2 1 2 The same holds for G. The rotation system for the disjoint union of G and G, is the union of their two rotation R R ∪ R R R R systems = . The boundary walks of are exactly the union those of in and those in . Therefore R the minimum number of boundary walks in equals n + n + n + n . And thus the least separated genus g 1 2 1 2 of G satisﬁes: | | − | | | | − | | E V + n + n + E V + n + n − g = 1 2 1 2 1 2 which implies the result. The Results Given a genus g, we compute three sets associated with it. I { } = Connected graphs whose least separated genus equals g g L { } = Graphs whose least separated genus equals g g G { } = Graphs that have a minimal separating embedding in genus g g |I | |I | Proposition 1. We have: = 17 and = 161. 2 3 Proof. This count was computer generated. The counting program follows the following steps. C 1. Generate the ﬁnite set of connected graphs in of candidate graphs for genus g (see deﬁnition 21, it is g important to note that condition 5 is computationally expensive so a weaker version is used which looks for non-intersecting loops instead of non-intersecting cycles.). C 2. For each connected graph G in generate the ﬁnite set of rotation systems of G satisfying Lemma 11 g up to cyclic permutation. | |−| | − 3. For each rotation system found in step 2, check whether it is two-sided and satisﬁes g = E V +n1+n2 1 2 (see theorem 5). I The graph G of step 2 is in if and only if any rotation system tests aﬃrmatively in step 3 (and did not g appear in a surface with lower genus). We keep a running list of the graphs G that pass the test, as well as the successful rotation systems. In genus 2, we determine all rotation systems that pass the test (see the table at the end of the article). In genus 3, we stop if we have 1 successful rotation system for a graph. Using the computer-generated count and some combinatorics yields the main result. I L G ≤ Theorem 6. The cardinalities of , , and for g 3 are as follows. g g g I L G Genus g g g 0 1 1 1 1 3 4 5 2 17 21 26 3 161 191 217 { } { } { } Remark: At the date of this writing, none of the integer sequences 1, 3, 17, 161 , 1, 4, 21, 191 , or 1, 5, 26, 217 are listed in the Online Encyclopedia of Integer Sequences [12]. 9 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: R

text: Proof.

text: Let

text: be

text: the

text: rotation

text: system

text: for

text: G

text: that

text: minimizes

text: the

text: number

text: of

text: boundary

text: walks

text: n

text: n

text: The

text: least

text: separated

text: genus

text: g

text: satisﬁes:

text: E

text: V

text: n

text: n

text: g

text: The

text: same

text: holds

text: for

text: G.

text: The

text: rotation

text: system

text: for

text: the

text: disjoint

text: union

text: of

text: G

text: and

text: G,

text: is

text: the

text: union

text: of

text: their

text: two

text: rotation

text: R

text: R

text: R

text: R

text: R

text: R

text: systems

text: The

text: boundary

text: walks

text: of

text: are

text: exactly

text: the

text: union

text: those

text: of

text: in

text: and

text: those

text: in

text: Therefore

text: R

text: the

text: minimum

text: number

text: of

text: boundary

text: walks

text: in

text: equals

text: n

text: n

text: n

text: n

text: And

text: thus

text: the

text: least

text: separated

text: genus

text: g

text: of

text: G

text: satisﬁes:

text: E

text: V

text: n

text: n

text: E

text: V

text: n

text: n

text: g

text: which

text: implies

text: the

text: result.

text: The

text: Results

text: Given

text: a

text: genus

text: g,

text: we

text: compute

text: three

text: sets

text: associated

text: with

text: it.

text: I

text: Connected

text: graphs

text: whose

text: least

text: separated

text: genus

text: equals

text: g

text: g

text: L

text: Graphs

text: whose

text: least

text: separated

text: genus

text: equals

text: g

text: g

text: G

text: Graphs

text: that

text: have

text: a

text: minimal

text: separating

text: embedding

text: in

text: genus

text: g

text: g

text: |I

text: |I

text: Proposition

text: We

text: have:

text: and

text: Proof.

text: This

text: count

text: was

text: computer

text: generated.

text: The

text: counting

text: program

text: follows

text: the

text: following

text: steps.

text: C

text: Generate

text: the

text: ﬁnite

text: set

text: of

text: connected

text: graphs

text: in

text: of

text: candidate

text: graphs

text: for

text: genus

text: g

text: (see

text: deﬁnition

text: it

text: is

text: g

text: important

text: to

text: note

text: that

text: condition

text: is

text: computationally

text: expensive

text: so

text: a

text: weaker

text: version

text: is

text: used

text: which

text: looks

text: for

text: non-intersecting

text: loops

text: instead

text: of

text: non-intersecting

text: cycles.).

text: C

text: For

text: each

text: connected

text: graph

text: G

text: in

text: generate

text: the

text: ﬁnite

text: set

text: of

text: rotation

text: systems

text: of

text: G

text: satisfying

text: Lemma

text: g

text: up

text: to

text: cyclic

text: permutation.

text: For

text: each

text: rotation

text: system

text: found

text: in

text: step

text: check

text: whether

text: it

text: is

text: two-sided

text: and

text: satisﬁes

text: g

text: E

text: V

text: (see

text: theorem

text: I

text: The

text: graph

text: G

text: of

text: step

text: is

text: in

text: if

text: and

text: only

text: if

text: any

text: rotation

text: system

text: tests

text: aﬃrmatively

text: in

text: step

text: (and

text: did

text: not

text: g

text: appear

text: in

text: a

text: surface

text: with

text: lower

text: genus).

text: We

text: keep

text: a

text: running

text: list

text: of

text: the

text: graphs

text: G

text: that

text: pass

text: the

text: test,

text: as

text: well

text: as

text: the

text: successful

text: rotation

text: systems.

text: In

text: genus

text: we

text: determine

text: all

text: rotation

text: systems

text: that

text: pass

text: the

text: test

text: (see

text: the

text: table

text: at

text: the

text: end

text: of

text: the

text: article).

text: In

text: genus

text: we

text: stop

text: if

text: we

text: have

text: successful

text: rotation

text: system

text: for

text: a

text: graph.

text: Using

text: the

text: computer-generated

text: count

text: and

text: some

text: combinatorics

text: yields

text: the

text: main

text: result.

text: I

text: L

text: G

text: Theorem

text: The

text: cardinalities

text: of

text: and

text: for

text: g

text: are

text: as

text: follows.

text: g

text: g

text: g

text: I

text: L

text: G

text: Genus

text: g

text: g

text: g

text: Remark:

text: At

text: the

text: date

text: of

text: this

text: writing,

text: of

text: the

text: integer

text: sequences

text: or

text: are

text: listed

text: in

text: the

text: Online

text: Encyclopedia

text: of

text: Integer

text: Sequences

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: |I | |I | Proof. The numbers for genera 0 and 1 are discussed in [3] and [8]. The cardinalities of and are given L G 2 I 3 in Proposition 1. We show that the counts for for can be expressed in terms of those for . |L | |I | g|I | g g To obtain from ≤ , we must add to graphs G with more than one component and such that g i i g g γ−(G) = g. According to Lemma 12, each component of such a graph G separates a lower genus. Lemma 13 then implies that: |L | |I ||I ||I | |I ||I | |I | = + + |L2| |I0||I0||I0||I | 0 |I1||I ||I2 | |I ||I | |I ||I | |I | = + + + + 3 0 0 0 0 0 0 1 0 2 1 1 3 − Any graph that minimally separates genus g 1, also minimally separates genus g (just add a handle to one of the components of the complement of the graph in a minimal separating embedding). Thus the total count of all minimal separating graphs in genus g can be com(cid:88)puted as follows g |G | |L | = g i i=0 I I Figure 1: consists of one graph (the circle). The other three constitute the set . From left to right, 0 1 respectively graphs 1, 2, 3, and 8 of the table. I Figure 2: Graphs in with one vertex. From left to right, respectively graphs 4, and 5 of the table. 2 I Figure 3: Graphs in with two vertices. From left to right ﬁrst row, respectively graphs 10, 11, and 12 of the 2 table. On the second row, graphs 13, 14 , and 15. Last row, graph 16. 10 ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: |I

text: |I

text: Proof.

text: The

text: numbers

text: for

text: genera

text: and

text: are

text: discussed

text: in

text: and

text: The

text: cardinalities

text: of

text: and

text: are

text: given

text: L

text: G

text: I

text: in

text: Proposition

text: We

text: show

text: that

text: the

text: counts

text: for

text: for

text: can

text: be

text: expressed

text: in

text: terms

text: of

text: those

text: for

text: |L

text: |I

text: g|I

text: g

text: g

text: To

text: obtain

text: from

text: we

text: must

text: add

text: to

text: graphs

text: G

text: with

text: more

text: than

text: one

text: component

text: and

text: such

text: that

text: g

text: i

text: i

text: g

text: g

text: γ−(G)

text: g.

text: According

text: to

text: Lemma

text: each

text: component

text: of

text: such

text: a

text: graph

text: G

text: separates

text: a

text: lower

text: genus.

text: Lemma

text: then

text: implies

text: that:

text: |L

text: |I

text: ||I

text: ||I

text: |I

text: ||I

text: |I

text: |I

text: ||I

text: |I

text: ||I

text: |I

text: Any

text: graph

text: that

text: minimally

text: separates

text: genus

text: g

text: also

text: minimally

text: separates

text: genus

text: g

text: (just

text: add

text: a

text: handle

text: to

text: one

text: of

text: the

text: components

text: of

text: the

text: complement

text: of

text: the

text: graph

text: in

text: a

text: minimal

text: separating

text: embedding).

text: Thus

text: the

text: total

text: count

text: of

text: all

text: minimal

text: separating

text: graphs

text: in

text: genus

text: g

text: can

text: be

text: as

text: follows

text: g

text: |G

text: |L

text: g

text: i

text: I

text: I

text: Figure

text: consists

text: of

text: one

text: graph

text: (the

text: circle).

text: The

text: other

text: three

text: constitute

text: the

text: set

text: From

text: left

text: to

text: right,

text: respectively

text: graphs

text: and

text: of

text: the

text: table.

text: I

text: Figure

text: Graphs

text: in

text: with

text: one

text: vertex.

text: From

text: left

text: to

text: right,

text: respectively

text: graphs

text: and

text: of

text: the

text: table.

text: I

text: Figure

text: Graphs

text: in

text: with

text: two

text: vertices.

text: From

text: left

text: to

text: right

text: ﬁrst

text: row,

text: respectively

text: graphs

text: and

text: of

text: the

text: table.

text: On

text: the

text: second

text: row,

text: graphs

text: and

text: Last

text: row,

text: graph

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: SYNCHRONIZATION FOR AN INFINITE CLASS OF CONTINUED FRACTION TRANSFORMATIONS 15 We seek synchronization intervals of the form [ζ, η), where the endpoints are identiﬁed by · · ∈ R r (ζ) = r (ζ) and LA (cid:96) (η) = r (η), for certain R, L G . Our synchronization intervals 0 0 0 0 3,n form a subset of full measure; to prove this, it will be very helpful to have the digits of the ζ, η. The following is key to ﬁnding these digits. ≥ ⊆ ∈ N Lemma 12. Fix m = 3, n 3, an interval [ζ, η] (0, γ ) and i, j . Suppose that there are (cid:48) ∈ 3,n R, L, L G (none of which is the identity) such that 3,n − (a) L = C 1ACR, · (cid:48) · ∈ (b) R r = r − and L (cid:96) = (cid:96) − , for all α [ζ, η], ·0 j 1 0∈ i 2 · (c) LA (cid:96) = (cid:96) − for all α [ζ, η), while LA (cid:96) (η) = r (η), · 0 i 1 0 0 (d) R r (ζ) = (cid:96) (ζ). 0 0 Then − · (i) (cid:96) − (η) = A 1LA (cid:96) (η) = (cid:96) (η), i 1 · 0 0 · (ii) r (η) = Ak+1C r − (η) = r (η), where k is such that AkC r (η) = r (η) j− · j 1 1 0 1 (iii) A 2CLA (cid:96) (ζ) = (cid:96) (ζ). 0 1 · − · Proof. For any α, the identity (a) implies LA (cid:96) = C 1ACR r . ∈ I 0 0 Recall that for all α, r (α) / . Now set α = η. Hypotheses (b,c) imply that (cid:96) − = − · 0 α · · i 1 A 1LA (cid:96) = (cid:96) . Now, if r = AkC r , then r = AkCLA (cid:96) , which again by (a) gives 0 − 0 · 1 · 0 1 · 0 r = AkC C 1ACR r = Ak+1CR r . Now (b) gives Ak+1C r − = r . 1 0 − · 0 − · j 1 1 Finally, (d) with (cid:96) = A 1C (cid:96) yield (cid:96) (ζ) = A 1CR r (ζ). Hypothesis (a) now yields that − · 1 0 1 0 (cid:3) A 2CLA (cid:96) (ζ) = (cid:96) (ζ). 0 1 = y x ζ η ω 2 2 2 L R =- y x 2 Figure 6. Determining the synchronization interval [ζ, η) = [ζ , η ). Here, k,v k,v m = 3, n = 3, and k = 1, v = 1. The labels L, R mark respectively the curves · · y = L r (α), y = R r (α) where α = x/2 = x/t . (See Deﬁnitions 14 1,1 0 1,1 0 3,3 and 24 for R and L in general.) Red gives the sing√le branch of y = r (α) k,v k,v − 1 while blue colors the two branches of y = (cid:96) (α) for (5 21)/2 < x < g2. The 4 x-axis is shown as a dotted line. ∈ We will be describing synchronization subintervals of α [0, 1] in terms of common initial portions of the digits of r (α). 0 ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: SYNCHRONIZATION

text: FOR

text: AN

text: INFINITE

text: CLASS

text: OF

text: CONTINUED

text: FRACTION

text: TRANSFORMATIONS

text: We

text: seek

text: synchronization

text: intervals

text: of

text: the

text: form

text: [ζ,

text: η),

text: where

text: the

text: endpoints

text: are

text: identiﬁed

text: by

text: R

text: r

text: (ζ)

text: r

text: (ζ)

text: and

text: LA

text: (η)

text: r

text: (η),

text: for

text: certain

text: R,

text: L

text: G

text: Our

text: synchronization

text: intervals

text: form

text: a

text: subset

text: of

text: full

text: measure;

text: to

text: prove

text: this,

text: it

text: will

text: be

text: very

text: helpful

text: to

text: have

text: the

text: digits

text: of

text: the

text: ζ,

text: η.

text: The

text: following

text: is

text: key

text: to

text: ﬁnding

text: these

text: digits.

text: N

text: Lemma

text: Fix

text: m

text: n

text: an

text: interval

text: [ζ,

text: η]

text: γ

text: and

text: i,

text: j

text: Suppose

text: that

text: there

text: are

text: R,

text: L,

text: L

text: G

text: (none

text: of

text: which

text: is

text: the

text: identity)

text: such

text: that

text: (a)

text: L

text: C

text: (b)

text: R

text: r

text: r

text: and

text: L

text: for

text: all

text: α

text: [ζ,

text: η],

text: ·0

text: j

text: 0∈

text: i

text: (c)

text: LA

text: for

text: all

text: α

text: [ζ,

text: η),

text: while

text: LA

text: (η)

text: r

text: (η),

text: i

text: (d)

text: R

text: r

text: (ζ)

text: (ζ).

text: Then

text: (i)

text: (η)

text: A

text: (η)

text: (η),

text: i

text: (ii)

text: r

text: (η)

text: r

text: (η)

text: r

text: (η),

text: where

text: k

text: is

text: such

text: that

text: AkC

text: r

text: (η)

text: r

text: (η)

text: j−

text: j

text: (iii)

text: A

text: (ζ)

text: (ζ).

text: Proof.

text: For

text: any

text: α,

text: the

text: identity

text: (a)

text: implies

text: LA

text: C

text: r

text: I

text: Recall

text: that

text: for

text: all

text: α,

text: r

text: (α)

text: Now

text: set

text: α

text: η.

text: Hypotheses

text: (b,c)

text: imply

text: that

text: α

text: i

text: A

text: Now,

text: if

text: r

text: AkC

text: r

text: then

text: r

text: AkCLA

text: which

text: again

text: by

text: (a)

text: gives

text: r

text: AkC

text: C

text: r

text: r

text: Now

text: (b)

text: gives

text: r

text: r

text: j

text: Finally,

text: (d)

text: with

text: A

text: yield

text: (ζ)

text: A

text: r

text: (ζ).

text: Hypothesis

text: (a)

text: now

text: yields

text: that

text: A

text: (ζ)

text: (ζ).

text: y

text: x

text: ζ

text: η

text: ω

text: L

text: R

text: y

text: x

text: Figure

text: Determining

text: the

text: synchronization

text: interval

text: [ζ,

text: η)

text: [ζ

text: η

text: Here,

text: k,v

text: k,v

text: m

text: n

text: and

text: k

text: v

text: The

text: labels

text: L,

text: R

text: mark

text: respectively

text: the

text: curves

text: y

text: L

text: r

text: (α),

text: y

text: R

text: r

text: (α)

text: where

text: α

text: x/t

text: (See

text: Deﬁnitions

text: and

text: for

text: R

text: and

text: L

text: in

text: general.)

text: Red

text: gives

text: the

text: sing√le

text: branch

text: of

text: y

text: r

text: (α)

text: k,v

text: k,v

text: while

text: blue

text: colors

text: the

text: two

text: branches

text: of

text: y

text: (α)

text: for

text: x

text: The

text: x-axis

text: is

text: shown

text: as

text: a

text: dotted

text: line.

text: We

text: will

text: be

text: describing

text: synchronization

text: subintervals

text: of

text: α

text: in

text: terms

text: of

text: common

text: initial

text: portions

text: of

text: the

text: digits

text: of

text: r

text: (α).

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 18 KARIANE CALTA, COR KRAAIKAMP, AND THOMAS A. SCHMIDT The following result gives the basic structure of the collection of potential synchronization intervals. (cid:91) Theorem 19. We have the following partition ∞ (0, γ ) = I . 3,n k,1 ∈ N ∈ V k(cid:91)=1 Furthermore, for each k and each v , the following is a partition: ∞ ∪ I = J I , k,v k,v k,Θq(v) (cid:48) q=q (cid:48) (cid:48) − where q = 0 unless v = c , in which case q = 1. 1 We postpone the proof of this theorem until page 28. When n = 3, the ﬁrst statement of the theorem describes the partition given by the intervals of deﬁnition of the leftmost red branches of Figure 5. See also Figure 8. I k,v I k,Θq(v) I k,Θ0(v) J k,v Jk,Θq(v) Jk,Θq−1(v) • • • • • • • • ζk,v ηk,v ζk,Θq(v) ηk,Θq(v) ζk,Θq−1(v) ηk,Θq−1(v) ζΘ0(v) ωk,v Figure 8. A hint of the partition of a general α-cylinder I . That ω = k,v k,Θq(v) ζ holds for appropriate v is part of Lemma 35. k,Θq−1(v) ←− The notation v denotes the wo←r−d formed by taking the letters of v in reverse order. Thus, v is a palindrome if and only if v = v . ∈ V Proposition 20. Suppose v . Then: (1) v is a word in at most three letters; (2) v is a palindrome; ≥ (3) if v = Θ (u) for some q 1, then v = uxu for some palindrome x. q (cid:48) (4) if u is the parent of v, then there is a palindrome y such that v = yu; (cid:48) (cid:48)(cid:48) (5) with this same y, one has v v = yv; (cid:54) (cid:48)(cid:48) (cid:48) (6) if further v = c , then there are palindromes a, z such that v = az, y = z a. 1 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: KARIANE

text: CALTA,

text: COR

text: KRAAIKAMP,

text: AND

text: THOMAS

text: A.

text: SCHMIDT

text: The

text: following

text: result

text: gives

text: the

text: basic

text: structure

text: of

text: the

text: collection

text: of

text: potential

text: synchronization

text: intervals.

text: Theorem

text: We

text: have

text: the

text: following

text: partition

text: γ

text: I

text: N

text: V

text: Furthermore,

text: for

text: each

text: k

text: and

text: each

text: v

text: the

text: following

text: is

text: a

text: partition:

text: I

text: J

text: I

text: k,v

text: k,v

text: k,Θq(v)

text: q=q

text: where

text: q

text: unless

text: v

text: c

text: in

text: which

text: case

text: q

text: We

text: postpone

text: the

text: proof

text: of

text: this

text: theorem

text: until

text: page

text: When

text: n

text: the

text: ﬁrst

text: statement

text: of

text: the

text: theorem

text: describes

text: the

text: partition

text: given

text: by

text: the

text: intervals

text: of

text: deﬁnition

text: of

text: the

text: leftmost

text: red

text: branches

text: of

text: Figure

text: See

text: also

text: Figure

text: I

text: k,v

text: I

text: k,Θq(v)

text: I

text: J

text: k,v

text: Jk,Θq(v)

text: ζk,v

text: ηk,v

text: ζk,Θq(v)

text: ηk,Θq(v)

text: ωk,v

text: Figure

text: A

text: hint

text: of

text: the

text: partition

text: of

text: a

text: general

text: α-cylinder

text: I

text: That

text: ω

text: k,v

text: k,Θq(v)

text: ζ

text: holds

text: for

text: appropriate

text: v

text: is

text: part

text: of

text: Lemma

text: The

text: notation

text: v

text: denotes

text: the

text: wo←r−d

text: formed

text: by

text: taking

text: the

text: letters

text: of

text: v

text: in

text: reverse

text: order.

text: Thus,

text: v

text: is

text: a

text: palindrome

text: if

text: and

text: only

text: if

text: v

text: v

text: V

text: Proposition

text: Suppose

text: v

text: Then:

text: v

text: is

text: a

text: word

text: in

text: at

text: most

text: three

text: letters;

text: v

text: is

text: a

text: palindrome;

text: if

text: v

text: Θ

text: (u)

text: for

text: some

text: q

text: then

text: v

text: uxu

text: for

text: some

text: palindrome

text: x.

text: q

text: if

text: u

text: is

text: the

text: parent

text: of

text: v,

text: then

text: there

text: is

text: a

text: palindrome

text: y

text: such

text: that

text: v

text: yu;

text: with

text: this

text: same

text: y,

text: one

text: has

text: v

text: v

text: yv;

text: if

text: further

text: v

text: c

text: then

text: there

text: are

text: palindromes

text: a,

text: z

text: such

text: that

text: v

text: az,

text: y

text: z

text: a.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##