Yue Kang

Danilo Alves De Lima

Alessandro Corrêa

Driving Behavior Correction in Human-Vehicle Interaction based on Dynamic Window Approach

Keywords: Human-Vehicle Interaction, Human Driving Behavior, Driving Safety, Dynamic Window Approach

This paper presents the approach of an applicable safety driving methodology for human drivers with focus on human-vehicle interaction. The approach is based on Dynamic Window Approach (DWA) in co-operation with perception of the obstacles. The human driving behaviors are modelled for the design of controller, refined by referential paths using evasive trajectory model, where linear and angular velocities are limited and corrected by DWA which performed as an obstacle avoidance strategy. Results of trajectory following and obstacle avoidance are compared with the Visual Servoing (VS) controller as a corresponding approach of autonomous control pattern.

I. INTRODUCTION

Human-Vehicle interaction has been of major interest since the very beginning of the intelligent vehicle history. The interaction, initially limited to the primary commands as steering wheel, accelerator and brake, has evolved to a general level where drivers have access to the knowledge of the vehicle state [START_REF] Damiani | Driver-vehicle interfaces and interaction: where are they going?[END_REF]. For instance, in the project CeMVocAS [START_REF] Tattegrain-Veste | Evaluation of a voice interface management system[END_REF], a first attempt to examine the driver workload while coping with the oncoming phone calls and to apply this concept to an on-vehicle speech recognition system was made. In a more recent approach, the project AIDE [START_REF] Andreone | Beyond context-awareness: driver-vehicle-environment adaptivity. from the comunicar project to the aide concept[END_REF] involved a real-time awareness system of traffic and environmental conditions. These conditions build up a provision of the information to the driver as simultaneous messages and warnings with the Interaction and Communication Assistant (ICA). During the progress of development, the main responsibility of the human-vehicle interaction remains steady: to enhance the driving safety.

Developing effective active safety devices has gained emphasis within the last decades for accident prevention and harm reduction [START_REF] Ghandour | Risk indicators evaluation based on anticipated vehicle dynamics parameters[END_REF]. A large number of road accidents occur on the main and secondary roads each year, and driver error is one of the reasons with evident importance [START_REF] Lotz | System architectures for automated vehicle guidance concepts[END_REF]. A growing number of applicable approaches has been brought out in the progress of various modelings of driving behavior. For instance, a similar system is proposed in [START_REF] Glaser | Speed limitation based on an advanced curve warning system[END_REF] which takes into account vehicle dynamics and driver behavior as coefficient that express how much acceleration the driver could accept. Another approach of software-based collision avoidance system was implemented to a dedicated short-range vehicle-to-vehicle communication for better mitigating accident collisions [START_REF] Tang | Collision avoidance timing analysis of dsrc-based vehicles[END_REF]. More recently in [START_REF] Wang | A safety-based approaching behavioural model with various driving characteristics[END_REF] a safety-based approaching behavioural model was proposed for the driver's car-following behavior with various driving characteristics, deducted from an integrated driving behavior modeling framework in previous works [START_REF] Toledo | Integrated driving behavior modeling[END_REF] [START_REF]Estimation of an integrated driving behavior model[END_REF].

However, these achievements focusing on modeling the characteristics and behavior of intelligent vehicles rarely employ the driver's control instructions to the vehicles, and human effect during the driving has failed to be taken into sufficient consideration while human drivers' repulsive controlling characteristics are still major causes of road crashes [START_REF] Houenou | Vehicle trajectory prediction based on motion model and maneuver recognition[END_REF] [START_REF] Isermann | Collision-avoidance systems proreta: Situation analysis and intervention control[END_REF]. As a complement of Advanced Driver Assistance Systems (ADASs) with focus on the human-vehicle interaction, especially the judgement and correction of human drivers'

The authors are with Heudiasyc UMR CNRS 7253 Université de Technologie de Compiègne. Yue Kang holds a Ph.D scholarship from Chinese Scolarship Council and Picardi region in France. Contact authors yue.kang@hds.utc.fr behavior, our approach aims at taking the decision of human drivers into consideration by modeling the driving behaviors, especially the faults and potential dangers. During the driving, the autonomous system interacts with the human driver by detecting these driving behaviors and providing reactions of correction.

Modeling the decision of human drivers preserves its significance as the foundation for the approaches of the judgement and correction of human drivers' behavior in human-vehicle interactions. In [START_REF] Angkititrakul | Impact of driving context on stochastic driver-behavior model: Quantitative analysis of car following task[END_REF] a stochastic car-following driver behavior modeling is proposed with operations of the gas and brake pedals in response to the stimuli of vehicle velocity and following distance. a more detailed model of driving behavior characteristics analysis is illustrated in [START_REF] Ge | Study on driving behavior and traffic conflict at highway intersection[END_REF] with a weight determination based on influences of various driving behaviors on conflict.

The objective of our approach is to simulate and correct the human drivers' decision faults, which is accomplished by applying the Dynamic Window Approach (DWA) [START_REF] Fox | The dynamic window approach to collision avoidance[END_REF]. The human decision faults are modelled as predefined trajectory paths where potential collisions and crashes occur [START_REF] Lima | Navigation of an autonomous car using vector fields and the dynamic window approach[END_REF]. This approach is emerged from the approach of our parallel work where the DWA method was applied with an image-based Visual Servoing (VS) controller to perform the autonomous road lane following task while avoiding obstacles. In the current approach we focus on the correction of the human decision faults in the same driving environment of the autonomous VS-DWA cooperative control pattern, and a comparaison of performance between the two controllers.

In order to present this methodology, this article is organized as follows: in Section II, we present the robot model and the simulation environment; in Section III, we illustrate our design of control pattern in the perspective of human-vehicle interaction with a short introduction of DWA-VS controller used for the comparaison, and the evasive trajectory as the reference for the design of HDB controller; finally experimental results with performance analysis are presented in section IV.

II. GENERAL DEFINITIONS

The robot in this work is considered to move in a planar workspace, similar to the one described in [START_REF] Cherubini | Visual servoing for path reaching with nonholonomic robots[END_REF], where the road lane center defines a path once differentiable in IR 2 . The robot follows the path according to the kinematic model of a front wheel car [START_REF] Luca | Robot Motion Planning and Control[END_REF] as:

    ẋr ẏr θ φ     =     cos θ cos φ sin θ cos φ sin φ/l 0     v1 +     0 0 0 1     v2 , (1)
where the vehicle configuration is given by q = [xr yr θ φ] T , with the position (xr, yr) and orientation (θ) of the car's reference frame {R} in relation to a static world reference frame {O}, and φ is the average steering angle of each front wheel by the Ackerman's approximation. The orientation and steering angles (θ and φ) are positive counter-clockwise, with θ ∈] -π, π] and φ ∈ [-φmax, φmax]. The variables are illustrated in the Figure 1.

The control input for the vehicle of the model ( 1) is u = [v1 v2] T , which consists of respectively the linear velocity v1 and the steering velocity v2 of the front wheels. With the relationship between linear velocity v and front wheels velocity v1 as v = v1 cos(φ), as well as the angular velocity θ = v1 cos(φ)/r1 = ω and the steering angle, it is possible to choose the robot control input as ur = [v ω] T .

For the presentation of Visual Servoing (VS) control used for further comparaisons in the Section III and IV, the Figure 1 also represents the camera frame {C} with optical center position in (xc, yc, zc) = (tx, ty, tz) in the robot frame and a constant tilt offset The obstacles on the road are represented as blocks with similar size to our vehicle, as in the Figure 3. An example from the camera point of view is also represented in the Figure 2. To simplify the problem, we assume that the obstacles are in two dimensions, rectangleshaped and can be detected by exteroceptive sensors, for instance, LIDAR. This assumption helps reduce the difficulty of establishing the simulating and experimental environment while maintain the feasibility and reliability of the obstacle avoidance required by the Dynamic Window Approach (DWA).

III. HUMAN-VEHICLE INTERACTIONS

Recalling the principal aim of our work, we propose an autonomous correction mechanisme to the driving behaviors based on the Dynamic Window Approach (DWA). The interaction between human drivers and the vehicle, which consists of actions taken by human drivers during the actual driving process, is represented by a predefined referential trajectory with a set of the vehicle configuration q = [xr yr θ φ] T defined in the Section II. This interaction replaces Fig. 3. Obstacles represented in world frame {W} (in blue), with detection of obstacles and also navigable zone boundaries (in pink).

the VS control in VS+DWA pattern, and is revised and optimized by the application of the new control input u = [v1 v2] T calculated by DWA.

A. Dynamic Window Approach

The Dynamic Window Approach is a reactive obstacle avoidance technique proposed originally by [START_REF] Fox | The dynamic window approach to collision avoidance[END_REF], with a modification for carlike robots presented in [START_REF] Rebai | Car-like robot navigation at high speed[END_REF], This approach optimize an objective function (2) in order to select the best control input regarding the desired configuration to the robot. The objective fonction is constituted with three weighted components: the goal position (heading), the obstacle distance (dist) and the final linear velocity (velocity), represented as:

DW A(v, ω) =α • heading(v, ω) + β • dist(v, ω) + γ • velocity(v, ω).
(

) 2
Initially, for the actual velocity of the robot (va, ωa), the dynamic window V d is defined for all reachable velocities in a time interval △t as:

V d = {(v, ω)| v ∈ [va -v△t, va + v△t] , ω ∈ [ωa -ω△t, ωa + ω△t]} (3)
where v and ω are respectively the linear and angular acceleration of the robot. Following, each reachable velocity must be classified as admissible or not depending on the obstacle distance (dist) and the robot maximum breaking accelerations ( vb , ωb ). The velocity is guaranteed as admissible if the distance to the obstacle in a circular trajectory exceeds the distance required to stop safely the vehicle. The collision detection algorithm implemented in the function dist(v, ω) is the one proposed by [START_REF] Arras | Real-time obstacle avoidance for polygonal robots with a reduced dynamic window[END_REF] for polygonal robots, which defines the set of admissible velocities:

