Vincent Colin
email: vincent.colin@univ-nantes.fr

K O Honda
email: honda@math.ucla.edu

FOLIATIONS, CONTACT STRUCTURES AND THEIR INTERACTIONS IN DIMENSION THREE

Keywords:

We survey the interactions between foliations and contact structures in dimension three, with an emphasis on sutured manifolds and invariants of sutured contact manifolds. This paper contains two original results: the fact that a closed orientable irreducible 3-manifold M with nonzero second homology carries a hypertight contact structure and the fact that an orientable, taut, balanced sutured 3-manifold is not a product if and only if it carries a contact structure with nontrivial cylindrical contact homology. The proof of the second statement uses the Handel-Miller theory of end-periodic diffeomorphisms of end-periodic surfaces. CONTENTS 1. Introduction 1 2. A brief overview of foliations and contact structures 3 3. From foliations to contact structures 5 4. Invariants of contact manifolds 12 5. From contact structures to foliations 20 References 22

INTRODUCTION

Codimension one foliations are a powerful tool for probing the topology of an ambient manifold of dimension three. Since the work of Gabai [START_REF] Gabai | Foliations and the topology of 3-manifolds[END_REF], taut foliations have been identified as a particularly relevant class of foliations, at the epicenter of many breakthroughs such as the resolution of the Property R and P conjectures for knots respectively by Gabai [START_REF] Gabai | Foliations and the topology of 3-manifolds II[END_REF] and Kronheimer-Mrowka [KM]. The theory of sutured manifolds and their decompositions [START_REF] Gabai | Foliations and the topology of 3-manifolds[END_REF] provides a (finite depth) taut foliation on every closed orientable irreducible 3-manifold with nontrivial integral second homology. The existence of a taut foliation on an irreducible 3-manifold M is currently conjectured to be equivalent to the left-orderability of the fundamental group of M [BGW].

Contact structures are more flexible in nature, but the results of Eliashberg-Thurston [ET] and Vogel [START_REF] Vogel | Uniqueness of the contact structure approximating a foliation[END_REF] give a correspondence between the two worlds, namely an essentially unique way to deform a taut foliation without a torus leaf into a tight contact structure. The stability of contact structures makes them appear as a discrete version of foliations. It is also important that tight contact structures might exist when taut foliations do not (for example on S 3 ), extending the possible range of investigations.

More interesting is that they are well-adapted to pseudo-holomorphic curve techniques. Amongst those, two invariants emerge: embedded contact homology and (cylindrical) contact homology. Both are homologies of chain complexes generated by finite products of periodic orbits of a Reeb vector field for a contact structure and whose differentials count certain pseudo-holomorphic curves in the symplectization of the contact manifold. Embedded contact homology (ECH) was defined by Hutchings [START_REF] Hutchings | An index inequality for embedded pseudoholomorphic curves in symplectizations[END_REF][START_REF] Hutchings | The embedded contact homology index revisited, New perspectives and challenges in symplectic field theory[END_REF][START_REF] Hutchings | Lecture notes on embedded contact homology, in Contact and Symplectic Topology[END_REF] and Hutchings-Taubes [START_REF] Hutchings | Gluing pseudoholomorphic curves along branched covered cylinders I[END_REF][START_REF] Hutchings | Gluing pseudoholomorphic curves along branched covered cylinders II[END_REF] and was shown to be a topological invariant [T2] isomorphic to the Heegaard Floer homology of Ozsváth-Szabó [START_REF] Ozsváth | Holomorphic disks and topological invariants for closed threemanifolds[END_REF][START_REF] Ozsváth | Holomorphic disks and three-manifold invariants: properties and applications[END_REF] in [START_REF] V. Colin | Embedded contact homology and open book decompositions[END_REF]- [START_REF] V. Colin | The equivalence of Heegaard Floer homology and embedded contact homology via open book decompositions III: from hat to plus[END_REF]. Contact homology, proposed by Eliashberg-Givental-Hofer [EGH] and defined in full generality by Pardon [Par] and Bao-Honda [BH], is a contact invariant which is sensitive to the particular choice of contact structure on a given manifold.

The theory of convex surfaces in contact 3-manifolds, developed by Giroux [START_REF] Giroux | Convexité en topologie de contact[END_REF], is also surprisingly close to the theory of sutured 3-manifolds, invented by Gabai to construct taut foliations. Indeed both interact in a nested way, making it possible to define invariants of sutured contact manifolds and develop a gluing theory for contact manifolds parallel to that of foliated sutured ones [START_REF] Honda | Tight contact structures and taut foliations[END_REF]- [START_REF] Honda | The contact invariant in sutured Floer homology[END_REF], [START_REF] Colin | Chirurgies d'indice 1 et isotopies de sphères dans les variétés de contact tendues[END_REF][START_REF] Colin | Recollement de variétés de contact tendues[END_REF], [CH, CGHH]. This combination of contact geometry and foliation theory through its holomorphic invariants -and in particular the contact class associated to a contact structure in the Heegaard Floer group [START_REF] Ozsváth | Heegaard Floer homology and contact structures[END_REF] -has expanded the applicability of Gabai's work and provided striking new results such as the proof of the Gordon conjecture by Kronheimer, Mrowka, Ozsváth and Szabó [KMOS] or the characterization of fibered knots by Ghiggini [Gh] and Ni [Ni]. The existence of a taut foliation on an irreducible rational homology sphere M is now conjectured to have a complete characterization in terms of Heegaard Floer homology (or equivalently ECH): the rank of the Heegaard Floer hat group of M is strictly larger than the order of H 1 (M ; Z).

The goal of this paper is to survey these interactions, with an emphasis on sutured manifolds and invariants of sutured contact manifolds. We also discuss some open problems. The paper contains two original results: the fact that a closed orientable irreducible 3-manifold M with nonzero second homology carries a hypertight contact structure (Theorem 3.14) and the fact that an orientable, taut, balanced sutured 3-manifold is not a product if and only if it carries a contact structure with nontrivial cylindrical contact homology (Theorem 4.14). The proof of Theorem 4.14 uses the Handel-Miller theory of end-periodic diffeomorphisms of end-periodic surfaces. We also discuss work in progress with Ghiggini and Spano [CGHS] to prove the isomorphism between the sutured versions of Heegaard Floer homology and ECH.

A BRIEF OVERVIEW OF FOLIATIONS AND CONTACT STRUCTURES

2.1. Definitions. On a 3-manifold M , there are two classes of homogeneous plane fields. Given a local nonvanishing 1-form α with kernel a homogeneous plane field ξ, either the 3-form α ∧ dα vanishes everywhere or is nonzero everywhere. In the first case, the plane field ξ integrates into a foliation and is locally defined by an equation dz = 0 in R 3 . It is the tangent space to the local surfaces {z = const}. In the second case, it is locally given by an equation dz -ydx = 0 and is a contact structure. In these coordinates, the vector field ∂ y is tangent to the contact plane and the slope of the line field ξ ∩ {dy = 0} in the (x, z) coordinates is y: the plane field ξ rotates with y, a manifestation of its maximal nonintegrability. When ξ is a contact structure, the sign of the 3-form α ∧ dα is independent of the choice of α and hence ξ induces an orientation of M .

In this paper, we assume that all plane fields are cooriented and 3-manifolds oriented.

The topology of a 3-manifold is often tested by looking at its submanifolds of dimensions 1 and 2. In the presence of a plane field ξ, one distinguishes horizontal curves (i.e., curves everywhere tangent to ξ) and transverse ones. Whether ξ is integrable or contact makes a huge difference: every horizontal curve of a foliation must stay in a leaf, whereas any two points can be connected by a horizontal (or transverse) arc in a contact manifold. If ξ is contact, a horizontal curve will usually be called Legendrian. Also in the contact case, there is a preferred class of transverse vector fields called Reeb vector fields which are the ones whose flow preserves ξ.

If S is a surface in (M, ξ), we define its characteristic foliation to be the singular foliation ξS of S generated by the singular line field ξ ∩ T S. The singularities are the points p ∈ S where ξ p = T p S. For a generic S, they are isolated. Generically the singularities of ξS are either saddles or centers when ξ is integrable, and saddles or sources/sinks when ξ is a contact structure. If both ξ and S are oriented, then the foliation ξS is also oriented.

The main tool for analyzing a 3-dimensional contact manifold is convex surface theory, which was developed by Giroux [START_REF] Giroux | Convexité en topologie de contact[END_REF]. When ξ is a contact structure, a closed surface S ⊂ (M, ξ) is convex if there exists a vector field X transverse to S and whose flow preserves ξ. The convexity condition is a C ∞ -generic condition. If S is convex, the dividing set

Γ S = {x ∈ S | X(x) ∈ ξ(x)}
is an oriented embedded 1-submanifold of S (i.e., a multicurve) transverse to the characteristic foliation ξS. It decomposes S into regions R + and R -such that X is positively (resp. negatively) transverse to ξ on R + (resp. R -). It turns out that the dividing set Γ S does not depend on the choice of the vector field X up to isotopy through curves transverse to the characteristic foliation ξS. The dividing set Γ S completely determines the germ of ξ near S. When ∂M is convex, the dividing set Γ ∂M gives M the structure of a sutured manifold; see Section 3.2. 2.2. Flexibility vs. rigidity. We review the boundary between flexibility and rigidity both for foliations and contact structures. 2.2.1. Foliations. We first discuss the situation for foliations. A Reeb component is a foliation of the solid torus S 1 × D 2 such that the boundary S 1 × ∂D 2 is a leaf and int(S 1 × D 2 ) is foliated by an S 1 -family of planes which "winds around" in such a way that the characteristic foliation of each meridian disk {θ} × D 2 consists of concentric circles with one singularity at the center. The presence of Reeb components makes foliations flexible and subject to an h-principle. In fact Thurston [Th] showed that on a given 3-manifold every plane field is homotopic to an integrable one, typically with many Reeb components. Along the same lines, by inserting Reeb components Eynard-Bontemps [E-B] showed that two integrable plane fields that are homotopic as plane fields are homotopic through integrable plane fields.

One gets more rigidity by considering foliations without Reeb components, or the more restrictive class of taut foliations, for which there is a closed transverse curve that passes through every leaf. This condition prevents Reeb components from existing. The existence of a taut foliation imposes strong restrictions on the ambient manifold: its universal cover is R 3 by Palmeira [Pa] and all the leaves are π 1 -injective by Novikov [No]. An equivalent definition for a foliation to be taut is to have a volume-preserving transverse vector field. Moreover, a vector field transverse to a taut foliation has no contractible periodic orbit. Finally, taut foliations only exist in a finite number of homotopy classes of plane fields [START_REF] Gabai | Essential laminations and Kneser normal form[END_REF].

2.2.2. Contact structures. On the contact side, a contact structure ξ is overtwisted if there exists an embedded disk D such that ξ = T D along ∂D; otherwise it is tight. In this paper we emphasize two subclasses of tight contact structures, mostly due to their close connections with taut foliations:

(1) universally tight contact structures, i.e., tight contact structures that remain tight when pulled back to the universal cover; and (2) hypertight contact structures, i.e., contact structures that admit Reeb vector fields with no contractible orbit. By a theorem of Hofer [Hof] that states that an overtwisted contact form on a closed manifold always admits a contractible Reeb orbit, a hypertight contact structure is always universally tight. The hypertightness condition also insures that the cylindrical contact homology is well-defined and hypertight contact forms are typically easier to deal with when computing holomorphic invariants; see Section 4.

