Carolina Medina

Jorge L Ramírez-Alfonsín

Gelasio Salazar

On the number of unknot diagrams

Let D be a knot diagram, and let D denote the set of diagrams that can be obtained from D by crossing exchanges. If D has n crossings, then D consists of 2 n diagrams. A folklore argument shows that at least one of these 2 n diagrams is unknot, from which it follows that every diagram has finite unknotting number. It is easy to see that this argument can be used to show that actually D has more than one unknot diagram, but it cannot yield more than 4n unknot diagrams. We improve this linear bound to a superpolynomial bound, by showing that at least 2 3 √ n of the diagrams in D are unknot. We also show that either all the diagrams in D are unknot, or there is a diagram in D that is a diagram of the trefoil knot.

Introduction

We follow standard knot theory terminology as in [START_REF] Adams | The knot book. An elementary introduction to the mathematical theory of knots[END_REF]. All knots under consideration are tame, that is, they have regular diagrams. All diagrams under consideration are regular.

Our main result

A staple in every elementary knot theory course is that, given any diagram D, it is always possible to turn D into a diagram of the unknot (that is, into an unknot diagram) by performing some crossing exchanges on D (see Figure 1). The minimum number of such crossing exchanges that turn D into an unknot diagram is a well-studied parameter, the unknotting number of D.

We review in Section 2 the well-known argument that turns any diagram D into an unknot diagram, by performing crossing exchanges. As we shall remark, this argument actually produces more than one unknot diagram from D, but it gives a relatively small number: if D has n crossings, this idea yields at most 4n distinct unknot diagrams that can be obtained from D by crossing exchanges. Our main result is that actually there is always a superpolynomial number of such unknot diagrams. Theorem 1. Let D be a knot diagram with n crossings. Then there are at least 2 3 √ n distinct unknot diagrams that can be obtained by performing crossing exchanges on D.

1

As far as we know, no non-trivial general lower bound along the lines of Theorem 1 has been previously reported. There is, however, a substantial amount of work related to the complementary problem: out of the 2 n diagrams that can be obtained from D by crossing exchanges, how many are knotted? This is related to the well-studied Frisch-Wasserman-Delbruck conjecture (see Section 2), which in its general form can be paraphrased as follows: if we take a random knot diagram with n crossings, then the probability that it is knotted tends to 1 as n goes to infinity. For our arguments, it will be convenient to formulate Theorem 1 in terms of shadows. We recall that the shadow S of a diagram D is the 4-regular plane graph obtained by transforming each crossing of D into a vertex.

Conversely, we may regard a diagram as a shadow for which we provide the over/under-crossing information at each vertex. That is, for each vertex it is prescribed which strand goes locally above (or, equivalently, is the overpass) and which strand goes locally below (or, equivalently, is the underpass). We call this information the prescription at the vertex.

At each vertex we have two possible prescriptions (corresponding to which of the strands is an overpass at the corresponding crossing). The collection of prescriptions for all the vertices yields an assignment on S, resulting in a diagram D. We say that S is the shadow of D, and that D is a diagram of S. If S has n vertices, then there are 2 n possible assignments on S, and so there are 2 n distinct diagrams of S. These 2 n distinct diagrams are the diagrams that can be obtained by performing crossing exchanges on D.

In view of this discussion, it follows that Theorem 1 can be alternatively written as follows.

Theorem 2 (Equivalent to Theorem 1). Let S be a shadow with n vertices. Then S has at least

2 3 √ n distinct unknot diagrams.
We use U(S) to denote the set of unknot diagrams of S. Thus, with this notation, Theorem 2 claims that every shadow S satisfies |U(S)| ≥ 2 3 √ n . Obviously, the exact number of unknot diagrams depends on the shadow under consideration. It is easy to show that out of the 2 4 diagrams obtained from the shadow of the diagrams in Figure 1, exactly 12 are unknot. There are also extreme examples such as the ones illustrated in Figure 2: all 2 4 diagrams of each of these shadows are unknot. It is straightforward to generalize these examples, showing that for every positive integer n there is a shadow on n vertices, all of whose diagrams are unknot.

Shadows that yield the trefoil knot

We also investigate which knots (other than the unknot) can be guaranteed to be obtainable from a given shadow. That is, given a knot K and a shadow S, is there an assignment on S that gives a diagram of K?

The first natural step is the trefoil knot. If D is a diagram whose corresponding knot is equivalent to the trefoil knot, then we say that D is a trefoil diagram.

For this particular knot we can give a complete answer. First let us note that there exist arbitrarily large shadows that do not have trefoil diagrams: it suffices to generalize the examples in Figure 2 to an arbitrary number of vertices. What we will show is that such shadows (that do not have trefoil diagrams) can be easily characterized.

A glaring feature of the shadows in Figure 2 is that each of their vertices is a cut-vertex. We use Tutte's notion of a cut-vertex [START_REF] Tutte | Connectivity in graphs[END_REF], which we review in Section 9. We show that the property that every vertex is a cut-vertex completely characterizes which shadows have only unknot diagrams, and that every shadow that does not have this feature has a trefoil diagram: Theorem 3. Let S be a shadow. Then every diagram of S is unknot if and only if every vertex of S is a cut-vertex. Moreover, if not every vertex of S is a cut-vertex, then S has a trefoil diagram.

It is natural to ask how far we can get along the lines of Theorem 3. The next obvious step is to investigate the figure-eight knot, which is the only knot with crossing number four. One might think that for the figure-eight knot, a result analogous to Theorem 3 could hold, at least for all sufficiently large non-simple shadows. Now it is easy to construct an arbitrarily large non-simple shadow, none of whose assignments gives a diagram of the figure-eight knot. Indeed, it suffices to artificially grow the trefoil diagram by gluing to it the shadow at the bottom of Figure 2, as shown in Figure 3. Thus, in order to meaningfully explore a possible extension of Theorem 3 to shadows other than the trefoil (say, to the figure-eight knot) one must exclude from consideration shadows that have cut vertices; that is, we must focus our attention on 2-connected shadows.

As it happens, no analogue of Theorem 3 holds for the figure-eight knot, even if the attention is restricted to 2-connected shadows, no matter how large. Moreover, no such analogue exists for any knot with positive even crossing number: Observation 4. Let K be any knot with positive even crossing number, and let n be a positive integer. Then there exists a 2-connected shadow S with more than n vertices such that, for every diagram D of S, the knot corresponding to D is not equivalent to K.

Outline of the proof of Theorem 2 and structure of this paper

In the next section we overview some previous results in the literature related to Theorem 2, and in Section 3 we review some elementary facts on shadows that we use extensively in this paper.

Our proof of Theorem 2 is of an inductive nature. In a nutshell the idea is that, given a shadow S, we obtain from S a smaller shadow S that is (loosely speaking) contained in S, and then show that every unknot diagram of S can be extended to at least two unknot diagrams of S. Applying a similar procedure to S , by an inductive reasoning we find the claimed lower bound for U(S).

For an illustration of one of the techniques we use, we refer the reader to Figure 7. If we remove from S the edges of the thick cycle C and suppress all resulting degree 2 vertices, we obtain the shadow S shown below S. We will use the notation S = S/ /C to indicate that S is obtained from S in this way. To the right of S we show an unknot diagram D of S , and above D we show how to extend D to four unknot diagrams of S. The idea here is simply that it suffices to have the strand corresponding to C lie entirely above or entirely below the rest of the diagram. This property implies that D and D are equivalent; since D is unknot, then these four diagrams are unknot.

We note that this technique cannot be applied using an arbitrary cycle C. We can use it only if C is a straight-ahead cycle, that is, as we traverse C (starting from some of its vertices), then, as we reach an intermediate vertex v, we must continue traversing C using the edge opposite to the one from which we arrived to v. (Straight-ahead cycles are called loops in [START_REF] Chang | Untangling planar curves, 32nd International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform[END_REF]).

In order to simplify our arguments, we will use the notion of a macro move in a diagram (following the terminology used by Kaufmann in [START_REF]The unknotting problem[END_REF]). An instance of a macro move is precisely when we have a strand all of whose crossings lie "above" the rest of the diagram; such a strand is an overstrand. Similarly, if all the crossings of the strand lie "below" the rest of the diagram, then the strand is an understrand. An overstrand (respectively, understrand) can be replaced with another overstrand (respectively, understrand) with the same endpoints, if these endpoints are distinct; the diagram thus obtained is equivalent to the original diagram. If an overstrand or understrand starts and ends at the same crossing point, then we can collapse the strand to this point, and the diagram thus obtained is equivalent to the original diagram. This is precisely the operation performed on the thick strands in diagrams D 1 , D 2 , D 3 , and D 4 in Figure 7. We will review macro moves in Section 4.

Back to the discussion on the proof of Theorem 2, we illustrate the second main technique we use in Figure 12. In the shadow S we identify two parallel edges with common endpoints u and v; these two edges and their endpoints form a digon. We obtain S by splitting the vertices u and v as shown. Chang and Erickson call this type of operation a 2 → 0 homotopy move, and this suggests that S has two fewer vertices than S. To the right of S we have an unknot diagram D of S . This diagram can be extended to the two illustrated diagrams D 1 and D 2 of S. In each of D 1 and D 2 we can apply a Reidemeister move of Type II on the strands corresponding to the identified digon, obtaining D . Since D is unknot, it follows that both D 1 and D 2 are unknot.

In Section 5 we formally explain and develop this first technique we have outlined. The limitation of the first technique is that, in order to successfully apply it recursively, it must be used on straightahead cycles that have a relatively small number of vertices: if the cycle whose edges we remove has a large number of vertices, then the resulting shadow S will have too few vertices, and so the inductive argument will yield a poor lower bound for |U(S)|. The problem is that we cannot guarantee that there always exist (relatively) small straight-ahead cycles. It is easy to give examples of arbitrarily large shadows for which there are only two cycles on which this technique can be used, and getting rid of one of these cycles trivializes the whole shadow.

For such cases in which the first technique does not suffice, we have at hand the second technique. Now the obvious limitation of this second technique is that there exist shadows that do not have any digons. To handle this possibility we need a variant of this second technique, which can be applied to a pair of internally disjoint paths with common endpoints. Such a pair of paths has a natural underlying digon-like structure, and most of the work needed to prove Theorem 2 involves the extension of the second technique to take advantage of such digon-like structures. Part of this work involves a detailed understanding on the existence and structure of digons in a system of two simple closed curves in the plane. This is carried out in Section 6. With this information at our disposal, we then formally lay out the second technique in Section 7.

The final step, given in Section 8, consists then on showing how these two techniques can be combined to yield Theorem 2.

The proof of Theorem 3 is in Section 9. In a nutshell, to prove Theorem 3 we investigate the structure of a shadow not all of whose vertices are cut vertices, and then explicitly construct a trefoil diagram for any such shadow. Also in this section we describe the infinite family of shadows that proves Observation 4. Finally, in Section 10 we present some concluding remarks and open questions.