Va = {(v, ω)| v ≤ 2 • dist(v, ω) • vb , ω ≤ 2 • dist(v, ω) • ωb } . (4)
Finally, Vs is defined to satisfy the maximum acceleration constraints vmax and ωmax. The dynamic window search space, which considers the actual speed of the vehicle, its accelerations, the obstacles in the workspace, and also the physical limits of the vehicle is consequently generated as:

VDW = V d ∩ Va ∩ Vs. (5)

B. Design of Control Pattern

According to the control input for the vehicle defined in the Section II as u = [v1 v2] T , we simplify the human control pattern. In an ideal driving environment where no obstacles are involved, the obstacle distance (dist) in the objective function is omitted. Naturally human driver conducts the vehicle in the center of the road lanes, with which the goal position (heading) in the objective function 2 is determined. The linear and the angular speeds depend on the maximum velocity constrain of the vehicle, the legal speed limitions of the road and the road conditions (turnings, intersections, etc.). In a simplified experimental circle track, the linear velocity v1 and the steering velocity v2 are constrained respecting these elements.

In general, human drivers avoid the collision with two principal reactions: decelerating and turning. Without any auxiliary perception of the environment, these reactions depend only on the individual judgement of the human drivers [START_REF] Ranney | Models of driving behavior: a review of their evolution[END_REF]. Consequently, the DWA guarantees a limitation of the input velocities with the help of the obstacle avoidance and the implement of the obstacle distance (dist). Nonetheless, apart form the obstacle avoidance, the essential aim of human drivers is still guiding the vehicle in the center of the road, and the the goal position (heading) remains unchanged.

As a contrast to the human control pattern, we apply the Visual Servoing (VS) strategy carried out by Cherubini et al [START_REF] Cherubini | Visual servoing for path reaching with nonholonomic robots[END_REF], in which two non-linear feedback controllers are designed for the propose of following a line path projected in the camera image. With the absence of the capacity to guarantee the safety of driving, a correction by an obstacle avoidance technique, in this case the DWA, is consequently necessary. Omitting the detail of visual perception and projection, the design of the feedback control of VS is represented as:

ω = -B + c (λe + Acv d ), ( 6
)
where ω is the feedback gain of the controller, e is the state error calculated according to the visual characteristics from the projected image, Ac and Bc are matrixes from the kinematic model ( 1) transformed to the image frame, and v d is the desired linear velocity of the tracking control. For more details of the implementation and stability analysis see [START_REF] Cherubini | An image-based visual servoing scheme for following paths with nonholonomic mobile robots[END_REF].

To imitate the behavior of human driving, we propose an ordinary but practicable design of feedback control according the Euclidean distance between the position (xr, yr) of the vehicle and a predefined referential trajectory path which represents the desired driving route. This design of feedback control, namely human driving behavior (HDB) controller is represented as:

ω = v d v l (xr -xp) 2 + (yr -yp) 2 + β, ( 7
)
where ω is the feedback gain of the controller, v d is the desired linear velocity of the tracking control, v l is the velocity limitation of the vehicle, (xr, yr) are coordinates of the position of the vehicle, (xp, yp) are coordinates of the corresponding point on the referential path, and β is an additive white Gaussian noise (AWGN) which represents inaccuracy of human drivers' control. Noted that this controller involves no angular information. This omission is acceptable in the circumstance where human drivers are rarely aware of the precise drift angle of the vehicle [START_REF] Keller | Active pedestrian safety by automatic braking and evasive steering[END_REF].

C. Referential Path Modeling

For the requirement of predefinition of the referential path in the design of HDB controller, a mathematical model of driving trajectory is essential. From the approach of vehicle trajectory prediction [START_REF] Houenou | Vehicle trajectory prediction based on motion model and maneuver recognition[END_REF] we are confirmed that, in an appropriately simplified driving circumstance, modeling the human drivers' behaviors with an ensemble of data, including the vehicle position coordinates which consist of a discrete path, and the linear and angular velocities representing the decision of acceleration, brake and steering, is practical and adequate. In an obstacle-free circumstance this path is located in the middle of the drivable road, in the form of segments in a straight line or an arc, depending on the road driving condition characteristics. With obstacles involved, this geometrical layout of driving path is inadequate. In our approach, an evasive trajectory [START_REF] Isermann | Collision-avoidance systems proreta: Situation analysis and intervention control[END_REF] is applied in the task of obstacle avoidance. This trajectory is described by a sigmoid curve in the form as:

y(x) = ym 1 + e -a(x-c) , ( 8
)
where ym is the maximum y-value, a defines the slope at x = c of the sigmoid curve and c defines the position of the inflection point of the curve, therefore the total length as s = 2c. The curve of the trajectory along with its parameters is presented in the Figure 4. Noted that the definition of the evasive trajectory is not a function of time (i.e. an abuse of the naming "trajectory"), we utilize henceforth this model as a segment of a referential path. For the determination of the referential path in the task of obstacle avoidance for HDB controller, we manually revise the initial path, which is obtained in the obstacle-free circumstance, at the segments where obstacles occupy the initial path, as presented in the Figure 5.

IV. EXPERIMENTAL RESULTS

A. Validation

Our first experiment aims at validating the design of imitational feedback controlling mechanism of the HDB controller that mimics the driving behaviors of humankind. The vehicle is set in a closedloop athletic-track-shaped environment as workspace without obstacles, in which a referential clockwise path in the middle of the rightside road is predefined. The vehicle succeeded the path following task in accordance with the HDB controller applied to the kinematic model ( 1), as represented in the Figure 6. The results in the Figure 6(a) demonstrated the driving route by HDB controller with an ideal referential path, while the Figure 6(b) and the Table I illustrated the divergence of the coordinates of the actual driving route in comparison with the reference. While the overall route converged to the referential path, the largest deviation of the driving route occurred when the vehicle left the curve and entered the straight road. This phenomenon is due to the absence of angular information in the design of the HDB controller, which causes time delay of establishing the steady angular state. It also reflects the common failure of the judgement by the human drivers as incorrect estimation of the actual steering angle of the vehicle.

B. Comparison with VS

For the purpose of proving the feasibility and reliability of our methodology in the sense of safety driving, we set up obstacles showed in the Figure 3 in the simulation environment, and apply DWA method to both HDB and VS controllers. The results are presented in the Figure 7. The routing result presented in the Figure 7(a) demonstrated that both controllers succeeded in guiding the robot to avoid obstacles with the application of DWA. Although the difference between the two routes did not prove adequately the advantage of our approach, the Figure 7(b) demonstrated that, after an essential deceleration before engaging the avoidance, the vehicle applied with the HDB controller passed the obstacle while maintaining a relatively high linear velocity. In contrast, with a sharp drop followed by a long period of low-speed forwarding, the robot guided by the VS controller failed to retain the velocity during a passing manoeuvre, which demanded a consequently long passing time and an increase of energy consuming. In addition, the Figure 7(c) and the Table II illustrated that HDB controller guaranteed the smoothness of turning procedure. The angular velocity of the robot calculated by HDB controller remained in a suitable interval. As a contrast, with the guidance of the VS controller, the angular velocity rapidly flipped with peak values considerably larger than those calculated by HDB controller. The experimental result proved HDB controller available and feasible with the cooperation of DWA method and a predefined referential path, while reducing the demand of deceleration in comparison with the VS controller.

C. Danger Behaviors Correction

In this experimental section, the performance of our methodology is examined in the circumstance where human drivers adopt danger behaviors while driving. For the purpose of representing the danger behaviors, the referential path is adjusted according to the evasive trajectory presented in the Section III-C. Firstly we postpone the turning of the path before bypassing an obstacle to simulate the delayed steering decision of human drivers. Another danger behavior is presented as a wrong turning which leads to a potential thread of collision. Both adjustments of the referential path are presented in the Figure 8(a).

The experimental result of the route, also presented in the Figure 8(a), illustrated that the robot successfully avoided the potential danger of collision with the application of HDB controller and VS-DWA method. The route taken by the robot applying the HDB controller held a safe distance from the obstacles and simultaneously remained smooth and stable from the perspective of the reference frame. In addition, the Figure 8(b) reclaimed the maintenance of linear velocity during the bypass period, as is mentioned in the Section IV-B. Although a larger interval of angular velocity is observed in the Figure 8(c), in comparison with the result in the Figure 7(c), the peaks during the first period of steering is decreased, and a smooth passing manoeuvre is consequently guaranteed.

In the following experiment, we took a step further to enlarge excessively the hazard of danger driving behavior by canceling the turning of the path before passing an obstacle. In such circumstance the obstacle occupies and blocks completely the referential pas as presented in the Figure 9(a).

The results presented in the Figure 9(a) revealed again a smooth and stable trajectory from the perspective of the reference frame with the manoeuvre of obstacle avoidance. The maintenance of linear velocity during the bypass period is also observed in such circumstance as illustrated in the Figure 9(b). The major concern in this part of experiment lies in the result of the angular velocity showed in the Figure 9(c). In comparison with the results from the previous experiments in the Figure 7(c) and 8(c), the angular velocity by HDB controller in such circumstance revealed a smooth process of steering with minor values of the angular velocity and fewer peaks. Due to the curve characteristics of the referential path, we conclude that the quality of the referential path influences considerably the behavior of HDB controller, thus affecting consequently the outcome of the practical control of the robot.

V. CONCLUSION

In this paper we have presented an approach of human-vehicle interaction by modeling the behaviors and decisions of human drivers, which has established the foundation of a simplified control pattern of human drivers' behaviors. With the application of DWA providing the validation of the linear and angular velocities of the vehicle, potential dangerous behaviors of human drivers have been refrained and corrected. Safety of driving in such circumstance has been therefore guaranteed.

In comparison with the experimental results of VS controller, our control pattern with the focus on human-vehicle interaction have proved its superiority in maintaining the smoothness and stability of the obstacle passing manoeuvre. Control strategies determined by human drivers, or in our approach by HDB controller, with both absolute values and smoothness of the control variables being promising, have also been confirmed as practical and applicable on actual intelligent vehicles. The realisation of the experimentations is being executed currently with our vehicle IRIS in the project VERVE 1 .