Similar to foliations with Reeb components, overtwisted contact structures are subject to an h-principle which was discovered by Eliashberg [START_REF] Eliashberg | Classification of overtwisted contact structures on 3-manifolds[END_REF]: there is exactly one homotopy class of overtwisted contact structures in every homotopy class of 2plane fields. However, rigidity shows up again when considering higher homotopy groups in the space of overtwisted contact structures. For example, we have the following:

Theorem 2.1 (Chekanov-Vogel [START_REF] Vogel | Non-loose unknots, overtwisted discs and the contact mapping class group of S 3[END_REF]). If ξ is an overtwisted contact structure of S 3 whose Hopf number is 1, then there exists a loop of overtwisted contact structures based at ξ that is contractible in the space of plane fields, but not in the space of overtwisted contact structures.

Problem 2.2. Does the same phenomenon hold for foliations with Reeb components? Tight contact structures have strong rigidity properties and admit a roughly classification in dimension three [START_REF] Colin | Une infinité de structures de contact tendues sur les variétés toroïdales[END_REF][START_REF] Colin | Finitude homotopique et isotopique des structures de contact tendues[END_REF][START_REF] Honda | Convex decomposition theory[END_REF]: They exist in a finite number of homotopy classes of plane fields. If M is atoroidal (e.g., hyperbolic), it carries finitely many -this number may be zero -tight contact structures up to isotopy. If M is toroidal and irreducible, it carries infinitely many tight contact structures up to diffeomorphism. Finally, the class of tight contact structures is stable under connected sum [START_REF] Colin | Chirurgies d'indice 1 et isotopies de sphères dans les variétés de contact tendues[END_REF].

Problem 2.3. Does every hyperbolic 3-manifold carry a tight contact structure?

Compare this to the situation for taut foliations where Roberts-Shareshian-Stein [RSS] showed that there are infinitely many hyperbolic 3-manifolds without taut foliations; there are other obstructions due to Calegari-Dunfield [CD] and Kronheimer-Mrowka-Ozsváth-Szabó [KMOS].

FROM FOLIATIONS TO CONTACT STRUCTURES

3.1. Perturbing foliations and torsion. The link between foliations and contact structures was discovered by Eliashberg and Thurston [ET].

Theorem 3.1 (Eliashberg-Thurston). Every C 2 foliation on a closed 3-manifold different from the foliation by spheres of S 1 × S 2 is a limit of a sequence of positive contact structures and also a sequence of negative contact structures. Moreover, if the foliation is taut, then every contact structure C 0 -close to it is semi-fillable and universally tight.

A contact 3-manifold (M, ξ) is semi-fillable if there exists a symplectic manifold (W, ω) with contact boundary ∂W = (M, ξ) (M , ξ ) such that ω| ξ∪ξ is symplectic. The symplectic manifold (W, ω) is called a semi-filling of (M, ξ).

Theorem 3.1 was extended by Bowden [START_REF] Bowden | Approximating C 0 -foliations by contact structures[END_REF] to the case of C 0 foliations and it was shown in [START_REF] Bowden | Contact perturbations of Reebless foliations are universally tight[END_REF][START_REF] Colin | Structures de contact tendues sur les variétés toroïdales et approximation de feuilletages sans composante de Reeb[END_REF] that every contact structure close to a Reebless foliation is universally tight. In the presence of a torus leaf, Giroux noticed that the torsion phenomenon could provide different contact structures approximating the same foliation. The following is the basic example: Example 3.2. On the 3-torus

T 3 = {(x, y, t) ∈ R/Z × R/Z × R/(2πZ)},
for any positive integer n and real number = 0, the plane field

ξ n = ker(dz + (cos(nx)dt -sin(ny)dt))
is a contact structure, positive when > 0 and negative when < 0. By Gray's stability theorem, for a fixed n all the structures ξ n with > 0 are isotopic, and similarly for < 0. Moreover, by Giroux [Gi2], two different n give two nondiffeomorphic contact structures. Finally we observe that when goes to 0, all these contact structures converge to the integrable plane field ξ 0 n = ker dz. More generally, let ξ n be the contact structure defined on the thickened torus

T 2 × I = {(x, y, t) ∈ R/Z × R/Z × [0, 2π]}
by the equation cos tdx -sin tdy = 0. We define the torsion τ (M,ξ) of a contact manifold (M, ξ) to be the supremum of the integers n for which there exists a contact embedding (T 2 × I, ξ n ) → (M, ξ). One can also specify the torsion τ η in a given isotopy class η of embeddings of T 2 . It is immediate from Eliashberg's classification of overtwisted contact structures that τ η is infinite for every η. When ξ is tight, τ η = 0 in every compressible class η.

The following is still open:

Problem 3.3. Prove that τ (M,ξ) < ∞ whenever (M, ξ) is tight.
It was shown in [START_REF] Colin | Sur la torsion des structures de contact tendues[END_REF] that sup η∈D τ η < ∞ when (M, ξ) is universally tight, where D is the set of isotopy classes of incompressible tori that do not appear in the Jaco-Shalen-Johannson (JSJ) decomposition of M . However, we still do not know whether τ η < ∞ for the JSJ classes and whether

τ (M,ξ) < ∞ if (M, ξ) is tight but not universally tight.
It was conjectured in [START_REF] Colin | Sur la géométrie des structures de contact en dimension trois: stabilité, flexibilité et finitude[END_REF] that the torsion phenomenon which appears in the presence of a torus leaf was the only reason for the nonuniqueness of the approximation. The answer to this problem was given by Vogel:

Theorem 3.4 (Vogel [START_REF] Vogel | Uniqueness of the contact structure approximating a foliation[END_REF]). If F is a foliation on a closed 3-manifold which does not have a torus leaf, is not a foliation by planes, and is not a foliation by cylinders, then it has a C 0 -neighborhood in the space of 2-plane fields in which all positive (or negative) contact structures are isotopic.

The strength of this result is that it implies that the invariants of a contact approximation such as contact homology immediately become invariants of the foliation.

It was already known by Honda-Kazez-Matić [KHM3] that:

Theorem 3.5. If π : M → S 1 is a fibered hyperbolic 3-manifold (and hence has pseudo-Anosov monodromy), then there is a unique positive contact structure ξ π up to isotopy that is homotopic to T F π , where F π is the foliation by fibers.

The contact homology of ξ π is thus an invariant of the pseudo-Anosov map.

Problem 3.6. Compute the contact homology in this case. What does it tell us about the pseudo-Anosov map? Study its behavior under composition of monodromies, provided they stay pseudo-Anosov. A first step was taken in Theorem 3.17, which provides a convenient Reeb vector field.

Problem 3.7. Given a fibration π : M → S 1 with pseudo-Anosov monodromy, is every taut foliation which is homotopic in the space of 2-plane fields to T F π homotopic through taut foliations to F π ?

3.2. Sutured manifold decompositions. One way to construct taut foliations and tight contact structures on a given 3-manifold M is to proceed as follows: (i) Decompose M into basic pieces.

(ii) Starting from model foliations/contact structures on these basic pieces, inductively glue them together to construct foliations/contact structures on the desired manifold M . It is nontrivial to ensure that at each step the gluing is compatible with the foliation/contact structure, and even more difficult in the contact case to ensure that tightness is preserved.

In this subsection we discuss decomposing M into basic pieces. A suitable decomposition, called a sutured manifold decomposition, was discovered by Gabai [START_REF] Gabai | Foliations and the topology of 3-manifolds[END_REF].

Definition 3.8. A sutured 3-manifold is a triple (M, Γ, U (Γ))
, where M is a compact 3-manifold with corners, Γ is an oriented 1-manifold in ∂M called the suture, and

U (Γ) = [-1, 0] × [-1, 1] × Γ is a neighborhood of Γ = {(0, 0)} × Γ in M with coordinates (τ, t) ∈ [-1, 0] × [-1, 1], such that the following hold: • U (Γ) ∩ ∂M = ({0} × [-1, 1] × Γ) ∪ ([-1, 0] × {-1, 1} × Γ). • ∂M -({0} × (-1, 1) × Γ) is the disjoint union of two submanifolds which we call R -(Γ) and R + (Γ)
, where the orientation of ∂M agrees with that of R + (Γ) and is opposite that of R -(Γ), and the orientation of Γ agrees with the boundary orientation of R ± (Γ). • The corners of M are precisely {0} × {±1} × Γ. We refer to A(Γ) = {0} × [-1, 1] × Γ as the vertical annular neighborhood of Γ in ∂M .

Our definition is slightly different from Gabai's original one from [START_REF] Gabai | Foliations and the topology of 3-manifolds[END_REF]: we introduced the neighborhoods U (Γ) and use smooth manifolds with corners instead of ones with boundary. We often suppress the data of the neighborhood U (Γ), since it is usually understood. Definition 3.9. A product sutured manifold is a sutured manifold of the form

(S × [-1, 1], Γ = ∂S × {0}),
where S is a compact oriented surface, each of whose components has nonempty boundary. Here

A(Γ) = ∂S × [-1, 1]. Definition 3.10. A sutured 3-manifold (M, Γ, U (Γ)) is taut if M is irreducible and R + (Γ) and R -(Γ) have minimal Thurston norm, i.e.
, the sum of the Euler characteristics of its nonspherical components, amongst properly embedded surfaces realizing the same homology class in

H 2 (M, Γ). It is balanced if χ(R + ) = χ(R -),
M has no closed components, and π 0 (A(Γ)) → π 0 (∂M ) is surjective.

We now describe how to apply a sutured manifold decomposition of a sutured manifold (M, Γ) into (M , Γ ) along a surface S. In what follows N (B) denotes a sufficiently small tubular neighborhood of B.

Let S ⊂ (M, Γ) be an oriented properly embedded surface such that S A(Γ), ∂A(Γ) and:

• each arc component c of S ∩ A(Γ) is nonseparating in A(Γ); • each closed component c of S ∩ A(Γ) is homologous to Γ ∩ A, where A is the component of A(Γ) containing c; • no component of S is a disk with boundary in R ± (Γ); and • no component of ∂S bounds a disk in R ± (Γ).
Let M = M \ int(N (S)) and let S + (resp. S -) be the portion of ∂N (S) ∩ ∂M where the orientation induced from S agrees with (resp. is opposite to) the boundary orientation on ∂M .

We then set

A(Γ ) := (A(Γ) ∩ M ) ∪ N (S + ∩ R -(Γ)) ∪ N (S -∩ R + (Γ)), R + (Γ ) := ((R + (Γ) ∩ M ) ∪ S + ) -int(A(Γ )), R -(Γ ) := ((R -(Γ) ∩ M ) ∪ S -) -int(A(Γ )),
where we smooth and introduce corners as appropriate.

A sutured manifold hierarchy is a sequence of such decompositions [START_REF] Gabai | Foliations and the topology of 3-manifolds[END_REF] showed that:

(M, Γ) = (M 0 , Γ 0 ) S 0 (M 1 , Γ 1 ) S 1 • • • S n-1 (M n , Γ n ) along π 1 -injective surfaces S i ⊂ M i , i = 1, . . . , n -1, such that (M n , Γ n ) is a product sutured manifold. Gabai
Theorem 3.11. A taut balanced sutured manifold admits a sutured manifold hierarchy.