Related work

Let us start by recalling the well-known argument showing that if S is a shadow, then there is an assignment on S that gives an unknot diagram. Let S be a shadow, and let p be a point in the middle of an edge of S. Starting at p, we traverse the curve underlying S, following any of the two possible directions (see Figure 4(a)). We obtain a diagram from S by following the rule that each time we arrive to a vertex for the first time, then we assign a crossing to this vertex so that the strand we are currently traversing is the overstrand. If we apply this procedure to the shadow in Figure 4(a), we get the unknot diagram shown in Figure 4(b). It is easy to convince oneself that a diagram produced in this manner is unknot; a formal proof can be found in [START_REF] Adams | The knot book. An elementary introduction to the mathematical theory of knots[END_REF]Section 3.1].

An unknot diagram obtained in this way is called a standard unknot diagram (see [START_REF]Handbook of knot theory[END_REF]), and also a descending diagram (see [START_REF] Mroczkowski | Diagrammatic unknotting of knots and links in the projective space[END_REF] and [START_REF] Ozawa | Ascending number of knots and links[END_REF]). To understand the motivation behind the terminology "descending", let us consider a knot that gets projected to such a diagram. Suppose that the z-axis is the one orthogonal to the plane where the diagram is drawn. Then the knot can be realized (in 3-dimensional space) so that, as we traverse the knot starting at the point p that projects to p, the z-coordinates are descending until we get to a point q whose projection is very close to p, and finally we join q to p with a z-ascending strand. As we mentioned in Section 1, for any given shadow S with n vertices, the number of unknot diagrams of S that can be produced with this construction is at most 4n. Indeed, there are 2n ways to choose p (since S has 2n edges), and for each of these 2n choices there are two possible directions to follow.

There seem to be very few results in the literature involving the number of unknot diagrams of an arbitrary shadow. Recently, Cantarella et al. [START_REF] Cantarella | Knot probabilities in random diagrams[END_REF] carried out a complete investigation of the knot types that arise in all shadows with 10 or fewer crossings. Their results show that, among all the diagrams associated to this huge collection of shadows, roughly 78% are unknot diagrams. Cantarella et al. observed that this large proportion is explained by the existence of "tree-like" shadows, such as the ones depicted in Figure 2. These are shadows in which every vertex is a cut-vertex, and so an easy induction shows that all of their diagrams are unknot.

There is a collection of quite interesting, deep results in the literature related to the complementary aspect of Theorem 2: out of the 2 n diagrams that have S as their shadow, how many are not unknot diagrams?

According to Sumners and Whittington [START_REF] Sumners | Knots in self-avoiding walks[END_REF], this was first asked in the context of long linear polymer chains, independently by Frisch and Wasserman [START_REF] Frisch | Chemical topology 1[END_REF] and Delbruck [START_REF] Delbruck | Knotting problems in biology[END_REF]. In our context, the Frisch-Wasserman-Delbruck Conjecture may be roughly paraphrased as follows: if p(n) is the probability that a random knot diagram with n crossings is knotted, then p(n) → 1 as n → ∞.

The first issue to settle in an investigation of the Frisch-Wasserman-Delbruck Conjecture is: what is a random knot diagram? In [START_REF] Sumners | Knots in self-avoiding walks[END_REF], Sumners and Whittington investigated (and settled in the affirmative) this conjecture in the model of self-avoiding walks on the three-dimensional simple cubic lattice (see [START_REF] Pippenger | Knots in random walks[END_REF] for a closely related result). The conjecture has also been settled in other models of space curves, such as self-avoiding Gaussian polygons and self-avoiding equilateral polygons [START_REF] Arsuaga | Linking of uniform random polygons in confined spaces[END_REF][START_REF] Buck | Random knots and energy: elementary considerations[END_REF][START_REF] Diao | Global knotting in equilateral random polygons[END_REF][START_REF] Diao | On random knots[END_REF][START_REF] Jungreis | Gaussian random polygons are globally knotted[END_REF].

The problem of proposing suitable models of random knot diagrams is of interest by itself. The associated difficulties are explained and discussed in [START_REF] Diao | Generating large random knot projections, Physical and numerical models in knot theory[END_REF], where two different such models are presented and investigated. We also refer the reader to the preliminary report by Dunfield et al. in [START_REF] Dunfield | Random Knots: A preliminary report[END_REF]. It is also worth mentioning the very recent work of Even-Zohar et al. [START_REF] Even-Zohar | Invariants of random knots and links[END_REF], where several rigorous results are established on the distributions of knot and link invariants for the Petaluma model, which is based on the representation of knots and links as petal diagrams [START_REF] Adams | Knot projections with a single multi-crossing[END_REF]. In a very interesting recent development, Chapman [START_REF] Chapman | Asymptotic laws for knot diagrams[END_REF][START_REF]Asymptotic laws for random knot diagrams[END_REF] proved the Frisch-Wasserman-Delbruck conjecture under a very general and natural model.

From the work of Chapman we know that if we take a random diagram on n vertices, then the probability that it is an unknot diagram decreases exponentially with n. Our work in this paper focuses on the abundance of unknot diagrams associated to an arbitrary (that is, not to a random) shadow.

Basic facts on shadows

A shadow of a diagram with at least one crossing is a 4-regular plane graph. For our upcoming arguments it will be convenient to admit a vertex-less simple closed curve as a shadow. This trivial shadow is the shadow of a trivial diagram, that is, a diagram with no crossings.

Thus every shadow is a 4-regular plane graph, but not every 4-regular plane graph is a shadow of a knot. A 4-regular graph is a shadow if and only if it has a straight-ahead Eulerian closed walk. We recall that a straight-ahead walk in a 4-regular graph is a walk in which every time we reach a vertex v in the walk, the next edge in the walk is the opposite edge to the one from which we arrived to v. A walk is closed if its final vertex is the same as its initial vertex, and it is Eulerian if each edge of the graph gets traversed exactly once in the graph.

We also recall that if C is a connected subgraph of a graph G, and every vertex of C has degree two (in C), then C is a cycle of G. For our purposes, a vertex-less graph (which, we recall, consists of a single edge, homeomorphic to a simple closed curve) will be considered a cycle.

If C is a cycle of a shadow S, and there exists a straight-ahead walk that traverses each edge of C exactly once, then C is a straight-ahead cycle of S. The initial (and final) vertex of this walk is a root of C. For an illustration of a straight-ahead cycle in a shadow we refer the reader to the top left of Figure 7. The trivial shadow has no vertices, but by convention we regard it as a straight-ahead cycle. Finally we note that it is easy to see that a straight-ahead cycle in a nontrivial shadow has a unique root.

In our arguments we make extensive use of the following properties of shadows. The first one is totally straightforward. Fact 5. Let v be a vertex of a shadow S. Then there is an Eulerian straight-ahead closed walk W that starts and ends at v. The walk W gets naturally decomposed into two edge-disjoint straightahead closed walks W 1 , W 2 , both of which have v as their startvertex and endvertex.

Fact 6. Every nontrivial shadow has at least two distinct (necessarily edge-disjoint) straight-ahead cycles.

Proof. Let v be a vertex of a shadow S, and let W 1 , W 2 be the straight-ahead closed walks (from Fact 5) that start and end at v. We show that as we traverse W 1 , we must encounter a straightahead cycle. Since the argument is symmetric on W 1 and W 2 , and these walks are edge-disjoint, this proves the fact.

We prove this by induction on the number of vertices of the walk. If v is the only vertex of W 1 , then this is obvious, as W 1 is itself a straight-ahead cycle. Thus suppose that W 1 has at least one vertex other than v. Suppose that W 1 is not a straight-ahead cycle. Then there exists a vertex u other than v that gets visited twice as we traverse W 1 . The subwalk of W 1 that starts and ends at u has fewer vertices that W 1 , and by the induction hypothesis it has a straight-ahead cycle C, which is also a straight-ahead cycle of W 1 .

Macro moves

The three Reidemeister moves are particular cases of more general operations that turn a diagram D into an equivalent diagram D , that is, a diagram D whose corresponding knot is isotopic to the knot represented by D. Following Kauffman [START_REF]The unknotting problem[END_REF], we call these operations macro moves. We quote the following lively passage from [START_REF]The unknotting problem[END_REF]: [

21, Section 2]"In a macro move, we identify an arc that passes entirely under some piece of the diagram (or entirely over) and shift this part of the arc, keeping it under (or over) during the shift."

We also refer the reader to the interesting discussion on macro moves (although not using this terminology) in mathoverflow.net initiated by Gowers [17].

We will use two particular kinds of macro moves. Before describing them, let us clarify the notion of strand that we will use throughout this work.

We adopt the viewpoint that a strand of a knot K is a connected (in our context, it will always be proper) subset of K. If a diagram D is obtained as a projection of K, then we refer to the part of D that corresponds to a strand of K also as a strand of D. We actually only use strands in diagrams, so there should be no confusion, whenever we work with a strand, as to whether we refer to a strand as a part of a diagram or as a piece of a knot. As an illustration, we refer the reader to Figures 5 and6. In the former, we have a strand σ whose endpoints coincide, in a crossing point, and in the latter we illustrate strands σ, σ with distinct endpoints. The first macro move we use is illustrated in Figure 5. Let x be a crossing point in a diagram D, and let σ be a proper strand that starts and ends at x. Further suppose that σ has no self-crossings other than x. If as we traverse σ starting from x (in any of the two possible directions), every crossing we find is an overpass (respectively, underpass) for σ, then σ is an overstrand (respectively, understrand) based at x.

Informally speaking, if σ is an overstrand (respectively, understrand) of D based at x, then σ lies above (respectively, below) the rest of the diagram. In either case we can then collapse σ to the point x, and the diagram D thus obtained is equivalent to D. We say that D is obtained from D by a macro move of Type A. We note that the classical Reidemeister move of Type I is a particular instance of a macro move of Type A, namely in the case in which x is the only crossing of σ.

The other macro move we use is illustrated in Figure 6. Let x, y be distinct non-crossing points in a diagram D. Suppose that σ is a strand of D with endpoints x, y, that does not cross itself, and has the property that as we traverse σ, all the crossings we find are overpasses (respectively, underpasses) for σ. Then we say that σ is an overstrand (respectively, understrand) of D. Let D be a diagram obtained from D by removing σ, and replacing it by another strand also with endpoints x, y, that is an overstrand (respectively, understrand) in D . Then D and D are clearly equivalent diagrams. We say that D is obtained from D by a macro move of Type B.

We note that the classical Reidemeister moves of Types II and III are particular instances of macro moves of Type B.

Obtaining unknot diagrams using cycle decompositions