Our approach has yet called for quite a few further progresses. The most apparent shortcoming of our design is the indispensable predefinition of the referential path or trajectory. A real-time calculation to achieve the referential trajectory from the perspective of human drivers, and a reliable localisation method to guarantee the acquisition of the position of the vehicle, are consequently desired. The characteristics of the referential path has also revealed its significance to the performance of the HDB controller. These current deficiencies will point out the direction of our future research, particularly for our experimental vehicle (Fluence-ZE, a zero emission vehicle from Renault) in order to experimentally validate our HDB method.

Fig. 1 .

 1 Fig. 1. Cinematic model diagram for a front wheel car-like robot. In this model the vehicle reference frame R performs circular trajectories related to the instantaneous center of curvature (ICC). The pinhole camera frame is also represented in C.

Fig. 2 .

 2 Fig. 2. Image frame {I} with the road lane center projection P (in red) related to the boundaries δ 1 and δ 2 (in yellow), its tangent Γ (in dark blue) at the point D and the angle offset Θ of Γ to the axis -Y .

Fig. 4 .

 4 Fig. 4. Evasive trajectory for obstacle avoidance.

Fig. 5 .

 5 Fig. 5. Referential path revision using evasive trajectory.

  (a) Reference path (in red, hereinafter) and actual driving route by HDB controller (in blue, hereinafter).

  of ref. Coor. x of actual driving Coor. y of ref. Coor. y of actual driving (b) Contrast of coordinates X and Y of the two routes.

Fig. 6 .

 6 Fig. 6. Validation of HDB controller design.

  HDB control driving route (in blue, hereinafter) and VS control driving route (in green, hereinafter), both in portion.

  Comparison of linear velocities.

Fig. 7 .

 7 Fig. 7. Comparison of performance in obstacle avoidance.

  Referential path with danger behaviors (in red) and corrected route by HDB controller (in blue), both in portion.

  Linear velocity calculated by HDB controller.

  /s) (c) Angular velocity calculated by HDB controller.

Fig. 8 .

 8 Fig. 8. Result of danger behaviors correction performed by HDB controller.

  Linear velocity calculated by HDB controller.

  /s) (c) Angular velocity calculated by HDB controller.

Fig. 9 .

 9 Fig. 9. Result of danger behaviors correction performed by HDB controller.

TABLE I .

 I MAX ERRORS OF THE DRIVING ROUTE.

TABLE II

 II

	.	COMPARISON OF PERFORMANCE IN OBSTACLE
		AVOIDANCE.

The project VERVE stands for Novel Vehicle Dynamics Control Technique for Enhancing Active Safety and Range Extension of Intelligent ElectricVehicles.


Isabelle Fabre
email: isabelle.fabre@educagri.fr

Cécile Gardiès
email: cecile.gardies@educagri.fr

Expected usage and perceived usage, photography as a methodological tool: the case of a learning centre in France

Keywords:

Photography beyond simple proof, became full research material (Bateson & Mead, 1942). It remains less investigated as a methodology in information and Communication Science (SIC) and particularly for the study of library use. However, the photography is a method of gathering information on the lived space that involves elements that tend to complicate the analysis. Therefore we can ask if photography is a medium, in the sense of support, of scientific data collection (Tardy, 2007), if it allows us to account, to signify the semiotic meaning (Barthes, 1980), of the actors expression. Our paper proposes to think on this methodological tool for data collection. It is based on a study of the "learnings centers" in France. This study analyzes the use of these new models of libraries in connection with the enounciation proposed by theses devices as a "work of reconciliation and confrontation of saying pictures" (Bonaccorsi, 2013). A focus on the occupation of spaces and movement of professionals and users will realize the trace of uses and intentions. The collected data furnish "a space waiting for configuration of the pictures by researcher [...] ephemeral support work and always in change [...] that offer an instrument for reflexivity [...] by linking meaningful shapes to practice who gives them status and quality" (Bonaccorsi, 2013). Face to methodological difficulties in use observation, photography can indeed be a means of investigation that serves two objectives -one on the variety of tools for collecting traces and another on taking into account different representations. The sensitive approach to qualitative methods that we specify gradually, built the empirical receptivity of the researcher involved in the process of "significance" (Leleu -Merviel, 2008).

Introduction and key question

Beyond providing a simple visual record, photography has become research material in its own right. Yet, it remains little investigated as a methodology in the Information and Communication Sciences (ICS) particularly in the study of library usage. Indeed, the use of libraries or documentation centres is evolving in line with changes in the ease of access to information and the forms of mediation seeking to adapt to these changes in order to meet new needs. But, perhaps paradoxically, this adjustment to needs is not straightforward as it is not easy to record the changes in usage which are often merely representations or projections. However, although photography constitutes a method for collecting information on space as it is experienced, bringing complex elements into play, it may be questioned whether photography, a record of scientific data [START_REF] Tardy | La photographie, outil documentaire des musées aux paysages[END_REF], allows us to demonstrate, to signify in the semeiological sense [START_REF] Barthes | La chambre claire[END_REF], the expression of the actors. The changes occurring in libraries and documentation centres are beginning to be implemented along the lines of the « learning centre » concept [START_REF] Jouguelet | Les Learning centres : un modèle international de bibliothèque intégrée à l'enseignement et à la recherche[END_REF][START_REF] Maury | Espaces documentaires, espaces de savoir, espaces d'expérience : vers une (re)définition du modèle des CDI ?[END_REF]. This puts the focus on learning thereby seeking to realign library services, traditionally based on accessing information, towards offering learning support through a critical approach to knowledge reception and acquisition. Whereas these developments in library usage appear to be confirmed by different studies, there is still a lot to be done to clarify the way in which users in schools and universities occupy these spaces. No longer solely dedicated to storing, in particular, scientific and technical information, libraries have become learning and living environments in which information, at least in a physical or paper format, does not necessarily take centre stage. Our paper proposes a reflection on this methodological data collection tool based on an exploratory study of "learning centres" in France. Our aim is to analyse the usage of these new library models in connection with what these systems enunciate, by working on "relating and confronting images" [START_REF] Bonaccorsi | Pratiquer les images en Sciences de l'information et de la communication : semiose, eikones, montage[END_REF]. By focusing on the occupation of the spaces and how the users and staff circulate within them, it will be possible to chart their usage and intentions. The data collected in this way constitutes "a space waiting for the researcher to configure it through images […] an ephemeral support to work with, constantly evolving […] which provides a tool for reflexivity […] relating signifying forms to practice which gives them status and quality" [START_REF] Bonaccorsi | Pratiquer les images en Sciences de l'information et de la communication : semiose, eikones, montage[END_REF]. Faced with the methodological difficulties of observing usage, photography may indeed constitute a means of investigation that serves two purposes -the purpose of varying the tools used for collecting evidence and that of considering representations in a different way. The sensory approach to the qualitative methods that we gradually specify, builds the empiric receptivity of the researcher who participates in the process of "signification" [START_REF] Leleu-Merviel | Quelques révisions du concept d'information In : Problématiques émergentes dans les sciences de l'information[END_REF].

How can photography contribute to gathering data on the link between the expected and perceived usage of a particular learning centre organisation? What are the new uses anticipated by the professionals orienting this new organization? Which features are emphasized? What new relationships to information and to documents are emerging from these foreseen uses? We present, firstly, our theoretical approach concerning photography as a sensory approach to representations, secondly the use made of the spaces and finally the links between information and learning. Based on these theoretical choices, we present the methodology used to set up a system of data collection and subsequently present some of the results which we analyse and discuss in the third section.

Theoretical approach

1-1 The sensory approach and use of images

The sensory approach refers to the question of sense. "Sense" designates both the faculty to perceive the impressions made by objects and each receptor system that makes perception and sensation possible. It involves the relationship between the perceptible object, which evokes an alternative reality to itself (a sign), and what it refers to. According to The Historical Dictionary of the French Language, "sense" is derived from "sensible" which describes in particular that which can be perceived by the senses. The adjective acquired a passive value in the 17 th century when it meant "clear, obvious". Sensory realities in Aristotle's philosophy designate the qualities that can be or seem to be perceptible to one or more of the senses. In general usage sensitive and sensory may be synonymous. "Sensitivity" designates, in particular, the quality of being sensitive to something. In the 18 th century, the word designated the quality of feeling and conveying emotions, then later came to denote a character capable of producing a sensation. "Sensory" concerns sensation, the action of perceiving, of feeling, of understanding. Photography is not only a specific act between an observer and the object photographed, it is an intermediary record which can be used to elaborate scientific material. In this respect, it is similar to the interview technique which is a reasoned process leading to the construction of representations.

Photography is a tool, like any other, which portrays reality as it is captured by an observer. It cannot be reduced to a creative act or to a support more subjective than any other collection of data [START_REF] Tardy | Représentations documentaires de l'exposition[END_REF]. It allows us to record what is real and can supplement a data collection method such as the interview. "This method provides a way in which the interview can move from the concrete (as represented by the literal objects in the image) to the socially abstract (what the objects in the photograph mean to the individual being interviewed)" [START_REF] Briden | Photo Surveys: Eliciting More Than You Knew to Ask For[END_REF]. Photography can also be considered alongside drawings done pre or post interview. The shift to a graphic portrayal, understood as with photography as the sensory approach from the actors' point of view [START_REF] Fabre | Des représentations croisées pour l'émergence d'une médiation de l'espace documentaire[END_REF], gives the interviewees the opportunity to bring their representations to light in a different way. This includes capturing the complexity of a system through a collection of representations then using it to analyse the library spaces and the usage expected of them.

1-2 Space and how it is used

