Armand Hatchuel
email: armand.hatchuel@mines-paristech.fr

Milena Klasing Chen

Creativity under strong constraints: the hidden influence of design models

In engineering design, constraints can stimulate creativity, but are also often cited as obstacles to innovation. So, do constraints hinder or foster creativity? Despite a number of studies, the reason why constraints can have a positive or a negative impact on creativity is still unknown. In this paper, we will support theoretically and empirically that the link between creativity and constraints is not determined by the type of constraints, but by the type of "design model" used. Using C-K theory -a well-documented, general, and formalized theory of design -we first prove that the dual impact of constraints on creativity is predictable. We thenuse C-K operators to distinguish two different design models: rule-based design and innovative design.We show that the first modelleads to a negative link between constraints and creativity; while the second model enables a positive effect. We illustrate these mechanisms through the analysis of several product developments based on both secondary and primary sources.

Introduction

In engineering design, as stated by Onarheim [START_REF] Onarheim | Creativity from constraints in engineering design: lessons learned at Coloplast[END_REF] , creativity and constraints are inevitably related. According to the Oxford dictionary, constraints are limitations or restrictions. When designing new products, constraints are the main reason why creativity is needed andnew solutions only emerge because of the identification of new constraints. But constraints are also often cited as the reason why creativity fails: in some cases, like in a mathematical problem, too many constraints can make it very hard to find a solution. So, do constraints hinder or foster creativity? Despite a number of studies trying to identify why or which constraints can have a positive ora negative impact on creativity, previous literature provides no clear explanation for this dual link. Thus we are left with the need to identify the hidden variable whose influence will determine when constraints will have a positive or a negative impact on creativity.

In this paper, we will discussa new research hypothesis: the link between creativity and constraints is not determined by the type of constraints, but bythe type of design model used. We will also show both theoretical and empirical elements that supports this hypothesis.

To define what we mean by "design model" we will bear on recent developments in Design theory, namely C-K design theory [START_REF] Hatchuel | A new approach of innovative design: an introduction to C-K theory[END_REF][START_REF] Hatchuel | C-K design theory: an advanced formulation[END_REF] that clarifies the distinction between two main design models:

i) The innovative design model,whichtriggers "expansions" and uses constraintsto enhance creativity;

ii)The rule-based design model, where constraints lead to a lock-in and to less innovations, or to no innovation at all.

In the following article we will characterize these two models using the notions and operators of C-K theory; and we will establish why they determine a positive or a negative relation between constraints and creativity.We will illustrate these mechanisms through the analysis of several product developments based on secondary sources and primary studies.

This paper is therefore composed of a literature review, showing the undetermined relation between constraints and creativity in engineering design and our research hypothesis. We then present contemporary design theory through the framework of C-K theory [START_REF] Hatchuel | A new approach of innovative design: an introduction to C-K theory[END_REF] , and explain how it predicts the two different impacts of constraints on creativity. Afterwards, wepresent empirical material that supports these predictions: case studies in which product developments and engineering tasks face strong constraints. We conclude by stating that the innovative design model and its associated form of reasoning should be taught and used extensively to foster the positive impact of constraints on creativity.

Literature review: The undetermined relation between constraints and creativity in engineering design

In engineering design,we often refer to creativity as defined by Amabile 4 (p126): "creativity is the production of novel and useful ideasby an individual or small group of individuals working together." She specifies that this definition is product-based, and novelty and usefulness of the product are evaluated. Creative ideas are described as the building blocks of innovation [START_REF] Amabile | A model of creativity and innovation in organizations[END_REF] . Therefore, we will here use creativity as the cognitive process that results in innovations.

Furthermore, Amabile [START_REF] Amabile | A model of creativity and innovation in organizations[END_REF] states that the highest level of individual creativity and highest innovation for organizations is reached in the intersection of resources, techniques and motivations. As stated by Rosso [START_REF] Rosso | Creativity and Constraint: Exploring the Role of Constraint in the Creative Processes of New Product and Technology Development Teams[END_REF] , following this construct of creativity means that constraints on resources and techniques should have a negative impact on creativity, reducing the innovative outcomes of the process. He furthermore states that constraints are also often described asreducing the "intrinsic motivation", which also should have a negative effect on the outputs of the creative process.

Despite this, many papers in engineering design support the idea that constraints lead to innovations, insisting on the positive effect constraints have on creativity.Literature on frugal innovation [START_REF] Rao | How disruptive is frugal?[END_REF] , on jugaad innovation [START_REF] Radjou | Jugaad Innovation: Think Frugal, Be Flexible, Generate Breakthrough Growth[END_REF] and on resource constrained product development [START_REF] Sharmaandg | Resource-constrained product development: Implications for green marketing and green supply chains[END_REF] cites the lack of resources, an obvious type of constraints, as the main trigger forcreative solutions. Authors defend that having less resources available forces to disrupt existing solutions, since the lack of resources make it impossible to adopt a regular solution. In these cases the severity of the constraints,like for instance dividing costs by 10 or 100, is often cited as what made them effective in triggering creativity. Keupp and Gassmann 9 also support a positive influence of knowledge constraints in the creation of radical innovation, leading to the reuse of previously unused knowledge andto knowledge re-organization.

The link between creativity and constraints in engineering design is therefore undetermined. Onarheim 1 speaks of a dual link between creativity and constraints, since constraints seem to have a positive and a negative influence according to the setting. Rosenzweig and Mazursky 10 also show that constraints can both enhance and limit creativity. According to their study some constraints on knowledge can lead to improve innovativeness, but extreme knowledge constraints reduce the firm's innovativeness.

Exploring the causes of the undetermined link

Reasons for this dual link have been looked for in the nature of constraints. Several efforts to classifyconstraintsand prove their contingent effectshave been attempted [START_REF] Lawson | Design Expertise[END_REF] .The classification proposed by Lawson and Dorst 11 is done according to three dimensions. The first dimension is the generator of the constraint, whocan be the designer, the client, the user or legislators. The second dimension defines a constraint as being internal to the designed product or contextual. The third dimension can beseparated into four types:functional, practical/technical, compositional or symbolic constraints. However, researchers found no evidence that the type of constraint was linked to a positive or negative influence on creativity.

Another hypothesis that has been tested without success is if being an individual or a team might be the explainingvariable for the impact of constraints on the creative process.Researchers have also investigated the influence of the designer's personality. However, Onarheim 1 finds that the same designer can in one project perceive a type of constraint as enhancing his creativity, and in another project see the same type of constraint as limiting his options. Although Rosso [START_REF] Rosso | Creativity and Constraint: Exploring the Role of Constraint in the Creative Processes of New Product and Technology Development Teams[END_REF] observes that team dynamics seem to influence this link, he states the link is not direct, and that the team dynamics, which he classified as "enabling" or "disabling" dynamics, can evolve over time.

We can thereforestate that the inconclusiveness of the existing literature reinforces the hypothesis that there may exist a hidden factor that affects the relationship between the outcomes of the creative process and constraints, as illustrated in Figure 1. This factor has not been identified so far;and previous studies seem to reject the idea that this hidden factor could be found in some typology of constraints. Our research has explored a different path. We will explain this dual link by the influence of a new type of variable, the type of design process that is used, which we call a design model. Figure 1 -Modeling the effect of constraints on creativity through the hypothesis of a hidden factor

Thevariable impact ofconstraints on creativity:a prediction of design theory

C-K design theory 2 has been recognized as a general and rigorous theory of design reasoning. We will now establish that C-K design theory: i) Predicts the dual link between constraints and creativity; ii) Helps to identify two design models that determine a positive or a negative link between constraints and creativity.

Introduction to C-K theory

We hereby propose a quick introduction to C-K theory. In C-K theory we have two different spaces, a concept (C) space and a knowledge (K) space. The C space contains propositions that do not have a logical status, which means that they are undecidable in K, neither true nor false. The K space contains propositions Crea ve process Constraints + Innova on -Innova on ? with a logical status, which means that they are either true or false [START_REF] Hatchuel | C-K design theory: an advanced formulation[END_REF] . The C-space is organized as a series of properties linked to an original concept in a tree-like fashion, while the K space is composed in an archipelagic way. A typical C-K representation is represented in Figure 2.



From C to K -this interaction is called a conjunction, and it means that a concept has reached a state where it achieves a logical status, and therefore becomes part of the knowledge space. This operator signals a final design has been reached.



From K to K -this interaction allows creating new knowledge from the existing knowledge, through deduction, modeling, optimization or evaluation.



From C to C -this interaction allows creating new concepts through partitioning or inclusion.

Constraints as knowledge

Given these basic elements of C-K theory, it is easy to establish new implications of what is called "constraints": a) Constraints in C-K theory are necessarily parts of the knowledge space, as they only have an impact if they are accepted as true. We will identify them as K*. Seeing constraints as knowledge extends the classic perspective of constraints as restrictions; it tells us that any restriction also describes unknown knowledge domains. For instance, if a cost is limited to a maximum P, such proposition can also indicate that the whole set of things, services, or processes, whose cost is inferior to P is largely unknown to the designer. Thus the constraints also act as a potential knowledge organizer preparing new K reordering [START_REF] Hatchuel | Towards an ontology of design: lessons from C-K design theory and Forcing[END_REF] . b) Adding a new knowledge (K* in our case) in the K space can have different impacts both on the C and the K space, which directly predicts a complex influence. c)In the C space, new knowledge can have three different impacts: i) it can block a previous path, hence block a design candidate; ii) it can create a new property,opening up a new path; and iii) it can re-open a previously blocked or pending C path. d) In the K space, adding K* can lead to a K-restructuring [START_REF] Potier | How innovative design can contribute to Chemical and Process Engineering development? Opening new innovation paths by applying the C-K method[END_REF] ,fostering the production of new knowledge or invalidating a given knowledge base, which will no longer be accepted astrue. These four types of impact are illustrated in Figure 3.

Defining design models as enablers of constraints' impacts: rule-based design and innovative design

We will now model the design reasoning when constraints are added in the C-K framework as described in two important currents inside design theories, rulebased design and innovative design. We find they have different approaches to constraints.

One example of rule-based design is systematic design, in which according to Pahl and al. [START_REF] Pahl | Engineering Design: A Systematic Approach[END_REF] , "the main task of engineers is to apply their scientific and engineering knowledge to the solution of technical problems, and then to optimize those solutions within the requirements and constraints set by material, technological, economic, legal, environmental and human-related considerations."This definition is modeled in Figure 4. Therefore constraints are seen as considerations that reduce the possible scope of solutions, since they are the borders and limitations needed to choose an optimum solution. In rule-based design, efforts are often focused on exploring improvements of an existing product. The identity of the product, which is defined by the set of main properties of this product, is not challenged. So when a constraint in rulebased design forbids an important property of the product, this is limiting, since alternatives would challenge the identity of the product. In C-K theory this means only small changes in the C space (δC).