We now formally lay out the first tool we develop to recursively construct unknot diagrams of a shadow. Let S be a shadow, and suppose that C is a straight-ahead cycle of S. Let S be the shadow obtained from S by removing the edges of C, and suppressing any resulting degree 2 vertices. We use the notation S = S/ /C to denote that S is obtained from S in this way.

The first key claim is that if S = S/ /C, then |U(S)| ≥ 2|U(S )|, and that a stronger inequality holds if C has more than one vertex: Proof. The main idea is that an unknot diagram of S can be "extended" to at least two unknot diagrams of S (and to at least four, if C has more than one vertex). Suppose first that C has more than one vertex, and let c be the root of C. We refer the reader to Figure 7 for an illustration of the proof, where C is the cycle formed by the thick edges.

Starting from any unknot diagram D of S , we obtain four distinct unknot diagrams of S as follows. First, we let each vertex in S that is in S maintain the prescription it has in D . Then the prescriptions at the vertices in S \ (S ∪ {c}) are given so that in the resulting diagram of S, the strand corresponding to C is either an overstrand or an understrand (two possibilities). Moreover, we still have the freedom to assign any of the two possible prescriptions at c. This yields in total four distinct diagrams of S. Each of these four diagrams is unknot: one can apply a macro move of Type A to the strand corresponding to C (this is either an over-or an under-strand, so such a move can be performed), to obtain the unknot diagram D . Thus these four diagrams are unknot.

Finally, if c is the only vertex of C, then we extend D to two unknot diagrams of S, by giving to c each of the two possible prescriptions.

We wish to iteratively apply this proposition until we end up with a trivial shadow. The formal setting makes use of the following definition.

Definition. (Cycle decomposition).

Let S be a shadow. Suppose that S = S 1 , S 2 , . . . , S p is a sequence of shadows, with the following properties:

• For i = 1, 2, . . . , p -1, there is a straight-ahead cycle C i of S i such that S i+1 = S i / /C i . • S p is the trivial shadow. Set C p := S p . Then the sequence C 1 , C 2 , . . . , C p is a cycle decomposition of S of size p.
In Figure 8 we give an example of a cycle decomposition. We remark that in a cycle decomposition C 1 , C 2 , . . . , C p of a shadow S, the cycles C 2 , . . . , C p are not necessarily straight-ahead cycles in S. Moreover, they do not even need be cycles of S. On the other hand, for i = 1, 2, . . . , p there is a cycle This lemma settles Theorem 2 if S has a cycle decomposition of the given size. If all cycle decompositions of S are smaller, then we need a different approach. Before we introduce this second tool we establish some elementary results on digons in systems of two simple closed curves.

D i in S such that D i is a subdivision of C i .

Digons in systems of two closed curves

Lemma 8 in the previous section settles Theorem 2 for shadows with sufficiently large cycle decompositions. For a shadow S that does not have this property, our approach will be to find two cycles B, R in S that have many vertices in common, and then to use these cycles to produce many unknot diagrams of S. This approach relies on the existence of digons (with special properties) in a system of two simple closed curves in the plane. In this section we investigate these systems of curves, and establish the required results.

Let β be a simple closed curve in the plane. A segment of β is a subset of β that is homeomorphic to the closed interval [0, 1]. Thus a segment of β is simply a non-closed curve (including its endpoints) contained in β.

Let β, ρ be two non-disjoint simple closed curves. A digon of (β, ρ) is a pair of segments (α, γ), where α is in β and γ is in ρ, such that (i) α and γ have common endpoints x, y; (ii) the only points of β that are in γ are x and y; and (iii) the only points of ρ that are in α are x and y. In Figure 9 we illustrate this concept.

β ρ γ 1 α 1 y γ 2 α 2 γ α x x y Figure 9:
On the left hand side we have two simple closed curves β (thick) and ρ (thin). The pair (α, γ) is a digon of (β, ρ). On the right hand side we have two simple closed curves β = α 1 ∪ α 2 (thick) and ρ = γ 1 ∪ γ 2 (thin). This last example illustrates that a digon does not necessarily bound an empty disk (that is, a disk whose interior does not contain any point in the curves). Indeed, the pair (α 2 , γ 1 ) is a digon of (α 1 ∪ α 2 , γ 1 ∪ γ 2 ), and α 2 ∪ γ 1 does not bound an empty disk.

If (α, γ) is a digon of (β, ρ), then α ∪ γ is a simple closed curve. Properties (ii) and (iii) above imply that at least one of the two connected components of R 2 \ (α ∪ γ) does not have any point in β ∪ ρ (that is, at least one of these connected components is an empty region). We remark that it is not necessarily true that this empty region is the disk bounded by α ∪ γ (see right hand side of Figure 9).

We now state and prove the results on digons that we need later. An intersection of two curves at a point x is a crossing if the curves intersect transversally at x. Otherwise the intersection is tangential.

Proposition 9. Let β, ρ be non-disjoint simple closed curves in the plane. Suppose that every intersection point of β and ρ is a crossing (rather than tangential). Then there are at least 4 distinct digons of (β, ρ). Moreover, if b is a point of β that is not in ρ, and r is a point of ρ that is not in β, then there exists a digon (α, γ) of (β, ρ) such that α ∪ γ contains neither b nor r.

Proof. To help comprehension, we colour β blue and ρ red. Let ∆ denote the closed disk bounded by β.

We can naturally regard the part of β ∪ ρ contained in ∆ as a 3-regular plane graph: each vertex is incident with two blue edges and one red edge. It is easily seen that if we take the dual of this plane graph, and discard the vertex corresponding to the unbounded face, the result is a tree. Now each leaf of this tree corresponds to a digon of (β, ρ). Since each tree with at least two vertices has at least two leaves, then there are at least two digons of (β, ρ) whose red segments are inside ∆. A totally analogous argument shows that there are at least two digons of (β, ρ) whose red segments are outside ∆. This shows the existence of at least four distinct digons of (β, ρ).

The existence of a digon (α, γ) of (β, ρ) such that α ∪ γ contains neither b nor r is easily worked out by a simple case analysis if β and ρ have exactly two intersection points. We note that, in this case, there is exactly one digon of (β, ρ) with this property.

Suppose β and ρ have at least 4 points in common. Then if (α, γ) and (α , γ ) are distinct digons, we must have α = α and γ = γ . Thus only one digon of (β, ρ) can contain b, and also only one can contain r. As there are at least four digons of (β, ρ), it follows that there are at least two (and in particular at least one) digons (α, γ) of (β, ρ) such that α ∪ γ contains neither b nor r. Proposition 10. Let β, ρ be simple closed curves in the plane that intersect in ≥ 3 points. Suppose that there is exactly one intersection point z of β and ρ that is tangential; all the other intersection points are crossings. Then there exists a digon (α, γ) of (β, ρ) such that α ∪ γ does not contain z.

Proof. As in the proof of Proposition 9, we colour β blue and ρ red, and let ∆ denote the closed disk bounded by β. On the left hand side we have the case in which δ ∩ ρ lies outside the disk ∆ bounded by β. Both γ and γ are segments inside ∆, and both (α, γ) and (α , γ ) are digons, neither of which contains z. In the example on the right hand side, δ ∩ ρ lies inside ∆, and γ is the only red segment that lies outside ∆. By letting α and α be the blue segments into which ρ naturally breaks β, we have that (α, γ) and (α , γ) are both digons. Of these two digons, only (α, γ) does not contain z.

Suppose that if we take a small disk δ centered at z (small enough so that z is the only point in β ∩ ρ that is in δ), then ρ ∩ δ lies outside ∆ (see Figure 10). The other possibility (ρ ∩ δ lies inside ∆) is handled in a totally analogous manner. Now we proceed as in the proof of Proposition 9, ignoring the part of β ∪ ρ outside ∆, and find at least two distinct digons (α, γ), (α , γ ) of (β, ρ), such that γ and γ (which are not necessarily distinct) are inside ∆. Only one of α and α can contain z. If α contains z, then (α , γ ) is a digon of (β, ρ) that does not contain z. If α contains z, then (α, γ) is a digon of (β, ρ) that does not contain z.

Obtaining unknot diagrams using digon-like structures

When we have a shadow S not having a sufficiently large cycle decomposition, and thus for which Lemma 8 does not guarantee enough unknot diagrams, the idea is to find two straight-ahead cycles in S with many common vertices, and then to use these two cycles to find many unknot diagrams of S. This approach is summarized in the following statement, our second main tool in the proof of Theorem 2. Although the arguments in the proof of this lemma depend on the parity of m, the core idea is the same in both cases. We will give separately the proofs for the cases m odd and m even. Even though in principle it would have been possible to present a unified proof, we have decided against this possibility. First, it would only have resulted in a marginal saving of space. Second, dealing with the easier case (m odd) first will allow us to present the main idea in the proof, without the additional complications involved in the case when m is even.

In both cases, to help comprehension we colour the edges of B and R blue and red, respectively.

Proof of Lemma 11 for odd m. We start by noting that since is m odd, then S = B ∪ R. Indeed, since B and R are straight-ahead cycles, it follows that if we regard them as simple closed curves, then they can have at most one non-crossing (that is, at most one tangential) intersection. An elementary argument using the Jordan curve theorem shows that the number of crossing intersections is even. Since m is odd, then these curves must have exactly one tangential intersection, which must then be the common root r of B and R. If we start a straight-ahead traversal of S starting at r, we traverse entirely one of B and R, return to r, and then traverse the other cycle, coming back again to r having traversed the whole shadow S. Thus S = B ∪ R, as claimed.

The proof is by induction on m. The base case m = 1 is trivial, as in this case the lemma only requires two unknot diagrams, and it is immediately seen that a shadow with one vertex has (exactly) two unknot diagrams.

Suppose then that m ≥ 3. It follows from Proposition 10 that there exist edges e, f with common endpoints u, v, where e is blue and f is red, such that e ∪ f is a digon. Moreover, it follows from that proposition that such edges e, f exist so that neither u nor v is r.

Let S be the shadow obtained from S by "splitting" each of u and v into two degree 2 vertices, and then suppressing these four degree 2 vertices, as illustrated in Figure 11. It is easy to see that the resulting graph S is indeed a shadow, with straight-ahead cycles B , R naturally induced from B and R, whose common root is still r, and such that S = B ∪ R . The key claim is that every unknot diagram of S can be extended to two unknot diagrams of S. See Figure 12 for an illustration. For let D be an unknot diagram of S . We construct from D two diagrams D 1 , D 2 as follows. For each vertex in S that is in S , we maintain the prescription it has in D . We obtain D 1 (respectively, D 2 ) by giving prescriptions to u and v such that the corresponding crossings are overpasses for the blue (respectively, red) strand.

Both D 1 and D 2 are unknot diagrams of S. This follows simply since, by applying a Reidemeister move of Type II to the strands corresponding to e and f , we obtain the unknot diagram D . Thus D 1 and D 2 are unknot.