Space implies a passage between an exterior and an interior. We do not penetrate a heterotopia [START_REF] Foucault | Des espaces autres (conférence au Cercle d'études architecturales[END_REF] by chance. We enter it by way of a material or symbolic area which marks the space as being "different" in that it is separate from the common space. Within it, we gain access to a different area where we can experience something. It is in this other location offered by the library space, that the user will occupy this freedom zone. The user acts differently depending on how he experiences the space, between wanting to use it and constraint. The library space can also be considered as a potential space linking transitional objects. Between harmony and illusion, the library space, thought out and organized by the practitioner, sometimes goes beyond the simple mediation of documents because it presents itself as a "potential space, a place in which to experience something" [START_REF] Belin | Une sociologie des espaces potentiels : logique dispositive et expérience ordinaire[END_REF]. For this to happen, the conditions of autonomy have to have been conceived and organized beforehand. The "transitional space" [START_REF] Winnicott | Jeu et réalité : l'espace potentiel[END_REF] is an area which will play an essential role in the processes of representation and symbolization and which will allow an initial step towards independence. The transitional space makes it possible to symbolize the world by distancing oneself from it. It is a halfway zone where a cultural experience can occur. Thus, the library space, as we have defined it [START_REF] Fabre | Espace et dispositif d'organisation des savoirs : vers une approche sensible[END_REF], contains an element of symbolism which places it in the imagination of those who design it and also of those who "use" it. Considering library space in terms of knowledge mediation confers upon it a role of relay, of intermediary in the same way that considering it in terms of its uses relates it to a process of assimilation and learning. Professionals in the field of information develop the space based on how they predict or presume it will be used. In this sense we can say that it is a space determined by the intentions of its developer, intentions which will be confronted with several ways of doing and experiencing things. It therefore becomes a space determined by multiple attributions which will only be perceived fragmentarily in so far as the intended uses continue to have a strong influence on the designer's imagination. In other words, if the documentation centres designed by teacher librarians with the intention of making processed and organized information available, give the impression they are above all else places to access information which, in order to become places "of knowledge" must receive some support to work on assimilating the information, the way students use the library space can orient this vision by transforming the initial intention. Notwithstanding, the library space can only become a learning space if this transformation is based on a form of mediation which takes into account the actual uses of the space; only then will it be possible to go beyond these uses towards knowledge construction.

Information and learning

The definition of information given by at least some schools of thought in the information and communication sciences, positions it within a process of dissemination-construction of knowledge. In other words, we could say that this process is akin to a process of transmissionacquisition i.e. learning. The significant proportion of information made available inside and outside the school sphere but that escapes traditional mediation by the teacher, has made it crucial for students to acquire information literacy skills. Indeed, this involves moving from the phase of accessing information to a phase which enables the student to locate, sort, and use effectively the information he needs to learn and therefore build new knowledge. In order to achieve this, there has been a transition from a situation where it was primarily the teacher who mediated the knowledge in the classroom to a situation in which teacher librarians also have this role. This specific mediation, qualified as documentary mediation, has materialised, on the one hand, as an established system (the CDI) which has organized knowledge and made it available in the form of processed and disseminated information and, and on the other hand, in the form of information education or guidance on how to handle information.

In other words, the general question of learning has never been absent either from the design of documentation centres or from the professional practices of teacher librarians; on the contrary, it has always been central to work on knowledge mediation which requires communicated and communicable knowledge [START_REF] Meyriat | De la science de l'information aux métiers de l'information[END_REF]. That is to say, knowledge mediation includes working with, on and about information. We are moving, therefore, towards a form of mediation that could be described as a collective form of knowledge mediation. This form of mediation is centered on the question of learning with, on and about information in systems whose denomination has signified, until now, work on information-documentation but that now proposes to include the question of learning more explicitly. This semantic shift could be accepted if, as we see it, learning clearly refers to the transition from an organisation of knowledge to knowledge communicated via information, towards suitable information for constructing new knowledge. Do the current learning centres reflect this collective mediation?

Methodological choices and data collection 2-1 Description of the context

This study concerns a secondary school of 300 students and 30 teachers partially assigned to the school. There are 3 first form classes, 3 second form classes, 3 third form classes and 4 fourth form classes. The population has decreased drastically in the surrounding geographical area. Formerly a town centre school, it now has to cater to the needs of students with serious learning difficulties who come from a wide variety of social backgrounds. The teachers have had to change the way they work: to function more as a team to cope with difficult classes, to adapt their teaching methods, to consider how to provide a different kind of support for students. The digital work environment facilitates learning partly by providing the possibility of putting homework exercises on-line, but also by making it possible for students, who have no Internet connection at home, to benefit from supervision and support when they come to work in the CDI. Following on from this, the « learning centre » spirit has imposed itself almost surreptitiously upon this specific teaching team. Its materialisation was enhanced by the juxtaposition of several rooms: the chief educational adviser's office which is adjacent to the school administration office, which leads into the CDI, which opens into both the supervised study area and a study room. It became known as a "Learning centre" after a school inspector's visit. The inspector made them realize that the development of these spaces and the student guidance methods used within them corresponded to the concept of "Learning centre"; a concept which is defined by the educational support and supervision available to students outside the classroom.

2-2 The method chosen

Our protocol is based on a mixed method combining observation on-site by the researcher and four interviews with the staff concerned with and involved in the « learning-centre » activities (a teacher librarian, a principal educational adviser and two educational assistants). The observation took place over several days during which the researcher made notes (kept a logbook), took photographs, made recordings and collected graphic depictions. The questions in the interview guide focused on the background to the project, how the actors perceived the project, support for the project, their vision of team work etc. Their representations of the space and its uses were also captured as drawings and photographs portraying the way they viewed this space. We chose to complete the interviews using alternative ways of representing reality because, in other field work, we had already seen the relevance of using drawings and photographs to communicate about usage or about a particular practice. Below is the sketch drawn by the researcher during the on-site observation which we used as a standard for analysing the drawings of the different actors.

Standard drawing 3 Results and analysis

The outcome of the interviews shows the need to qualify the formalization of the "Learning centre" by specifying the context of the project. Thus, the actors describe it as a humble approach to the reflection on a "learning centre" (LC) which resulted from the combination of several factors: -a profound change in the student population transforming the elitist "town centre" school into a school catering to an increasingly disadvantaged and vulnerable population; -an outdated documentation and information centre (CDI) in 2005 when the teacher librarian arrived; -a pre-existing layout making it easier to connect the different rooms. They are all on the same floor, there are no corridors, or schoolyard to cross, just a separating door which made it easier for the students to circulate.

-a desire to work together shared by the teacher librarian and the chief educational adviser For the principal educational adviser and the teacher librarian, the key words to describe the project are accommodating students, using the space as a real study area for the students, supervising and offering support to students working individually. For one of them, the specificity of the CDI is that "the different people and work spaces are close together" and for the other "the proximity of the different work spaces" and "the good atmosphere within the team". Beyond this initial approach to the LC and its uses, we go on to present the results and our analysis of them focusing on two main aspects; on one hand the relationship between space and the way the staff organise their work and, on the other hand, space in relation to resource materials.

Space and the way the staff organise their work

In order to bring out the salient points, the results are presented thematically and as a collection of verbatim accounts taken from the interviews, drawings and photographs. To distinguish between the different material, we indicate AE1 and AE2 when referring to the accounts given by educational assistants we interviewed, D for the teacher librarian and CPE for the principal educational adviser.

3-11 Physical and symbolic boundaries

The first striking feature seems to us to be the delimitation of the spaces and what they symbolise. The project materialised from a rethinking of the enclosed space of the CDI together with the other adjacent enclosed spaces which were trigger components of the new project. This is how the educational assistants describe the boundaries between the spaces: AE1 : « when the teacher librarian is with a group of students, she takes the first formers for documentation classes, we are in our supervised study period so we close the door and are with our students in the study room, keeping them as quiet as possible and helping them if necessary. So that means they don't have access to the CDI". AE2 : « the door between the school administration office and the CDI is closed when we are discussing things that the students mustn't hear, we shut the door and open it again automatically afterwards". AE2 : « if my colleague is supervising the study period, with a large group of students, if we are in the school administration office and my colleague is having problems handling seventy students or the students are being a real pain, the fact that all these doors are open means we can get up and help her out for ten minutes". AE1 : « thanks to this we can hear and see what's going on… » AE2 : « all working together… » In the photograph, one of the assistants has chosen to portray the space by way of the partitions and doors that divide it up. we have a different space to put students where we can split up the groups, integrate a class which, like this morning, doesn't have lessons and well, without having to put them in the big supervised study room where we handle the day to day running of things. So, there, the study room, there it is and here's the school admin office and my office, that's the CPE's office, and the school admin office and actually it's that, it's the, the fact that there are doors but that they are never closed. Whereas when I started working here they were shut […] that's it. So that's really, with the exit here to the schoolyard. […] this set of doors has really been a fundamental element.

It is surprising to note the perpetual oscillation, in the verbatim accounts, between, on the one hand the desire for a global space without boundaries and on the other the chronic allusion to the different areas using the name of each subspace. This tends to divide rather than unify the space; just as if each actor were subconsciously seeking to conserve the specifities linked to his role within this shared space. For example, the denomination "Room 28" thus, remains, in some respect, both inside and outside the LC project. We find here the heterotopia developed by Foucault which locates spatial boundaries inside a collective imagination.

3-12 Circulation

The second striking feature in the results concerns the circulation of students (especially between the areas called the "documentation centre", the "supervised study room", and the "school administration office") during a supervised study activity, which is generally considered to be difficult to manage in schools. We can see here that this problem is tackled in such a way that it becomes a crucial factor for developing the spaces in relation to student support. AE1 : « As soon as the students arrive for supervised study we tell them the CDI is closed for the hour. So, they know that they will have to work with our support as they won't have access to the books or the computers in the CDI". AE2 : « There is another thing we haven't mentioned, that is, thanks to this room (room 28), with the sliding door, if we stand up between the two spaces (study area and room 28), we can handle more students: once because a teacher was absent, the supervised study room was full, we sent some students to the CDI and we put a whole class in room 28, next door".

D's photo Room 28, adaptable as required

The photo taken by the teacher librarian shows how the modularity has allowed them to open up the space to accommodate the activity. AE1 : « the three doors were open and there were students everywhere. The CPE, our immediate superior, was close by. If we find ourselves in a particularly delicate situation with a student, she'll help us out with the punishments or just with the discussion if we are having a hard time. Managing the flow of students within the different areas relates here to the notion of transitional space but also to potential space. Indeed, the actors seek access to a new potential space by denying the boundaries and creating signifying routes to it.

3-13 Space utilisation

Student utilisation of the space and the uses anticipated by the staff, seem, indeed, to be strongly linked here to the question of learning even though we can observe that what is targeted is more a form of peer-to-peer collaborative learning. AE1 : « Very often we are both supervising study periods » AE2 «we often go into the CDI, we do the rounds. Sometimes we leave them to get on with it and we do our best to answer their questions.

AE1's photo

In the photo, her colleague is helping a group of students with their homework.

Nevertheless the photo chosen by AE1 shows the adult is present in a supporting role which contributes to the goal of learning in this space. The educational assistants recognize that their role is to supervise and offer support to the students. AE2 : « it can happen that we are not really free sometimes. My colleague will try to do what she can or she'll ask a good student if he thinks he can explain the notion to his classmate. In fact, sometimes we even prefer it if they explain things to each other […] they go over it together in their own words. This introduces them to peer support, rather than always asking an adult, the information is on hand just next to them, whereas we would have to look through the whole lesson to be able to help". From the staff's point of view, if the LC provides learning support, it seems also to be developing towards a system of peer-to-peer learning as we can see in the following extracts. AE1 : We use room 28 whenever we can when there are a lot of students in supervised study because during these periods, the tables are organized so that they can work together, and we can see them. However, this means we lose a fair bit of space and capacity so this room is really useful".

D's photo Some of the students in the same class have chosen to leave the supervised study area and work in a small group in the CDI.

The photo taken by the teacher librarian shows how she really wants to develop the CDI into a work space.

AE2 : « some students really like coming to work in the CDI. They bring their maths, they do their homework". The teacher librarian's choice of photo does not highlight the use of the resources or documentation in the CDI but seems to relate to the students' autonomy both in terms of how they choose to use this space and the work they do in it.

3-2 Space and documentation

3-21 Spaces and sub-spaces

The function of each subspace, particularly those which are dedicated to storing documents, is not referred to at all in the drawings with the exception of the "reading" area shown by AE1. During the interviews, AE2 points out that : "We have the key to get into the storeroom, if we need three history or four science textbooks we can go and get them from the storeroom if they are available".

The teacher librarian's drawing.

Paradoxically, it's the teacher librarian who has drawn the most minimalist sketch of the different spaces which make up, what she continues to call, the "CDI », but next to it, she does choose to list some key words which characterise the system. The drawing shows a juxtaposition of the subspaces but does not really indicate how to circulate between them. This said, the fact that there is a circle encompassing the subspaces, reinforces the idea of a desire for globality which is not always satisfied when we refer to the subspaces in detail.

In the CPE's account, we note that she specifies the spaces and their uses in terms of the different roles played by the teacher librarian: "It was my job to say to the educational assistants: remember that Katia is also a teacher so when she tells you that the CDI is closed, well she needs to focus on her class, on the lesson, that's the way it is. I had to get them to take that on board. She's too busy to worry about book loans, so, we can do it, discreetly, we can go in, we can provide this service but that's where we must be wary because it's at these times she's at her most vulnerable, so to speak, because we might be interrupting her in the middle of her lesson plan and put her in a difficult position. She's already managed to explain that and it's up to us to be wary of this. I'm not saying that there won't be times when we slip up, as educational supervisors we have our flaws, OK, but straight away one of us should speak up and say be careful. And it was the same thing for the teachers". The permeability of the subspaces is limited according to the tasks the staff carry out in them and not according to student usage. In this way the teaching function is partially sanctified to the detriment of a desired utilisation.

3-22 Use of documents

The development of this school into an LC incorporating the CDI, seems to be leading towards a different relationship to the use of documentary resources within the subspaces, which is also influencing the mediations at work.

AE2 : « it's great that we can help them consider other options when they are looking for information. We tell them, for example, no you won't find exactly what you're looking for on Internet, look in the library's journals section, you'll find the answer in one of the magazines there". AE1 : « we ask them if they have work to do on documentation so we can then send them to the CDI, they have access to the computers, to the books and afterwards we are there to help them with their information search, just like the teacher librarian ». What AE1says here is reflected in her drawings and photographs, in which we find the most significant presence of material resources. They are present both in the subspaces, like the reading area, and in the storeroom where the textbooks and archives are kept. They also appear in the foreground of the photo of the lending service which, taken from this angle, puts the viewer in the teacher librarian's "entrenched" position behind the service desk, discussing a certain document with a student.

AE1's drawing AE1's photo In the photo, documents are present on the shelves. In the background we can see a row of computers with two students working on them. So, although the material resources are only vaguely referred to in one part of the verbatim accounts and only slightly prominent in the pictures, they do, reappear in the description of how the spaces are used.

3-23 Presence/absence of the documents

Certain elements shown in the photos and drawings are clues to the uses perceived by the staff like the presence or absence of documents, computers, the students' personal resources and the documents used by staff.

Here is a photo of one of the educational assistants' work stations. We can see her coat, the attendance register, the computer connected to the school's network. On the right, printed charts are posted on a cork notice board. D : « There is textbook content but it's mainly in maths they work on that. Er ..they give them exercises to do on-line and they get the correction, they know which student is connected, at what time and why. That's how we discovered that some students work during the night. Yes…It sets you thinking when you find out that the students who zone out in class were connected at three in the morning. We had a case recently. Students who don't stop yawning in class but when the maths teacher sees they do their exercises between two and three o'clock in the morning (silence) well you can address the problem face on (laughter). That's how it goes…"

The uses perceived here are related to the learning process-learning support. The absence of documents from the CDI, as seen in the photos and confirmed in the accounts shows that the LC project is adapting to this evolution in usage which highlights the fact that information access is no longer the primary objective of those who use these spaces.

The use of photography and drawing helps qualify the accounts formatted by the formalization of the LC project which the different actors have assimilated as a group, and which ressembles the official line. We can work on the assumption that photography could help to bring different representations to the surface and allow the researcher to adopt a sensory approach to both the expected and perceived usage of space, however, one of the flaws in this study is that the interpretation of the pictures is left up to the researcher; the actors were not given the chance to complete what they said initially with a description of the pictures and drawings they did. We do, nonetheless, believe that pooling several subjectivites, those of the researcher and those of the actors, could provide new opportunities yet to be confirmed.

Conclusion

Given the difficulty involved in grasping new usages of school libraries, we have suggested using photography as a sensory methodology for perceiving the uses of the redesigned library space. This approach has led us to specify, from a theoretical point of view, how the angle or focus of the picture could offer a sensory means to approaching the developments in progress in the field of documentation. This then led us to explain what these uses of the library space imply and also the relationship between information and learning.

Based on these elements, we have tried to address expected and perceived usage of a "Learning centre" in France using an approach involving photography, drawing and recorded interviews with staff members. The results of this study show that despite a desire for unification, the boundaries between the subspaces persist whereas circulation and usage are becoming more fluid. This tends to confirm the potential of an existing yet still transitional space. Furthermore, the dichotomy between the space as an area for living, working and ultimately learning, seems to take precedence over using the documents related to a library space. This reflects the project signified by a change in denomination shifting from "Information and Documentation Centre" to "Learning Centre". Photography as a methodological tool complementary to interviews and drawings has proved its relevance here but would benefit from being associated with the words and images of the students, a perspective which will be further developed in forthcoming research on Learning centres.

  AE2's photo View taken from the school administration office, of the open door to the supervised study room through the CDI. AE2's drawing In the drawing the educational assistant has clearly indicated the doors between the different spaces with a bold line The drawings show both the boundaries and how to get from one space to another. AE2 : "by closing the door we also get a break (sigh) because some weeks are long and occasionally our patience is sorely tested" The principal educational adviser's drawing seems to go along with this although compared to the very angular depiction shown in the first drawing, she has added a slightly different perspective because the circles soften the boundaries. CPE's drawing CPE : « To draw what the LC represents for me …I, I have to split the different spaces up but which in the end …so here is the CDI […] room 28 which I use a lot err…here's room 28 which I often use cos thanks to this um, sort of multi purpose room,

  AE2's photo the educational assistant's desk when she is supervising in the study room.D's photo taken from the school administration office.In this photo, taken by the teacher librarian, we can see the computer workstation connected to a printer. On the right we can just make out the photocopier. All this material is reserved for staff use only. Only those students who ask for or who really need one can get a photocopy which will be made by a member of staff. Has the teacher librarian taken this photograph to illustrate this boundary? It coincides with the following element revealed during the interview: D : « reflection on the LC means rethinking the space and obviously considering new tools and devices. Those of us working in documentation are currently asking ourselves : should we equip the CDI with tablets or e-readers? That's the question, that's what we're debating. At the moment we can't agree because these electronic devices are constantly evolving. Should we consider using tools which will soon become obsolete? We also have the problem of Wi-Fi connection and its authorisation in schools. So, now either we dig in our heels and resist or we start seriously thinking about the issue, we're not clear on this". D : " We already have some on-line lessons. But even on the subject of digital textbooks, there are still some CDIs where it is forbidden to come and work on maths. That should perhaps change. Why ban maths from the CDI? On what grounds? » D : We open up the digital world to the students but some of them are in difficulty, not all families are equipped so we have to adapt to this. This means we have to stay open longer and find solutions; that has also made us think about things. To start with we said OK but how do we make it work? We put the textbooks on-line, OK….then what? So that's helped, it's helped to encourage the use of new computers in the CDI and during supervised study. Technology mustn't become an obstacle for students".

Curriculum Vitae

Isabelle Fabre


Eric Balandraud
email: eric.balandraud@imj-prg.fr

AND Maurice Queyranne
email: maurice.queyranne@sauder.ubc.ca

Fabio Tardella
email: fabio.tardella@uniroma1.it

LARGEST MINIMAL INVERSION-COMPLETE AND PAIR-COMPLETE SETS OF PERMUTATIONS

whether they are published or not. The documents may come

We consider the following extremal problems in the theory of permutations. Given integer n ≥ 2, let S n denote the symmetric group of all permutations of [n] := {1, 2, . . . , n} (so |S n | = n!), and A n = {(i, j) : i, j ∈ [n], i = j} the set of all (ordered) pairs from [n] (so |A n | = n(n -1)). A permutation π = (π(1), . . . , π(n)) covers the pair (π(k), π(l)) ∈ A n iff k < l. An inversion (see, e.g., [START_REF] Bóna | Combinatorics of permutations[END_REF][START_REF] Margolius | Permutations with inversions[END_REF][START_REF] Markowsky | Permutation lattices revisited[END_REF]) is a pair (j, i) ∈ A n with j > i. Let I n ⊂ A n denote the set of all inversions. A set Q ⊆ S n of permutations is inversion-complete (resp., pair-complete) if every inversion in I n (resp., pair in A n ) is covered by at least one permutation in Q. An inversioncomplete set Q is minimally inversion-complete if no proper subset of Q is inversioncomplete; and similarly for pair-completeness. For example, the set Q ′ = {rev n }, where (using compact notation for permutations) rev n = n(n -1) . . . 21 is the reverse permutation, is minimally inversion-complete, and has minimum cardinality for this property; whereas the set P ′ = {id n , rev n }, where id n = 12 . . . n is the identity permutation, is minimally pair-complete, and has minimum cardinality.

We determine the maximum cardinality γ I (n) of a minimal inversion-complete subset Q ⊆ S n , as well as the maximum cardinality γ P (n), of a minimal paircomplete subset P ⊆ S n . The latter problem arose in the determination of the Carathéodory numbers for the integral L ♮ convexity structures on the (n -1)dimensional real and integer vector spaces R n-1 and Z n-1 , see [START_REF] Queyranne | Carathéodory, Helly and Radon Numbers for Sublattice Convexities in Euclidian, Integer and Boolean Spaces[END_REF]. 1 It was posed by the second author as "An Integer Programming Formulation Challenge" at the Integer Programming Workshop, Valparaiso, Chile, March 11-14, 2012.

Stimulated by personal communication of an early version of our results, Malvenuto et al. [START_REF] Malvenuto | The maximum cardinality of minimal inversion complete sets in finite reflection groups[END_REF] determine the exact value of, or bounds on, the maximum cardinality of minimal inversion-complete sets in more general classes of finite reflection groups.

Perhaps unexpectedly (since there are twice as many pairs to cover as inversions), the maximum cardinalities γ I (n) and γ P (n) considered herein are equal for all n ≥ 4 (and they only differ by one unit, viz., γ P (n) = γ I (n) + 1, for n = 2 and 3). Furthermore, for all n ≥ 4 the family Q * n of all maximum-cardinality minimal inversion-complete subsets of S n is strictly contained in the family P * n of all maximum-cardinality minimal pair-complete subsets. All our proofs are constructive and produce corresponding optimal sets of permutations.

In Section 1 we prove: Theorem 1. (i) For every n ≥ 2, the maximum cardinality of a minimal inversioncomplete subset of S n is γ I (n) = ⌊n 2 /4⌋. (ii) For every even n ≥ 4, the family Q * n of all maximum-cardinality minimal inversion-complete subsets of S n is the family of all transversals of a family of n 2 /4 pairwise disjoint subsets of S n , each of cardinality n 2 -1 ! 2 , and

thus |Q * n | = n 2 -1 ! n 2 /2 .
(iii) For every odd n ≥ 5, Q * n is the disjoint union of the families of all transversals of two families, each one of ⌊n 2 /4⌋ pairwise disjoint subsets of

S n of cardinality ⌊ n 2 ⌋ -1 ! ⌊ n 2 ⌋!, and thus |Q * n | = 2 ⌊ n 2 ⌋ -1 ! ⌊ n 2 ⌋! ⌊n 2 /4⌋ .
To prove Theorem 1, we first establish the upper bound γ I (n) ≤ ⌊n 2 /4⌋ by applying Mantel's Theorem (which states, [START_REF] Mantel | Vraagstuk XXVIII[END_REF][START_REF] Turán | Egy gráfelmèleti szélsöértekfeladatrol[END_REF], that the maximum number of edges in an nvertex triangle-free graph is ⌊n 2 /4⌋) to certain "critical selection graphs" associated with the minimal inversion-complete subsets of S n . We then show that this upper bound is attained by the families of transversals described in parts (ii)-(iii). We complete the proof by showing that, for n ≥ 4, every Q ∈ Q * n must be such a transversal. Note that these results imply the asymptotic growth rate |Q * n | = 2 θ(n 3 log n) as n grows.

In Section 2 we prove: Theorem 2. (i) For every integer n ≥ 2, the maximum cardinality of a minimal pair-complete subset of S n is γ P (n) = max n, ⌊n 2 /4⌋ . (ii) For all n ≥ 5 the set P * n of maximum-cardinality minimal pair-complete subset of S n is equal to the set τ • Q * n resulting from applying every possible permutation τ ∈ S n of the index set [n] to each Q ∈ Q * n . (iii) For all n ≥ 5 there is a one-to-one correspondence between P * n and the Cartesian product [n] ⌊n/2⌋ × Q * n , where [n] ⌊n/2⌋ is the family of all subsets S ⊂ [n] with cardinality |S| = ⌊n/2⌋.

The intuition for the formula γ P (n) = max n, ⌊n 2 /4⌋ in part (i) is that it suffices to consider two classes of minimal pair-complete subsets: (1) the subsets P (each of cardinality n) formed by the n circular shifts of any given permutation π ∈ S n , i.e., | for all n ≥ 5, their asymptotic growth rate (as n grows) are similar, differing only in lower order terms in the exponent θ(n 3 log n).

P = {π, π • σ, π • σ 2 , . . . , π • σ n-1 },

minimal Inversion-Complete Sets of Permutations

In this Section we prove Theorem 1 and present a characterization of the family Q * n of all maximum-cardinality minimal inversion-complete subsets of S n . For n = 2, there is a single inversion (2, 1), which is covered by the reverse permutation 21, so part (i) of Theorem 1 trivially holds and Q * 2 = {21}. Hence assume n ≥ 3 in the rest of this Section.

Consider any minimal inversion-complete subset Q of S n . Since Q is minimally inversion-complete, for every permutation π ∈ Q there exists an inversion (j, i) ∈ I n , called a critical inversion, which is covered by π and by no permutation in Q \ {π} (for otherwise Q \ {π} would also be inversion-complete, and thus Q would not be minimally inversion-complete). For every permutation π ∈ Q, select one critical inversion that it covers (arbitrarily chosen if π covers more than one critical inversion). Let q j,i denote the unique permutation in Q that covers the selected critical inversion (j, i). Consider a corresponding critical selection graph

G Q = ([n], E Q )
, where E Q is the set of these |Q| selected critical inversions (one for each permutation in Q), considered as undirected edges. Thus

|E Q | = |Q|.
Recall that a graph G is triangle-free if there are no three distinct vertices i, j and k such that all three edges {i, j}, {i, k} and {j, k} are in G.

Lemma 1. If subset Q ⊆ S n is minimally inversion-complete, then every corre- sponding critical selection graph G Q is triangle-free. Proof. Assume Q ⊆ S n is minimally inversion-complete, and let G Q = ([n], E Q ) be a corresponding critical selection graph.
We need to show that, if E Q contains two adjacent edges {i, j} and {j, k}, then it cannot contain edge {i, k}. Thus assume that {i, j} and {j, k} ∈ E Q and, without loss of generality, that i < k. We want to show that (k, i) cannot be a selected critical inversion. We consider the possible relative positions of index j relative to i and k:

• If j < i < k, i.e., both (i, j) and (k, j) are selected critical inversions, then q k,j cannot cover (i, j) and therefore we must have k before j before i in q k,j (that is, these three indices must be in positions

π -1 (i) < π -1 (j) < π -1 (k) in π = q k,j
). This implies that (k, i) cannot be a selected critical inversion. • If i < k < j, i.e., both (j, i) and (j, k) are selected critical inversions, then this is dual (in the order-theoretic sense) to the previous case: q j,i cannot cover (j, k) and therefore we must have k before j before i in q j,i , implying that (k, i) cannot be a selected critical inversion. • Else i < j < k, i.e., both (j, i) and (k, j) are selected critical inversions.

In every permutation π ∈ Q \ {q j,i , q k,j } we must have i before j before k But then (k, i) cannot be a selected critical inversion, since it can only be covered in Q by q j,i or q k,j , for each of which another critical inversion has been selected. Therefore, (k, i) cannot be a selected critical inversion. This implies that no three indices i, j and k can define a triangle in G Q .

Since

|Q| = |E Q |, Mantel's Theorem implies
Corollary 2. For every n ≥ 2, the maximum cardinality γ I (n) of a minimal inversion-complete subset of S n satisfies γ I (n) ≤ ⌊n 2 /4⌋.

We prove constructively that the upper bound in Corollary 2 is attained, i.e., that part (i) of Theorem 1 holds. For n = 3, we have 3 triangle-free graphs on vertex set {1, 2, 3}, each consisting of exactly two of the three possible edges. Consider the edge set

E ′ = {1, 2} , {1, 3} : if it is the edge set of a critical selection graph G Q ′ , then we must have q ′ 2,1 = 213 ∈ Q ′ (for otherwise, q ′ 2,1
would also cover the inversion (3, 1), contradicting that (3, 1) is also selected), and similarly q ′ 3,1 = 312 ∈ Q ′ . Thus Q ′ must be the set {213, 312}, which is indeed inversion-complete, and thus a largest minimal inversion-complete subset of S 3 . This implies that γ I (n) = 3 = ⌊ n 2 4 ⌋ holds for n = 3. Similarly, the edge sets E ′′ = {1, 2} , {2, 3} and E ′′′ = {1, 3} , {2, 3} define the other two maximum-cardinality minimal inversion-complete subsets Q ′′ = {213, 123} and

Q ′′′ = {231, 321} of S 3 . Thus Q * 3 = {Q ′ , Q ′′ , Q ′′′ } and |Q * 3 | = 3.
Thus assume n ≥ 4 in the rest of this Section. We now introduce certain subsets of S n , which we will use to show that the upper bound in Corollary 2 is attained, and to construct the whole set Q * . For every triple (i, c, j) of integers such that 1 ≤ i ≤ c < j ≤ n, let F i,c,j denote the set of all permutations π ∈ S n such that:

• π(h) ≤ c for all h < c;

• π(c) = j;

• π(c + 1) = i; and

• π(k) ≥ c + 1 for all k > c + 1. If c > 1 the first two conditions imply that π(1), . . . , π(c-1) is any permutation of [c]\{i}; and if c+1 < n the last two conditions imply that π(c+2), . . . , π(n) is any permutation of {c+1, . . . , n}\{j}. Thus the cardinality of F i,c,j is (c-1)! (n-c-1)!. Note also that, for every π ∈ F i,c,j , (k, h) = (j, i) is the unique inversion (k, h) with h ≤ c < k that is covered by π. Thus for every fixed c the sets

F i,c,j (1 ≤ i ≤ c < j ≤ n) are pairwise disjoint (F i,c,j ∩ F i ′ ,c,j ′ = ∅ whenever (i, j) = (i ′ , j ′ )).
Recall that, given a collection F of sets, a transversal is a set containing exactly one element from each member of F . Lemma 3. For every integers 1 ≤ c < n, every transversal T of the family

F c = {F i,c,j : 1 ≤ i ≤ c < j ≤ n} is minimally inversion-complete.
Proof. Given such a transversal T , let t i,j denote the permutation in T ∩ F i,c,j . For every inversion (j, i) ∈ F n , we consider the relative positions of i and j with respect to c:

• If i ≤ c < j, then t i,j is the unique permutation in T that covers the inversion (j, i). • If i < j ≤ c, then the inversion (j, i) is covered by every t i,j ′ ∈ T with j ′ > c. • Else, c + 1 ≤ i < j, then the inversion (j, i) is covered by every t i ′ ,j ∈ T with i ′ ≤ c. Therefore, T is inversion-complete and for every i ≤ c < j the inversion (j, i), covered by t i,j , is critical. This implies that T is minimally inversion-complete.

For a fixed c such that 1 ≤ c < n, there are c(n-c) subsets F i,c,j (with i ≤ c < j) (and these subsets are nonempty and pairwise disjoint). Hence the cardinality of every transversal

T satisfies |T | = |F c | = c(n -c) ≤ ⌊ n 2 4 ⌋, with equality iff c ∈ ⌊ n 2 ⌋, ⌈ n 2 ⌉ .
Combining with Lemma 2, we obtain: Corollary 4. For every n ≥ 4, γ I (n) = ⌊n 2 /4⌋ and, for every c ∈ ⌊ n 2 ⌋, ⌈ n 2 ⌉ , every transversal T of the family

F c = {F i,c,j : 1 ≤ i ≤ c < j ≤ n} is a maximum- cardinality minimal inversion-complete subset of S n .
Part (i) of Theorem 1 follows. To prove parts (ii) and (iii), we invoke the "strong form" of Mantel's Theorem [START_REF] Mantel | Vraagstuk XXVIII[END_REF][START_REF] Turán | Egy gráfelmèleti szélsöértekfeladatrol[END_REF]: an n-vertex triangle-free graph has the maximum number ⌊n 2 /4⌋ of edges iff it is a balanced bipartite graph, i.e., with ⌊ n 2 ⌋ vertices on one side and ⌈ n 2 ⌉ on the other. Lemma 5. For n ≥ 4, a subset of S n is a maximum-cardinality minimal inversioncomplete subset iff it is a transversal of the family F c for some c ∈ ⌊ n 2 ⌋, ⌈ n 2 ⌉ . Proof. Sufficiency was established by Lemma 3. To prove necessity, let n ≥ 4 and consider any Q ∈ Q * n and a corresponding critical selection graph G Q . By Lemma 1, Corollary 4, and the strong form of Mantel's Theorem, G Q is a balanced complete bipartite graph. We first claim that the side W of G Q that contains index 1 must be W = [c] with c ∈ ⌊ n 2 ⌋, ⌈ n 2 ⌉ . For this, consider (since n ≥ 4) any three indices i > 1 in W and j < k on the other side. Thus (j, 1) and (k, 1) are critical inversions. Furthermore, the edges {i, j} and {i, k} in G Q are also defined by critical inversions, which depend on the position of index i relative to j and k:

• If 1 < j < i < k, then (i, j) and (k, i) are critical inversions. Then every permutation π ∈ Q \ {q j,1 , q i,j , q k,i } has 1 before j before i before k, and thus does not cover the inversion (k, 1). Thus (k, 1) cannot be a critical inversion, a contradiction. • If 1 < j < k < i, then (i, j) and (i, k) are critical inversions. On one hand, every permutation π ∈ Q ′ = Q \ {q j,1 , q i,j } has 1 before j before i, and thus does not cover the inversion (i, 1). Similarly, every permutation π ∈ Q ′′ = Q\{q k,1 , q i,k } has 1 before k before i, and thus does not cover the inversion (i, 1) either. Therefore Q = Q ′ ∪ Q ′′ does not cover the inversion (i, 1), a contradiction. This implies that we must have 1 < i < j < k, i.e., that i < j for every i ∈ W and every j ∈ [n] \ W . This proves our claim that W = [c] for some c which, by the strong form of Mantel's Theorem, must be ⌊ n 2 ⌋ or ⌈ n 2 ⌉. As a consequence, Q = {q j,i : 1 ≤ i ≤ c < j ≤ n}. Every q j,i ∈ Q must have j before i, and also h before j for every h ∈ [c]\{i} (for otherwise q j,i would also cover the inversion (j, h), contradicting the fact that q j,h is the unique permutation in Q that covers (j, h)) and i before k for every k ∈ {c + 1, . . . , n} \ {j} (for otherwise q j,i would also cover the inversion (k, i)). Therefore q j,i ∈ F i,c,j , and thus Q is a transversal of F c . The proof is complete. Parts (ii) and (iii) of Theorem 1 now follow, noting that: (1) F c consists of c(nc) pairwise disjoint subsets F i,c,j ; (2) c ∈ ⌊ n 2 ⌋, ⌈ n 2 ⌉ ; and (3) for n odd, all subsets F i,⌊n/2⌋,j and F i ′ ,⌈n/2⌉,j ′ are pairwise disjoint (indeed, with n odd, every π ∈ F i,⌊n/2⌋,j has π(c + 1) ∈ [c] while every π ∈ F i ′ ,⌈n/2⌉,j ′ has π(c + 1)

∈ [n] \ [c]). Remark 1. Thus we have Q * 2 = 1, Q * 3 = 3, Q * 4 = 1, Q * 5 =
128 and, as noted in the Introduction, the asymptotic growth rate |Q * n | = 2 θ(n 3 log n) .