3.3. Construction of hypertight contact structures. Next we discuss the construction step in the contact case.

Definition 3.12. A sutured contact manifold (M, Γ, U (Γ), ξ) is a sutured 3-manifold (M, Γ, U (Γ)) together with a contact form λ for ξ such that: (i) the Reeb vector field R λ for λ is positively transverse to R + (Γ) and negatively transverse to R -(Γ);

(ii) λ = Cdt + β in U (Γ), where β is independent of t. In particular, R λ = 1 C ∂ t in U (Γ). A contact form λ satisfying (i) and (ii) is adapted to (M, Γ, U (Γ)).
The initial step in the construction is a product sutured contact manifold, i.e., a product sutured manifold (S × [-1, 1], Γ = ∂S × {0}) with contact form λ = dt + β, where dβ is an area form on S.

The reverse process of a sutured manifold decomposition is called "sutured manifold gluing". By "going back up" the sutured manifold hierarchy and gluing carefully, we obtain the following: Theorem 3.13 ( [CH]). If (M, Γ) is a taut balanced sutured manifold, then it carries an adapted hypertight contact form.

In the rest of this subsection we upgrade Theorem 3.13 to: Theorem 3.14. If M is a closed, oriented, connected, irreducible 3-manifold with H 2 (M ; Z) = 0, then M carries a hypertight contact structure.

Let S be an embedded genus-minimizing surface in a closed M such that 0 = [S] ∈ H 2 (M ; Z). The first step of a sutured hierarchy starting with (M, Γ = ∅) yields the sutured manifold (M 1 = M \ int(N (S)), Γ 1 = ∅) with R ± = S ± , which is taut but not balanced since π 0 (A(Γ 1 )) → π 0 (∂M 1 ) is not surjective. In order to remedy this we choose nonseparating simple closed curves δ + and δ -on R ± ⊂ ∂M 1 and take

R + := (R + -N (δ + )) ∪ N (δ -), R -:= (R --N (δ -)) ∪ N (δ + ), Γ 1 := ∂R + = ∂R -.
The need to make this modification is a reflection of the fact that a Reeb vector field cannot be made transverse to a closed surface. This creates some difficulties; in particular we risk losing control of the dynamics of the Reeb vector field. We have a way around this and still retain control of the dynamics by making the Reeb vector field transverse to a branched surface.

At this point we recall the following definition; see [Li] for an explanation of the terms: Definition 3.15 ( [Li]). A branched surface is laminar if the horizontal boundary of fibered neighborhood of the branched surface is incompressible, there is no monogon, there is no Reeb component, and there is no sink disk.

It was shown in [Li] that a laminar branched surface carries an essential lamination, which can be thought of as a simultaneous generalization of an incompressible surface and a taut foliation.

The key fact about essential laminations that we need is [GO, Theorem 1(d)]:

Theorem 3.16 (Gabai-Oertel [GO]). Let L be an essential lamination on M . If γ is a closed curve which is efficient for L and γ ∩ L = ∅, then γ is not contractible in M .

Here a curve γ is efficient for L if no arc c of γ ∩ (M -L) (or rather its closure c) can be pushed into a leaf of L relative to its endpoints.

As a warm-up we prove the following:

Theorem 3.17. If M is a closed 3-manifold which admits a fibration π : M 3 → S 1 with fibers of genus g ≥ 1, then it carries a hypertight contact structure. When the monodromy is pseudo-Anosov and g > 1, then the unique tight contact structure ξ π homotopic to the tangent plane of the fibers is hypertight.

Proof. The case of g = 1 is straightforward and was observed by Giroux: there exists a contact form such that the characteristic foliation on each torus fiber is linear and the Reeb vector field is tangent to the fibers and "orthogonal" to the characteristic foliation. We consider the g ≥ 2 case. We show that ξ π has a contact 1-form whose Reeb vector field is transverse to a laminar branched surface B and has no contractible periodic orbit in M \ N (B).

Lemma 3.18. Let T be a compact, connected, oriented surface of genus > 1 with two boundary components γ 1 and γ 2 and let δ -, δ + ⊂ T be two nonseparating oriented simple closed curves. Then there exists a contact form α on T × [-1, 1] with the following properties:

(1) The Reeb vector field R of α is positively transverse to T ×{t}, t ∈ [-1, 1], and is tangent to the interval fibers of (∂T )

× [-1, 1]. (2) ξ = ker α is positively transverse to γ i × {t} for t ∈ [-1, 1] and i = 1, 2,
and to δ -× {-1} and δ + × {1}.

(3) γ 1 ×{t} α = γ 2 ×{t} α = δ -×{-1} α = δ + ×{1} α = 1.
Proof of Lemma 3.18. The contact structure will be a modification of the [-1, 1]invariant contact structure on T ×[-1, 1]. By the Flexibility Lemma [CH, Lemma 5.1], it suffices to construct a contact form α near T × {±1} that satisfies the properties of Lemma 3.18.

We perform this construction near T = T × {1} for an arbitrary nonseparating simple closed curve δ = δ + ; situation for T × {-1} and δ -is analogous. As all nonseparating simple closed curves in T are diffeomorphic by a diffeomorphism of T which is the identity near ∂T , it suffices to do the construction for some δ.

Let F be an oriented singular Morse-Smale foliation on T such that:

• its singularities are all positive;

• F has no periodic orbits; and • F exits from T along its boundary. Then there exists a 1-form λ such that F = ker λ and dλ is an area form on T . The form dt + λ on T × R t is contact, its Reeb vector field is ∂ t and the characteristic foliation on T = T × {0} agrees with F. By attaching a cylindrical collar ∂T × [0, 1] to T along ∂T = ∂T × {0} and extending λ, we can increase the λ-lengths of each component of the boundary at will and thus assume that they are both equal to a certain value κ 0. There is quite a bit of flexibility to choose F; in particular we may choose F so that F is transverse to a (necessarily orientable) train track T = c 0 ∪c 1 , where c 0 is a smooth homologically nontrivial simple closed curve and c 1 is an arc with both endpoints on c 0 , approaching c 0 from opposite sides. The train track T carries infinitely homologically nontrivial simple closed curves ζ 1 , ζ 2 , . . . ; they are all transverse to F and some ζ j has λ-length greater than κ. Now we can enlarge T by attaching another collar so that the λ-length of each boundary component agrees with the λ-length of δ := ζ j . The normalization (3) is obtained by rescaling.

We state without proof a classical result on the connectedness of the curve complex: Fact 3.19. For every pair of nonseparating simple closed curves δ -, δ + on a closed oriented surface S, there exists a sequence of nonseparating simple closed curves δ 0 , . . . , δ n such that δ i ∩ δ i+1 = ∅, δ 0 = δ -, and δ n = δ + . Now let S be a fiber of the fibration π : M → S 1 and let φ : S ∼ → S be the monodromy. Let δ 0 , . . . , δ n be the sequence of nonseparating oriented simple closed curves on S given by Fact 3.19 for δ 0 = φ(δ + ) and δ n = δ + . We consider the surfaces S i = S × { i n }, i = 0, . . . , n, in S × [0, 1]. We briefly comment on orientations of δ i : Choose an orientation for δ n = δ + . Then the orientation for δ 0 = φ(δ + ) is determined. Choose orientations on δ 1 , . . . , δ n-1 arbitrarily.

Let S i = S i \ U i , where U i = N (δ i × { i n }) ⊂ S i , and let γ 1 i and γ 2 i be the two components of ∂S i . Suppose the orientation on γ 1 i agrees with that of δ i . We apply Lemma 3.18 to a small neighborhood S i × [-, ] of S i to obtain a contact form α i on S i × [-, ], for which the curves δ i-1 × {-} in S i × {-} and -δ i+1 × { } (note the orientation reversal) in S i × { } are α i -positively transverse and have α i -length 1, and γ 1 i × {± } and γ 2 i × {± } have α i -length 1. We then identify a neighborhood of

γ 2 i ×{-} ⊂ S i ×{-} with a neighborhood of -δ i × { } ⊂ S i-1 × { } and a neighborhood of γ 1 i × { } ⊂ S i × { } with a neighborhood of δ i ×{-} ⊂ S i+1 ×{-},
in a manner compatible with the forms α i .

After smoothing we obtain a fibered neighborhood N (B) ⊂ M of a branched surface B whose vertical fibers are tangent to the Reeb vector field R of a contact form α. One easily verifies that B is a laminar branched surface (for example, sink disks do not exist by our choice of curves δ i ).

It remains to extend α to the exterior of N (B).

By construction, M \ int(N (B)) is diffeomorphic to Σ×[0, 1],
where Σ is a compact oriented surface with boundary. The Reeb vector field is positively transverse to Σ×{0, 1} for a suitable orientation of Σ and tangent to (∂Σ) × [0, 1]. Hence, using the Flexibility Lemma, we can extend the contact form α and the Reeb vector field R to Σ 0 × [0, 1] so that the Reeb vector field gives a fibration by intervals. Let us write ξ = ker α.

Claim 3.20. The Reeb field R has no contractible periodic orbit, i.e., ξ is hypertight.

Proof. Every periodic orbit ζ of R must intersect B. Since B is laminar, ζ is also transverse to an essential lamination L carried by B. The curve ζ is efficient with respect to L, for example since L is orientable. Theorem 3.16 then implies that ζ is not contractible.

One easily checks that e(ξ), [F ] = -χ(F ). Since ξ is hypertight by the claim, it is tight, and is therefore contact isotopic to ξ π by Theorem 3.5. This completes the proof of Theorem 3.17. This strategy extends to control the dynamics in the last gluing of a sutured manifold hierarchy in the general case:

Proof of Theorem 3.14. Let S be an embedded genus-minimizing surface in M with [S] = 0. We first cut M along S to obtain (M 1 , Γ 1 ) with boundary R + (Γ 1 ) = S + and R -(Γ 1 ) = S -and Γ 1 = ∅. Next we cut M 1 along the surface S 1 ⊂ M 1 , with ∂S 1 intersecting S + and S -along multicurves δ + and δ -, respectively, to obtain (M 2 , Γ 2 ) such that A(Γ 2 ) corresponds to thickenings of δ ± . We may take each of δ + and δ -to be a union of parallel oriented nonseparating simple closed curves, since Gabai's construction of the sutured manifold hierarchy guarantees such "well-grooming" of δ ± = S 1 ∩ S ± . Theorem 3.13 constructs a hypertight contact form on (M 2 , Γ 2 ).

The rest of the proof is similar to that of Theorem 3.17: We take a sequence δ 0 , . . . , δ n of curves in S from δ 0 = δ + to δ n = δ -furnished by Fact 3.19; here δ + and δ -are unions of parallel curves and each δ i , i = 1, . . . , n -1 is connected. Following the proof of Theorem 3.17, we construct contact forms α i on S i ×[-, ] for i = 1, . . . , n -1 and glue the pieces S i × [-, ], i = 1, . . . , n -1, in the same way. We also glue M 2 and S 1 × [-, ] so that a neighborhood of

δ 0 ⊂ R + (Γ 2 ) is identified with a neighborhood of δ 0 × {-} ⊂ S 1 × {-} and a neighborhood of γ 2 1 × {-} ⊂ S 1 × {-} is identified with a neighborhood of -δ 1 ⊂ R + (Γ 2
) and analogously glue M 2 and S n-1 × [-, ]. Note that since δ + (also δ -) not necessarily connected we need to make the appropriate adjustments to Lemma 3.18(3). We then extend the contact form to the exterior of