This argument shows that S has as least twice as many unknot diagrams as S , and so the lemma follows by induction.

Proof of Lemma 11 for even m. A similar reasoning as the one at the beginning of the proof of Lemma 11 shows that in this case necessarily S = B ∪ R, and that the respective roots b and r of B and R must be distinct. Since S = B ∪ R, then S has edges that are neither blue nor red; we colour these edges gray.

Let S denote the graph that results by removing from S all edges not in B ∪ R, and supressing all resulting degree 2 vertices. Thus S is the shadow of a link with two components: S has exactly two straight-ahead cycles, namely the cycles B and R naturally inherited from B and R.

Note that the roots b and r are not anymore vertices in S, but we can still regard them as middle points b and r of edges of B and R, respectively. We say that an unlink diagram of S is (b, r)-avoiding if it can be taken to the trivial unlink diagram by a series of Reidemeister moves of Type II, none of which involves moving or passing above/below neither b nor r.

It is easy to see that arguments totally analogous to those in the proof above for the case m odd (but in the present case using Proposition 9 instead of Proposition 10) yields that S has at least 2 m/2 distinct (b, r)-avoiding unlink diagrams.

The key point that we will now show is that each of these 2 m/2 (b, r)-avoiding unlink diagram of S can be extended to an unknot diagram of S. Given an (b, r)-avoiding unlink diagram D of S, we extend it to a diagram D of S as follows:

(i) For each crossing of D that is in D, we let it maintain in D the prescription it has in D.

(ii) If a crossing in D involves a blue (respectively, red) strand and a gray strand, then we let it be an overpass for the blue (respectively, red) strand. Loosely speaking, the blue and red strands are "above" the gray strands.

(iii) For the vertices that are incident with four gray edges (if any) we proceed as follows. Let S be the shadow that results by removing the edges of B ∪ R, and supressing all resulting degree 2 vertices. We give the prescription on the vertices of S by asking that the resulting assignment on S is an unknot diagram (take for instance any descending diagram of S ).

(iv) We give arbitrary prescriptions to the crossings corresponding to b and r.

These rules give prescriptions to all the vertices in S. We claim that the resulting diagram D of S is unknot.

To prove that D is unknot, we start by arguing that the blue-red crossings can be eliminated by using macro moves of Type B. For consider a sequence of (b, r)-avoiding Reidemeister Type II moves that unlink D. Since the blue and red strands are "above" the gray strands (by condition (ii)), each of this moves can be translated to a macro move of Type B on D; this is the step in which it is essential that these moves on D are (b, r)-avoiding.

Thus we can eliminate from D all blue-red crossings by a sequence of macro moves of Type B. After this, the remaining blue and red strands are still overstrands (again by condition (ii)), and so they can be collapsed to b and r, respectively, by using macro moves of Type A. Since by (iii) the resulting diagram is unknot, it follows that D is an unknot diagram, as claimed.

Thus each (b, r)-avoiding unlink diagram of S can be extended to an unknot diagram of S. Since these extensions are all distinct to each other, and the number of (b, r)-avoiding unlink diagrams is at least 2 m/2 , it follows that |U(S)| ≥ 2 m/2 .

Proof of Theorem 2

Lemmas 8 and 11 take care of Theorem 2 when S is a shadow that either (i) has a cycle decomposition of size at least 3 √ n; or (ii) has two straight-ahead cycles with at least 2 3 √ n common vertices.

Unfortunately, there exist shadows that satisfy neither (i) nor (ii). However, we can show that if S does not satisfy (i), then there is a substructure of S that does satisfy (ii). To make this precise, let us introduce the concept of a subshadow. A shadow T is a subshadow of S if there is a sequence S = S 1 , S 2 , . . . , S r = T of shadows, such that for i = 1, 2, . . . , r -1, there is a straight-ahead cycle C i of S i such that S i+1 = S i / /C i . Note that a shadow is a subshadow of itself.

An easy but crucial fact that follows from Proposition 7 is that if T is a subshadow of S, then |U(S)| ≥ |U(T )|. Thus in order to apply Lemma 11 to obtain Theorem 2, we do not need the existence of two straight-ahead cycles with these properties in S itself; it suffices to guarantee the existence of such straight-ahead cycles in some subshadow T of S. This last ingredient is provided by the following statement.

Lemma 12.

Let S be a shadow with n vertices. Suppose that every cycle decomposition of S has size at most 3 √ n. Then there is a subshadow T of S that has straight-ahead cycles B and R, such that B and R have at least 2 3 √ n vertices in common.

Before moving on to the proof of this lemma, for completeness let us formally show that with this last ingredient we can finally prove Theorem 2.

Proof of Theorem 2. If S has a cycle decomposition of size at least 3 √ n, then we are done by Lemma 8. If every cycle decomposition of S has size at most 3 √ n, then by Lemma 12 it follows that S has a subshadow T with straight-ahead cycles B and R that have at least 2 3 √ n common vertices. Applying Lemma 11 to T , we obtain

|U(T )| ≥ 2 3 √ n . Since |U(S)| ≥ |U(T )|, the theorem follows.
The proof of Lemma 12 relies on the following two results on cycle decompositions. Proposition 13. Let S be a nontrivial shadow, and let C be a straight-ahead cycle of S. Then there is at most one straight-ahead cycle of S/ /C that is not a subdivision of a straight-ahead cycle of S.

Proof. Let S := S/ /C, and let F be the set of all straight-ahead cycles of S . Each F ∈ F is obtained from a cycle F in S, by suppressing from F the vertices that are in C (if any). Let F denote the family of all such cycles F . It is readily seen that each F ∈ F is a straight-ahead cycle in S, unless F contains the root of C. Since at most one element in F can contain the root of C, the proposition follows. Proposition 14. Let S be a nontrivial shadow. Let C = C 1 , C 2 , . . . , C p be a cycle decomposition of S, and let D 1 , D 2 , . . . , D p be the primary sequence of C. Then at least two elements in {D 1 , D 2 , . . . , D p } are straight-ahead cycles of S.

Proof. We proceed by induction on p. The base case p = 2 is straightforward. Thus we take a cycle decomposition C 1 , C 2 , . . . , C p of a shadow S, with p ≥ 3, and assume that the statement holds for all cycle decompositions (of any shadow) of size less than p.

Evidently, C 1 is a straight-ahead cycle of S. Let S 2 := S/ /C 1 . Consider the cycle decomposition

C 2 = C 2 , C 3 , . . . , C p of S 2 ,
and let E 2 , E 3 , . . . , E p be the associated primary sequence. By the induction hypothesis, there exist distinct j, k ∈ {2, . . . , p} such that E j , E k are straight-ahead cycles of S 2 .

By Proposition 13, at most one of E j and E k is not a subdivision of a straight-ahead cycle of S. Without loss of generality, E j is a subdivision of a straight-ahead cycle of S. Now D j is a subdivision of E j , and so it follows that D j is a straight-ahead cycle in S. This completes the proof, since D 1 and D j are straight-ahead cycles in S.

Proof of Lemma 12. Let S be a shadow with n vertices, and let C 1 , C 2 , . . . , C p be a cycle decomposition of S, with p ≤ 3 √ n. Let D 1 , D 2 , . . . , D p be the primary sequence of C 1 , C 2 , . . . , C p . We start by noting that there exist r, s ∈ {1, 2, . . . , p} such that D r and D s have at least 2 3 √ n common vertices. To see this, note that each vertex in S is in the intersection of exactly two cycles in D 1 , D 2 , . . . , D p . If each pair of cycles in this sequence had fewer than 2 3 √ n common vertices, this would imply that S has fewer than p 2 • 2 3

√ n ≤ 3 √ n 2 • 2 3
√ n = n -n 2/3 vertices. Now let T be a subshadow of S such that (i) T has a cycle decomposition E 1 , E 2 , . . . , E q , with primary sequence F 1 , F 2 , . . . , F q such that both D r and D s are subdivisions of cycles in {F 1 , F 2 , . . . , F q }; and (ii) no subshadow of S with fewer vertices than T satisfies (i). Note that T is well defined, as S itself satisfies (i), as witnessed by its cycle decomposition C 1 , C 2 , . . . , C p . We claim that T satisfies the conditions in the lemma.

To show this, let j, k be the integers in {1, 2, . . . , q} such that D r is a subdivision of F j , and D s is a subdivision of F k .

We proceed by contradiction. Suppose that one of F j and F k is not a straight-ahead cycle of T . Then, by Proposition 14, there is an ∈ {1, 2, . . . , q}, = j, k, such that F is a straightahead cycle of T . Let T := T / /F . Then E 1 , E 2 , . . . , E q naturally induces a cycle decomposition E 1 , E 2 , . . . , E -1 , E +1 , . . . , E q of T . Indeed, for each i ∈ {1, 2, . . . , -1, + 1, . . . , q} it suffices to let E i be the cycle that results by suppressing from E i all the vertices that are in E , if any.

Let F 1 , F 2 , . . . , F -1 , F +1 , . . . , F q be the primary sequence of E 1 , E 2 , . . . , E -1 , E +1 , . . . , E q . Then, for each i ∈ {1, 2, . . . , -1, + 1, . . . , q} we have that F i is a subdivision of F i . In particular, F j is a subdivision of F j , and F k is a subdivision of F k . It follows that back in S, D r is a subdivision of F j , and D s is a subdivision of F k . Since this violates the minimality of T , we conclude that F j and F k are straight-ahead cycles of T . The lemma now follows by setting B = F j and R = F k , since these two cycles have the same number of common vertices as D r and D s , which is at least 2 3 √ n.

Proofs of Theorem 3 and Observation 4

Let us start by recalling the concept of a cut-vertex in a graph. Following Tutte [START_REF] Tutte | Connectivity in graphs[END_REF], a 1-separation of a connected graph G is an ordered pair (H, K) of subgraphs of G, each with at least one edge, such that H ∪ K = G and H ∩ K is a graph that consists of a single vertex. The vertex of H ∩ K is the cut-vertex of the 1-separation. We remark that sometimes a cut-vertex of a connected graph is thought of as a vertex whose deletion produces a disconnected graph. We note that Tutte's notion of a cut-vertex is more general. Consider for instance vertex v in the shadow at the top of Figure 2. If we delete this vertex, together with its incident edges, the resulting graph is still connected, and yet v is a cut-vertex according to Tutte's definition. Under Tutte's definition, if a graph G can be obtained from two disjoint graphs, taking one vertex of each of these graphs and identifying these two vertices into a vertex v, then v is a cut-vertex of G.

Proof of Theorem 3

We prove the two statements in Theorem 3 separately.

(I) Every diagram of S is unknot if and only if every vertex of S is a cut-vertex.