minimal Pair-Complete Sets of Permutations

In this Section we prove Theorem 2. To simplify the presentation, let µ(n) := max n, ⌊n 2 /4⌋ . For n = 2, the unique cover of the two pairs (1, 2) and (2, 1) is S 2 itself, hence γ P (2) = 2 = µ(2) and P * 2 = {S 2 }. Note that, as for inversions, given any minimal pair-complete subset P of S n , for every permutation π ∈ P there exists a critical pair (i, j) ∈ F n which is covered by π and by no other permutation in P . Observe however that, in contrast with inversion-completeness, the notion of pair-completeness does not assume any particular order of the indices. Thus, if P ⊆ S n is (minimally) pair-complete then for any permutation τ ∈ S n of the index set [n], the set τ • P = {τ • π : π ∈ P } is also (minimally) pair-complete. (Indeed, π covers (i, j) iff τ • π covers (τ (i), τ (j)).)

For n = 3 consider the set P 3 := {123, 231, 312}. It is easily verified that P 3 is pair-complete and the pairs (1, 3), (2, 1) and (3, 2) are critical pairs covered by the permutations 123, 231 and 312, respectively. Hence P 3 ∈ P * 3 and thus

γ P (3) ≥ |P 3 | = 3 = µ(3).
To verify the converse inequality, viz., γ P (3) ≤ µ(3), consider any P ∈ P * 3 : by the preceding observation, we may assume, w.l.o.g., that P contains the identity permutation π 1 = id 3 . This permutation π 1 covers all three pairs (i, j) with i < j. Then the permutation π 2 ∈ P that covers the pair (3, 1) must also (depending of the position of index 2) cover at least one of the pairs (2, 1) or [START_REF] Mantel | Vraagstuk XXVIII[END_REF][START_REF] Malvenuto | The maximum cardinality of minimal inversion complete sets in finite reflection groups[END_REF]. Hence there is at most one pair which is not covered by {π 1 , π 2 }, and thus γ P (3) = |P | ≤ 3 = µ(3), implying γ P (3) = µ(3). Therefore part (i) of Theorem 2 holds for n ∈ {2, 3}. Lemma 6. If n ≥ 4, for every permutation τ ∈ S n of the index set [n] and every maximum-cardinality minimal inversion-complete set Q ⊂ S n , the set τ • Q is minimally pair-complete.