Another characteristic of rule-based design theories is that the goal is to propose solutions with a maximum reuse of existing knowledge [START_REF] Le Masson | The Interplay between Creativity Issues and Design Theories: A New Perspective for Design Management Studies?[END_REF] . This means that any constraint that would demand an important creation of new knowledge to be overcome would also be limiting, since creating a lot of new knowledge is considered too costly. This means that there are only small changes in the K space (δK).

In innovative design theories, on the contrary, efforts are focused on challenging all the properties of the product and exploring a maximum of alternatives. As stated by Elmquist and Segrestin [START_REF] Elmquist | Sustainable development through innovative design: lessons from the KCP method experimented with an automotive firm[END_REF] , in innovative design theories the identity of the product is deliberately challenged.The introduction of a new knowledge, even if it closes down a certain C-path, also leads to challenge other aspects of the identity of the product, and therefore opens up new paths.So this approach fosters creativity, since it forces the emergence of new knowledge and concepts once a constraint exists. When modeled in the C-K theory framework, we observe both big changes in the C and K spaces (ΔC and ΔK).

The two models and the different impacts of constraints on creativity according to the design model can therefore be summarized as seen in table 1. We will test the proposed explanation through the study of products developed under constraints in the next part.

Empirical case studies: how the design model enables increased creativity through constraints

In this part we will describe two cases in which the authors participated in a resource constrained product development, to show how the design reasoning affects the relationship between constraints and creativity. We will then model different innovative products, based on secondary sources, developed under different types of strong constraints, to show that innovative design reasoning allowed fostering creativity independently of the type of constraint.

Designing a new mobility system under resource constrains

In our first case, the authors had the opportunity, through an intervention research [START_REF] Radaelli | Intervention Research as Management Research in Practice: Learning from a Case in the Fashion Design Industry[END_REF] from beginning of 2012 to the beginning of 2015, to accompany the development of mobility offers with a strong resource constraint. This work took place in a public transport operator, who was eager to propose transport offers with radically lower costs. A research program on 'low cost products' was launched inside the company, and a study of 50 different products yielded two different approaches to low cost: one following rule-based design theories and called 'low cost adaptation', the other one following innovative design theories, called 'smart low cost design' [START_REF] Chen | The design and characteristics of low cost products, 1st Interdisciplinary Innovation conference[END_REF] . Low cost adaptation started from an existing product and aimed maximizing cost reduction while minimizing customer utility reduction. Since this approach starts from an existing product, very little changes in its properties were proposed. Smart low cost design in turn, starts from the functions to be fulfilled and a cost goal, and therefore all the properties of the product are still to be defined.

To allow the design of mobility offers with strong resource constrains inside the operator, an oriented creativity workshop was organized. Participants were supplied the two approaches to low cost and asked to develop products following them. We observed that both approaches were used, but that participants had difficulties proposing a coherent offer usingrule-based design, following the 'low cost adaptation' strategy. This was the case since the resource constraint was too important. To preserve the identity of the object, participants were not allowed to change much in the structuring properties, which were also the main sources of cost. So the aimed cost reduction could not easily be achieved through this path. Although several small improvements were proposed, the final offer still had to have the same identity, and this strongly limited possible solutions. We saw that constraints were reducing creativity.

Inthe case of the 'smart low cost design', constraints on resources were seen asan opportunity to rethink some of the structuring properties with the highest cost. The constraint gave the actors a reason to discuss some of these properties, which in normal cases would not be challenged. The innovative design reasoning and research for new knowledge allowed proposing alternatives, leading to several different possible propositions. Here we observedthat constraints increased creativity by opening new design spaces.

Designing a new cockpit under certification constraints

In our second case study, one of the authors accompanied an intervention research 17 inside an aeronautics system assemblerin 2014, during the development of a cockpit with a strong resource constraint.

The development through a rule-based design was impossible and highlighted a previously hidden constraint that blocked most innovations on the cockpit: the cockpit had to be certified, and this imposed a very specific set of technologies and procedures to build the cockpit.Adding a constraint on resources blocked that path. An effort was therefore made to apply an innovative design reasoning, and to try to open up new paths. By using the constraints as an opportunity to discuss certification, it was possible to propose new paths, like a re-discussion of certification or the launch of non-certified objects. The use of these two design models and their results are illustrated in Figure 5, where we can observe how the innovative design model allowed increasing creativity.

Designing a wheelchair under multiple constraints

The nextproduct we will model, for which we sourced information from secondary sources, had several types of constraints. It was a low-cost, all-terrain, level propelled wheelchair proposed by Winter [START_REF] Winter | Stakeholder and constraint-driven innovation of a novel, lever-propelled, all-terrain wheelchair[END_REF] . This was not only a resource constrained object, but also afunctionally constrained object: The wheelchair had to be adapted to rough terrain and to tight spaces, to be repairable anywhere and to provide the user a comfortable mobility during the whole day. Following a rule-based design reasoning, independent solutions for each one of the different constraints can be found. Comfortable mobility during the whole day is provided by electric wheelchairs, rough terrain wheelchairs have been developed with bigger wheels and heavier chairbody, and simpler wheelchair models can be repaired more easily.

However combining all of these constraints with a resource constraint and staying in a rule-based design model (which means not changing the main properties of a wheelchair) leads to a dead end. In this case having a great number of constraints does not leave any place for designers to work in. However, by employing an innovative design reasoning, designers searched for new knowledge both on the context for which the chair was being developed, on the usage and on the user's ergonomics, as well as on mechanics. Thisnew

All paths blocked

Noncer fied object Evolu on cer fica knowledge allowed proposing new properties for the wheelchair and developing an entire new C-path. The work done is modeled in a simplified C-K in Figure 6.

Designing an infant warmer under multiple constraints

A further example of innovative product build under constraints is a recurrent example when discussing jugaad or frugal innovation: Embrace,described by Radjou et al. [START_REF] Radjou | Jugaad Innovation: Think Frugal, Be Flexible, Generate Breakthrough Growth[END_REF] as a portable infant warmer costing less that 2 percent the cost of a classical incubator. This product, like the all-terrain wheelchair discussed previously, integrated multiple constraints. As described by Radjou et al. [START_REF] Radjou | Jugaad Innovation: Think Frugal, Be Flexible, Generate Breakthrough Growth[END_REF] , it integrated strong resource constraints;the need for portability; a constraint on the technology used, that had to work even with unreliable electrical power; and a constraint on usage, the product had to be operable without specialized training. The great number of constraints imposed here, made it impossible to propose a solution with the properties found in existing products, following rulebased design.

Through the innovative design model however, designers were able to completely rethink the product, and to propose a sleeping bag like device. It is very simple to use, having only one ok/not ok indication, so it can be operated by the infant's parents at home. This completely changed the usage and the customers of the product. And it relies on a different technology, a phase-change material, which does not need constant electrical power.

The infant warmer is a good opportunity to compare the impact of different constraints in an innovative design regime, since another resource-constrained infant warmer, the Lullaby, has been launched by GE some years ago [START_REF] Ramdorai | Study 2: Lessons from GE Healthcare: How Incumbents Can Systematically Create Disruptive Innovations[END_REF] . An innovative design approach was also used, and the constraints were faced as opportunities to explore new C-paths. However, this infant warmer did not have an as strong resource constraint (it was priced 70% cheaper than other models) and had no constraint on electrical power. Therefore the developed warmer was still adapted to hospitals only and not for home-use. Due to the fact that this warmer did not challenge all the properties of the infant warmer, it has a smaller degree of innovativeness then Embrace. It does not change the usage and the clients. Wecan therefore conclude that even following an innovative design approach, the level of innovativeness can vary. The main difference between the constraints on the two products is how far they challenge the identity of the object. In the case of Lullaby, there is no strong constraint on the technologyoron the usage. Therefore the exploration led to an innovation that is less of a breakthrough then Embrace.

The launch of a further product, Lullaby Warmer Prime(this time aimed at another segment, mostly small clinics instead of hospitals) shows that the innovativeness, in the case of constraints that do not challenge the identity of the object so strongly, depends on the cognitive resources employed and the expansion in knowledge that is searched for.

Main empirical findings: Increasing creativity through the innovative design model

All these cases illustrate the impact constraints on a product can have on the creative process: they show how constraints can be opportunities when using an innovative design reasoning, and how they are mostly limiting in a rule-based design. Our four cases are summarized in table 2, where we show the effects of the applied design models. As we can observe in this table, constraints can be used to foster creativity through the innovative design model. We will now discuss these results in the C-K framework.

Discussion and conclusion: design models as strategies on heredity and Knowledge creation

In this article, we used the C-K theory to model the effect of constraints on creativity. We hypothesized that the dual link between constraints and creativity could be explained by a hidden variable: the design model.

Through our studied cases, both the empirical and those based on the literature, we can conclude that constraints will block creativity when two aspects are combined: i) C has a fixed structure, which means that we are not allowed to open paths in C that are far away from the identity of the object, past design having an important influence; ii)

Little new knowledge (K) is created. This means that the impact of constraints depend of two aspects: heredity orthe importance given to past design, and the cognitive resources employed in searching for new knowledge and disjunctions from this knowledge leading to new concepts. The two design models proposed hererule-based and innovative design -differ in these two aspects, as can be seen in table 3. In some cases however, the constraint does not challenge heredity in rulebased design, which means that alternatives can be proposed respecting the identity of the object. In these cases, as was seen in the definition given by Pahl et al. [START_REF] Pahl | Engineering Design: A Systematic Approach[END_REF] and modeled in Figure 4, the outcome will be a product with a lower level of innovativeness.

And in the case of innovative design, constraints that challenge the identity of the product foster creativity and lead to higher innovation levels. For a constraint that does not challenge the identity of the object, the impact of the constraint depends on the cognitive resources employed. Despite the fact that creativity is fostered by the constraints in an innovative design model, when the constraint impacts less structuring properties, there is no need to generate high levels of innovation to find a suitable answer. The degree of innovativeness therefore depends on the cognitive resources employed. If the research for new knowledge is extensive, these constraints can lead to high levels of innovation. If the research for knowledge is focused on finding a "quick-win" solution, the level of innovativeness will be lower. These results are summarized in table 4.

Further research

Our research allowed us to show that the design model has an influence on the link between constraints and creativity in engineering design, and we therefore contribute to a gap in literature on the explanations of the dual link between them. We furthermore found reason to believe that if constraints challenge the identity of the product or not impacts the innovativeness of the creative reasoning outcome. A limitation of our research is that it is based on only 4 cases and is not exhaustive, it would be enriching to follow the creative process in more cases and to verify the exactitude of the exposed link. Furthermore, in the studied cases, we mainly studied the impact of constraints on the final product on the creative process outcome. However, constraints can also exist on the design process itself, not only on the product. Hoegl et al. [START_REF] Hoegl | Financial constraints in innovation projects: When is less more?[END_REF] evaluated the impact of financial constraints on innovation projects, and identified five different factors that can lead to inhibit or enable innovation project performance:a bounded creativity approach, leveraging domain relevant skills, engaging objectives, team cohesion and team potency. Although we find evidence that limiting cognitive resources can have an impact on creativity in an innovative design approach, a similar study should be done on evaluating other kinds of constraints on the design process. This would add to another research gap, on the impact of constraints on the design process on creativity.