For brevity, let us say that a shadow is simple if each of its vertices is a cut-vertex. For the easier direction of (I), we note that if D is a diagram of a simple shadow, then every crossing in D is nugatory. We recall that a nugatory crossing in a diagram corresponds precisely to a cut-vertex in its shadow. This crossing can be trivialized by a switching operation of the diagram, thus obtaining an equivalent diagram with fewer crossings. If every crossing in a diagram is nugatory, then it is equivalent to the trivial diagram. Thus, if S is simple, then all the diagrams of S are unknot.

We prove the other direction of (I) by induction on the number of vertices of S. In the base case S consists of exactly one vertex, and the statement is trivial. For the inductive step, we assume that the statement holds for all simple shadows with fewer than n vertices, for some n ≥ 2, and let S be a simple shadow with n vertices.

First we note that if S has no cut-vertex, then not all the diagrams of S are unknot. To see this, let D be an alternating diagram of S, that is, a diagram in which as one traverses the diagram, one encounters an overcrossing, then an undercrossing, then an overcrossing, and so on. Since S has no cut vertices, then D has no nugatory crossings, that is, D is a reduced diagram. The validity [START_REF] Louis | State models and the Jones polynomial[END_REF][START_REF] Murasugi | Jones polynomials and classical conjectures in knot theory[END_REF][START_REF] Morwen | A spanning tree expansion of the Jones polynomial[END_REF] of the First Tait Conjecture (if D is a reduced alternating diagram, then no diagram equivalent to D has fewer crossings than D) then implies that the knot represented by D cannot be the unknot.

We can then assume that S has a cut-vertex v. Then there are subgraphs H, K of S, both with at least one edge, such that H ∪ K = S and H ∩ K consists solely of v. Note that v has degree 2 in both H and K. Let H (respectively, K ) be the graph obtained by suppressing v in H (respectively, K). Then H and K are shadows, each with fewer than n vertices.

We claim that both H and K are simple. For suppose that H is not simple, and let D H be a knotted diagram of H . Let D K be an unknot diagram of K . We can naturally combine D H and D K into a diagram D of S, by giving any prescription to v. Since D K is unknot, it follows that D and D H are equivalent, and so D is a knotted diagram of S. Since this contradicts the assumption that S is simple, we conclude that H must be simple. The same argument shows that K is simple.

The inductive hypothesis then implies that every vertex of H and K is a cut-vertex, and from this it immediately follows that every vertex of S is a cut-vertex.

(II) If not every vertex of S is a cut-vertex, then S has a trefoil diagram.

It is easy to see that if every straight-ahead cycle of a shadow has only one vertex (that is, it consists of a vertex and a loop-edge), then every vertex is a cut-vertex of the shadow. From (I) it then follows that if not all the vertices of a shadow are cut vertices, then the shadow has a straight-ahead cycle with more than one vertex.

The proof is by induction on the number of vertices of S. A quick analysis shows that in a shadow with 1 or 2 vertices, all the vertices are cut vertices. It is also readily seen that up to isomorphism there is only one shadow with 3 vertices, such that not all of its vertices are cut vertices. This is the shadow of the familiar diagram of the trefoil knot. This shadow has evidently a trefoil diagram, and so this settles the base case n = 3.

For the inductive step, we take a shadow S on n ≥ 4 vertices, where not all the vertices of S are cut vertices, and assume that (II) holds for shadows with fewer than n vertices.

Let S be a shadow in which not every vertex of S is a cut-vertex. It follows from the observation above that S has a straight-ahead cycle with more than one vertex. Let C be such a straight-ahead cycle, and let r be its root. Let W be the other straight-ahead closed walk that starts and ends at r. Note that S = C ∪ W .

The walk W can then be naturally written as the concatenation of three walks W 1 , W 2 , and W 3 , as follows. Since C has at least one vertex other than r, and W is a closed walk and S = C ∪ W , then W and C must have at least two vertices in common, other than r.

Let u be the first vertex of C (other than r) that we find as we traverse W . After reaching u, we continue traversing W ; let v be the first vertex in C that we find in this continuation of the traversal of W . Then let W 1 be the part of W from r to u, let W 2 be the part of W from u to v, and let W 3 be the part from v to r. Note that W 1 is contained in a component ∆ 1 of R 2 \ C, and W 2 is contained in the other component ∆ 2 . The end edges of W 3 are contained in ∆ 1 , but some parts of W 3 may be in ∆ 1 .

The situation is illustrated in Figure 13(a). The dashed parts of W 1 and W 2 hint to the fact that W 1 and W 2 may not be paths. The dashed parts of W 3 suggest that the beginning and the end of W 3 are in ∆ 1 , but other parts of W 3 may be in ∆ 2 .

We now show that if one of W 1 , W 2 , W 3 is not a path, then we are done by the induction hypothesis. For suppose that W 1 is not a path. Since W 1 is a straight ahead-walk, it follows that there must exist a straight-ahead cycle F contained in W 1 . We note that none of r, u, and v can be in F . Now let T := S/ /F . The shadow T has then a straight-ahead cycle (namely the one naturally induced by C) with more than one vertex, and so by the induction hypothesis T has a trefoil diagram. But this trefoil diagram can be extended to an equivalent diagram of S, by having the strand corresponding to F to be an overstrand. Therefore we conclude that S has a trefoil diagram.

In exactly the same way it is shown that if one of W 2 and W 3 is not a path, then we are done by the induction hypothesis. We can then assume that W 1 , W 2 , and W 3 are paths. A possible scenario is illustrated in Figure 13(b). We finish the proof by showing that S has a trefoil diagram.

Consider a diagram D of S in which the strand corresponding to W 3 is an overstrand. An example is illustrated in Figure 14(b), which is a diagram of the shadow in Figure 13.

r W 2 W 3 W 3 W 1 v u C (a) r W 2 W 3 v u W 1 C (b)
Figure 13: If S is a shadow with a straight-ahead cycle C that has more than one vertex, then S must have roughly the structure shown in (a). That is, the complement of C in S can be naturally decomposed into three parts W 1 , W 2 and W 3 , where W 1 and W 2 are contained in distinct components of R 2 \ C, and W 3 need not be contained in any of these components, but its end edges are contained in the same component as W 1 . In part (b) of this figure we depict a whole shadow that satisfies these properties.

With a macro move of Type B we can replace this strand with a strand that is contained in ∆ 2 , and has no internal crossings. Let D be the diagram thus obtained. (See Figure 14(b)). The shadow of D is then isomorphic to the usual shadow of the trefoil knot, and so it follows that by giving suitable prescriptions at r, u, and v (as in Figure 14(b)), we obtain that D is a diagram of the trefoil knot. By giving these prescriptions at r, u, and v also in D, it follows that D and D are equivalent, and so D is a trefoil diagram of S.

Proof of Observation 4

For each integer n ≥ 3, let C n be the shadow obtained by taking a cycle with n vertices and adding a parallel edge to each edge. In Figure 15 we illustrate C 7 .

To prove Observation 4 it suffices to show that for every odd integer n, if D is a diagram of C n , then the knot corresponding to D is either trivial, or it has odd crossing number.

We prove this by induction on n. For the base case n = 3 it is readily seen that every diagram of C 3 is either a trefoil diagram or an unknot diagram. Suppose then that n ≥ 5, and that the statement holds for all odd integers smaller than n.

Let D be a diagram of C n . Since C n is a 2-connected graph, it follows that D is a reduced diagram. If D is alternating then, since D is reduced, the crossing number of the knot corresponding to D is n [START_REF] Louis | State models and the Jones polynomial[END_REF][START_REF] Murasugi | Jones polynomials and classical conjectures in knot theory[END_REF][START_REF] Morwen | A spanning tree expansion of the Jones polynomial[END_REF]. Suppose finally that D is not alternating. Then there are two neighbour crossings on which we can perform a Reidemeister move of Type II on D, obtaining a diagram of C n-2 , and the result follows by the induction hypothesis.

Concluding remarks and open questions

Before starting this project, we considered the following question. Given a shadow S on n vertices, how many different knot types are there among the 2 n distinct diagrams of S? This question was posed by the third author in mathoverflow.net [26]. Among the replies received, Andy Putnam mentioned shadows that have only unknot diagrams. After obtaining the easy characterization of which shadows have this property (the first part of Theorem 3), we turned our attention to the main topic in this paper.

We find the question in the previous paragraph quite interesting. We leave aside those shadows that only have unknot diagrams, as they admit an easy characterization. The graphs used in the proof of Observation 4 show that for each odd integer n, there is a 2-connected shadow C n on n vertices, such that among the 2 n distinct diagrams of C n there are only n/2 distinct knot types. Now, even though very large, these shadows have very small depth [START_REF] Chang | Untangling planar curves, 32nd International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform[END_REF].

We adapt the notion of depth of a simple curve, to the parallel context of the depth of a shadow. The depth of a face f of a shadow S is the length of a minimum distance path, in the dual graph of S, from the dual vertex of f to the dual vertex of the unbounded face. The depth of S is then the maximum depth over all faces of S.

Is it true that one can guarantee many more knot types for 2-connected shadows with large depth? We note that the 2-connectedness requirement is important, as the shadow on top of Figure 2 can be generalized to obtain a shadow with arbitrarily large depth, and that only has unknot diagrams. Perhaps some of the tools developed in [START_REF] Chang | Untangling planar curves, 32nd International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform[END_REF] can shed light on this question.

It seems natural to ask if one could hope to prove a much better bound than the one given by Theorem 2. To explore this question, we let U min (n) denote the best possible bound. That is, for each positive integer n, U min (n) := min It follows from the work in [START_REF] Chapman | Asymptotic laws for knot diagrams[END_REF][START_REF]Asymptotic laws for random knot diagrams[END_REF] that there is a constant d, 1 < d < 2, such that U min (n) < d n . To find explicit upper bounds for d, we can proceed as follows. Consider any fixed shadow T with m vertices, and let t := |U(T )|. Now let T k denote the connected sum T k of k copies of T . (One can easily extend to shadows the definition of the connected sum of diagrams). Since the connected sum of two diagrams is unknot if and only if each of the diagrams is unknot, it follows that T k has exactly t k unknot diagrams. Thus T k is a shadow with n := km vertices and |U(T k )| = t k = (t k/n ) n = (t 1/m ) n . From this it follows that U min (n) ≤ t 1/m .