Proof. By a preceding observation, it suffices to prove that, for n ≥ 4, every maximum-cardinality minimal inversion-complete set Q ∈ S n is minimally paircomplete. By Lemma 5, every such Q must be a transversal of F c for some c ∈ ⌊ n 2 ⌋, ⌈ n 2 ⌉ . Consider any pair (i, j) ∈ A n and, w.l.o.g., i < j: • If i ≤ c < j then q j,i ∈ F i,c,j ∩ Q is the unique permutation in Q that covers the inversion (j, i), and every other permutation in Q covers (i, j). • If i < j ≤ c then, for every k ∈ {c + 1, . . . , n}, q k,i covers (j, i) and q k,j covers (i, j). • Else, c < i < j and, dually, for every h ∈ [c], q i,h covers (i, j) and q j,h covers (j, i).

Therefore Q is pair-complete, and every pair (j, i) with i ≤ c < j is critical and covered by q j,i ∈ Q.

Since |Q| = ⌊ n 2 4 ⌋ = |{(j, i) : 1 ≤ i ≤ c < j ≤ n}|, Q is minimally pair-complete.
Corollary 7. For every n ≥ 4, the maximum cardinality γ P (n) of a minimal paircomplete subset of S n satisfies γ P (n) ≥ γ I (n) = ⌊n 2 /4⌋.