Finally, one of the managerial implications of this work is showing how different design reasoning can be introduced to overcome situations in which constraints block creativity. We only studied two cases in which the creativity block camefrom the rule-based design reasoning used, and in both cases using innovative design reasoning was the chosen solution. It would be interesting to add other cases to this, to verify our findings.

About the Authors

Armand Hatchuel is Professor, co-head of the chair of Design theory and methods for innovation at Mines ParisTech-PSL Research University. Beyond decision and optimization theory, he has developed with Benoit Weil, a new design theory (called C-K theory) that models the generative logic of new objects, and is discussed in Engineering, cognitive psychology and management journals. It had a strong impact on how creative design is organized in worldwide companies. He has published extensively and is member of journal and scientific boards. He received several awards. He is fellow of the national academy of technologies and of the Design Society.

Milena Klasing Chencurrently works in innovation in the transport sector. Her work is done in partnership with the chair on Design theory and methods for innovation at Mines ParisTech-PSL Research University. She has specialized on "low cost" and how it can lead to innovations, proposing a design model with two approaches for it.Furthermore, she has studied value creation through low cost in complex value networks.

Figure 2 -

 2 Figure 2 -Example of C-K representation

Figure 3 -

 3 Figure 3 -Effect of adding a new knowledge in the C and K spaces

Figure 4 -

 4 Figure 4-Modeling the approach of constraints in systematic design

Table 1 -

 1 Identity of the object in the two design models and impact of constraints Design identity of the object Changes in C and K spaces Little change of the C and the K spaces (δC and δK) Big changes in the C and the K spaces (ΔC and ΔK) Constraint as… Limiting possible choices New knowledge (K*) opening new design spaces Effect of constraints Reduce creativity Increase creativity

Figure 5 -

 5 Figure 5 -Comparing a rule-based and an innovative design reasoning models applied to the low cost cockpit

Figure 6 -

 6 Figure 6 -Modelling the rule-based and innovative design of an all-terrain low cost wheelchair

Table 2 -

 2 The four studied cases, the type of constraint and the effects of the two design models

		Constraints		Rule-based design	Innovative design
	Mobility offer	Resources		Blocked	Increased creativity
	Cockpit	Resources	and	Blocked	Increased creativity
		certification
	All-terrain	Multiple constraints	-	Increased creativity
	wheelchair
	Infant warmer	Multiple constraints	-	Increased creativity

Table 3 -

 3 Different approaches of heredity and new knowledge creation in the two design models

	Design reasoning model	Rule-based design	Innovative design
	Heredity	Maximize	Minimize
	New knowledge creation	Minimize	Maximize

Table 4 -

 4 Impact of the two design regimes according to the challenge of the constraints

Design reasoning model Rule-based design Innovative design Constraint challenges the identity of the product

				Blocked	High level of innovativeness
	Constraint	does	not	Low level of innovativeness	High or low level of
	challenge the identity of the		innovativeness, according to
	product				the	cognitive	resources
					employed


Guogang Liu

POSITIVE LOOPS OF LOOSE LEGENDRIAN EMBEDDINGS AND APPLICATIONS

Keywords:

In this paper, we prove that there exist contractible positive loops of Legendrian embeddings based at any loose Legendrian submanifold. As an application, we define a partial order on Cont0(M, ξ), called strong orderability, and prove that overtwisted contact manifolds are not strongly orderable.

Introduction

In this paper, we focus on the study of positive contact and Legendrian isotopies in a cooriented contact manifold (M, ξ).

A contact manifold (M 2n+1 , ξ) is a 2n + 1 dimensional smooth manifold M with a nonintegrable hyperplane field ξ which is called a contact structure. When ξ is co-oriented, it is given by the kernel of a contact 1-form α. For example, in R 4 with the usual coordinates (x 1 , x 1 , y 1 , y 2 ), the sphere S 3 carries a contact form α std = (y 1 dx 1 -x 1 dy 1 + y 2 dx 2 -x 2 dy 2 )| S 3 . We denote ξ std the contact structure defined by α std . It induces a contact structure on the quotient RP 3 which is also denoted by ξ std .

One class of submanifolds of (M 2n+1 , ξ) with an interesting behavior is that of Legendrian submanifolds. A n-dimensional submanifold L ⊂ M 2n+1 is called a Legendrian submanifold if α| L = 0. A contactomorphism of (M, ξ) is a diffeomorphism which preserves ξ and a contact isotopy (ϕ t ) t∈[0,1] is a path of contactomorphisms with ϕ 0 = id. We say a contact isotopy (ϕ t ) t∈[0,1] is positive if α(∂ t φ t ) > 0. That is to say, the infinitesimal generator of the isotopy is positively transverse to ξ everywhere. An isotopy (ϕ t ) t∈[0,1] based at a Legendrian submanifold L is said to be a Legendrian isotopy if ϕ t (L) is a Legendrian submanifold for all t. Similarly, We say ϕ t is positive if α(∂ t ϕ t ) > 0. This notion of positivity does only depend on the image L t = ϕ t (L) of the isotopy. For us, a Legendrian isotopy will be such a family of unparametrized Legendrian submanifolds.

With the concept of positive contact isotopy, Eliashberg and Polterovich defined a partial order on the universal cover Cont 0 (M, ξ) of the identity component of the contactomorphisms group of (M, ξ). A class of contact isotopy [(ψ t ) t∈ [0,1] ] is greater than another class [(ϕ t ) t∈[0,1] ] if there exists a positive contact isotopy from ϕ 1 to ψ 1 which is homotopic to the concatenation of the opposite of (ϕ t ) t∈[0,1] and (ψ t ) t∈[0,1] . Proposition 0.1. [START_REF] Eliashberg | Partially ordered groups and geometry of contact transformations[END_REF] If (M, ξ) is a contact manifold, the following conditions are equivalent:

(i). (M, ξ) is non-orderable; (ii). There exists a contractible positive loop of contactomorphisms for (M, ξ).

This order is closely related to squeezing properties in contact geometry [START_REF] Eliashberg | Partially ordered groups and geometry of contact transformations[END_REF] as well as to the existence of bi-invariant metrics on Cont 0 (M, ξ) or on the space of Legendrian submanifolds [START_REF] Colin | The discriminant and oscillation lengths for contact and Legendrian isotopies[END_REF].

From the beginning of the 80's, it is known that the world of contact structures splits in two classes with opposite behaviors. Following Eliashberg, we say that a contact structure ξ on M 3 is overtwisted if there exists an overtwisted disk D OT ⊂ M , i.e. an embedded disk which is tangent to ξ along its boundary. The overtwisted contact structures are flexible and classified by an adequate h-principle [START_REF] Eliashberg | Classification of overtwisted contact structures on 3-manifolds[END_REF]. We denote α OT a contact form for an overtwisted contact structure ξ defined on a neighborhood of an overtwisted disk. More recently, the work of Niederküger [START_REF] Niederkrüger | The plastikstufe -a generalization of the overtwisted disk to higher dimensions[END_REF] and Borman-Eliashberg-Murphy [BEM15] have described a similar dichotomy in the higher dimensional case. Following a suggestion of Niederküger, we say a contact structure ξ is overtwisted if (M 2n+1 , α) contains D 3 × D 2n-2 (r) with α| D 3 ×D 2n-2 (r) = α OT -(ydx -xdy) for some constant r > 0 large enough depending on the dimension of M [CMP15]. As in dimension three, Borman, Eliashberg and Murphy [BEM15] have shown that overtwisted contact structures are purely topological objects and are flexible.

On the contrary, we say ξ is a tight contact structure if it is not overtwisted. For example, the contact manifolds (S 3 , ξ std ) and (RP 3 , ξ std ) are tight according to the fundamental result of Bennequin [START_REF] Bennequin | Entrelacements et équations de pfaff[END_REF]. Similar results hold in higher dimension, where holomorphic methods give that a Liouville fillable contact structure is tight, see [START_REF] Niederkrüger | The plastikstufe -a generalization of the overtwisted disk to higher dimensions[END_REF].