To apply this approach we have explored a variety of shadows for which we can estimate (upper bound) their number of unknot diagrams. Using SnapPy [START_REF] Culler | SnapPy, a computer program for studying the geometry and topology of 3-manifolds[END_REF] we found that there is a shadow S on 16 vertices such that |U(S)| < 6416. From the previous discussion it follows that, for every positive integer n divisible by 16, U min (n) ≤ (6416

Figure 1 :

 1 Figure 1: On the left hand side we have a diagram of the figure-eight knot. By performing a crossing exchange on the top left crossing, we obtain the unknot diagram on the right hand side.

  v

Figure 2 :

 2 Figure 2: All the diagrams of these shadows are unknot.

Figure 3 :

 3 Figure 3: Every diagram of this shadow is either a trefoil diagram or an unknot diagram, and this can be easily generalized to obtain arbitrarily large shadows with the same property.

Figure 4 :

 4 Figure 4: Creating an uknot diagram starting from any given shadow.

Figure 5 :

 5 Figure 5: A macro move of Type A. In the diagram D on the left-hand side, the thick strand σ is an overstrand based at x. The diagram on the right-hand side is obtained by collapsing σ to x, that is, by removing σ \ {x} from D. Therefore these diagrams are equivalent.

Figure 6 :Proposition 7 .

 67 Figure 6: A macro move of Type B. The thick strand σ with endpoints x, y is an overstrand in the left-hand side diagram. We obtain the right-hand side diagram by replacing this overstrand with the overstrand σ . These diagrams are thus equivalent.

  The cycles D 1 , D 2 , . . . , D p are pairwise edgedisjoint, and S = ∪ p i=1 D i . The sequence D 1 , D 2 , . . . , D p is the primary sequence of C 1 , C 2 , . . . , C p . We can now give the first main ingredient in the proof of Theorem 2.

1 Figure 7 :

 17 Figure 7: Illustration of the proof of Proposition 7. y

Figure 8 :Lemma 8 .

 88 Figure 8: A cycle decomposition of the shadow S = S 1 in (a). In (b) we highlight with dotted edges a straight-ahead cycle C 1 of S 1 . After removing the edges of C 1 , and suppressing the three resulting degree 2 vertices, we reach the shadow S 2 = S 1 / /C 1 in (c). The dotted cycle C 2 in (c) is a straight-ahead cycle of S 2 , and in (d) we show the shadow S 3 = S 2 / /C 2 . We finally set C 3 = S 3 (thus C 3 is a vertex-free cycle). The sequence C 1 , C 2 , C 3 is then a cycle decomposition of S = S 1 .

Figure 10 :

 10 Figure10: Illustration of the proof of Proposition 10. On the left hand side we have the case in which δ ∩ ρ lies outside the disk ∆ bounded by β. Both γ and γ are segments inside ∆, and both (α, γ) and (α , γ ) are digons, neither of which contains z. In the example on the right hand side, δ ∩ ρ lies inside ∆, and γ is the only red segment that lies outside ∆. By letting α and α be the blue segments into which ρ naturally breaks β, we have that (α, γ) and (α , γ) are both digons. Of these two digons, only (α, γ) does not contain z.

Lemma 11 .

 11 Let S be a shadow, and let B and R be distinct straight-ahead cycles of S. Suppose that B and R have exactly m vertices in common. Then |U(S)| ≥ 2 m/2 .

Figure 11 :Figure 12 :

 1112 Figure 11: Obtaining S from S by splitting two vertices. The relevant part of the blue cycle B(respectively, red cycle R) is drawn with thick (respectively, thin) edges. The blue edge e and the red edge f have common endpoints u, v. We split each of u and v into two degree 2 vertices, and then suppress these four vertices. The resulting shadow S also has the property that it is the union of two straight-ahead cycles. We can naturally label these cycles B and R , letting B (respectively, R ) be the cycle that contains the remains of the red edge f (respectively, the blue edge e).

Figure 14 :

 14 Figure 14: On the left hand side we have a diagram of a shadow in which W 1 , W 2 , and W 3 are paths (this is actually a diagram of the shadow in Figure 13(b)), and the strand σ corresponding to W 3 is an overstrand. We can use a macro move of Type B to shift σ to a strand σ with no internal crossings, to obtain the equivalent diagram shown in (b). This last diagram is clearly a trefoil diagram, and so the diagram in (a) is a trefoil diagram of the shadow in Figure 13(b).

Figure 15 :

 15 Figure 15: The shadow C 7 . No diagram associated to C 7 is equivalent to a diagram of a knot with even crossing number (and in particular to the figure-eight knot).

|V 3 √

 3 (S)|=n |U(S)|, where the minimum is taken over all shadows with n vertices. Under this terminology, Theorem 2 gives the superpolynomial bound U min (n) ≥ 2 n . Leaving aside relatively marginal possible improvements, such as showing that U min (n) ≥ 2 √ n , the important question seems to be the following. Question 15. Is U min (n) an exponential, or a subexponential function?

Question 16 .

 16 1/16 ) n ≈ (1.729) n . Theorem 3 gives a structural characterization of which shadows have a trefoil diagram, and Observation 4 shows that there are arbitrarily large 2-connected shadows that do not have a figureeight diagram. It seems natural to inquire what can be said about the figure-eight knot: Is there a simple characterization of which shadows have a figure-eight diagram? Is it true that every sufficiently large 3-connected shadow contains a diagram of the figure-eight knot?

√ n for every positive integer n, it follows that in this case we are also done.

Acknowledgements

This work started while the second author visited the other authors, supported by the Laboratorio Internacional Asociado Solomon Lefschetz (LAISLA), which has now become the Unité Mixte Internationale CNRS-CONACYT-UNAM "Laboratoire Solomon Lefschetz". The first and third author were supported by Conacyt grant 222667. We thank Ronald Ortner for helpful comments, and Mario Eudave for his guidance at the beginning of this project.


Idir Hamaz
email: ihamaz@laas.fr

Laurent Houssin
email: lhoussin@laas.fr

Sonia Cafieri
email: sonia.cafieri@enac.fr

A Branch-and-Bound procedure for the robust cyclic job shop problem

Keywords: Cyclic job shop problem, robust optimization, Branch-and-Bound algorithm

This paper deals with the cyclic job shop problem where the task durations are uncertain and belong to a polyhedral uncertainty set. We formulate the cyclic job shop problem as a two-stage robust optimization model. The cycle time and the execution order of tasks executed on the same machines correspond to the here-and-now decisions and have to be decided before the realization of the uncertainty. The starting times of tasks corresponding to the wait-and-see decisions are delayed and can be adjusted after the uncertain parameters are known. In the last decades, different solution approaches have been developed for two-stage robust optimization problems. Among them, the use of affine policies, column generation algorithms, row and row-and-column generation algorithms. In this paper, we propose a Branch-and-Bound algorithm to tackle the robust cyclic job shop problem with cycle time minimization. The algorithm uses, at each node of the search tree, a robust version of the Howard's algorithm to derive a lower bound on the optimal cycle time. We also develop a heuristic method that permits to compute an initial upper bound for the cycle time. Finally, encouraging preliminary results on numerical experiments performed on randomly generated instances are presented.

Introduction

Most models for scheduling problems assume deterministic parameters. In contrast, real world scheduling problems are often subject to many sources of uncertainty. For instance, activity durations can decrease or increase, machines can break down, new activities can be incorporated, etc. In this paper, we focus on scheduling problems that are cyclic and where activity durations are affected by uncertainty. Indeed, the best solution for a deterministic problem can quickly become the worst one in the presence of uncertainties.

In this work, we focus on the Cyclic Job Shop Problem (CJSP) where processing times are affected by uncertainty. Several studies have been conducted on the CJSP in its deterministic setting. The CJSP with identical jobs is studied in [START_REF] Roundy | Cyclic schedules for job shops with identical jobs[END_REF] and the author shows that the problem is N P-hard and proposes a Branch-and-Bound algorithm to solve the problem. The more general CJSP is investigated in [START_REF] Hanen | Study of a np-hard cyclic scheduling problem: The recurrent job-shop[END_REF], where the author proposes a mixed linear integer programming formulation and presents a Branch-and-Bound procedure to tackle the problem. A general framework for modeling and solving cyclic scheduling problems is presented in [START_REF] Brucker | A general model for cyclic machine scheduling problems[END_REF]. The authors present different models for cyclic versions of CJSP. However, a few works consider cyclic scheduling problems under uncertainty. The cyclic hoist scheduling problem with processing time window constraints where the hoist transportation times are uncertain has been investigated by Che et al. [START_REF] Che | Robust optimization for the cyclic hoist scheduling problem[END_REF]. The authors define a robustness measure for cyclic hoist schedule and present a bi-objective mixed integer linear programming model to optimize both the cycle time and the robustness.

Two general frameworks have been introduced to tackle optimization problems under uncertainty. These frameworks are Stochastic Programming (SP) and Robust Optimization (RO). The main difference between the two approaches is that the Stochastic Programming requires the probability description of the uncertain parameters while RO does not. In this paper, we focus on the RO paradigm. More precisely, we model the robust CJSP as a two-stage RO problem. The cycle time and the execution order of tasks on the machines corresponding to the here-and-now decisions have to be decided before the realization of the uncertainty, while the starting times of tasks corresponding to the wait-and see decisions are delayed and can be adjusted after the uncertain parameters are known. In recent years there has been a growing interest in the two-stage RO and in the multi-stage RO in general. The two-stage RO is introduced in [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF], referred to as adjustable optimization, to address the over-conservatism of single stage RO models. Unfortunately, the two-stage RO problems tend to be intractable [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF]. In order to deal with this issue, the use of affine policies ( [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF]) and decomposition algorithms ( [START_REF] Thiele | Robust linear optimization with recourse[END_REF], [START_REF] Zeng | Solving two-stage robust optimization problems using a columnand-constraint generation method[END_REF], [START_REF] Ayoub | Decomposition for adjustable robust linear optimization subject to uncertainty polytope[END_REF]) have been proposed. This paper deals with the CJSP where the task durations are uncertain and belong to a polyhedral uncertainty set. The objective is to find a minimum cycle time and an execution order of tasks executed on the same machines such that a schedule exists for each possible scenario in the uncertainty set. To tackle the problem we design a Branch-and-Bound algorithm. More precisely, at each node of the search tree, we solve a robust Basic Cyclic Scheduling Problem (BCSP), which corresponds to the CJSP without resource constraints, using a robust version of Howard's algorithm to get a lower bound. We also propose a heuristic algorithm to find an initial upper bound on the cycle time. Finally, we provide results on numerical experiments performed on randomly generated instances. This paper is structured as follows. In Section 2, we present both the Basic Cyclic Scheduling Problem and the Cyclic Job Shop Problem in their deterministic case and introduce the polyhedral uncertainty set considered in this study. Section 3 describes a Branch-and-Bound (B&B) procedure to solve the robust CJSP. Numerical experiments performed on randomly generated instances are reported and discussed in Section 4. Finally, some concluding remarks and perspectives are drawn in Section 5.

The cyclic scheduling problems

In this section, we first introduce the Basic Cyclic Scheduling Problem which corresponds to the CJSP without resource constraints. This problem will represent a basis for the Branch-and-Bound method designed for the robust CJSP solving. Next, we present the CJSP in its deterministic case. Finally, we present the uncertainty set that we consider in this paper and we formulate the CJSP with uncertain processing times as a two-stage robust optimization problem.