As we did for inversions, to every minimal pair-complete subset P of S n and selection of a critical pair covered by each permutation in P , we associate a corresponding critical selection graph G P = ([n], E P ) where E P is the set of |P | selected critical pairs (one for each permutation in P ), considered as undirected edges. Thus |E P | = |P |. Let p i,j denote the unique permutation in P that covers the selected critical pair (i, j). Lemma 8. If n ≥ 4 and P ⊆ S n is minimally pair-complete, then every corresponding critical selection graph G P is triangle-free.

Proof. Assume n ≥ 4 and P ⊆ S n is minimally pair-complete, and let G P = ([n], E P ) be a corresponding critical selection graph. By Corollary 7, |P | ≥ ⌊n 2 /4⌋ ≥ 4. We have to show that for any three indices i, j, k such that {i, j} and {j, k} ∈ E P , we must have {i, k} ∈ E P .

• First, consider the case where both pairs (i, j) and (j, k) are critical. In every permutation π ∈ P \ {p i,j , p j,k } we must thus have k before j before i.

Since k is before i in all these |P | -2 ≥ 2 permutations, (k, i) cannot be a critical pair. Furthermore (i, k) cannot be a selected critical pair, since it can only be covered by p i,j and p j,k , for each of which another critical pair has been selected. Therefore, as claimed, we cannot have {i, k} in E P .