M 2 ∪ (∪ n-1 i=1 S i × [-, ])/ ∼, which is of the form Σ × [0, 1].
All the periodic orbits must efficiently intersect a laminar branched surface and hence are not contractible by Theorem 3.16. Problem 3.21. Does every Haken manifold carry a tight contact structure? Problem 3.22. Is every universally tight contact structure on a 3-manifold with universal cover R 3 hypertight?

INVARIANTS OF CONTACT MANIFOLDS

4.1. Sutured contact homology and sutured ECH. For more details see [EGH], [Hu1, Hu2, Hu3], [CGHH] for contact homology, ECH, and sutured versions of these theories, respectively.

There are two main invariants of a contact manifold (M, ξ), obtained as the homology of chain complexes generated by finite products γ = i γ i of periodic orbits of a Reeb vector field R λ , ξ = ker λ, subject to some conditions and whose differentials count (Fredholm or ECH) index 1 J-holomorphic curves that limit to cylinders over collections of periodic orbits at the s → ±∞ ends in the symplectization (R s × M, d(e s λ)) for some "adapted" almost complex structure J, modulo translation in the s-direction. In this text we use F = Z/2-coefficients.

The first invariant contact homology is sensitive to the particular choice of contact structure. In the case of a hypertight contact form λ, there is a simpler version where the chain complex can be taken to be the free F-vector space generated by the (good) periodic orbits of R λ and the differential to be a count of J-holomorphic cylinders; this yields the cylindrical contact homology of (M, λ).

The second invariant embedded contact homology (ECH) is a topological invariant of the ambient manifold M and is isomorphic to the Heegaard Floer homology of -M , i.e., M with the orientation reversed. In particular, the contact class c(M, ξ), associated to the contact structure (M, ξ) in the Heegaard Floer hat group HF (-M ), is defined in the ECH hat group ECH(M ) to be the homology class of the empty set of orbits.

In the case of a sutured contact manifold (M, Γ, ξ = ker λ), the hypothesis that λ is a contact form adapted to (M, Γ), together with the choice of a tailored almost complex structure J on the symplectization from [CGHH], prevents a sequence of holomorphic curves from exiting the symplectization R × M along its boundary R × ∂M and allows us to extend the definition of contact homology and ECH to sutured manifolds [CGHH]. The resulting groups are the sutured contact homology and sutured ECH groups and are denoted by HC(M, Γ, ξ) and ECH(M, Γ, ξ).

The following gluing theorem holds for both:

Theorem 4.1 ([CGHH]). If (M , Γ , ξ ) is obtained from (M, Γ, ξ
) by a sutured gluing, then there are injections

ECH(M, Γ, ξ) → ECH(M , Γ , ξ ), HC(M, Γ, ξ) → HC(M , Γ , ξ ).
Let M be a closed manifold and K ⊂ M be a knot. We define the knot ECH of (M, K) as follows: Let N (K) be a small tubular neighborhood of K, Γ two parallel meridian sutures on ∂N (K), and ξ a contact structure adapted to (M \ int(N (K)), Γ). Then the knot ECH is

ECH(M \ int(N (K)), Γ, ξ),
defined in analogy with Juhász' observation that the knot Heegaard Floer homology group HF K(M, K) satisfies:

HF K(M, K) HF (M \ int(N (K)), Γ).
Here we denote the sutured Heegaard Floer homology of a sutured manifold S (in a slightly nonstandard manner) by HF (S).

Let (M, ξ) be a closed contact manifold and Λ ⊂ (M, ξ) a Legendrian knot. We define the contact homology Legendrian invariant of Λ to be

HC(M \ int(N (Λ)), Γ Λ , ξ),
where N (Λ) is the standard tubular neighborhood of Λ and Γ Λ has two parallel sutures whose slope is induced by the framing along Λ given by ξ.

Problem 4.2. Compute this Legendrian knot invariant on significant examples.

ECH and Heegaard

Floer homology for a sutured manifold. In work in progress with Ghiggini and Spano [CGHS], we study the extension of the isomorphism between ECH and Heegaard Floer homology from [CGH0, CGH1, CGH2, CGH3] to sutured manifolds.

The ECH group ECH(M, Γ, ξ) admits a decomposition into homology classes A ∈ H 1 (M ; Z) of "orbit sets" γ as follows:

ECH(M, Γ, ξ) = ⊕ A∈H 1 (M ;Z) ECH(M, Γ, ξ, A).
The sutured Heegaard Floer homology group HF (M, Γ) admits a decomposition into relative Spin c -structures which form an affine space over H 2 (M, ∂M ; Z):

HF (M, Γ) = ⊕ s∈H 2 (M,∂M ;Z) HF (M, Γ, s).
We expect to prove the following: In the rest of this subsection we will refer to consequences of the conjecture and its expected proof as "corollaries". 4.2.1. Case of a knot. The sutured isomorphism specializes to an isomorphism between knot ECH and knot Heegaard Floer homology.

Corollary 4.4. Let M be a closed manifold, K ⊂ M a knot, N (K) its tubular neighborhood, and Γ two parallel meridian sutures on ∂N (K). Also let ξ be a contact structure adapted to (M \ int(N (K)), Γ). Then

ECH(M \ int(N (K)), Γ, ξ) HF (-(M \ int(N (K))), -Γ) HF K(-M, -K).
Suppose that K ⊂ M is nullhomologous. Fix a minimum genus Seifert surface S for K with genus g. Then we can decompose ECH(M \ int(N (K)), Γ, ξ) according to the homological intersection number ι(γ) = γ, S . Similarly, HF K(-M, -K) = ⊕ g j=-g HF K(-M, -K, j) where the decomposition is according to the relative Spin s -structure, normalized so that its graded Euler characteristic j rk HF K(-M, -K, j) • t j agrees with the Alexander polynomial of K. Corollary 4.4 can be written more precisely as: (4.2.1) ECH(M \ int(N (K)), Γ, ξ, ι) HF K(-M, -K, g -ι).

By Equation (4.2.1), the ECH of a knot is supported in grading 0 ≤ ι ≤ 2g. Combined with the work of Ghiggini [Gh] and Ni [Ni]

S ∼ → S such that h| ∂S = id. Let N (∂S) = ∂S × [0, 1] be a neighborhood of ∂S = ∂S × {0} in S.
We isotop h to h on S so that:

(1) during the isotopy ∂S × {0} is rotated at most , and

(2) h is a rotation by an angle φ(r) on ∂S×{r} (here we are viewing ∂S S 1 using the boundary orientation), where φ : [0, 1] → R satisfies φ(0) = -, φ( 1 2 ) = 0, φ(1) = , and φ (r) > 0. We are also assuming that > 0 is sufficiently small so that the only periodic points of period 1 in N (∂S) are along {r = 1 2 }. We then perturb h to a flux zero area-preserving map h with respect to some area form ω so that all the fixed points are nondegenerate. In particular, two fixed points appear along {r = 1 2 }, an elliptic one e and a hyperbolic one h.

Let SF (S, h ) be the symplectic Floer homology of h , whose chain complex is generated by all its fixed points but e. By the methods of Hutchings and Sullivan [HS] combined with [CGHH, Theorem 10.3.2], (4.2.3) ECH(M \ int(N (K)), Γ, ξ, ι = 1) SF (S, h ).

Combining Equations (4.2.1) and (4.2.3), we obtain:

Corollary 4.5. HF K(-M, -K, g -1) SF (S, h ).

This result was implicitly conjectured by the two authors and Ghiggini as a combination of [CGHH, Conjecture 1.5] and [CGH0, Theorem 10.3.2], precisely formulated in the thesis [Sp], and first proven using a different argument in [GS]. Recently, Kotelskiy [Ko] reformulated this conjecture in the language of bordered Floer homology and gave some evidence for it. 4.2.3. Dynamical characterization of product sutured manifolds. Using Conjecture 4.3, one can transfer results from the Heegaard Floer side to the ECH side. The following is obtained by transferring the corresponding Heegaard Floer characterization (due to Juhász [START_REF] Juhász | Floer homology and surface decomposition[END_REF]) to ECH.

Corollary 4.6. The sutured contact manifold (M, Γ, ξ) satisfies

ECH(M, Γ, ξ) F if and only if (M, Γ) is a product sutured manifold.
Here is another formulation, which answers a question of John Pardon and can be thought of as an extension of the Weinstein conjecture [T1] to sutured contact 3-manifolds.

Corollary 4.7. If (M, Γ, ξ) is a sutured contact manifold with adapted contact form λ whose Reeb vector field R λ has no periodic orbit, then (M, Γ, ξ) is a tight product sutured contact manifold (S×[-1, 1], Γ = ∂S×{0}, ξ), where ξ is [-1, 1]invariant. If S is planar in addition, then every orbit of R λ flows from S × {-1} to S × {1}; in particular R λ has no trapped orbits. Problem 4.8. Can one prove that if there is no periodic orbit in S × [0, 1], then there is also no trapped orbit even when S is not planar?

In the higher-dimensional case, there can be trapped orbits without periodic ones, as proven by Geiges, Röttgen and Zehmisch [GRZ].

Recall the depth of a sutured manifold is the minimum number of steps in a sutured hierarchy needed to get to a product sutured manifold. We have the following dynamical characterization of depth k sutured manifolds: Corollary 4.9. If (M, Γ, ξ = ker λ) is a taut sutured contact manifold of depth greater than 2k with H 2 (M ) = 0 and if R λ is nondegenerate and has no elliptic orbit, then it has at least k + 1 hyperbolic orbits.

Proof. Under the hypothesis of the theorem, Juhász [Ju3, Theorem 4] shows that rk HF (-M, -Γ) ≥ 2 k+1 . By Conjecture 4.3, the ECH chain complex must have rank ≥ 2 k+1 . When there are no elliptic orbits, this implies the existence of at least k + 1 hyperbolic orbits for R λ .

Note that every Reeb vector field can be perturbed so that it only has hyperbolic orbits up to a certain action threshold L [CGH1, Theorem 2.5.2] and the number of hyperbolic orbits seems to go to ∞ as L → ∞ whenever there is an elliptic orbit to start with. 4.2.4. Nonvanishing of contact invariants. One of the central tools in recent years has been the following: Theorem 4.10 (Ozsváth-Szabó [START_REF] Ozsváth | Holomorphic disks and genus bounds[END_REF]). If (M, ξ) is a symplectically semi-fillable contact structure, then the contact invariant c(ξ) in HF (M ; F[H 2 (M ; Z)]) with respect to "twisted coefficients" is nonzero. In particular, it is the case when ξ is the deformation of a taut foliation.

This result contrasts with the fact that c(ξ) = 0 when ξ is overtwisted.

Proof. We explain how to prove Theorem 4.10 in the equivalent setting of ECH, assuming the existence of cobordism maps that are defined on the chain level and count J-holomorphic curves. This is work in progress of Jacob Rooney [Ro].

Let (W, dβ) be a symplectic semi-filling of (M, ξ) such that ∂W = (M, ξ) (M , ξ ). The semi-filling W , together with an adapted almost complex structure J on W , induces a cobordism map