Basic Cyclic Scheduling Problem (BCSP)

Let T = {1, ..., n} be a set of n generic operations. Each operation i ∈ T has a processing time p i and must be performed infinitely often. We denote by < i, k > The k th occurrence of the operation i and by t(i, k) the starting time of < i, k >.

The operations are linked by a set P of precedence constraints (uniform constraints) given by

t(i, k) + p i t(j, k + H ij ), ∀(i, j) ∈ P, ∀k ≥ 1, (1)
where i and j are two generic tasks and H ij is an integer representing the depth of recurrence, usually referred to as height. Furthermore, two successive occurrences of the same task i are not allowed to overlap. This constraint corresponds to the non-reentrance constraint and can be modeled as a uniform constraint with a height H ii = 1.

A schedule S is an assignment of starting time t(i, k) for each occurrence < i, k > of tasks i ∈ T such that the precedence constraints are met. A schedule S is called periodic with cycle time α if it satisfies t(i, k) = t(i, 0) + αk, ∀i ∈ T , ∀k ≥ 1.

(

For the sake of simplicity, we denote by t i the starting time of the occurrence < i, 0 >. Since the schedule is periodic, a schedule can be completely defined by the vector of the starting times (t i ) i∈T and the cycle time α.

The objective of the BCSP is to find a schedule that minimizes the cycle time α while satisfying precedence constraints. Note that other objective functions can be considered, such as work-in-process minimization [START_REF] Hanen | Study of a np-hard cyclic scheduling problem: The recurrent job-shop[END_REF].

A directed graph G = (T , P), called uniform graph, can be associated with a BCSP such that each node v ∈ T (resp. arc (i, j) ∈ P) corresponds to a generic task (resp. uniform constraint) in the BCSP. Each arc (i, j) ∈ P is labeled with two values, a length L ij = p i and a height H ij .

We denote by L(c) (resp. H(c)) the length (resp. height) of a circuit c in graph G, representing the sum of lengths (resp. heights) of the arcs composing the circuit c.

Let us recall the necessary and sufficient condition for the existence of a feasible schedule.

Theorem 1 (Hanen C. [2]). There exists a feasible schedule if and only if any circuit of G has a positive height.

A graph that satisfies the condition of Theorem 1 is called consistent. In the following, we assume that the graph G is always consistent. In other words, a feasible schedule always exists.

The minimum cycle time is given by the maximum circuit ratio of the graph G that is defined by

α = max c∈C L(c) H(c)
where C is the set of all circuits in G. The circuit c with the maximum circuit ratio is called a critical circuit. Thus, the identification of the critical circuit in graph G allows one to compute the minimum cycle time.

Many algorithms for the computation of the cycle time and the critical circuit can be found in the literature. A binary search algorithm with time complexity O(nm log(n) + log(max (i,j)∈E (L ij , H ij )) ) has been proposed in [START_REF] Gondran | Graphs and Algorithms[END_REF]. Experimental study about maximum circuit ratio algorithms has been presented in [START_REF] Dasdan | Experimental analysis of the fastest optimum cycle ratio and mean algorithms[END_REF]. This study shows that the Howard's algorithm is the most efficient among the tested algorithms.

Once the optimal cycle time α is determined by one of the algorithms cited above, the optimal periodic schedule can obtained by computing the longest path in the graph G = (T , P) where each arc (i, j) ∈ P is weighted by p i -αH ij .

The BCSP can also be solved by using the following linear program:

min α (3)
s.t. t j -t i + αH ij ≥ p i ∀(i, j) ∈ P (4)
where t i represents t(i, 0), i.e., the starting time of the first occurrence of the task i. Note that the precedence constraints (4) are obtained by replacing in (1) the expression of t(i, k) given in (2).

Cyclic Job Shop Problem (CJSP)

In the present work, we focus on the cyclic job shop problem (CJSP). Contrary to the BCSP, in the CJSP, the number of machines is lower than the number of tasks. As a result, an execution order of the operations executed on the same machine have to be determined. Each occurrence of an operation i ∈ T = {1, ..., n} has to be executed, without preemption, on the machine M (i) ∈ M = {1, ..., m}. Operations are grouped on a set of jobs J , where a job j ∈ J represents a sequence of generic operations that must be executed in a given order. To avoid overlapping between the tasks executed on the same machine, for each pair of operations i and j where

M (i) = M (j) , the following disjunctive constraint holds ∀ i, j s.t. M (i) = M (j) , ∀k, l ∈ N : t(i, k) ≤ t(j, l) ⇒ t(i, k) + p i ≤ t(j, l) (5) V
To summarize, the CJSP is defined by

• a set T = {1, ..., n} of n generic tasks, • a set M = {1, ..., m} of m machines,
• each task i ∈ T has a processing time p i and has to be executed on the machine M (i) ∈ M, • a set P of precedence constraints, • a set D of disjunctive constraints that occur when two tasks are mapped on the same machine, • a set J of jobs corresponding to a sequence of elementary tasks. More precisely, a job J j defines a sequence J j = O j,1 . . . O j,k of operations that have to be executed in that order.

The CJSP can be represented by directed graph G = (T , P ∪ D), called disjunctive graph. The sequence of operations that belong to the same job are linked by uniform arcs in P where the heights are equal to 0. Additionally, for each pair of operations i and j executed on the same machine, a disjunctive pair of arcs (i, j) and (j, i) occurs. These arcs are labeled respectively with L ij = p i and H ij = K ij , and L ji = p j and H ji = K ji where K ij is an occurrence shift variable to determine that satisfy K ij +K ji = 1 (see [START_REF] Hanen | Study of a np-hard cyclic scheduling problem: The recurrent job-shop[END_REF] for further details). Note that the K ij variables are integer variables and not binary variables as is the case for the non-cyclic job shop problem. Two dummy nodes s and e representing respectively the start and the end of the execution are added to the graph. An additional arc (e,s) with L es = 0 and H ij = W IP is considered. The W IP parameter is an integer, called a work-in-process, and represents the number of occurrences of a job concurrently executed in the system.

A lower bound on each occurrence shift value K ij that makes the graph G consistent can be obtained as follows (see [START_REF] Hanen | Study of a np-hard cyclic scheduling problem: The recurrent job-shop[END_REF], [START_REF] Fink | A new procedure for the cyclic job shop problem[END_REF]):

K - ij = 1 -min{H(µ) | µ is a path from j to i in G = (T , P ∪ ∅)}. (6)
Since K ij + K ji = 1, one can deduce an upper bound:

K - ij ≤ K ij ≤ 1 -K - ji . (7)
The objective of the problem is to find an assignment of all the occurrence shifts, in other words, determining an order on the execution of operations mapped to the same machine such that the cycle time is minimum. Note that, once the occurrence shifts are determined, the minimum cycle time can be obtained by computing the critical circuit of the associated graph G.

CJSP problem with uncertain processing times (U Γ -CJSP)

We define the uncertainty set through the budget of uncertainty concept introduced in [START_REF] Bertsimas | The price of robustness[END_REF]. The processing times (p i ) i∈T are uncertain and each processing time p i belongs to the interval [ pi , pi + pi ], where pi is the nominal value and pi the deviation of the processing time p i from its nominal value. We associate a binary variable ξ i to each operation i ∈ T . The variable ξ i is equal to 1 if the processing time of the operation i takes its worst-case value, 0 otherwise. For a given budget of uncertainty Γ , that is a positive integer representing the maximum number of tasks allowed to take their worst-case values, the processing time deviations can be modeled trough the following uncertainty set:

U Γ = (p i ) i∈T ∈ R n : p i = pi + pi ξ i , ∀ i ∈ T ; ξ i ∈ {0, 1}; i∈T ξ i ≤ Γ .
The BCSP problem under the uncertainty set U Γ is studied in [START_REF] Hamaz | Robust Basic Cyclic Scheduling Problem[END_REF]. Three exact algorithms are proposed to solve the problem. Two of them use a negative circuit detection algorithm as a subroutine and the last one is a Howard's algorithm adaptation. Results of numerical experiments show that the Howard algorithm adaptation yields efficient results.

The problem we want to solve in this study can be casted as follows:

min α (8) s.t. ∀ p ∈ U Γ : ∃ t ≥ 0 t j -t i + αH ij ≥ p i ∀ (i, j) ∈ P t j -t i + αK ij ≥ p i ∀ (i, j) ∈ D (9)
K ij + K ji = 1 ∀ (i, j) ∈ D (10)
K - ij ≤ K ij ≤ 1 -K - ji ∀ (i, j) ∈ D (11)
K ij ∈ Z ∀ (i, j) ∈ D (12)
α ≥ 0

In other words, we aim to find a cycle α and occurrence shifts (K ij ) (i,j)∈D such that, for each possible value of the processing times p ∈ U Γ , there always exists a feasible vector of starting time (t i ) i∈T . Note that, once the occurrence shifts are fixed, the problem can be solved as a robust BCSP by using the algorithms described in [START_REF] Hamaz | Robust Basic Cyclic Scheduling Problem[END_REF]. The following theorem characterizes the value of the optimal cycle time for U Γ -CJSP: Theorem 2 ( [START_REF] Hamaz | Robust Basic Cyclic Scheduling Problem[END_REF]). The optimal cycle time α of the U Γ -CJSP is characterized by

α = max c∈C      (i,j)∈c Lij (i,j)∈c H ij + max ξ: i∈T ξi≤Γ      (i,j)∈c Lij ξ i (i,j)∈c H ij          
, where Lij = pi , Lij = pi and C is the set of all circuits in G.

Branch-and-Bound method

We develop a Branch-and-Bound algorithm for solving U Γ -CJSP. Each node of the Branch-and-Bound corresponds to a subproblem defined by the subgraph G s = (T , P ∪ D s ), where D s ⊆ D is a subset of occurrence shifts already fixed.

The algorithm starts with a root node G root where D root = ∅, in other words, no occurrence shifts are fixed. The branching is performed by fixing an undetermined occurrence shift K ij and creates a child node for each possible value of

K ij in [K - ij , 1 -K - ji ].
Each of these nodes is evaluated by computing the associated cycle time, such that a schedule exists for each p ∈ U Γ . This evaluation is made by means of the robust version of Howard's algorithm. Our method explores the search tree in best-first search (BeFS) manner, and, in order to branch, it chooses the node having the smallest lower bound. This search strategy can lead to a good feasible solution. A feasible solution is reached when all occurrence shifts are determined. Note that the nominal starting times (i.e. the starting times when no deviation occurs) can be determined by computing the longest path in the graph G where each arc (i, j) is valued by p i -αH ij , and the adjustment is accomplished by shifting the starting of the following tasks by the value of the deviation. More details are provided in the next subsections.

Computation of an initial upper bound of the cycle time

In order to compute an initial upper bound, we design a heuristic that combines a greedy algorithm with a local search. The greedy algorithm assigns randomly a value to a given occurrence shift

K ij in the interval [K - ij , 1 -K - ji ]
, and updates the bounds on the rest of the occurrences shifts such that the graph remains consistent. These two operations are repeated until all occurrence shifts are determined. Once all occurrence shifts are determined, a feasible schedule is obtained, consequently the associated optimal cycle time represents an upper bound of the global optimal cycle time. The local search algorithm consists in improving the cycle time by adjusting the values of the occurrence shifts that belong to the critical circuit. The idea behind these improvements is justified by the following proposition: Proposition 1. Let (K ij ) (i,j)∈D be a vector of feasible occurrence shifts and ᾱ the associated cycle time given by the critical circuit c. Let (u, v) ∈ D be a disjunctive arc such that (u, v) ∈ c. If the following relation holds:

max l∈P uv max p∈U Γ (i,j)∈l p i -ᾱH ij + p v -ᾱ(K vu -1) ≤ 0, ( 14
)
where P uv is the set of paths from u to v, then the solution (K ij ) (i,j)∈D where K uv = K uv + 1 and K vu = K vu -1 has a cycle time less or equal to ᾱ.

Proof. Let (K ij ) (i,j)∈D be a vector of feasible occurrence shifts, ᾱ the associated cycle time given by the critical circuit c and (u, v) ∈ D a disjunctive arc that belongs to c. Let us assume that relation ( 14) is verified. It is easily seen that putting K uv = K uv + 1 makes the height of the circuit c increase by one and consequently makes decrease the value of its circuit ratio. In order to maintain the condition K uv + K vu = 1 verified, increasing the value of K uv by one involve decreasing the value of K vu by one. Now, it follows that decreasing the value of K vu by one must ensure that the values of the circuits passing through the disjunctive arc (u, v) do not exceed ᾱ. This condition is verified, because by ( 14) we have:

max l∈P uv max p∈U Γ (i,j)∈l p i + p v (i,j)∈l H ij + (K vu -1) ≤ ᾱ
In other words, the maximum circuit ratio passing by the disjunctive arc (j, i) has a value less or equal to ᾱ. Moreover, since the value of ᾱ and the values of the processing times are positives, then (i,j)∈l H ij + (K vu -1) > 1. This ensure that the associated graph to the robust CJSP is still consistent and the solution (K ij ) (i,j)∈D is feasible.

The pseudo-code of the proposed heuristic is given in Algorithm 1.

Algorithm 1 Initial upper bound computation

1: Compute a lower bounds on the occurrences shifts Kij; 2: for all (i, j) ∈ D do 3:

Update bounds on the occurrence shifts; 4:

Affect randomly value to Kij on the interval [K - ij , 1 -K - ji ]; 5: end for 6: Compute the associated cycle time ᾱ and the critical circuit c. 7: while it < itmax do 8:

Let (u, v) ∈ {(u, v) ∈ D such that (u, v) ∈ c}; 9: luv ← max l∈P uv max p∈U Γ
(i,j)∈l pi -ᾱHij; 10:

if luv + pv -ᾱ(Kvu -1) ≤ 0 then 11:

Kuv ← Kuv + 1; 12:

Kvu ← Kvu -1; 13:

end if 14:

Compute the associated cycle time ᾱ and the critical circuit c; 15: it← it+1; 16: end while

Lower bound

In the Branch-and-Bound algorithm, an initial lower bound is derived and compared to the incumbent. If the value of the initial lower bound and the value of the incumbent are equal, then an optimal solution is obtained and the Branchand-Bound is stopped. It is easily seen that the problem where the disjunctive arcs are ignored is a relaxation of the initial problem. Consequently, the associated cycle time, α basic , is a lower bound on the optimal cycle time. Furthermore, an other lower bound can be computed by reasoning on the machine charges. Let M (i) ∈ M be a given machine and S ⊆ T the set of operations mapped on the machine M (i) , then the optimal cycle time α opt ≥ i∈S p i , for each p ∈ U Γ . Since this relation is verified for each machine, one can deduce the following lower bound:

α machine = max m∈M,p∈U Γ    i∈T :M (i) =m p i    .
In the Branch-and-Bound procedure, we set the initial lower bound LB to the maximum value between α machine and α basic .

Node evaluation

In the Branch-and-Bound algorithm, we aim to find a feasible vector (K ij ) (i,j)∈D of occurrence shifts such that the value of the associated cycle time that ensure, for each p ∈ U Γ , the existence of schedule is minimum. In order to fathom nodes with partial solution in the search tree, it has to be evaluated by computing an associated lower bound. Let us consider a given node of the search tree defined by the subgraph G s = (T , P ∪ D s ), where D s ⊆ D is the set of fixed occurrence shifts. This subgraph represents a relaxation of the initial problem since only a subset a disjunctive arcs is considered. Consequently, the associate cycle time is a lower bound on the optimal cycle time.

Branching scheme and branching rule

To our knowledge, two branching schemes have been proposed for the cyclic job shop problem. In both of the branching schemes, the branching is performed on the unfixed occurrence shifts. The first one is introduced in [START_REF] Hanen | Study of a np-hard cyclic scheduling problem: The recurrent job-shop[END_REF]. Based on the interval of possibles values [K - ij , 1 -K - ji ] for the occurrence shift K ij such that (i, j) ∈ D, the author uses a dichotomic branching. In the first generated node, the interval of possible values of the occurrence shifts

K ij is restricted to [K - ij , c ij ] and in the second one it is restricted to [c ij + 1, 1 -K - ji ]
, where c ij is the middle of the initial interval. The second branching scheme is introduced in [START_REF] Fink | A new procedure for the cyclic job shop problem[END_REF]. The branching consists in selecting an unfixed disjunction and generate a child node for each possible value of the occurrence shift

K ij in the interval [K - ij , 1 -K - ji ].
In each node, the algorithm assigns the corresponding possible value to the occurrence shift K ij . In this paper, we follow the same branching scheme introduced in [START_REF] Fink | A new procedure for the cyclic job shop problem[END_REF]. This branching scheme allows us to have, at each node, a subproblem which corresponds to a robust BCSP. Consequently, we can use the existing robust version of the Howard's algorithm to find the cycle time ensuring, for each p ∈ U Γ , the existence of a schedule. Different branching rules have been tested and numerical tests show that branching on occurrence shifts K ij where K - ij + K - ji is maximum yields best running times. This performance can be explained by the fact that this branching rule generates a small number of child nodes, which limits the size of the search tree.

We implemented the Branch-and-Bound algorithm in C++ and conducted the numerical experiments on an Intel Xeon E5-2695 processor running at 2.30GHz CPU. The time limit for each instance is set up to 900 seconds.

Since there are no existing benchmarks for the CJSP, even in its deterministic setting, we generate randomly 20 instances for each configuration as follows. We consider instances where the number of tasks n varies {10, 20, 30, 40, 50, 60, 80, 100}, the number of jobs j in {2, 3, 4, 5, 6, 10, 16} and the number of machines m in {5, 6, 8, 10}. Each nominal duration pi of task i is generated with uniform distribution in [START_REF] Roundy | Cyclic schedules for job shops with identical jobs[END_REF][START_REF] Dasdan | Experimental analysis of the fastest optimum cycle ratio and mean algorithms[END_REF] and its deviation value pi in [0, 0.5p i ].

Table 1 reports average solution times for the instances having from 10 to 40 tasks and with a budget of uncertainty varying from 0% to 100%. All these instances are solved before reaching the time limit. The average running times show that the Branch-and-Bound algorithm is not very sensitive to the variation of the budget of the uncertainty, but there is still a small difference. This can be explained by the number of the nodes explored in the Branch-and-Bound tree which can differ from an instance with a given value of Γ to another one. Table 1 also displays the percentage of deviation, for a given budget of uncertainty Γ , of the optimal cycle time α Γ from the nominal optimal cycle time α nom , where all tasks take their nominal values. This percentage of deviation is computed as Dev α = α Γ -αnom αnom . The table shows that the percentage of deviations varies from 25.41% to 56.43%. In other words, these deviations represent the percentage of the nominal cycle time that has to be increased in order to protect a schedule against the uncertainty. We remark that the deviations stabilize when the budget of the uncertainty is greater than 20 or 30 percent. This situation occurs probably when the number of arcs of the circuit having the maximum number of arcs is less than Γ . In this case, increasing Γ does not influence the optimal cycle time. The second situation occurs when heights of other circuits than the actual critical circuit c have greater value than the height of c. In this case, increasing the budget of the uncertainty does not make the value of c lower than the others.

Table 2 shows the number of the instances that are solved before reaching the time limit. These results concern instances having from 50 to 100 tasks. The table shows that the Branch-and-Bound is not able to solve all these instances in less then 900 seconds. For example, among instances with 80 tasks, 16 jobs and 5 machines, only three instances have been solved.

Concluding remarks and perspectives

In this paper, we consider the cyclic job shop problem where the task durations are subject to uncertainty and belong to a polyhedral uncertainty set. We model the problem as two-stage robust optimization problem where the cycle time and the execution order of tasks mapped on the same machine have to be decided before knowing the uncertainty, and the starting times of tasks have to be determined after the uncertainty is revealed. We propose a Branch-and-Bound method that solves instances with at most 40 tasks but starts to have difficulties with bigger instances. The next step is to investigate other techniques such as decomposition algorithms.

2 .

 2 Number of solved instances in less than 900 seconds among 20 instances.

Table 1 .

 1 Average solution times in seconds for the Branch-and-Bound algorithm and percentage value of the deviation of the cycle time from the nominal cycle.

	# Tasks # Jobs # Machines Γ (%) Devα(%) Time (s)
				0	0	0.012
				10	25.41 0.0123
				20	41.89 0.0137
				30	48.95 0.0157
	10	2	5	40	51.67 0.0171
				50	53.18 0.0185
				70	53.49 0.0214
				90	53.49 0.0251
				100	53.49 0.0256
				0	0	0.2980
				10	33.61 0.2136
				20	49.49 0.2432
				30	55.44 0.5685
	20	3	6	40	56.43 0.2994
				50	56.43 0.3258
				70	56.43 0.3783
				90	56.43 0.3996
				100	56.43 0.4695
				0	0	22.6434
				10	38.25 12.0085
				20	49.03 15.4099
				30	50.91 66.2474
	30	5	8	40	50.91 16.3096
				50	50.91 17.1160
				70	50.91 13.8331
				90	50.91 15.7524
				100	50.91 15.8249
				0	0	138.9174
				10	37.92 55.9220
				20	54.46 92.1455
				30	54.91 96.7587
	40	4	8	40	54.91 134.4442
				50	54.91 155.2327
				70	54.91 187.2088
				90	54.91 204.4813
				100	54.91 177.2455