l before k before i, and thus does not cover the pair (i, l). Thus (i, l) cannot be a critical inversion, a contradiction.

Thus we must have both (j, k) and (j, l) in A P . This implies that all pairs (j, k) ) For all n ≥ 5 there is a one-to-one correspondence between P * n and the Cartesian product [n] ⌊n/2⌋ × Q * n .

Proof. Assume n ≥ 5 and consider any P ∈ P * n . In the proof of Lemma 9 we showed that there exists a unique balanced ordered partition (W, W ) of [n] such that all critical pairs (j, k) of P have j ∈ W and k ∈ W . Let again c := |W | ∈ ⌊ n 2 ⌋, ⌈ n 2 ⌉ , but now select the (unique) "canonical" permutation τ W associated with this ordered partition, that monotonically maps [c] to W (i.e., such that 1 ≤ i < j ≤ c implies τ W (i) ∈ W and τ W (i) < τ W (j) ∈ W ) and monotonically maps [c] = {c + 1, . . . , n} to W (i.e., such that c + 1 ≤ k < l ≤ n implies τ W (k) ∈ W and τ W (k) < τ W (l) ∈ W ). Then, as also noted in the proof of Lemma 9, every critical pair in Q P := τ -1 W • P is an inversion, and thus Q P ∈ Q * n . Consider the mapping Φ : P * n → [n] ⌊n/2⌋ ×Q * n defined by Φ(P ) = Φ(P ) 1 , Φ(P ) 2 with Φ(P ) 1 = W if Q P is a transversal of F ⌊n/2⌋ (i.e., if |W | = ⌊n/2⌋, where {W, W } is the balanced ordered partition associated with P , as defined in the preceding paragraph), and Φ(P ) 1 = W otherwise (i.e., if n is odd and Q P is a transversal of F ⌈n/2⌉ , and thus |W | = ⌊n/2⌋); and with Φ(P ) 2 = Q P = τ -1 W • P . To complete the proof, it suffices to show that every pair (X, Q) ∈ [n] ⌊n/2⌋ × Q * n is the image Φ(P ) of exactly one P ∈ P * n . Thus consider any (X, Q) ∈ [n] ⌊n/2⌋ × Q * n . Recall that the balanced ordered partition associated with any transversal

Q of F c is ([c], [c]).
If Q is a transversal of F ⌊n/2⌋ then we use X to play the role of W , that is, we let P := τ X • Q, so P ∈ P * n and Φ(P ) 2 = τ -1 X • P = Q. The balanced ordered partition associated with P is (τ X • [c], τ X • [c]) = (X, X), and therefore Φ(P ) 1 = X. This implies that Φ(P ) = (X, Q), as desired. Furthermore, consider any P ′ ∈ P * n such that Φ(P ′ ) = (X, Q). Since Q P ′ = Φ(P ′ ) 2 = Q is a transversal of F ⌊n/2⌋ and Φ(P ′ ) 1 = X, the balanced ordered partition associated with P ′ is (W ′ , W ′ ) = (X, X). But then P ′ = τ W ′ • Q P ′ = τ X • Q = P . Therefore, for every (X, Q) ∈ [n] ⌊n/2⌋ × Q * n such that Q is a transversal of F ⌊n/2⌋ , there exists exactly one P ∈ P * n such that Φ(P ) = (X, Q). The proof for the remaining case, i.e., when n is odd and Q is a transversal of F ⌈n/2⌉ , is similar, by simply exchanging the roles of X and X. This shows that Φ is a one-to-one correspondence from P * n to [n] ⌊n/2⌋ × Q * n .

The proof of Theorem 2 is complete

  with j ∈ W and k ∈ W := [n] \ W define arcs in A P , i.e., are critical. Let c := |W | ∈ ⌊ n 2 ⌋, ⌈ n 2 ⌉ and consider any permutation τ that sends [c] to W (and thus [c] to W ): every critical pair in Q = τ -1 • P is an inversion, hence Q is minimally inversion-complete. Since |Q| = |P | = γ P (n) = γ I (n), it has maximum cardinality. This completes the proof. It remains to prove: Lemma 10. (Part (iii) of Theorem 2.

• A dual argument shows that if both (j, i) and (k, j) are selected critical pairs then {i, k} ∈ E P . • Now consider the case where (j, i) and (j, k) are selected critical pairs. Since p j,i does not cover (j, k), we have k before j before i in p j,i , implying that (k, i) cannot be a selected critical pair. Similarly, p j,k does not cover (j, i) and therefore we must have i before j before k in p j,k , implying that (i, k) cannot be a selected critical pair. Therefore, as claimed, we cannot have {i, k} in E P . • A dual argument applies to the remaining case, showing that if both (i, j) and (k, j) are selected critical pairs then {i, k} ∈ E P . Thus we must have {i, k} ∈ E P . This completes the proof that G P is trianglefree.

These results and Mantel's Theorem imply part (i) of Theorem 2. They also imply that, for n ≥ 4, all the sets τ • Q in Lemma 6 are in P * n . To complete the proof of part (ii) it now suffices to prove the converse for n ≥ 5.

Lemma 9. If n ≥ 5, a subset P of S n is a maximum-cardinality minimal paircomplete subset iff P = τ • Q for some permutation τ of the index set [n] and some maximum-cardinality minimal inversion-complete subset Q of S n .

Proof. Sufficiency was just established. To prove necessity, let n ≥ 5 and consider any P ∈ P * n and a corresponding critical selection graph G P . By Lemma 8, Theorem 2 (i), and the strong form of Mantel's Theorem, G P is a balanced complete bipartite graph. Now, also consider the associated critical selection digraph (directed graph) D P = ([n], A P ), wherein each edge {i, j} is directed as arc (i, j) ∈ A P if the pair (i, j) is critical. If (i, j) ∈ A P , then the reverse pair (j, i) must be covered by every permutation in P \ {p i,j }; since |P | -1 = ⌊n 2 /4⌋ -1 ≥ 2 when n ≥ 5, (j, i) cannot be critical, i.e., (j, i) ∈ A P . Thus, every edge {i, j} in the underlying graph G P of D P corresponds to exactly one arc, (i, j) or (j, i), in D P . We now prove that when n ≥ 5 the digraph D P is acyclic, i.e., it does not contain any (directed) circuit. Indeed, if D P contains a directed path (i(1), . . . , i(k)), then every permutation π ∈ Q \ {p i(1),i(2) , p i(2),i(3) . . . , p i(k-1),i(k) } has i(1) after i(2) after i(3), etc, after i(k -1) after i(k), and thus i(k) before i(1). Since |P | -(k -1) ≥ ⌊ n 2 4 ⌋ -(n -1) ≥ 2 when n ≥ 5, pair (i(k), i(1)) cannot be critical, and thus (i(k), i(1)) ∈ A P .

Since digraph D P is acyclic, there is at least one vertex i with in-degree zero. Since the underlying graph G P is a balanced complete bipartite graph, the side

. Consider any indices j ∈ W and k = l on the other side. Since vertex i has no entering arc, arcs (i, k) and (i, l) are in A P , and we consider the possible orientations of the edges {j, k} and {j, l}:

• If both edges are oriented into j, i.e., (k, j) and (l, j) in A P , then, on one hand, every permutation π ∈ P ′ = P \ {p k,j , p i,k } has j before k before i, and thus does not cover the pair (i, j). Similarly, every permutation π ∈ P ′′ = P \ {p l,j , p i,l } has j before l before i, and thus does not cover the pair (i, j) either. Therefore P = P ′ ∪ P ′′ does not cover the pair (i, j), a contradiction. • If one of these two edges is oriented into j and the other one from j, w.l.o.g., (k, j) and (j, l) in A P , then every permutation π ∈ P \ {p j,l , p k,j , p i,k } has