Φ : ECC(M ) ⊗ ECC(M ) → ECC(∅) F,
where ECC denotes the ECH chain complex; it satisfies Φ∂ = 0 since ∂Φ = 0. Recall that the contact class c(ξ) is represented by the empty set ∅ of orbits; Φ is defined so it satisfies Φ(∅ ⊗ ∅) = ∅. If c(ξ) = 0, then there exists x ∈ ECC(M ) such that ∂x = ∅. Then

Φ∂(x ⊗ ∅) = Φ(∅ ⊗ ∅) = ∅, which contradicts Φ∂ = 0.
Using the same circle of ideas, Ozsváth-Szabó [START_REF] Ozsváth | Holomorphic disks and genus bounds[END_REF] showed that if M admits a taut foliation, then rk HF (M ) > |H 1 (M ; Z)|, i.e., M is not an L-space, leading to the following conjecture [START_REF] Boyer | On L-spaces and left-orderable fundamental groups[END_REF][START_REF] Juhàsz | A survey of Heegaard Floer homology[END_REF]: Conjecture 4.11. A closed rational homology 3-sphere M carries a taut foliation if and only if M is not an L-space.

It is also conjectured that the existence of a taut foliation is equivalent to the left-orderability of π 1 (M ) for a rational homology sphere M . In one direction, Calegari-Dunfield [CD, Corollary 7.6] showed that the existence of a taut foliation on a atoroidal manifold implies the left-orderability of π 1 of a finite cover of M . Problem 4.12. Find a relationship between contact geometry and the left-orderability of π 1 (M ). Problem 4.13. Show that if M is Haken and ξ is a contact structure on M , then rk( ECH(M, ξ)) ≥ 2. One might want to find tight contact structures with nonvanishing contact class; see Problem 3.21. 4.3. Cylindrical contact homology of sutured manifold. In this subsection, we prove another contact characterization of product sutured manifolds: Theorem 4.14. A taut balanced sutured manifold (M, Γ) is not a product if and only if it carries an adapted hypertight contact form whose cylindrical contact homology has rank ≥ 1.

First recall from [CGHH] that when (M, Γ, U (Γ), ξ = ker λ) is a sutured contact manifold, we can define its vertical completion by gluing

• ([1, +∞) × R + (Γ), dt + λ| R + (Γ) ) to (M, λ) along R + (Γ) = {1} × R + (Γ) and • ((-∞, -1] × R -(Γ), dt + λ| R -(Γ) ) to (M, λ) along R -(Γ) = {1} × R -(Γ).
Proof. If (M, Γ) is a taut balanced sutured manifold, then it admits a sutured manifold hierarchy by Gabai [START_REF] Gabai | Foliations and the topology of 3-manifolds[END_REF] and carries a hypertight contact structure by Theorem 3.13; this is obtained from the product sutured contact manifold by successive gluing. By Theorem 4.1 we know that, at each gluing step of the hierarchy, the cylindrical contact homology of the previous piece injects into the cylindrical contact homology of the next one.

In order to prove the theorem, it suffices to show that gluing step corresponding to the decomposition (P , Γ ) S (P, Γ), where (P, Γ) is a product and (P , Γ ) is not a product, produces (P , Γ , ξ ) with nontrivial cylindrical contact homology. We first give a brief description of the gluing step: Let (P, Γ, ξ) be a product sutured contact manifold with contact form dt + λ where

P = [-1, 1] t × R and R ± (Γ) = {±1} × R = {±1} × R ± (Γ).
Let S ± be a compact subsurface with corners in R ± (Γ) such that ∂S ± is the concatenation of arcs a

1 ± , b 1 ± , . . . , a k ± , b k ± in (cyclic) order, where int(a i ± ) ⊂ int(R ± (Γ)) and b i ± ⊂ ∂R ± (Γ). Let φ : S + ∼ → S -be a diffeomorphism with φ(a i + ) = b i -and φ(b i + ) = a i -.
Then, modulo some adjustments to the contact form that we need to make near S + and S -, we can glue (P, Γ, ξ) along S + and S -using φ and apply smoothing operations to obtain the sutured contact manifold (P , Γ , ξ ); see [CGHH].

Another way to construct (P , Γ , ξ ) is as follows and is described in detail in [CGHH, Section 4.3, Steps 1-4]:

(1) Glue (P, Γ, ξ) along S + and S -using φ.

(2) Glue ([1, 3]×(R + (Γ)\S + ), dt+λ| R + (Γ) ) to the result of (1) by identifying

{1} × (R + (Γ) \ S + ) and {1} × (R + (Γ) \ S + ) [1, 3] × a + and [-1, 1] × b -,
where we are writing

a ± = ∪ k i=1 a k ± and b ± = ∪ k i=1 b k ± .
(3) Iterate the process to glue fibered pieces

([2n + 1, 2n + 3] × (R + (Γ) \ int(S + )), dt + λ| R + (Γ) ), n ≥ 1 ([-2n -1, -2n + 1] × (R -(Γ) \ int(S -)), dt + λ| R -(Γ) ), n ≥ 1.
This leads us to the vertical completion

(P ∞ , Γ ∞ , ξ ∞ ) of (P , Γ , ξ ); see Fig- ure 1. S ∞ [-1, 1]× S ∞ \ R + (Γ) FIGURE 1. The construction of S ∞
The noncompact surface S ∞ ⊂ P ∞ given by

S ∞ = ({1} × R) ∪ (∪ n≥1 {2n + 1} × (R + (Γ) \ int(S + ))) ∪ (∪ n≥1 {-2n -1} × (R -(Γ) \ int(S -)))
divides (P ∞ , Γ ∞ , ξ ∞ ) into a noncompact sutured manifold (P ∞ , Γ ∞ , ξ ∞ ), which is an horizontal extension of (P, Γ, ξ) by product pieces. Conversely,

(P ∞ , Γ ∞ , ξ ∞ ) is obtained from (P ∞ , Γ ∞ , ξ ∞ ) by gluing R + (Γ ∞ ) S ∞ to R -(Γ ∞ ) S ∞ by a diffeomorphism φ ∞ : S ∞ ∼ -→ S ∞ .
An analysis of the situation shows that the surface S ∞ is an end-periodic surface and φ ∞ an end-periodic diffeomorphism of S ∞ . We refer to [Fe] for precise definitions. End-periodic diffeomorphisms of end-periodic surfaces have a Thurston-Nielsen theory which was discovered by Handel-Miller, described by Fenley [Fe], and developed by Cantwell-Conlon [CC].

In our case, the relevant fact is the following:

Fact 4.15. If (P ∞ , Γ ∞ ) -or equivalently its compactification (P , Γ ) -is not a product, then φ ∞ : S ∞ ∼ -→ S ∞ is isotopic to an end-periodic homeomorphism ψ ∞ : S ∞ ∼ -→ S ∞ which has a finite number of periodic points of minimum period, say k, and with nonzero total Lefschetz number in their Nielsen classes.

Briefly, if indeed (P ∞ , Γ ∞ ) is not a product, then φ ∞ is not isotopic to a translation and there exist ψ ∞ isotopic to φ ∞ and a pair of geodesic laminations Λ + , Λ -⊂ S ∞ with nonempty intersection [START_REF] Cantwell | End periodic automorphisms of surfaces and foliations[END_REF]Proposition 4.28] that are preserved by ψ ∞ [CC, Theorem 4.54], such that:

(1) The dynamical system (2) There is a union P + (resp. P -) of components of

ψ ∞ : Λ + ∩ Λ -→ Λ + ∩ Λ -
S ∞ \ Λ + (resp. S ∞ \ Λ -)
such that all the points of S ∞ \ (Λ + ∪ P + ) (resp. S ∞ \ (Λ -∪ P -)) belong to the "negative (resp. positive) escaping set" and hence are not periodic points [CC, Lemma 5.15]. There exists a compact region of the form cl(Q + ∩ Q -), where Q ± is a component of P ± (this is called a nucleus [CC, Definition 6.41]), whose piecewise smooth boundary alternates between arcs of Λ + and arcs of Λ -and which is left invariant by some

ψ k ∞ . If cl(Q + ∩ Q -)
is a rectangle, then there is a hyperbolic orbit which is isolated in its Nielsen class. Otherwise we apply the Thurston-Nielsen decomposition to

(cl(Q + ∩Q -), ψ k ∞ ).
If there is a pseudo-Anosov component, then there are infinitely many Nielsen classes with nonzero total Lefschetz number. If all the components are periodic, at least one component has negative Euler number, again giving rise to a Nielsen class with nonzero total Lefschetz number.

In particular, in every such Nielsen class, φ ∞ itself has periodic points with nonzero total Lefschetz number. Those periodic points correspond to closed orbits of a Reeb vector field that intersects S ∞ k times. The differential in cylindrical contact homology counts holomorphic cylinders, and hence preserves the splitting of the orbits into Nielsen classes. Moreover, the total Lefschetz number in a Nielsen class corresponds to the Euler characteristic of the corresponding subcomplex, so every Nielsen class with nonzero Lefschetz number gives at least one generator in cylindrical contact homology.

Conversely, if (M, Γ) is a product sutured manifold and if a contact structure ξ adapted to (M, Γ) has a well-defined cylindrical contact homology, then ξ is tight by Hofer [Hof]. Since (M, Γ) is product disk decomposable, we can normalize the contact structure on a collection of compressing disks and apply Eliashberg's classification of tight contact structures on the remaining ball [START_REF] Eliashberg | Contact 3-manifolds twenty years since Jean Martinet's work[END_REF] to show that there is a unique tight contact structure adapted to (M, Γ), namely the [-1, 1]invariant one. Hence ξ has a Reeb vector field without periodic orbits and its cylindrical contact homology is trivial.

Remark 4.16. The above proof allows us to estimate the size of HC(M, Γ, ξ) depending on φ ∞ . For example, if φ ∞ is reducible with a pseudo-Anosov component, then rk HC(M, Γ, ξ) = ∞ and the rank of the subspace generated by orbits of action less than L > 0 grows exponentially with L.

Problem 4.17. Use this presentation via end-periodic diffeomorphisms of endperiodic surfaces to give a direct proof of Corollary 4.6, i.e., if (M, Γ) is not a product, then rk ECH(M, Γ, ξ) ≥ 2, where one of the generators is the empty set of orbits. The difference with the previous case is that the ECH differential counts curves with genus that might not preserve Nielsen classes. Problem 4.18. Show that a hypertight contact structure on a closed hyperbolic 3-manifold has infinite rank cylindrical contact homology and that the rank of the subspace of its contact homology generated by orbits of action less than L > 0 grows exponentially with L. See Problem 3.6.

FROM CONTACT STRUCTURES TO FOLIATIONS

As we have already seen, a taut foliation F without sphere leaves can be approximated by a positive and a negative contact structure ξ + and ξ -. Both are used to construct a weak filling and thus prove the nonvanishing of the contact invariant.

In [CF], the first author and Firmo studied the converse construction, based on prior results of Eliashberg-Thurston [ET] and Mitsumatsu [Mi]. Since the contact structures approximate the same foliation, they are C 0 -close to each other, and in particular they have a common positively transverse vector field.

This motivates the following definition:

Definition 5.1. A contact pair is a pair (ξ + , ξ -) consisting of a positive contact structure ξ + and a negative contact structure ξ -such that there exists a nonvanishing vector field Z which is positively transverse to both ξ + and ξ -.

A contact pair is tight if both ξ + and ξ -are tight.

In particular, if ξ + and ξ -are everywhere transverse, then (ξ + , ξ -) is a contact pair.