The orderability property is not shared by all contact manifolds (see the work of Albers, Frauenfelder, Fuchs and Merry [AF12, [START_REF] Albers | Orderability, contact non-squeezing, and Rabinowitz Floer homology[END_REF][START_REF] Albers | Orderability and the Weinstein Conjecture[END_REF] for more examples ).

Theorem 0.2. (i). (S 3 , ξ std ) is non-orderable while (RP 3 , ξ std ) is orderable [EKP06]; (ii).
There are some overtwisted contact manifolds which are non-orderable [START_REF] Casals | On the non-existence of small positive loops of contactomorphisms on overtwisted contact manifolds[END_REF].

It is interesting to see that tight contact manifolds can be orderable or not despite their rigid nature. At the same time we guess overtwisted contact manifolds are non-orderable.

Question 0.3. Are all overtwisted contact manifolds non-orderable?

In order to answer the above question, we transfer the study of positive contact isotopies to that of positive Legendrian isotopies by the trick of contact product. Indeed, a positive contact isotopy of (M, ξ) can be lifted to a negative Legendrian isotopy of the diagonal ∆ M ×M × {0} in the contact product (M × M × R, α 1 -e s α 2 ). Here α 1 and α 2 denote the pull-backs of α by the first and second projection from M × M × R to M . The advantage is that the study of positive Legendrian isotopies should be easier than that of contact isotopies.

In that context, there is a natural question regarding positive Legendrian isotopies: (ii). the zero-section of (T * M ×R, dz -ydx) is not in a positive loop of Legendrian embeddings [START_REF] Vincent Colin | Positive isotopies of Legendrian submanifolds and applications[END_REF].

We let F be the front projection (

T * M × R, dz -ydx) → M × R : (x, y, z) → (x, z). For a Legendrian submanifold L ⊂ (T * M × R, dz -ydx), the subset L F := F (L) ⊂ M × R is the front of L.
We usually identify L F with L, since the y coordinates are given by the slopes of the front. In the case where L and M are of dimension 1, we can replace a smooth segment of L F by a zigzag with two cusps. The zig-zag either has a z-shape, as in Figure 1, or an s-shape (the symmetric of Figure 1 by the vertical axis). The Legendrian submanifold obtained by this operation is denoted by S(L) and is called a stabilization of L. When we want to make it clearer, we will discrimate between the z-shape/positive stabilization denoted S + (L) and the s-shape/negative stabilization S -(L).

We have:

Proposition 0.7. [START_REF] Vincent Colin | Positive isotopies of Legendrian submanifolds and applications[END_REF] Let L be the zero-section of T * S 1 × R and S(L) a stabilization of L.

Then there exists a loop of positive Legendrian embeddings based at S(L).

For a contact manifold (M, ξ) of dimension strictly higher than three, Murphy [START_REF] Murphy | Loose Legendrian Embeddings in High Dimensional Contact Manifolds[END_REF] introduced the class of loose Legendrian submanifolds. This is a higher dimensional generalization of the stabilized S(L) in dimension three. Loose Legendrian submanifolds satisfy a h-principle discovered by Murphy which make them flexible. The main result of this article extends this flexible behavior. Theorem 0.8. Let (M, ξ) be a contact manifold of dimension ≥ 5 and L ⊂ (M, ξ) be a Legendrian submanifold. If L is loose then there exists a contractible positive loop of Legendrian embeddings based at L. Without the looseness assumption, F.Laudenbach has proven that there always exist positive loops of Legendrian immersions [START_REF] Laudenbach | Positive Legendrian regular homotopies[END_REF].

As an application of Theorem 0.8, we obtain a holomorphic curve free proof of the existence of tight (i.e. non overtwisted in the Borman-Eliashberg-Murphy sense [BEM15]) contact structures in every dimensions. The "hard part" of the argument uses Theorem 0.6 whose proof relies on the existence of a generating function for a specific class of Legendrians (in that case the Legendrian fibers of the Legendrian fibration in (R n × S n-1 , ξ std )). Corollary 0.9. [START_REF] Murphy | Loose Legendrians and the plastikstufe[END_REF] The contact manifold (R n × S n-1 , ξ std ) is tight.

This corollary is proved in Subsection 3.1. In the last section, we define a new partial order on certain groups Cont 0 (M, ξ), called strong orderability, based on the transfer of an isotopy of contactomorphisms to a Legendrian isotopy of their graphs in the contact product. We then drop the graph condition to stick to Legendrian isotopies and get a (possibly) different notion than that of Eliashberg-Polterovich's [START_REF] Eliashberg | Partially ordered groups and geometry of contact transformations[END_REF]. Proposition 0.10. Let (M, ξ) be a contact manifold. Then (M, ξ) is strongly orderable if and only if there does not exist a contractible positive loop of Legendrian embeddings based at the diagonal of the contact product of (M, ξ).

As an example we prove that the contact manifold (S 1 , dθ) is strongly orderable.

In that context, we explain the following result which was first suggested by Klaus Niederkrüger and also observed by Casals and Presas.

Proposition 0.11. Let (M 2n+1 , α) be a compact overtwisted contact manifold. Then the contact product (M ×M ×R, α 1 -e s α 2 ) is also overtwisted and the diagonal ∆ ⊂ (M ×M ×R, α 1 -e s α 2 ) is loose.

Therefore, according to Proposition 0.11, we have the following result: Theorem 0.12. Overtwisted contact manifols are not strongly orderable.

Organisation of the paper:

In section 1, we recall some basic definitions including Murphy's loose Legendrian embeddings. In section 2, we give the proof of Theorem 0.8. Finally, we prove all the other results mentioned above in the last section.

Acknowledgment: This paper comes from my thesis work. First of all, I wish to express my infinite gratitude to my adviser Vincent Colin for his encouragements and countless help. I also thank Francois Laudenbach, Baptiste Chantraine, Claude Viterbo and Francisco Presas sincerely for their appreciation and indispensable advices. I have already presented the main results in several conferences and seminar talks, I would like to thank the audiences for their attentions and valuable questions and suggestions.

Basic definitions in Contact Geometry

Let L : Y → (J 1 (Y ), α) be a smooth Legendrian embedding. We denote its front map by

L F : Y → Y × R.
Given a Legendrian submanifold L , there is a neighborhood U (L ) of L contactomorphic to a neighborhood of the zero section in J 1 (L , α), according to the Weinstein neighborhood theorem. If L a Legendian submanifold close to L then we can talk about the front L F of L in this Weinstein neighborhood.

If φ t : Y → Y × R is an homotopy of fronts (with φ t (Y ) transverse to the R factor), we denote φ t its Legendrian lift and write v φt and v φt for the corresponding generating time dependent vector fields.

1.1. Positive Legendrian isotopies. Definition 1.1. [CFP10, CN10](Positive Legendrian isotopy) Let (M, ξ = kerα) be a contact manifold, L ⊂ M a Legendrian submanifold, ϕ : L × [0, 1] → M a Legendrian isotopy and let X t = dϕ dt where t ∈ [0, 1]. We say ϕ is positive if X t is transverse to ξ positively, i.e. α(X t ) > 0.
Moreover, ϕ is said to be a positive loop if in addition ϕ 0 (L) = ϕ 1 (L).

The following remark is the starting point of our study.

Remark 1.2. [START_REF] Vincent Colin | Positive isotopies of Legendrian submanifolds and applications[END_REF] Let L : S 1 → (J 1 (S 1 ), ξ std ) be a Legendrian embedding whose front have positive slopes everywhere. Then there exists a positive Legendrian loop based at L. Proof. Regard S 1 as R/Z with coordinate x. Denote Z = L F (S 1 ). On Z, the slopes ∂z/∂x > 0 are positive. See figure 1. Consider the vector field X t := -∂ x on J 1 (S 1 ) and its flow ϕ t . Because α(X t ) > 0 on ϕ t (Z) for every t ∈ [0, 1], then ϕ t is a positive Legendrian isotopy. Since ϕ 1 = Id, then we have a positive loop.

Remark 1.3. If the front of L has negative slopes everywhere, we can choose v = ∂ x so that its flow is a positive loop. 1.2. Loose Legendrian embeddings. In this section, we recall Murphy's notion of loose Legendrian embeddings, wrinkled Legendrian embeddings and the idea for resolving wrinkles [START_REF] Murphy | Loose Legendrian Embeddings in High Dimensional Contact Manifolds[END_REF]. For simplicity, we give the following equivalent definition of a loose Legendrian. Definition 1.4. Let L : Y n → (J 1 (Y n ), ξ std ) be a Legendrian embedding. Let Λ be a one dimensional zigzag and N be a closed n -1 dimensional manifold. We say L is loose if its front contains Λ × N . In particular, it is obtained from a Legendrian L by replacing a neighborhood of N ⊂ L by N times a zigzag. We denote L = S N ± (L ), where ± stands for the z-or s-shape of the zig-zag. Definition 1.5. [START_REF] Yakov | Wrinkled Embeddings[END_REF](Wrinkled embeddings) See figure 3. Let W : R n → R n+1 be a smooth, proper map, which is a topological embedding. Suppose W is a smooth embedding away from a finite collection of spheres {S n-1 j }. Suppose, in some coordinates near these spheres, that W can be parametrized by

W (u, v) = (v, u 3 -3u(1 -|v| 2 ), 1 5 u 5 - 2 3 u 3 (1 -|v| 2 ) + u(1 -|v| 2 ) 2 ,
where our domain coordinates lies in a small neighborhood of the sphere

{|v| 2 + u 2 = 1} ⊂ R n .
Then W is called a wrinkled embedding, and the spheres S n-1 j are called the wrinkles. Remark 1.8. We will put the C ∞ -topology on the space of wrinkled Legendrian embeddings. Thus we can talk about a smooth family of wrinkled embeddings (L t , Φ t , N t ).

Given a Legendrian L, we denote L w a wrinkled Legendrian obtained by adding some wrinkles to L. Given a twist marking N on L w and η > 0, we denote W -1 η,N (L w ), or W -1 η (L w ) when N is understood, be the operation of resolving the wrinkles along N with an η-small operation.

To measure proximity, we can first perform an immersed resolution W -1 0 (L w ), where along N we incorporate a completely flat zig-zag, covering a segment times N . Then

W -1 η (L w ) is η-C ∞ - close to W -1 0 (L w )
. This operation can be done parametrically, as summarized in the following theorem of [START_REF] Murphy | Loose Legendrian Embeddings in High Dimensional Contact Manifolds[END_REF].

Theorem 1.9. [START_REF] Murphy | Loose Legendrian Embeddings in High Dimensional Contact Manifolds[END_REF] Let L w t be a smooth family of wrinkled Legendrian embeddings, let (Φ t , N t ) be the twist markings. Then there is a smooth family of Legendrian embeddings L t , such that L t is identical to L w t outside of any small neighborhood of N t for all t. Also, the resolution L t can be taken to be as close as we want from L w t .

Theorem 1.10. In our case, we note that the stabilization operation passing from L to S N + (L) might change the formal isotopy class of the Legendrian L, even if N has Euler characteristic zero. However, we can go back to the original formal class by stabilizing again to S N -(S N + (L)). This fact will be used later on in the proof of our main theorem to correct formal classes.

Contractible positive Legendrian loops

In this section we prove our main theorem 0.8 in a geometric way.

Proof. We start with a loose Legendrian L and work in a compact region of its standard neighborhood J 1 (L).

A. Construction of a positive loop

We first describe an elementary operation that will be applied repeatedly. Recall L F is the front projection of L. Since L is the zero-section in J 1 (L), one can canonically identify L F with L.

We consider a n-disk D n 0 ⊂ L F , written as D n-2 0 × D 2 (2) together with coordinates (u, ρ, θ), where (ρ ≤ 3, θ) are polar coordinates on D 2 . We let L w be the wrinkled Legendrian obtained by adding one wrinkled disk D w 0 along the (n -1)-disk

D 0 = {1 ≤ ρ ≤ 2, θ = 0} to L F , so that D w 0 ⊂= {1 ≤ ρ ≤ 2}.
We moreover slightly modify L w along D 0 × S 1 = {1 ≤ ρ ≤ 2}, where S 1 corresponds to the θ direction, by propagating the slope of the wrinkle in the θ-direction so that:

• every circle L w ∩ {ρ = ρ 0 ∈ (1, 2), u = u 0 }, contained in the {(u 0 , ρ 0 , θ, z)} cylinder, has a positive slope, i.e. is positively transverse to ∂ θ as in Figure 1;

• L w is equal to L F away from {1 ≤ ρ ≤ 2}.
The situation is pictured in Figure 6. We take a twist marking N ⊂ D n 0 for D w 0 so that if N is the closed submanifold N ∪ D 0 ⊂ L F then the Euler characteristic χ(N ) of N is zero.

Step 1. We rotate the wrinkle positively in the θ-direction.

Given some constant K 0 > 0, we rotate positively the wrinkle in the θ-direction with (large) speed K 0 ∈ N: We take a z-invariant path of diffeomorphisms φ 0 t in the front such that φ 0 t (u, ρ, θ, z) = (u, ρ, θ -2K 0 πt, z) and φ 0 t globally preserves L w \ {1 ≤ ρ ≤ 2}. By construction

L w t,K 0 = φ 0 t (L w
) is a loop of wrinkled fronts, even if φ 0 t is only a path. Its lift L w t,K 0 is a nonnegative loop of wrinkled Legendrians based in L w . Non-negativity comes from the fact that the infinitesimal generator of the isotopy φ 0 t is either tangent (outside {1 ≤ ρ ≤ 2}) or positively transverse (inside {1 ≤ ρ ≤ 2}) to the front of L w t,K 0 .

Step 2. We resolve the wrinkle. We now parametrically resolve the wrinkle φ 0 t (D w 0 ) ⊂ L w t,K 0 along the marking φ 0 t (N ) ⊂ L w t,K 0 to get a loop W -1 η 0 (L w t,K 0 ) of Legendrian fronts (notice that φ 0 1 (N ) = N ). Doing so, we might introduce some negative displacement near φ 0 t (N ), but, taking the size of the resolution η 0 small enough in front of K 0 and the slope of the circles {ρ = ρ 0 ∈ [5/4, 7/4], u = u 0 }, we can make sure that the isotopy is still positive in the region {5/4 ≤ ρ ≤ 7/4}.

Here, we notice that the loop of fronts W -1 η 0 (L w t,K 0 ) is obtained from L F by replacing a neighborhood of φ 0 t (N ) by the product of N with a z-shape. In particular, the loop of fronts W -1 η 0 (L w t,K 0 ) admits a parametrization by a loop of homeomorphisms (which are diffeomorphisms except at the cusps of the fronts) ψ 0 t,K 0 : L → W -1 η 0 (L w t,K 0 ) which is constant away from D n 0 . When we lift the loop of fronts W -1 η 0 (L w t,K 0 ) to a loop of Legendrians L 0 t,K 0 in J 1 (L), we can lift the loop of parametrizations ψ 0 t,K 0 to a loop of smooth parametrizations Ψ 0 t,K 0 , which is constant away from D n 0 . The loop L 0 t,K 0 is positive along Ψ 0 t,K 0 ({5/4 ≤ ρ ≤ 7/4}).

Step 3. We adjust the formal class. In steps 1 and 2, we have constructed a loop for a stabilization S N + (L) of L, which might not be formally Legendrian isotopic to L. Following Proposition 1.10, we correct this by stabilizing again parametrically along a parallel copy of ψ 0 t,K 0 (N ) to obtain a loop of Legendrians based at S N -(S N + (L)). This second stabilization can be made small at will (in the sense that the s-shape is squashed) so that the positivity property of step 2 is still unchanged and we still have a loop of parametrizations, that we persist to write Ψ 0 t,K 0 .

This preparatory work been done, the proof starts from a covering of L by open sets

A i ⊂ D n i , i = 0, . . . , k, of the form S 1 × D n-1 = {5/4 ≤ ρ ≤ 7/4} ⊂ D n i as before.
We then construct our loop by induction: by step 1,2,3, we construct a loop of Legendrians L 0 t,K 0 = Ψ 0 t,K 0 (L) which is positive along Ψ 0 t,K 0 (A 0 ), by rotating a wrinkle with speed K 0 . We now take a loop of standard Weinstein neighborhoods N (L 0 t,K 0 ) of L 0 t,K 0 parametrized by t ∈ S 1 , in which L 0 t,K 0 is the zero section diffeomorphic to L. This is given by a family of embeddings J 1 (L) → J 1 (L) sending the zero section to L 0 t,K 0 = Ψ 0 t,K 0 (L). These embeddings can be chosen to extend Ψ 0 t,K 0 , so we still denote them Ψ 0 t,K 0 : J 1 (L) → N (L 0 t,K 0 ). We then apply steps 1,2,3 to A 1 , D n 1 in J 1 (L), though of as the source of Ψ 0 t,K 0 , by rotating a wrinkle with (relative) speed K 1 and resolving it with size η 1 . This means we are performing this step in the moving neighborhood Ψ 0 t,K 0 (J 1 (L)) of L 0 t,K 0 . We get a loop of Legendrians L 1 t,K 1 = Ψ 1 t,K 1 (L) in the moving neighborhood J 1 (L). Viewed in the original jet-space, we are considering the loop Ψ 0

t,K 0 (L 1 t,K 1 ) = Ψ 0 t,K 0 (Ψ 1 t,K 1 (L)
). We see that if we take K 1 large enough, in particular with respect to η 0 and K 0 , then the loop Ψ 0 t,K 0 (Ψ 1 t,K 1 (L)) becomes positive along Ψ 0 t,K 0 (Ψ 1 t,K 1 (A 1 )) -where it was before possibly negative. We also have to take η 1 small enough so that the isotopy remains positive along Ψ 0 t,K 0 (Ψ 1 t,K 1 (A 0 )) after resolving the wrinkle with size η 1 . Precise computations are described by the following composition of speeds:

Since v Ψ 0 t,K 0 • Ψ 1 t,K 1 (x) = v Ψ 0 t,K 0 ( Ψ 1 t,K 1 (x)) + D Ψ 0 t,K 0 (v Ψ 1 t,K 1 (x)), we have α(v Ψ 0 t,K 0 • Ψ 1 t,K 1 (x)) = α(v Ψ 0 t,K 0 ( Ψ 1 t,K 1 (x))) + ( Ψ 0 t,K 0 ) * α(v Ψ 1 t,K 1 (x)).
Now, we have that α(v Ψ 0 t,K 0

) > -k 0 independent of K 1 . Moreover, since the isotopy of Legendrians is compactly supported, there exists some c 0 > 0 independent of K 1 such that Ψ 0 * t,K 0 α = f α, where f > c 0 > 0 in a neighborhood of the original L which contains all the deformations.

We can thus see that in the neighborhood of Ψ 0 t,K 0 (Ψ 1 t,K 1 (A 1 )) where the slope of the front is larger than some

c 1 > 0, α(v Ψ 1 t,K 1 • Ψ 0 t,K 0 ) > -k 0 +c 0 c 1 K 1 . Thus, for K 1 large enough Ψ 0 t,K 0 • Ψ 1 t,K 1 is positive in the neighborhood of Ψ 0 t,K 0 (Ψ 1 t,K 1 (A 1 )
). Near A 0 where the loop was already positive, we do not alter positivity if the size η 1 of the resolution is small enough.

Once this is understood, it is clear that we can repeat the process until we get a loop which is positive everywhere. At each step the rotation speed has to be higher and higher with respect to previous operations.

To conclude, we observe that we have been producing a loop based at a loose Legendrian which is formally isotopic to L, and thus by Murphy's theorem [START_REF] Murphy | Loose Legendrian Embeddings in High Dimensional Contact Manifolds[END_REF] Legendrian isotopic to L.

B. Contractibility

We show that the positive loop that we have been constructing is contractible amongst Legendrian loops.

The construction was inductive on the set of annuli (A i ) and thus it is enough to check that the first loop W -1 η 0 (L w t,K 0 ) is homotopic to a constant loop. We first treat the case when the dimension of the Legendrian L is greater of equal to 3. Define φ 0 s,t such that φ 0 s,t (u, ρ, θ, z) = (u, ρ -s, θ -2K 0 πt, z). We can see that φ 0 s,t (L w ) is a homotopy from φ 0 t,K 0 (L w ) to φ 0 1,t (L w ) which is a loop of rotation of a wrinkled disk D w around some point, says x 0 . Up to homotopy, the wrinkled disk φ 0 1,t (D w ) is completely determined by its normal vector in L at x 0 , and thus by a map S 1 → S n-1 . Since n ≥ 3, this map is homotopic to a point and thus we can deform our loop of wrinkled Legendrians to a constant loop. Moreover, this homotopy can be extended to a homotopy of twist markings from the original loop of twists markings to a constant loop. Resolving parametrically the markings, we get a homotopy from W -1 η 0 (L w t,K 0 ) to a constant loop. The extra stabilization of step 3 to fix the formal isotopy class enters the same scheme and can be also homotoped to a constant operation. This concludes the proof.

The case when the dimension of L is two follows the same scheme, except that we homotope the loop of resolved wrinkles Ψ 0 t,K 0 (U ), where U is a circle times a z-shape segment, to a constant annuli around the circle {ρ = 1}.

Applications

In this chapter, we give some applications of our main theorem. First, we reprove tightness of (S n-1 × R n , ξ std ). Second, we define a partial order on the universal cover Cont 0 (M, ξ) of the identity component of the group of contactomorphisms of a contact manifold (M, ξ) and prove that overtwisted contact structures are not orderable.

3.1. Tightness of (S n-1 × R n , ξ std ). In this section we prove Corollary 0.9. A similar proof for S 1 × R 2 was given in [START_REF] Vincent Colin | Positive isotopies of Legendrian submanifolds and applications[END_REF].

Proof. Assume (S n-1 × R n , ξ std ) is overtwisted, and D OT ⊂ (S n-1 × R n , ξ std ) is an overtwisted disk. Denote π : S n-1 × R n → R n the projection. There exists some point x ∈ R n such that the fiber π -1 (x) ∩ D OT = ∅. According to [CMP15], the fiber π -1 (x) is loose. Thus, there exists a positive loop based at it by Theorem 0.8. That contradicts Theorem 0.6. Therefore, the manifold (S n-1 × R n , ξ std ) is tight.

Positive loops and orderings.

Definition 3.1. Given a contact manifold (M, α), the manifold (Γ M , α) = (M ×M ×R, α 1 -e s α 2 ) is called a contact product. Here α i = π * i α where π i project Γ M to the i-th factor. The Legendrian submanifold of (Γ M , α) ∆ = {(x, x, 0)} is called the diagonal.

The contact product Γ M is a special case of a contact fibration. We recall the definition from [START_REF] Presas | A class of non-fillable contact structures[END_REF]. Definition 3.2. Let (E, ξ = kerα) be a contact manifold, and E -→ B is a fibration with fiber F . Then (E, ξ = kerα) -→ B is called a contact fibration if (F, α| F ) is a contact manifold. Let (E, ξ = kerα) -→ B be contact fibration we say that the horizontal distribution H = (T F ∩ ξ) ⊥dα is the contact connection associated to the fibration. Note that Γ M is a contact fibration with F = (M, α) and B = M × R. We now explain the following result which was first suggested by Klaus Niederkrüger and also observed by Casals and Presas.

Proposition 3.6. Let (M 2n+1 , α) be a compact overtwisted contact manifold and let (Γ M , α) be the associated contact product. Then (Γ M , α) is also overtwisted and the diagonal ∆ ⊂ Γ M is loose.

Proof. We apply the overtwisted criterion from [CMP15]. If λ = ydx -xdy, it is enough to construct a higher dimensional overtwisted ball D = (B 2n+1 OT × D 2n+2 (r), α OT -λ) ⊂ (Γ M , α) for some r large enough, such that D does not intersect ∆.

Let S 2n+1 = {(x, y) | x 2 +y 2 = 1} with its standard contact form α std , and let ϕ 0 : S 2n+1 ×R → R 2n+2 , (x, y, s) → (e s x, e s y). Note that ϕ * 0 λ = α std . We take a Darboux ball B ⊂ (M, α) and we regard it as a subset of (S 2n+1 , α std ). Then we can construct a contact embedding ϕ

: (M × B × R, α) → (M × R 2n+2 , α 1 -λ) by the following series of contact embeddings (M × B × R, α) i → (M × S 2n+1 × R, α 1 -e s α std ) id×ϕ 0 -→ (M × R 2n+2 , α 1 -λ). Let B 2n+1 OT ⊂ M be a overtwisted ball, then D 0 = (B 2n+1 OT × D 2n+2 (r), α 1 -λ) is the overwisted ball in (M × R 2n+2 , α 1 -λ).
We can move D 0 away from ϕ(∆) by Corollary 3.5. More precisely, we take the vector field V = 2r∂ x + 2r∂ y on R 2n+2 , then lift it to a contact vector field V = V + 2r(y -x)R α on M × R 2n+2 where R α is the Reeb vector field of (M, α). Let φ t be the contact isotopy of on (Γ M , α). We denote gr(φ) = φ| ∆ which is in Leg(M, Γ M ). In fact, given a positive contact isotopy φ t , we can see that gr(φ t ) is a negative Legendrian isotopy. Therefore, we would like to transfer the study of positive contact isotopies to that of negative Legendrian isotopies.

V . Denote C = {rx | x ∈ B, r > 0} the cone defined by B. Then D 1 = φ 1 (D 0 ) ⊂ M × (C \ {0}) = ϕ(M × B) does not intersect ϕ(∆). Therefore D = ϕ -1 (D 1 )
Definition 3.8. Let f = [f t ] and g = [g t ] be two elements in Cont 0 (M, ξ). We say f g if there exists a non-positive path L t ∈ Leg(M, Γ M ) from gr(g 1 ) to gr(f 1 ) and gr(g t ) * L t is homotopic to gr(f t ). The space Cont 0 (M, ξ) and (M, ξ) are said to be strongly orderable if defines a partial order 1 on it. Otherwise, they are said to be non strongly orderable.

Remark 3.9. Let C be the set generated by all the homotopy classes of non-positive paths in Leg(M, Γ M ). Then f g equals to gr(g

-1 f ) ∈ C. Given [L t ] ∈ C and φ ∈ Cont 0 (M, ξ), then we have [ φL t ] ∈ C.
Therefore, the order is left invariant, that is to say, given f and g in Cont 0 (M, ξ), if f g, then hf hg for all h ∈ Cont 0 (M, ξ). Because if L t is a non-positive path from g 1 to f 1 , then h1 L t is a non-positive path from h 1 g 1 to h 1 f 1 . Proposition 3.10. Let (M, ξ) be a contact manifold. Then (M, ξ) is strongly orderable if and only if there does not exist a contractible negative loop of Legendrian embeddings based at ∆.

Proof. Let f = [f t ], g = [g t ] and h = [h t ] be elements in Cont 0 (M, ξ). The relation is reflective, since we have f f by the definition of . If there are two non-positive paths L 1 t from gr(g 1 ) to gr(f 1 ) and L 2 t from gr(h 1 ) to gr(g 1 ), then L 2 t * L 1 t is a non-positive path 1 in the sense of a partial order on sets from gr(h 1 ) to gr(f 1 ). Thus, the relation is transitive. Now we check the antisymmetry of . According to [START_REF]Universal orderability of Legendrian isotopy classes[END_REF][Propostion 4.5], the existence of contractible non-positive non-trivial loop of Legendrian embeddings is equivalent to the existence of contractible negative loop of Legendrian embeddings. Thus, for any f = 1, on one hand, if there does not exist any negative loop based at ∆, we can not find a non-negative path L 1 t and a non-positive path L 1 t in the homotopy class of gr(f t ) at the same times. Otherwise, L 1 t * L 2 t would be a contractible nonnegative loop. On the other hand, if there exists a non-positive loop f t based at ∆, then f 1/2 1 and 1 f 1/2 . That means (M, ξ) is not strongly orderable.

Our definition is stronger than that of [START_REF] Eliashberg | Partially ordered groups and geometry of contact transformations[END_REF], since we do not require the path of Legendrian embeddings φ t to be graphical for all t.

Corollary 3.11. Let (M, ξ) be a contact manifold. If (M, ξ) is strongly orderable, then it is orderable.

A contact manifold which is not strongly orderable is said to be weakly non-orderable. Immediately, according to Proposition 3.6 and Corollary 3.7, we deduce theorem 0.12 saying that overtwisted contact manifols are weakly non-orderable. We have the following example of strong orderability.

Theorem 3.12. (S 1 , ξ std ) is strongly orderable.

Proof. Denote dθ the standard contact form for S 1 . We have a contactomorphism ϕ : (Γ S 1 , dθ 1e s dθ 2 ) → (S 1 × T * S 1 , dz -ydx), (θ 1 , θ 2 , s) → (z = θ 1 -θ 2 , x = θ 2 , y = e s -1) such that ϕ(∆) is the zero-section. Assume there exists a contractible positive loop based at the zerosection of (S 1 × T * S 1 , dz -ydx), then it lifts to a positive loop based at the zero-section of (R 1 × T * S 1 , dz -ydx). However, such loops do not exist according to [START_REF] Vincent Colin | Positive isotopies of Legendrian submanifolds and applications[END_REF] (notice this is not a trivial result). Thus (S 1 , ξ std ) is strongly orderable.

Question 3.13. Is (RP 3 , ξ std ) strongly orderable?

Figure 1 .

 1 Figure 1. A positive stabilized front.

Figure 2 .

 2 Figure 2. A loose embedding of S 2 .

Figure 3 .

 3 Figure 3. Wrinkled embedding.

Figure 4 .

 4 Figure 4. A wrinkled sphere.

[ Mur12 ]

 Mur12 Let L n be a loose Legendrian and N ⊂ L be a closed codimension 1 submanifold of Euler characteristic 0. If we stabilize L positively and negatively along N , we obtain a Legendrian S N -(S N + (L)) which is isotopic to L. Sketch of proof. First of all, the stabilized Legendrian S N -(S N + (L)) is loose. By Murphy's hprinciple, have to show that S N -(S N + (L)) is formally Legendrian isotopic to L. This is a consequence of the fact that S N -(S N + (L)) is obtained from a Murphy N -stabilization of L by an

Figure 5 .

 5 Figure 5. Resolve a wrinkle.

Figure 6 .

 6 Figure 6. Rotation of the wrinkle.

  Remark 3.3. The horizontal distribution depends on the contact form α.The connection defined above has the following properties: Proposition 3.4.[START_REF] Presas | A class of non-fillable contact structures[END_REF] For a path γ : [0, 1] → B, the monodromy m γ : F (γ(0)) → F (γ(1)) induced by γ is a contactomorphism. Corollary 3.5. Let φ ∈ Dif f 0 (B). Then it lifts to a contactomorphism φ.

  is one of the overtwisted balls we want.Corollary 3.7. Let (M, α) be a compact overtwisted contact manifold and (Γ M , α) the contact product. Then there exists a positive loop of Legendrian embeddings based at ∆.Let Leg(M, Γ M ) be the set of Legendrian embeddings M → (Γ M , α). Given φ ∈ Cont 0 (M, ξ = kerα) with φ * α = e g(x) α, it induces a contactomorphism φ(x, y, s) := (x, φ(x), s -g(y))


Tetsuya Furukawa
email: furukawa@econ.kyushu-u.ac.jp

Masahiro Kuzunishi
email: kuzunisi@dpc.agu.ac.jp

Strength of Relationship between Multi-labeled Data and Labels

Keywords: Masahiro Kuzunishi, Multi-labeled Data, Ranks of Labels, Levels of Data, Criteria for the Strength

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

With increasing various kinds of data such as numerical data, texts, images, and movies, utilization of collected data is becoming more important [START_REF] Fazzinga | RFID-Data Compression for Supporting Aggregate Queries[END_REF] [START_REF] Zhang | Object Class Detection: A Survey[END_REF] [START_REF] Zhu | Matching Heterogeneous Event Data[END_REF]. Such data must be organized properly to utilize well and classification of data is one of the efficient methods [START_REF] Ding | Optimizing Index for Taxonomy Keyword Search[END_REF] [START_REF] Silla | :A Survey of Hierarchical Classification Across Different Application Domains[END_REF]. Individual data is classified to a category by a certain attribute, for example, region or industry, and the data is annotated with the label of the category [START_REF] Cardoso-Cachopo | Semi-supervised Single-label Text Categorization using Centroid-based Classifiers[END_REF].

When data relates to multiple categories, the data is classified to those categories and annotated with the set of labels [START_REF] Tang | Large Scale Multi-label Classification via MetaLabeler[END_REF]. However, the strength of relationship between data and categories is different in general. Ranks of the labels which express how close the data is to categories enable us to use the data more precisely. Suppose that data are classified by business categories and annotated with sets of labels of the categories. If ranks are given to the labels of a data according to the financial figures (net revenues, net income, etc.) of the relating business field, users can compare the data of automobile and finance as primary categories with the data of automobile as a primary category and finance as a secondary category.

Although ranks of labels give us richer information, target data identified by a set of labels are not clear because there are various strength of relationship between the data and the set of labels. Even if users need the data which relate to a set of labels more closely, there are cases that the strength can not be decided.

Example 1. For the strength of relationship between data and a set of labels L 1 = {Transportation, Electronics}, it is not decided clearly whether the data on the company where automobile, mobile phone, and finance are primary relates to L 1 more closely than the data on the company where only automobile is primary and mobile phone and finance are secondary. While the former data relates to L 1 more closely if the primary categories related to L 1 are evaluated before the unrelated category to L 1 , the latter data is closer to L 1 if the primary categories after the unrelated category.

Criteria for the strength of relationship between data and a set of labels enable to evaluate the degree of the strength. The purpose of this paper is to propose such criteria by discussing the strength of relationship between data and a set of labels. This paper also refers to the strength of the criteria and introduces levels of data, which is decided by the strongest criterion that the data satisfies.

Ranks in classification of data have been studied in the field of information retrieval mainly. Those researches focus on the accuracy and the efficiency of automatic ranking of data [START_REF] Kim | Ranking using Multiple Document Types in Desktop Search[END_REF] [START_REF] Lopez | A Model for Multi-label Classification and Ranking of Learning Objects[END_REF]. After ranking, personal preferences of queries are measured and the ranks of data based on those numerical values are applied to the advanced information retrieval [START_REF] Wang | Personalized Ranking Model Adaptation for Web Search[END_REF]. Many researches focus on ranking data known as Top-k, where significant data are selected by measuring the degree of relationship between data and a set of labels [START_REF] Chakrabarti | Ranking Objects by Exploiting, Relationships: Computing Top-K over Aggregation[END_REF] [START_REF] Lu | Optimal Top-k Generation of Attribute Combinations based on Ranked Lists[END_REF]. While their purpose is to evaluate data on a specific domain quantitatively to develop applications, the purpose of this paper is to build fundamental theories of multi-labeled data by evaluating data qualitatively.

This paper is organized as follows. Section 2 refers to the strength of relationship between data without ranks and a set of labels, and introduces criteria to decide the strength. In Section 3, criteria for data with ranks are discussed. Section 4 proposes the strength of the criteria and the levels of data to express the degree of the strength. The discussions of Sections 3 and 4 are for two rank data, which are extended to k rank data in Section 5. Section 6 concludes the paper.

Strength of Relationship between Objects and Labels

Individual data or an object is classified by a certain type of characteristic, which is called an attribute. For example, an object is classified to manufacturing, transportation, automobile, etc., where the attribute is industry. This paper assumes that an object is classified to the lowest category to which the object is related in a given classification hierarchy.

Let o be an object, L be a label, and L = {L 1 , L 2 , • • • , L n } be a set of labels. When o is classified to multiple categories, o is annotated with the set of labels of those categories, which is denoted by L(o) and called a set label of o.

For labels L 1 and L 2 , L 1 is lower than L 2 (L 2 is higher than L 1 ) if the category of L 1 is a lower concept of the category of L 2 , and L 1 ⪯ L 2 denotes that L 1 is lower than or equal to L 2 . L 1 relates to L 2 if L 1 ⪯ L 2 and a label L relates to a set of labels L if L relates to a label of L. Label Transportation relates to label Manufacturing because Transportation ⪯ Manufacturing.

For sets of labels L and L ′ , the set of the labels of L which relate to

L ′ is described by Rel L ′ (L) = {L | L ∈ L, ∃L ′ ∈ L ′ , L ⪯ L ′ }.
Let L be a set of labels to be used to identify target objects. If there is such a label in L(o) that relates to L (Rel L (L(o)) ̸ = ϕ), o relates to L . Let L be the set of objects relating to L.

There are several kinds of objects in L such as objects which relate to multiple labels of L, objects which relate to other labels than L, and so on. There are various ways to decide the degree of how strong an object o relate to L, and the number of labels relate to L may not be affected on the strength of relationship between o and L. This paper focuses on the qualitativeness of relationship and does not mention the number of the labels which relate to L.

There are several kinds of objects identified by L, and the strength of relationship between objects and L is different in general. Criteria for the strength enable us to select proper objects according to their purposes.

For objects

o 1 and o 2 , o 1 < L o 2 , o 1 < o 2 if L is

Criteria for the Strength of Relationship

This section introduces ranks to express how close objects are to the categories. The more number of ranks give us the richer information and allow more precise analysis. This section discusses the cases where the number of ranks is two for simplicity. The discussions for two rank objects are extended to k rank objects in Section 5.

Let the ranks of labels of set labels be primary and secondary.

-Primary labels : If an object is classified to a category and relates to the category mainly, the label of the object is a primary label.

-Secondary labels : If an object is classified to a category and relates to the category but not mainly, the label of the object is a secondary label.

For an object o, let P (o) and S(o) be the set of the primary labels and the set of the secondary labels of L(o), respectively.

Property 1. L(o) = P (o) ∪ S(o). Property 2. P (o) ∩ S(o) = ϕ. Property 3. P (o) ̸ = ϕ.
The rest of this section discusses criteria for two rank objects. It is reasonable to think that an object o 1 relating to a set of labels L (Rel L (L(o 1 )) ̸ = ϕ) relates to L more closely than an object o 2 not relating to L (Rel L (L(o 2 )) = ϕ). Thus the condition whether a label of L(o) relates to L is a criterion for the strength of relationship between o and L.

cnd LE : For a set of labels L and an object o, there exists a label of L(o) which relates to L, that is,

Rel L (L(o)) ̸ = ϕ.
Since it is acceptable to think that an object o 1 relating to a set of labels L mainly (Rel L (P (o 1 )) ̸ = ϕ) relates to L more closely than an object o 2 not relating to L mainly (Rel L (P (o 2 )) = ϕ), the condition whether a primary label of L(o) of an object o relates to L is a criterion for the strength of relationship between o and L. 3 and L 3 is the same as the strength of relationship between o 3 and L 3 because both of them have primary labels relating to L 3 .

If there are no labels of P (o) which relate to other labels than L, the strength of relationship is decided by whether there exist labels of S(o) which relate to other labels than L. If there exist such labels in S(o), it means that there exist labels of L(o) which relate to other labels than L, and this condition is equivalent to cnd LN . This section gave the criteria for the strength of relationship between o and L. cnd LE and cnd P E are based on relationship between L(o) and the labels of L, and cnd LN and cnd P N are based on relationship between L(o) and other labels than L.

The Strength of the Criteria

This section discusses the strength of the criteria. When the strength of relationship between an object o 1 and a set of labels L is compared with the strength of relationship between an object o 2 and L, a criterion cnd 2 is stronger than a criterion cnd 1 for L if the strength can be decided by whether an object satisfies cnd 2 rather than cnd

̸ ∈ L cnd2 because cnd 1 is a criterion. Although o 2 satisfies cnd 2 and o 1 satisfies cnd 1 but not cnd 2 , cnd 1 < cnd 2 is not satisfied because o 1 < o 2 is not satisfied. Thus L cnd2 ⊆ L cnd1 if cnd 1 < cnd 2 .
If a criterion cnd 1 implies a criterion cnd 2 (cnd 1 ⇒ cnd 2 ), L cnd1 ⊆ L cnd2 and vice versa. Thus the strength of cnd 1 and cnd 2 is decided by implication of cnd 1 and cnd 2 because Lemma 1 shows that the strength of cnd 1 and cnd 2 is decided by the inclusion relation of the objects satisfying cnd 1 and cnd 2 .

Theorem 1. For criteria cnd 1 and cnd 2 , cnd 1 < cnd 2 is equivalent to

cnd 2 ⇒ cnd 1 . Proof. If cnd 1 < cnd 2 , L cnd2 ⊆ L cnd1 by Lemma 1. If L cnd2 ⊆ L cnd1 , cnd 2 ⇒
cnd 1 because objects satisfying cnd 2 also satisfy cnd 1 . On the other hand, if

cnd 2 ⇒ cnd 1 , L cnd2 ⊆ L cnd1 . Lemma 1 shows that cnd 1 < cnd 2 if L cnd2 ⊆ L cnd1 .
If one criterion implies another criterion, those criteria are based on the same point of view, which means that the criteria can be used to evaluate the strength of relationship of objects and sets of labels consistently by Theorem 1. The rest of this section discusses implication of the criteria to decide the strength of the criteria.

If an object o satisfies cnd P E , there exists a label of P (o) relating to L, which is a label of L(o) and o satisfies cnd LE too. If o satisfies cnd P N , there is no label of P (o) which relates to other labels than L. Since there always exist labels of P (o), there are labels of P (o) which relate to L and o satisfies cnd P E too. . By Lemma 1, the inclusion relation of objects according to the levels is shown in Figure 1 and users can select the range of the objects on their purposes.

L cnd P E L cnd P N L cnd LN L cnd LE

k Ranks

The discussion for two rank objects is extended to k rank objects. Let k ranks be R

1 , • • • , R i , • • • , R k (1 ≤ i ≤ k)
where R i is stronger than R j (i < j). In the case of k = 2, R 1 = P and R 2 = S. For an object o, let R i (o) be the set of labels of L(o) whose rank is R i , and R * i (o) = ∪ j=1,i R j (o) be the set of labels of L(o) whose ranks are stronger than or equal to R i .

The properties of set labels of two rank objects in Section 3 are extended to k ranks.

Property 4. L(o) = ∪ i=1,k R i (o). Property 5. R i (o) ∩ R j (o) = ϕ (i ̸ = j). Property 6. R 1 (o) ̸ = ϕ.
The rest of this section discusses the criteria for k rank objects. The criteria for the strength of relationship between a set of labels L and the set labels of an object o can be divided into two types, which are the criteria for relationship between L and the labels of L(o) and the criteria for relationship between L and other labels than L(o). Each of them is extended for k rank. cnd RiE (1 ≤ i ≤ k) : For a set of labels L and an object o, there exists a label of L(o) which relates to L and whose rank is stronger than or equal to R i , that is,

Rel L (R * i (o)) ̸ = ϕ. cnd RiN (1 ≤ i ≤ k) :
For a set of labels L and an object o, there does not exist a label of L(o) which relates to other labels than L and whose rank is stronger than or equal to R i , that is,

Rel L (R * i (o)) = R * i (o).
Lemmas 2, 3, and 4 correspond to the following lemmas for k rank objects.

Lemma 5. For cnd RiE (2 ≤ i ≤ k), cnd Ri-1E ⇒ cnd RiE . Proof. For an object o which satisfies cnd Ri-1E , Rel L (R * i-1 (o)) ̸ = ϕ. Since R * i-1 (o) ⊆ R * i (o), Rel L (R * i (o)) ̸ = ϕ, and o satisfies cnd R * i E . Lemma 6. For cnd RiN (2 ≤ i ≤ k), cnd RiN ⇒ cnd Ri-1N . Proof. For Rel L (R * i (o)) = R * i (o). Since R * i-1 (o) ⊆ R * i (o), Rel L (R * i-1 (o)) = R * i-1 (o),
L (R 1 (o)) ̸ = ϕ. Thus o satisfies cnd R1E .
Since implication of the criteria is shown by Lemmas 5, 6, and 7, the following theorem on the strength of the criteria is satisfied.

Theorem 3. For cnd RiE and cnd

RiN (1 ≤ i ≤ k), cnd R k E < cnd R k-1 E < • • • < cnd R1E < cnd R1N < • • • < cnd R k-1 N < cnd R k N . Proof. cnd R k N ⇒ cnd R k-1 N ⇒ • • • ⇒ cnd R1N ⇒ cnd R1E ⇒ • • • ⇒ cnd R k-1 E ⇒ cnd R k E because cnd RiN ⇒ cnd Ri-1N
, cnd R1N ⇒ cnd R1E , and cnd Ri-1E ⇒ cnd RiE by Lemmas 6, 7, and 5, respectively. Thus cnd

R k E < cnd R k-1 E < • • • < cnd R1E < cnd R1N < • • • < cnd R k-1 N < cnd R k N by Theorem 1.

Conclusion

This paper introduced the criteria for the strength of relationship between an object o and a set of labels L, which are cnd LE , cnd P E , cnd P N , and cnd LN . o satisfies cnd LE , cnd P E , cnd P N , and cnd LN if o relates to L, L mainly, only L mainly, and only L, respectively. Referring to the strength of the criteria, it was shown that cnd LE < cnd P E < cnd P N < cnd LN . Thus the strongest criterion which o satisfies can be used as the levels to express the degree of the strength. Those results can be applied to k rank objects.

The strength of the criteria is decided by implication of the criteria. If one criterion implies another criterion, both of them can be used to evaluate the strength of relationship between objects and sets of labels because their criteria are based on the same point of view. The criteria proposed in this paper enable to evaluate data with ranks qualitatively and consistently. Thus users can select the range of data at each of levels based on the criteria according to the purpose of the utilization of data. In general, the range of data is decided by changing the set of labels to identify the data. For example, if users want to utilize data widely, lower concept labels are replaced by higher concept labels or additional labels are inserted. In such utilization of data, originally intended purpose may not be realized because the set of labels itself has been changed. The levels based on the criteria solve this issue because the range of data can be changed according to the levels even if the set of labels is no change.

Example 2 .

 2 For a set of labels L 2 = {Transportation}, L 2 includes object o 1 such that L(o 1 ) = {Automobile}, object o 2 such that L(o 2 ) = {Automobile, Motorcycle} where multiple labels of L(o 2 ) relate to L 2 , object o 3 such that L(o 3 ) = {Automobile, Finance} where Finance does not relate to L 2 , etc.

  cnd P E : For a set of labels L and an object o, there exists a primary label of L(o) which relates to L, that is, Rel L (P (o)) ̸ = ϕ. There are cases that secondary labels of L(o) affect the strength of relationship between o and L. If Rel L (P (o)) = ϕ, the strength by S(o) is equivalent to cnd LE . Suppose Rel L (P (o)) ̸ = ϕ. For an object o 1 such that Rel L (P (o 1 )) ̸ = ϕ and Rel L (S(o 1 )) ̸ = ϕ and an object o 2 such that Rel L (P (o 2 )) ̸ = ϕ and Rel L (S(o 2 )) = ϕ, both o 1 and o 2 do not relate to L more closely than the other. Example 3. Suppose the labels of object o 1 and object o 4 are P (o 1 ) = {Automobile}, S(o 1 ) = ϕ, P (o 4 ) = {Automobile}, and S(o 4 ) = {Mobile Phone} for set of labels L 3 = {Manufacturing}. Although

Lemma 2 .Lemma 3 .

 23 For cnd P E and cnd LE , cnd P E ⇒ cnd LE . Proof. For an object o which satisfies cnd P E , since Rel L (P (o)) ̸ = ϕ by satisfying cnd P E and L(o) = P (o) ∪ S(o) by Property 1, P (o) ⊆ L(o). Thus Rel L (L(o)) ̸ = ϕ, and o satisfies cnd P E . If o satisfies cnd LN , there is no label of L(o) which relates to other labels than L. It means that there is no label of P (o) which relates to other labels than L and o satisfies cnd P N too. For cnd LN and cnd P N , cnd LN ⇒ cnd P N . Proof. For an object o which satisfies cnd LN , Rel L (L(o)) = L(o), in other words, L(o) does not include a label relating to other labels than L. Since L(o) = P (o) ∪ S(o) by Property 1, L(o) does not include labels which relate to other labels than L, and Rel L (P (o)) = P (o). Thus o satisfies cnd P N .

Lemma 4 .

 4 For cnd P N and cnd P E , cnd P N ⇒ cnd P E . Proof. For an object o which satisfies cnd P N , Rel L (P (o)) = P (o), in other words, P (o) does not include a label relating to other labels than L. Since P (o) ̸ = ϕ by Property 3, there always exists a label of P (o) which relates to L, and Rel L (P (o)) ̸ = ϕ. Thus o satisfies cnd P E . The strength of the criteria is decided by implication of cnd LE , cnd P E , cnd P N , and cnd LN as shown by Lemmas 2, 3, and 4.

Fig. 1 .

 1 Fig. 1. Inclusion Relation of Objects Satisfying each of the Criteria

  obvious, denotes that o 2 relates to L more closely than o 1 . A condition cnd is a criterion for strength of relationship between a set of labels and an object if o 2 satisfies cnd and o 1 does not for any objects o 1 and o 2 such that o 1 < L o 2 .

  Mobile Phone of L(o 4 ) relating to L 3 is a secondary label, it is not acceptable to think that o 1 relates to L 3 more closely than o 4 because o 1 and o 4 have primary label Automobile for L 3 , namely, both of them relate to Manufacturing mainly. For object o ′ 4 such that P (o ′ 4 ) = {Automobile, Mobile Phone} and S(o ′ 4 ) = ϕ, it is not reasonable to think that o 4 relates to L 3 more closely than o ′ 4 because Mobile Phone of L(o ′ 4 ) is a primary label and Mobile Phone of L(o 4 ) is a secondary label. Since the number of the labels which relate to L 3 does not affect the strength, the strength of relationship between o ′ 4 and L 3 is the same as the strength of relationship between o 1 and L 3 . For a set of labels L and objects o 1 and o 2 , it can be regarded that o 1 relates to L more closely than o 2 if L(o 1 ) does not include other labels than L and L(o 2 ) includes such labels. cnd LN : For a set of labels L and an object o, there does not exist a label of L(o) which does not relate to L, that is, Rel L (L(o)) = L(o). is also acceptable to think that an object o 1 relates to L more closely than an object o 2 if P (o 1 ) does not include other labels than L while P (o 2 ) includes other labels than L. cnd P N : For a set of labels L and an object o, there does not exist a label of P (o) which does not relate to L, that is, Rel L (P (o)) = P (o). For the criteria for secondary labels of L(o) which relate to other labels than L, if there are labels of P (o) which relate to other labels than L, such labels of S(o) do not affect the strength of relationship. Example 4. Suppose object o 3 such that P (o 3 ) = {Automobile, Finance} and S(o 3 ) = ϕ and object o ′ 3 such that P (o ′ 3 ) = {Automobile, Finance} and S(o ′ 3 ) = {Education} are evaluated for L 3 = {Manufacturing}. Although o ′ 3 has secondary label Education which relates to other labels than Manufacturing, it is not acceptable to think that o ′ 3 relates to L 3 more closely o 3 . For object o ′′ 3 such that P (o ′′ 3 ) = {Automobile, Finance, Education}, it is not acceptable to think that o ′′ 3 relates to L 3 more closely than o ′ 3 because o ′′ 3 has primary label Education. Thus o ′ 3 < o ′′ 3 is not satisfied. The strength of relationship between o ′′

	It

  1 . In other words, if o 1 < o 2 for o 1 and o 2 such that o 1 dose not satisfy cnd 2 and o 2 satisfies cnd 2 regardless of whether o 1 or o 2 satisfies cnd 1 , cnd 2 is stronger than cnd 1 for L. That's because the strength can be decided if o 1 does not satisfy cnd 2 while o 1 may be relate to L more closely than o 2 by cnd 1 . For a set of labels L and criteria cnd 1 and cnd 2 , cnd 2 is stronger than cnd 1 for L if o 1 < L o 2 for any objects o 1 and o 2 such that o 1 satisfies cnd 1 but not cnd 2 and o 2 satisfies cnd 2 , denoted by cnd 1 < L cnd 2 , or cnd 1 < cnd 2 if L is obvious. The set of the objects of L which satisfy a criterion cnd is denoted by L cnd (={o | o ∈ L, o satisfies cnd}). The strength of criteria can be decided by the inclusion relation among the set of the objects which satisfy each of the criteria. For a set of labels L and criteria cnd 1 and cnd 2 , cnd 1 < cnd 2 if and only if L

	Definition 1. Lemma 1.

cnd2 ⊆ L cnd1 . Proof. For objects o 1 in L cnd1 and o 2 in L cnd2 , if o 1 ̸ ∈ L cnd2 , o 1 < o 2 because cnd 2 is a criterion. Since o 1 satisfies cnd 1 but not cnd 2 and o 2 satisfies cnd 2 , cnd 1 < cnd 2 . If L cnd2 ⊆ L cnd1 is

not satisfied, there exists such an object o 2 that o 2 ∈ L cnd2 and o 2 ̸ ∈ L cnd1 . o 2 satisfies cnd 2 but not cnd 1 . On the other hand, o 2 < o 1 for such an object o 1 that o 1 ∈ L cnd1 and o 1

Theorem 2 .

 2 For cnd LE , cnd P E , cnd P N , and cnd LN , cnd LE < cnd P E < cnd P N < cnd LN . Proof. cnd LN ⇒ cnd P N ⇒ cnd P E ⇒ cnd LE because cnd LN ⇒ cnd P N , cnd P N ⇒ cnd P E , and cnd P E ⇒ cnd LE by Lemmas 3, 4, and 2, respectively. Thus cnd LE < cnd P E < cnd P N < cnd LN by Theorem 1. Since Theorem 2 shows the strength of the criteria, the strongest criterion satisfied by o is to express the strength of relationship between o and L, which is defined as the level of o for L. Levels of objects enable us to evaluate the strength of the objects for L. Mobile Phone} satisfies only cnd LE and o ′ 5 is at the lowest or the weakest level on the strength. Since object o ′′ 5 such that P (o ′′ 5 ) = {Automobile, Finance} and S(o ′′ 5 ) = {Mobile Phone} includes primary label Automobile for L 1 , o ′′ 5 satisfies cnd P E too, namely, o ′′ 5 is at the second level on the strength. Moreover, object o ′′′ 5 such that P (o ′′′ 5 ) = {Automobile, Mobile Phone} and S(o ′′′ 5 ) = {Finance} satisfies cnd P N because o ′′′ 5 does not have the primary labels which relate to other labels than L 1 , and o ′′′ 5 is at the third level on the strength. Finally, object o ′ 4 (P (o ′ 4 ) = {Automobile, Mobile Phone} and S(o ′ 4 ) = ϕ) satisfies cnd LN because o ′ 4 has no label which relates to other labels than L 1 , and o ′ 4 is at the highest or the strongest level on the strength. Thus

	Example 5. For L 1 = {Transportation, Electronics}, object o ′ 5 such that P (o ′ 5 ) = {Finance} and S(o ′ 5 ) = {Automobile, o ′ 5 < o ′′ 5 < o ′′′ 5 < o ′ 4

  and that o satisfies cnd R * i-1 N . Lemma 7. For cnd R1N and cnd R1E , cnd R1N ⇒ cnd R1E . Proof. For an object o which satisfies cnd R1N , Rel L (R 1 (o)) = R 1 (o), in other words, R 1 (o) does not include a label relating to other labels than L. Since R 1 (o) ̸ = ϕ by Property 6, there always exists a label of R 1 (o) which relates to L, and Rel