Let (ξ + , ξ -) be contact pair. Generically ξ + and ξ -are transverse to each other away from a link ∆ in M , on which they coincide as oriented 2-planes. One can further normalize ξ + and ξ -on a neighborhood of ∆ so it becomes a normal contact pair; see [CF, Section 2.3] for the definition and [CF, Prop. 2.1] which shows that any contact pair can be isotoped into a normal one. In particular, for a normal pair, the link ∆ is transverse to ξ ± away from a finite number of points.

If α ± is a contact form for ξ ± , then the smooth vector field X ∈ ξ -given by

i X dα -| ξ -= α + | ξ -
directs ξ + ∩ ξ -and is zero along ∆. For x ∈ M and t ∈ R, denote by φ t (x) the image of x by the time-t flow of X.

Lemma 5.2 ([CF]

). If (ξ + , ξ -) is a normal contact pair on a closed 3-manifold M , then the plane fields λ t ± (x) := (φ t ) * ξ ± (φ -t (x)) limit to a common plane field λ as t → +∞. Moreover λ is continuous and invariant by the flow of the smooth vector field X.

The plane field λ is then locally integrable, but not uniquely since λ is only continuous.

Problem 5.3. Try to improve λ so it becomes a genuine foliation. One possible approach is to apply the work of Burago-Ivanov [BI] to prove that λ gives a branching foliation, in which case it could always be deformed into a genuine foliation.

The integral leaves of λ nevertheless reflect the properties of ξ + and ξ -.

Proposition 5.4 ( [CF]). If (ξ + , ξ -) is a normal tight contact pair on a closed 3manifold M , then λ has no integral 2-sphere.

Moreover, we have: Theorem 5.5 ( [CF]). Let (ξ + , ξ -) be a normal tight contact pair on a closed 3manifold M . If λ is uniquely integrable, then the integral foliation F of λ does not contain a Reeb component whose core c is zero in H 1 (M ; Q). Moreover, M carries a Reebless foliation.

Remark 5.6. Conversely, if the integral foliation F of λ is taut, then the structures ξ ± are universally tight, since they can be deformed continuously to F. Problem 5.7. Show that under the hypotheses of Theorem 5.5, the foliation F has no Reeb components (even when 0 = [c] ∈ H 1 (M ; Q)).

A contact pair (ξ + , ξ -) is strongly tight if any two points in M can be joined by an arc that is positively transverse to both ξ + and ξ -. This condition is equivalent to the property that any two points in M can be joined by an arc positively transverse to λ.

Suppose (ξ + , ξ -) is strongly tight. If λ is uniquely integrable, then its integral foliation F is taut and ξ + and ξ -are universally tight and semi-fillable. The key step in the construction of a semi-filling is the existence of a closed 2-form ω, called a dominating 2-form, which satisfies ω| F > 0. The usual construction of a dominating 2-form ω (i.e., summing well-chosen Poincaré duals ω γ supported on small tubular neighborhoods of closed transversals γ to ξ ± ) works even when λ is not integrable. Hence ξ + and ξ -are semi-fillable even when λ is not assumed to be uniquely integrable.

In certain situations, one can prove the integrability of λ and derive strong constraints, as in this version of the Reeb stability theorem.

Theorem 5.8 ( [CF]). Let M be a compact connected oriented 3-manifold with ∂M = S 2 . If M carries a normal tight contact pair (ξ + , ξ -) such that

(1) ∆ intersects ∂M transversely in two points N and S and

(2) X exits transversely from M along ∂M \ {N, S}, then M B 3 . The proof of Theorem 5.8 relies on the fact that, under the assumptions of the theorem, the foliation λ is integrable and the leaves are disks. Problem 5.9. Show that if M carries a tight contact pair, then it is irreducible.

In general, it is not easy to verify the condition in the definition of a contact pair that ξ + and ξ -have a common transverse vector field Z.

Problem 5.10. Let ξ + be a positive contact structure and ξ -be a negative contact structure such that ξ + and ξ -are homotopic as plane fields. Can one isotop ξ -to ξ -so that (ξ + , ξ -) is a contact pair? Can this be done with parameters?

The parametric version of Problem 5.10 can be solved on the ball, where it is in fact equivalent to Cerf's theorem or Hatcher's theorem: Let ζ 0,+ and ζ 0,-be the standard contact structures on the unit ball B 3 , with equations dz ± r 2 dθ = 0 in cylindrical coordinates. In this case X = r∂ r and λ = {dz = 0}. Now take a diffeomorphism φ of B 3 which is the identity on the boundary and consider ξ 1,± = φ * ξ 0,± . By Eliashberg [START_REF] Eliashberg | Contact 3-manifolds twenty years since Jean Martinet's work[END_REF], we know that the space of (positive or negative) tight contact structures on B 3 that agree with ξ 0,± along ∂B 3 is contractible, so we can find paths of contact structures ξ t,± , t ∈ [0, 1], from ξ 0,± to ξ 1,± . If we could make (ξ t,+ , ξ t,-) into a path of contact pairs by deforming ξ t,-, this would immediately give a path λ t of integral foliations by disks from λ 0 to λ 1 and then, by standard arguments, an isotopy from φ to the identity, i.e., an alternative proof of Cerf's theorem -and with more parameters, a proof of Hatcher's theorem. On the other hand, we know that such a deformation is possible: it can be constructed by an application of Hatcher's theorem.

  Conjecture 4.3. If (M, Γ, ξ = ker α) is a sutured contact manifold, then ECH(M, Γ, ξ, A) HF (-M, -Γ, s ξ + P D(A)).

  is conjugate to a two-sided Markov shift of finite type [CC, Theorem 9.2].

  Problem 5.11. Prove Hatcher's theorem using the parametric version of Problem 5.10. Problem 5.12. Try to use families of contact pairs to solve Problem 3.7.

VC supported by ANR Quantact and KH supported by NSF Grants DMS-1406564 and DMS-1549147.


Huy Duong

Brigitte Jaumard
email: bjaumard@cse.concordia.ca

David Coudert
email: david.coudert@inria.fr

Ron Armolavicius

Efficient Make Before Break Capacity Defragmentation

Keywords: Network reconfiguration, rerouting, defragmentation, make-before-break

Optical multilayer optimization continuously reorganizes layer 0-1-2 network elements to handle both existing and dynamic traffic requirements in the most efficient manner. This delays the need to add new resources for new requests, saving CAPEX and leads to optical network defragmentation. The focus of this paper is on Layer 2, i.e., on capacity defragmentation at the OTN layer when routes (e.g., LSPs in MPLS networks) are making unnecessarily long detours to evade congestion. Reconfiguration into optimized routes can be achieved by re-defining the routes, one at a time, so that they use the vacant resources generated by the disappearance of services using part of a path that transits the congested section. For the Quality of Service, it is desirable to operate under Make Before Break (MBB), with the minimum number of rerouting. The challenge is to identify the rerouting order, one connection at a time, while minimizing the bandwidth requirement. We propose an exact and scalable optimization model for computing a minimum bandwidth rerouting scheme subject to MBB in the OTN layer of an optical network. Numerical results show that we can successfully apply it on networks with up to 30 nodes, a very significant improvement with the state of the art. We also provide some defragmentation analysis in terms of the bandwidth requirement vs. the number of reroutings.

I. INTRODUCTION

Network reconfiguration is required in order to adapt to traffic changes, network failures, or new deployment of network resources. It occurs at the optical layer in order to make sure that the upper layer traffic, e.g., IP layer traffic, can be efficiently carried. In such a case, we deal with lightpath reconfigurations and the primary objective is to reduce disruptions to user traffic carried by existing lightpaths, measured by the number of disrupted lightpaths or the duration of lightpath disruptions [START_REF] Li | Survey of WDM network reconfiguration: topology migrations and their impact on service disruptions[END_REF]. Network reconfiguration may also appear in the OTN (Optical Transport Network) layer, in order to attain a better resource utilization [START_REF] Józsa | On the solution of reroute sequence planning problem in MPLS networks[END_REF]. In heavily loaded networks, dynamic connection addition and drop actions may result in a set of connections where some paths are not the shortest possible ones, leading to poor resource utilization compared to an optimal or at least optimized state. Thus, global connection re-optimization is proposed at certain time intervals (e.g., daily, weekly) to improve the network performance.

Researchers have investigated this connection reoptimization along two directions. In the first one, it consist in computing an optimized provisioning, and then find a sequence of connection rerouting in order to migrate from the current network provisioning to the optimized one with the minimum number of disruptions. In the second direction, the idea is to compute the best rerouting that allows moving away from the current provisioning with no disruption. While many studies have investigated the first direction, very few looked at the second one. In this paper, we propose to explore the second direction, and propose a scalable optimization model and algorithm in order to reach the best possible network provisioning subject to no disruptions, i.e., under the so-called Make Before Break (MBB) paradigm.

The paper is organized as follows. We briefly review the related papers to defragmentation in the OTN layer, in the next section (Section II), as well as the model of Klopfenstein [START_REF] Klopfenstein | Rerouting tunnels for MPLS network resource optimization[END_REF], which is the only previously proposed optimization model for rerouting subject to MBB. We next describe in Section III our proposed decomposition model, called DEFRAG RC, which requires in practice a much smaller number of variables and constraints than the model of Klopfenstein [START_REF] Klopfenstein | Rerouting tunnels for MPLS network resource optimization[END_REF]. In Section IV, we explain how to solve efficiently the proposed DEFRAG RC model with the DEFRAG MBB algorithm, which contains a polynomial algorithm for the generation of the rerouting configurations. Numerical results are presented in Section V. Conclusions are drawn in the last section.

II. STATE OF THE ART

Note that we focus on Layer 2, while being aware that a lot of work has been recently made on Layer 0 in the context of flexible optical networks. But capacity defragmentation differs from spectrum defragmentation as there is no need to take care of continuity or contiguity constraints, and therefore we omit references related to Layer 0.

A. Literature Review

Several studies have been devoted to network reconfiguration with the minimum number of disruptions, following the strategy of migrating from a legacy ineffective routing to a given optimized one. These studies usually have the constraint that a request can be rerouted at most once (i.e., from legacy to optimized route), together with the requirement of finding an optimized rerouting that is as close as possible to the legacy one. As a result, it usually prevents the existence of a strategy using only MBB due to the presence of dependency cycles (e.g., request k 1 needs to be rerouted before k 2 because a link of the new route of k 2 belongs to the current route of k 1 , and for similar reasons, k 2 needs to be rerouted before k 1 ). In order to find a rerouting strategies, authors have proposed to use the break-before-make (BBM) paradigm that allows for the temporary interruption of requests, and so breaking dependency cycles. For instance, Jose and Somani [START_REF] Jose | Connection rerouting/network reconfiguration[END_REF] propose heuristics for minimizing the total number of BBMs used in the rerouting strategy, and Coudert et al. [START_REF] Coudert | Reconfiguration of the routing in WDM networks with two classes of services[END_REF], [START_REF] Coudert | Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth[END_REF] and Solano and Pióro [START_REF] Solano | Lightpath reconfiguration in WDM networks[END_REF] provide scalable exact algorithms to minimize the concurrent number of BBMs. Tradeoffs between these two conflicting objectives are investigated by Cohen et al. [START_REF] Cohen | Tradeoffs in process strategy games with application in the WDM reconfiguration problem[END_REF] and Solano [START_REF] Solano | Analyzing two conflicting objectives of the WDM lightpath reconfiguration problem[END_REF]. To further reduce the total or concurrent number of BBMs, Kadohata et al. [START_REF] Kadohata | Wavelength path reconfiguration design in transparent optical WDM networks[END_REF] propose to use spare wavelengths to reroute a request to a temporary route rather that using a BBM. Said differently, they save one BBM by performing two MBBs. The network reconfiguration problem has also been investigated in logical layers, e.g., for MPLS networks [START_REF] Beker | Off-line MPLS layout design and reconfiguration: Reducing complexity under dynamic traffic conditions[END_REF], [START_REF] Coudert | On rerouting connection requests in networks with shared bandwidth[END_REF], [START_REF] Józsa | On the solution of reroute sequence planning problem in MPLS networks[END_REF], with the same constraints and objectives as above. On the other hand, while many studies have investigated rerouting strategies both at the optical and the logical layer, very few studies have considered rerouting subject to the MBB paradigm (i.e., joint computation of optimized routing and rerouting strategy subject to MBB). Klopfenstein's study [START_REF] Klopfenstein | Rerouting tunnels for MPLS network resource optimization[END_REF] is the only one proposing an optimization model, but unfortunately it is not scalable. We recall it in the next section as an introduction for our decomposition model in Section III.

B. Notations

We consider a network represented by a directed multigraph G = (V, L) where V is the set of nodes (indexed by v) and L is the set of links (indexed by ). Different links may exist between two nodes in order to model different logical links, with e.g., different types of traffic. We denote ω -(v) (resp. ω + (v)) the set of incident links incoming to (resp. outgoing from) node v ∈ V . Let C denote the transport capacity of link . Let K be the set of connection requests (indexed by k). Connection request k ∈ K is characterized by its source (s k ), destination (d k ), and bandwidth requirement (b k ).

We assume that the network undergoes a series of connection request re-optimization at different time stamps (rerouting events). Let T (indexed by t) be the set of those time stamps, with t = 0 being the initial one.

C. Klopfenstein's Model (2008)

The model of Klopfenstein [START_REF] Klopfenstein | Rerouting tunnels for MPLS network resource optimization[END_REF] consists in finding the best possible rerouting, while guaranteeing it can be reached within a Make Before Break (MBB) policy. Indeed, Klopfenstein [START_REF] Klopfenstein | Rerouting tunnels for MPLS network resource optimization[END_REF] proposed a very general network resource utilization function subject to a parameter α and that can be written as follows:

OBJ α = 1 1 -α ∈L C - link load k∈K b k x k 1-α , (1)
There are two particular cases of interest, for which the objective (1) is a linear function:

• α = 0, the objective consists then in maximizing the overall spare capacity:

max OBJ 0 = ∈L C - ∈L b k k∈K x k (2)
• α = ∞, the objective consists then in maximizing the smallest link spare capacity,

max min ∈L C - k∈K b k x k . (3)
In the sequel, we will adopt OBJ 0 . The set of variables is defined as follows: -x t k = 1 if demand k uses link in its routing at step t, 0 otherwise. -π t k = 1 if demand k is rerouted at step t, 0 otherwise. These objectives and variables are decided by a set of below constraints:

∈ω -(v) x t k - ∈ω + (v) x t k =    -1 if v = s k 1 if v = d k 0 otherwise k ∈ K, v ∈ V, t ∈ T (4) k∈K x t k b k ≤ C ∈ L, t ∈ T (5) k∈K π t k ≤ 1 t ∈ T (6)
x t k -x t-1 k ≤ π t k k ∈ K, ∈ L, t ∈ T (7) x t k ∈ {0, 1} k ∈ K, ∈ L, t ∈ T (8) π t k ∈ {0, 1} k ∈ K, t ∈ T. (9)
Constraints ( 4) are flow constraints and used in order to establish a route for each request, at each time period. Due to the subsequent constraints, the set of paths at time t will differ by at most one path from time t -1. Constraints (5) enforce the transport capacity constraints. Constraints [START_REF] Coudert | Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth[END_REF] impose that at most one request per step is rerouted. Constraints [START_REF] Solano | Lightpath reconfiguration in WDM networks[END_REF] are redundant if π t k = 1, i.e., if request k is rerouted at step t so that the routing variables x t k can be redefined, and otherwise impose that x t-1 k = x t k , i.e., that routing is not modified. Indeed, note that if there is a rerouting, the two reroutings (legacy vs. optimized) must differ by at least one added and one dropped link. If π t k = 0, this is not allowed as

x t-1 k -x t k ≤ 0, and consequently x t-1 k = x t k .
The last two sets of constraints define the domain of the variables. Note that if the rerouted path has a link in common with the original one, there is no need to double the capacity reservation corresponding to the considered demand [START_REF] Klopfenstein | Rerouting tunnels for MPLS network resource optimization[END_REF]. Largest data instance on which experiments were conducted in [START_REF] Klopfenstein | Rerouting tunnels for MPLS network resource optimization[END_REF]: a network with 10 nodes and about 40 links with capacity C . Authors were not able to obtain optimal solutions for more than 5 reroutings within the time limit imposed (30 minutes).

III. A DECOMPOSITION MODEL: DEFRAG RC

In this section, we propose a decomposition model, called DEFRAG RC, based on a set of rerouting operations, where each rerouting operation proposes a potential MBB rerouting of a single connection request, i.e., a connection request for which there exists an alternate route with enough spare

k∈K p∈P t k z t kp ≤ 1 t ∈ T (11) t∈T p∈P t k z t kp ≤ 1 k ∈ K (12) C t ≤ C ∈ L, t ∈ T (13) C t = C t-1 - k∈K p∈P t k b k (a 0 k -δ p )z t kp ∈ L, t ∈ T (14) C t ≥ 0 ∈ L, t ∈ T (15) z t kp ∈ {0, 1} k ∈ K, t ∈ T, p ∈ P t k (16) (Restricted) Master problem, RMP Minimize c PPt = -u (11) t - k∈K u (12) k π k - ∈L k∈K b k u (14) t (π k a 0 k -α k ) (17) s.t.: ∈ω -(v) α k - ∈ω + (v) α k =    -π k if v = s k π k if v = d k 0 otherwise k ∈ K, v ∈ V (18) ∈ω + (v) α k ≤ 1 k ∈ K, v ∈ V (19) α k ≤ π k k ∈ K, ∈ L (20) k∈K π k = 1 (21) α k ∈ {0, 1} k ∈ K, ∈ L (22) π k ∈ {0, 1} k ∈ K. ( 23
)
Pricing problem, PP t Observe that less than |T | rerouting operations might be sufficient to reach that optimized provisioning. The objective is to minimize the bandwidth requirements of the provisioning at time |T |. Observe that there is no guarantee to reach the best provisioning with a monotonous sequence, i.e., such that the overall bandwidth requirement decreases after each single rerouting operation (of a connection request). It may happen that the overall bandwidth requirement increases after a given rerouting operation in order to reach the minimum bandwidth provisioning at a later time, or at time |T |.

Let P be the overall set of potential rerouting operations, with P = k∈K t∈T P t k , where P t k is the set of routes of connection request k ∈ K at time stamp t ∈ T .

The integer linear programming (ILP) formulation of DE-FRAG RC uses the following variables:

-

z t kp = 1 if route p ∈ P t k is selected at time stamp t ∈ T for the rerouting of k ∈ K, 0 otherwise. -C t = required bandwidth on link ∈ L at time stamp t ∈ T .
It also uses the following parameters: -

a 0 k = 1 if link ∈ L is used in the initial routing of connection request k ∈ K, 0 otherwise. -C 0 = k∈K b k a 0 k = initial bandwidth usage on link ∈ L. -δ p = 1 if path p ∈ P uses link ∈ L, 0 otherwise.
Objective: maximize the spare capacity

max ∈L C -C |T | . (24)
As ∈L C is a constant value, the objective can be re-expressed as minimizing the bandwidth usage:

[DEFRAG RC] min ∈L C |T |
subject to ( 11)-( 16).

Constraints [START_REF] Beker | Off-line MPLS layout design and reconfiguration: Reducing complexity under dynamic traffic conditions[END_REF] in Figure 1 prevent from selecting more than one rerouting operation at each time period. Note that |T | ≤ |K| is an upper bound on the number of rerouting operation as we cannot predict a priori the number of required MBB reroutings. Constraints [START_REF] Coudert | On rerouting connection requests in networks with shared bandwidth[END_REF] ensure that a connection request is rerouted at most once. Constraints (13) make sure that transport capacities are never exceeded at any time stamp. Constraints (14) update the bandwidth usage on link at time stamp t, taking into account the unique connection request that has been rerouted at t. Constraints (15)-( 16) define the domain of the variables.

IV. SOLUTION PROCESS: THE DEFRAG MBB ALGORITHM

The model DEFRAG RC has an exponential number of variables, and therefore column generation is required in order to efficiently solve its linear relaxation. This technique consists of decomposing the original problem into a Restricted Master Problem -RMP -(i.e., model ( 10)-( 16) with a very restricted number of variables) and one or several pricing problems -PPs. In the particular case of model ( 10)-( 16), we will show in next section that the pricing problem can be decomposed into |K| × |T | independent smaller pricing problems, each denoted by PP k t . The RMP and the PP(s) are solved alternately. Solving the RMP consists in selecting the best connection reroutings, while solving the PPs allows the generation of improving potential reroutings, i.e., such that, if added to the current RMP, improve the optimal value of its linear relaxation. The process continues until the optimality condition is satisfied, that is, all the so-called reduced costs defining the objective function of the pricing problems are positive. An ε-optimal solution is derived by solving exactly the ILP model associated with the last RMP, with ε defined as follows:

ε = (z ILP -z LP ) /z LP , (25)
where z LP and zILP denote the optimal LP value and the optimal ILP value of the last RMP, respectively.

Pricing Problem, PP t Let u (11) t ≤ 0, u (12) k ≤ 0 and u (14) t 0 be the values of the dual variables associated with Constraints ( 11), ( 12) and ( 14), respectively. We use the following binary variables:

-π k = 1 if k ∈ K is selected for rerouting, 0 otherwise. -α k = 1 if π k = 1 and the route of k ∈ K uses link ∈ L, 0 otherwise.
The goal of PP t is to select a unique request for potential rerouting, the one with a new route of minimum cost (Objective (17) in Figure 1). Constraints (18) take care of identifying the best possible route, using flow constraints, for the request that is rerouted, i.e., the unique request k such that π k = 1.

Constraints
where c k PPt denotes the reduced cost of PP k t :

min c k PPt = 0 -u (11) t -u (12) k - ∈L b k u (14) t (a 0 kl -α k ) (27)
subject to:

∈ω -(v) α k - ∈ω + (v) α k =    -1 if v = s k 1 if v = d k 0 otherwise , v ∈ V (28) ∈ω + (v) α k ≤ 1 v ∈ V (29) α k ∈ {0, 1} k ∈ K, ∈ L. ( 30
)
Now, observe that PP k t is a weighted shortest simple path problem in a graph with possibly negative weight cycles. This problem is NP-hard by a reduction from the longest simple path problem (see [START_REF] Cormen | Introduction to Algorithms[END_REF]Section 24.1]), and so cannot be solved using only the Bellman-Ford-Moore (BFM) algorithm, even if it takes care of the negative weights. However, we can still use the BFM algorithm, but with some additional tool. As we cannot enforce the simple path condition, the BFM algorithm may fail to output a path with a negative reduced cost, due to the discovery of a negative cycle. In such a case, we then recourse to the solution of the ILP formulation of PP k t (( 27)-( 30)), which includes constraints to enforce the simple path condition. While we did encounter negative loops, it was quite rare and the solution of pricing problems with an ILP solver did not hamper much the overall computational times. It is worth noting that calls to the BFM algorithm can be grouped by sources. So |V | calls to BFM suffice to solve PP t . Proof: Note that the reduced cost in (27) can be rewritten:

c k PPt = -u (11) t -u (12) k - ∈L b k u (14) t a 0 kl constant + ∈L b k u (14) t α k . ( 31
)
This entails that the solution of PP k t can be reduced to the solution of:

[PP generic kt ] min ∈L u (14) t ϕ subject to: (28) -(30).
Observe that problem PP generic tk is equivalent to a shortest simple path problem with negative weights, without any guarantee that it contains no negative cycles. Taking into account that (i) the coefficients of the objective function are independent of k, and (ii) the BFM algorithm can be easily modified in order to output a shortest path tree from a given source node, see, e.g., [START_REF] Cormen | Introduction to Algorithms[END_REF], (i.e., it computes all the (weighted) shortest paths from a given source node), we can then use |V | calls of the BFM algorithm, one from each possible source node, for a given t. Then, for each connection k, we can compute c k PPt using (31) and check whether the reduced cost is negative, and, if so, generate a new potential rerouting.

Solution Process

In order to be done efficiently, the solution of the |K| Elementary Pricing Problem (PP k t ) for a given t require their grouping as seen in the previous paragraph. In the context of a column generation model with a large set of different pricing problems, the efficiency of the solution depends on the best combination of linear program re-optimization (i.e., solution of the current Restricted Master Problem), and the solution of the whole set or a subset of pricing problems. We solve all the elementary PP k t associated with a given t, and add to the RMP the rerouting associated with the smallest reduced cost. We then perform a round robin on t.

V. NUMERICAL RESULTS

A. Data Sets

We consider a network with 32 nodes and 250 directed links, which corresponds approximately to a Ciena customer network. Existing network connections were used to construct a traffic matrix input to a simulation generating realistic random connection states. Connection requests had Poisson arrivals based on the traffic matrix and random durations drawn from a common exponential distribution. Each connection had a Weibull distributed bandwidth with a coefficient of variation of 0.3. Connections were routed on the shortest path (in hop count) that had sufficient bandwidth. A load factor parameter was used to globally vary the connection arrival rates: the corresponding equilibrium connection states represent a range of congestion levels from light to heavy. For each load factor, we considered 10 defragmentation events. Defragmentation was performed with a period of 1 mean connection duration ensuring that sufficient connection requests and termination events occurred to produce comparably degraded pre-fragmentation connection states. Characteristics of the data sets are described in Table I, where for each load factor, we provide the average number of granted requests right before each defragmentation. We compared the performance of our model and algorithm with the model of Klopfenstein [START_REF] Klopfenstein | Rerouting tunnels for MPLS network resource optimization[END_REF]. We use a dataset with a load factor of 0.5 as differences were already quite significant for a small load as indicated by the results reported in Table II. Therein, we report the results for each of the 10 defragmentation events. Columns entitled DEFRAG RC correspond to the results obtained with the DEFRAG RC model and DEFRAG MBB algorithm. We observe that although the accuracy of the model of Klopfenstein [START_REF] Klopfenstein | Rerouting tunnels for MPLS network resource optimization[END_REF] is better (i.e., 0% for the data sets with a 0.5% factor), the computing times are significantly larger, indeed about 100 times longer. Moreover, the computing time ratio is increasing with the load factor, that is why we only report the results for a 0.5 load factor. Although our proposed model does not always reach the 0% solution accuracy, the reached accuracy is very good as it is only 0.3% on average. The number of rerouting operations is larger with the model of Klopfenstein [START_REF] Klopfenstein | Rerouting tunnels for MPLS network resource optimization[END_REF] as a consequence of a larger bandwidth saving due to a higher accuracy, but the difference is rather small however (ratio of 1.3 on average).

C. Defragmentation Efficiency

All statistics computed in this section corresponds to averages computed on all 10 defragmentations performed for each loading factor. We first analyze the efficiency of the generation process for rerouting configurations with the results reported in Table III. We observe that, as the traffic load is increasing, then the number of initial reroutings of the initial set of configurations decreases in percentage. This can be explained by the fact that there is less spare capacity, and therefore, the number of rerouting sequences is more limited, and therefore the reroutings to be performed and their ordering is more difficult to identify in a simple greedy algorithm. In terms of the overall number of generated reroutings, note than the number of selected ones is at most |T |. We observe that for the 0.5 load, we reach the minimum bandwidth requirement with around 60 reroutings on average, and with less than 160 reroutings on average for the 0.6 load. In Table IV, we report on the accuracy of the solutions: it is rather stable with |T |, i.e., between 2% and 3%, which is satisfactory taking into account the computational additional cost it would require for getting an optimal solution with a branch-and-price solution, instead of the current solution process. Computational times are also quite reasonable, although too long for a real-time defragmentation operation. However, we expect to reduce them significantly in the near future with the addition of heuristics to speed up the solution process.

D. Defragmentation Performance

We investigated the reduction of the overall bandwidth requirements after each defragmentation, and report in Figure 2 the reduction at each defragmentation event for the two extreme loading factors, i.e., 0.5 and 1.0. As already anticipated with the results of Table IV, increasing |T | for the 0.5 load does not help to reduce further the minimum bandwidth requirement. For the 1.0 load, we get around an additional 5% bandwidth requirement reduction when increasing |T | from 60 to 100, and then again from 100 to 150.

VI. CONCLUSION

We have proposed a new model for progressive defragmentation, i.e., computing a sequence of make before break reroutings leading to the minimum bandwidth requirements. It corresponds to a huge improvement with respect to the previous model proposed by Klopfenstein [3] as it allows to reach up to 150 reroutings in less than a few hours, while the model of [START_REF] Klopfenstein | Rerouting tunnels for MPLS network resource optimization[END_REF] was only scalable for toy problems. We plan to investigate further the proposed model in order that it can handle the case of more than one rerouting per (selected) connection while minimizing the overall number of reroutings.

Fig. 1 :

 1 Fig. 1: Flow chart of decomposition model DEFRAG RC

Theorem 1 :

 1 All pricing problems can be investigated with at most O(|V |) runs of the BFM algorithm, leading to an O |L| × (|K| + |V | 2 ) × |T | time complexity.

  For a given t, computing c k PPt for all k can be done in O(|K| × |L|), once all |V | BFM calls have been made, and each call to BFM requires time O(|V | × |L|), hence the overall complexity O |L| × (|K| + |V | 2 ) × |T | .

Fig. 2 :

 2 Fig. 2: Reduction (%) of bandwidth requirement

  Each PP t can be decomposed into |K| elementary pricing problems PP k t , each examining the option of rerouting request k ∈ K at time period t by setting π k = 1 in PP t . Then, the solution of PP t is given by

	Elementary Pricing Problem PP k t
	c PPt = min

(19) make sure that we only output simple path, with no loops. Constraints (20) make sure that routing variables α k are null if request k is not selected for rerouting during time stamp t, i.e., the time period associated with the PP t pricing problem. Constraints (21) ensure that each PP t selects exactly one connection for potential rerouting at time stamp t. Constraints (22)-(23) define the domain of the variables. k∈K {c k PPt : k is rerouted at time period t},

TABLE I :

 I Characteristics of the data sets

	Load factor	Number of requests
	0.5	777.2
	0.6	894.6
	0.7	951.4
	0.8	971.1
	0.9	993.3
	1.0	1,015.4
	B. Comparison with the Model of Klopfenstein [3]

TABLE II :

 II Comparative results with the model of Klopfenstein[START_REF] Klopfenstein | Rerouting tunnels for MPLS network resource optimization[END_REF]

	Defrag. event	Bandwidth saving DEFRAG RC Klopfenstein [3]	ε	# reroutings DEFRAG RC Klopfenstein [3]	Computing times DEFRAG RC Klopfenstein [3]
	1	3.2%	3.5%	0.3%	5	5	0.1	13.5
	2	7.5%	8.2%	0.1%	13	15	0.2	11.8
	3	9.9%	11.0%	0.0%	15	17	0.1	10.2
	4	2.3%	2.7%	0.8%	6	15	0.2	29.0
	5	9.6%	10.9%	0.7%	14	20	0.1	22.7
	6	12.0%	13.7%	0.5%	16	18	0.3	17.1
	7	6.6%	7.1%	0.2%	13	15	0.2	15.9
	8	3.0%	3.1%	0.4%	5	7	0.1	17.4
	9	6.7%	7.3%	0.3%	10	13	0.1	11.9
	10	5.4%	5.7%	0.0%	7	7	0.1	2.9
	Average	6.6%	7.3%	0.3%	10.40	13.20	0.15	15.2
	Ratio	1.1			1.3		101.3

TABLE III :

 III Impact of the Initial Rerouting Configurations and Overall Number of Configurations

		# Initial configurations	# Initial configurations in optimal solution	Overall # of generated configurations
	Load factor	T = 60	T = 100	T = 150	T = 60	T = 100	T = 150	T = 60	T = 100	T = 150
	0.5	47.6	50.7	50.7	25.7 (42.8%)	25.3	23.6 (25.7%)	1,308.2	2,338.1	3,465.1
	0.6	60	100	132.6	26.0 (43.3%)	46.6	62.2 (26.0%)	1,254.0	2,169.6	3,669.5
	0.7	60	100	150	23.4 (39.0%)	39.0	70.1 (23.4%)	1,187.4	1,956.3	2,782.4
	0.8	60	100	150	21.9 (36.5%)	38.2	65.8 (21.9%)	1,245.5	2,074.3	2,798.7
	0.9	60	100	150	19.1 (31.8%)	33.3	65.9 (19.1%)	1,173.7	1,906.9	2,804.2
	1.0	60	100	150	18.8 (31.3%)	31.6	58.0 (18.8%)	1,274.7	1,996.3	2,806.2

TABLE IV :

 IV Number of Reroutings and Accuracy

		Number of required rerouting		Accuracy (ε)		Computation times (minutes)
	Load factor	T = 60	T = 100	T = 150	T = 60	T = 100	T = 150	T = 60	T = 100	T = 150
	0.5	52.9	62.2	63.5	1.6	2.2	2.2	23.8	36.3	89.1
	0.6	59.6	98.6	139.2	2.1	2.2	2.7	24.3	55.2	316.3
	0.7	59.3	97.0	147.2	2.7	2.8	2.3	22.8	51.8	235.0
	0.8	58.9	97.8	145.9	2.7	2.6	2.6	25.9	57.0	230.5
	0.9	59.6	99.3	147.9	2.2	2.2	2.8	22.4	46.6	263.5
	1.0	59.4	99.6	147.5	2.5	2.1	2.3	26.0	54.3	264.6

ACKNOWLEDGMENTS B. Jaumard has been supported by a Concordia University Research Chair (Tier I). H. Duong was supported by a MITACS & Ciena Converge Fellowship. D. Coudert was supported by ANR program "Investments for the Future" under reference ANR-11-LABX-0031.