Florent Foucaud

Narges Ghareghani

Pouyeh Sharifani

Extremal digraphs for open neighbourhood location-domination and identifying codes *

A set S of vertices of a digraph D is called an open neighbourhood locating-dominating set if every vertex in D has an in-neighbour in S, and for every pair u, v of vertices of D, there is a vertex in S that is an in-neighbour of exactly one of u and v. The smallest size of an open neighbourhood locating-dominating set of a digraph D is denoted by γOL(D). We study the class of digraphs D whose only open neighbourhood locating-dominating set consists of the whole set of vertices, in other words, γOL(D) is equal to the order of D. We call those digraphs extremal. By considering digraphs with loops allowed, our definition also applies to the related (and more widely studied) concept of identifying codes. We extend previous studies from the literature for both open neighbourhood locating-dominating sets and identifying codes of both undirected and directed graphs. These results all correspond to studying open neighbourhood locating-dominating sets on special classes of digraphs. To do so, we prove general structural properties of extremal digraphs, and we describe how they can all be constructed. We then use these properties to give new proofs of several known results from the literature. We also give a recursive and constructive characterization of the extremal di-trees (digraphs whose underlying undirected graph is a tree).

Introduction

We consider extremal questions regarding the open neighbourhood location-domination problem on directed graphs (digraphs for short). This problem is part of the area of identification problems in discrete structures (such as graphs, digraphs or hypergraphs). In this type of problems, one wishes to uniquely determine some elements of the structure (usually the vertices or the edges) by means of a solution set (of vertices, edges or substructures), in the sense that each element to be distinguished is covered by a unique subset of the solution. Problems of this kind have been studied under various names and in different contexts such as separating systems, discriminating codes, or test collections, see for example [START_REF] Bollobás | On separating systems[END_REF][START_REF] Bondy | Induced subsets[END_REF][START_REF] Charbit | Discriminating codes in bipartite graphs: bounds, extremal cardinalities, complexity[END_REF][START_REF] Henning | Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs[END_REF][START_REF] Moret | On minimizing a set of tests[END_REF][START_REF] Rényi | On random generating elements of a finite Boolean algebra[END_REF]. They have many applications to various domains such as biological testing [START_REF] Moret | On minimizing a set of tests[END_REF], threat detection in facilities [START_REF] Ungrangsi | An implementation of indoor location detection systems based on identifying codes[END_REF] or fault diagnosis in computer networks [START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF][START_REF] Rao | Computational complexity issues in operative diagnostics of graph-based systems[END_REF].

Definitions. In this paper, we consider directed graphs (digraphs for short) which can contain loops (a loop is an arc from a vertex to itself). The vertex set and arc set of a digraph D is denoted by V (D) and A(D), respectively. An arc from vertex x to vertex y is denoted xy, its tail is x and its head is y. Multiple arcs between the same pair of vertices are allowed, but two arcs with the same tail and head are meaningless. Hence, we assume there are no multiple arcs. A digraph with no loops and with at most one arc between any pair of vertices is called an oriented graph. A digraph is called reflexive if each vertex has a loop. The in-neighbourhood of a vertex x of D is denoted by N - D (v), and similarly N + D (v) is the out-neighbourhood of v (we may drop the D subscripts if D is clear from the context). A source is a vertex with no in-neighbour, and a sink is a vertex with no out-neighbour. By the underlying graph of a digraph D, we mean the undirected simple graph (without loops and repeated edges) on vertex set V (D) obtained from D by adding an edge between x and y if x ̸ = y and there exists an arc in D between x and y. A di-tree is a digraph whose underlying graph is a tree. A rooted directed tree is a directed graph without loops and directed 2-cycles whose underlying graph is a tree, which contains a single source called root, and where each arc is oriented away from the root.

We say that a digraph is connected if its underlying graph is connected (this corresponds to the notion of weak connectivity of digraphs). If a digraph is not connected, we refer to its connected components as the digraphs formed by the connected components of its underlying graph. A directed cycle is a sequence of arcs such that the head of each arc is the same as the tail of the next one, the head of the last arc is the same as the tail of the first arc, and every vertex occurs only in two arcs of the sequence.

OLD sets.

The concept of open neighbourhood locating-dominating sets (OLD sets for short) was defined for undirected graphs under the name of IDNT codes by Honkala, Laihonen and Ranto in [23, Section 5] and independently rediscovered by Seo and Slater in [START_REF] Seo | Open neighbourhood locating-dominating sets[END_REF][START_REF] Seo | Open neighbourhood locating-dominating in trees[END_REF], who coined the term "OLD set". We extend the definition to digraphs, in the same way as the definition of dominating sets of undirected graphs is classically extended to digraphs [START_REF] Fu | Dominating set and converse dominating set of a directed graph[END_REF]. Given a digraph D, a set S of vertices is an open neighbourhood locating-dominating set of D if (i) every vertex has an in-neighbour in S (open neighbourhood domination condition) and (ii) for every pair of vertices, there is a vertex of S that is an in-neighbour of exactly one of the two vertices (open neighbourhood location condition). The open neighbourhood location-domination number (OLD number for short) of D, denoted γ OL (D), is the smallest size of an OLD set of D. Note that a digraph with a vertex of in-degree 0 or with two vertices with the same in-neighbourhood (called in-twins), does not admit any OLD set, but if the graph does not contain any such vertices, the whole vertex set is an OLD set. A digraph is called locatable if it admits an OLD set.

Since their introduction over a decade ago, OLD sets have been extensively studied, see [START_REF] Chellali | On open neighbourhood locating-dominating in graphs[END_REF][START_REF] Foucaud | Identification, location-domination and metric dimension on interval and permutation graphs[END_REF][START_REF] Foucaud | Identification, location-domination and metric dimension on interval and permutation graphs[END_REF][START_REF] Givens | Open locating-dominating sets in circulant graphs[END_REF][START_REF] Henning | Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs[END_REF][START_REF] Kincaid | Optimal open-locating-dominating sets in infinite triangular grids[END_REF][START_REF] Panda | Algorithmic aspects of open neighbourhood location-domination in graphs[END_REF][START_REF] Seo | Open neighbourhood locating-dominating in trees[END_REF] for some papers on the topic. The concept of OLD sets is related to the one of locating-dominating sets, defined by Slater in the 1980s [START_REF] Slater | Domination and location in acyclic graphs[END_REF][START_REF] Slater | Dominating and reference sets in a graph[END_REF], where the open neighbourhood domination condition is replaced by closed neighbourhood domination, and the location condition is only required for pairs of vertices that are not in the solution set. In the related notion of identifying codes, one replaces open (in-)neighbourhoods in both conditions by closed (in-)neighbourhoods. More precisely, a set S of vertices is an identifying code of a digraph D if (i) every vertex of D has a vertex of S in its closed in-neighbourhood and (ii) for every pair of vertices, there is a vertex of S that belongs to the closed in-neighbourhood of exactly one of the two vertices. These notions were mainly studied for undirected graphs, but locating-dominating sets of digraphs were studied in [START_REF] Bellitto | Locating-dominating sets in local tournaments[END_REF][START_REF] Bousquet | Locating-dominating sets: from graphs to oriented graphs[END_REF][START_REF] Charon | Identifying and locating-dominating codes: NP-completeness results for directed graphs[END_REF][START_REF] Foucaud | Domination and location in twin-free digraphs[END_REF][START_REF] Skaggs | Identifying vertices in graphs and digraphs[END_REF] and identifying codes of digraphs were studied in [START_REF] Berger-Wolf | Identifying codes and the set cover problem[END_REF][START_REF] Charon | A linear algorithm for minimum 1-identifying codes in oriented trees[END_REF][START_REF] Charon | Identifying and locating-dominating codes: NP-completeness results for directed graphs[END_REF][START_REF] Cohen | On the minimum size of an identifying code over all orientations of a graph[END_REF][START_REF] Foucaud | Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets[END_REF][START_REF] Skaggs | Identifying vertices in graphs and digraphs[END_REF].

In this paper, our goal is to study those locatable digraphs whose only OLD set is the whole set of vertices, which we call extremal digraphs.

Previous results. All undirected graphs whose only OLD set is the whole set of vertices were characterized in [START_REF] Foucaud | Characterizing extremal graphs for open neighbourhood location-domination[END_REF], as the family of half-graphs defined in [START_REF] Erdős | Some combinatorial, geometric and set theoretic problems in measure theory[END_REF] (a half-graph is a special bipartite graph with both parts of the same size, where each part can be ordered so that the open neighbourhoods of consecutive vertices differ by exactly one vertex). Digraphs with no directed 2-cycles whose only identifying code is the whole set of vertices were characterized in [START_REF] Foucaud | Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets[END_REF], as transitive closures of top-down oriented forests. The aim of this paper is to study the set of digraphs whose only OLD set is the whole set of vertices. In fact, the above results can be reformulated in our setting.

When a vertex has a loop, then its open in-neighbourhood is the same as its closed in-neighbourhood. Thus, for a reflexive digraph, the concept of an OLD set is the same as the one of an identifying code, as defined above. A digraph is symmetric if for each arc xy, the arc yx also exists. A symmetric digraph can be seen as an undirected graph. Thus, considering OLD sets of digraphs where loops are allowed, generalizes previous works on identifying codes of both digraphs and undirected graphs, and on OLD sets of undirected graphs.

Using the digraph terminology, we can reformulate existing results from the literature in our setting as follows (the two first theorems were proved in the context of identifying codes).

Theorem 1 ([21]

). For a connected, symmetric and reflexive locatable digraph D of order n, γ OL (D) = n if and only if n = 1.

Theorem 2 ([17, Theorem 9]). For a connected and reflexive locatable digraph D of order n without directed 2-cycles, γ OL (D) = n if and only if the digraph obtained from D by removing all loops is the transitive closure of a rooted directed tree.

Theorem 3 ([13, Theorem 1]). For a connected, symmetric and loop-free locatable digraph D of order n, γ OL (D) = n if and only if the underlying graph of D is a half-graph.

Also note that both OLD sets and identifying codes can be seen as a special case of discriminating codes in bipartite graphs, studied in [START_REF] Charbit | Discriminating codes in bipartite graphs: bounds, extremal cardinalities, complexity[END_REF][START_REF] Charon | Discriminating codes in (bipartite) planar graphs[END_REF]. Given a bipartite graph G with partite sets I and A, a discriminating code of G is a subset C of vertices of A such that each vertex of I has a unique and nonempty neighbourhood within C. Given a digraph D, one can construct a bipartite graph where I and A are two copies of V (D) and a vertex in I is adjacent to all vertices in A corresponding to its in-neighbours in D. Now, a subset C of A is a discriminating code in the bipartite graph if and only if it is an OLD set in D. A similar construction (with closed in-neighbourhoods instead of open in-neighbourhoods) can be done for identifying codes [START_REF] Foucaud | Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets[END_REF]. The problem of studying those bipartite graphs where all vertices of A are required in any discriminating code was one of the main problems studied in [START_REF] Charbit | Discriminating codes in bipartite graphs: bounds, extremal cardinalities, complexity[END_REF], and thus the present paper partially answers this question.

Our results. We first study, in Section 2, general properties of digraphs of order n with OLD number n. In such digraphs, every vertex is needed in every OLD set, either to dominate a vertex, or to locate a pair of vertices. Such vertices are called forced. We show that however, in such a digraph, no vertex can be double-forced (i.e. forced because of two distinct reasons). We also show that the vertex set of such graphs can always be partitioned into subsets, each of which contains a spanning directed cycle. We then give a characterization of the (very rich) class of digraphs of order n with OLD number n. We use the found structural properties and the characterization to give new proofs of Theorem 1, Theorem 2 and Theorem 3 in Section 3. Then, we focus, in Section 4, on the class of extremal di-trees, and give a recursive and constructive characterization of these digraphs. We conclude in Section 5.

Structural properties of extremal digraphs

We now describe the structure of digraphs whose only OLD set is the whole vertex set. There are many such digraphs, as we will see. To achieve this, we will first prove some preliminary results.

Forced vertices

In a locatable digraph D, some vertices have to belong to any OLD set: we call such vertices forced, as was done in e.g. [START_REF] Foucaud | Bounds on identifying codes in terms of degree parameters[END_REF] in the context of identifying codes. There are two types of forced vertices: those that are forced because of the domination condition, and those that are forced because of the location condition. Definition 4. Let D be a locatable digraph. A vertex v of D is called domination-forced if there exists a vertex w, such that v is the unique in-neighbour of w. Vertex v is called location-forced if there exist two distinct vertices x and y, such that N -(x) ⊖ N -(y) = {v} (where A ⊖ B denotes the symmetric difference of two sets A and B). A vertex v is called double-forced, if either it is both domination-forced and location-forced, or it is location-forced because of two different pairs of vertices.

We can observe the following. Proposition 5. If there is a vertex v in a locatable digraph D which is neither domination-forced nor location-forced, then V (D) \ {v} is an OLD set of D.

Proof. Since v is not domination-forced, every vertex of D has an in-neighbour in V (D) \ {v}. Moreover, since v is not location-forced, for every pair z, w of distinct vertices in D, there is a vertex in V (D) \ {v} in the symmetric difference N -(z) ⊖ N -(w), which therefore distinguishes z and w.

Proposition 5 implies that in any extremal digraph D, every vertex is domination-forced or location-forced (or both). (In fact, we will show in Proposition 11 that no vertex of D could be both domination-forced and location-forced.)

We get a direct corollary of Proposition 5, which will be used several times in the proofs of Section 4.

Corollary 6. Let D be an extremal digraph. If a vertex is not domination-forced (resp. location-forced), then it must be location-forced (resp. domination-forced).

Before proving our characterization, we will use the following celebrated theorem of Bondy, which is important for our line of work (see for example [START_REF] Foucaud | Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets[END_REF] and references therein).

Theorem 7 (Bondy's Theorem [START_REF] Bondy | Induced subsets[END_REF]). Let V be an n-set, and A = {A 1 , A 2 , . . . , A n } be a family of n distinct subsets of V . There is an (n -1)-subset X of V such that the sets A 1 ∩ X, A 2 ∩ X, A 3 ∩ X, . . . , A n ∩ X are still distinct. Corollary 8. Every locatable digraph D of order n has at most n -1 location-forced vertices.

Proof. Construct from digraph D the set system with V (D) as its n-set and where the A i 's are all the open in-neighbourhoods of vertices of D. Theorem 7 implies that there is one vertex such that removing it does not create two same open in-neighbourhoods. In other words, this vertex is not location-forced.

Forcing arcs

When a vertex x is forced, either it is the unique in-neighbour of some vertex y, or there are two vertices y, z such that x is the only vertex in the symmetric difference between N -(y) and N -(z), and x ∈ N -(y). In some sense, the arc xy is remarkable in that respect. We highlight such arcs as follows.

Definition 9. Let D = (V, A) be an extremal digraph. Then the arc xy ∈ A is called a forcing arc if either N -(y) = {x} or there is a vertex z ∈ V such that N -(y) \ N -(z) = {x}.
A forcing cycle is a cycle all whose arcs are forcing arcs.

Note that a vertex is forced if and only if it is the tail of a forcing arc. Thus, if D has only forced vertices, every vertex has a forcing outgoing arc.

The next lemma is important for our study.

Lemma 10. Let D be an extremal digraph. Let x be an arbitrary vertex of D and let D ′ be the digraph obtained from D by deleting all non-forcing arcs of D, which have x as their tails. Then, D ′ is locatable and extremal. Moreover, if x is not location-forced, then D and D ′ have the same sets of forcing arcs.

Proof. First, we prove that D ′ is locatable. Towards a contradiction, suppose that there exist two in-twins: vertices y and z such that

N - D ′ (y) = N - D ′ (z).
Since D is locatable, we conclude that x had exactly one of y and z as an out-neighbour in D; without loss of generality suppose that xy is an arc of D. But then, xy would be a forcing arc and it would not have been deleted from D, a contradiction. Moreover, assume that there is a vertex t of in-degree 0 in D ′ . Then, x must have been the only in-neighbour of t in D, but then the arc xt would be forcing and t would have in-degree 1 in D ′ , a contradiction. Therefore, D ′ is locatable.

We will now show that every vertex of D ′ is the tail of a forcing arc, implying that γ OL (D ′ ) = n, and that if x is not location-forced, then D and D ′ have the same sets of forcing arcs.

By Proposition 5, all vertices of D are either domination-forced or location-forced. By deleting all nonforcing arcs of D which have x as their tail, it is clear that all domination-forced vertices remain dominationforced, and each forcing arc xy having a domination-forced vertex as its tail remains forcing. Thus, to complete the proof, it remains only to consider location-forced vertices and those forcing arcs of D that have a location-forced vertex as their tails.

To this end, consider a location-forced vertex t in D, that is, there are two vertices u and v such that

N - D (u)\N - D (v) = {t}; thus, tu is a forcing arc in D. If x is neither an in-neighbour of u nor an in-neighbour of v, or if x = t, then in D ′ we still have N - D ′ (u) \ N - D ′ (v)
= {t} and tu is still a forcing arc in D ′ . Otherwise, x is an in-neighbour of u or v and x ̸ = t, thus, x must be an in-neighbour of both u and v in D (possibly, x = u or x = v). If both arcs xu and xv are not forcing or if both are forcing, then again in

D ′ , N - D ′ (u) \ N - D ′ (v)
= {t} and tu is still a forcing arc in D ′ . If xu is forcing and xv is not forcing in D, since u has both x and t as in-neighbours, xu is a location-forcing arc and there is a vertex w with N -(u) \ N -(w) = {x}. We note that since x ̸ = t and t ∈ N D (u), we have tw ∈ A(D). But then, in D ′ , we have

N - D ′ (w) \ N - D ′ (v) = {t}.
Thus, t is still location-forced in D ′ . Though the forcing arc tu is no longer forcing in D ′ , now the arc tw is forcing in D ′ (and in that case we had that x is location-forced).

Assume finally that xv is forcing and xu is not forcing in D. If xv is forcing because of domination, it means that x is the unique in-neighbour of v in D, and thus u is dominated only by x and t; in D ′ , u is dominated only by t, and thus in D ′ the arc tu remains forcing and t is now domination-forced. Otherwise, xv is forcing because of location: there is a vertex w such that N - D (v) \ N - D (w) = {x}. We note that since xu is non-forcing arc in D, and N - D (u)\N - D (w) = {x, t}, we conclude that in D ′ , we have N D ′ (u)\N D ′ (w) = {t}. Thus, the arc tu stays forcing in D ′ and t is still location-forced.

This means that each vertex of D ′ is either domination-forced or location-forced, and thus, we conclude that γ OL (D ′ ) = n. Moreover, the only case where D ′ and D had different sets of forcing arcs occurred when x was location-forced, as claimed.

We next show that in an extremal digraph, no two forcing arcs can have the same tail. Proof. We prove this by induction on n. We can assume D is connected, as it suffices to prove the claim for each connected component. If n = 1, the only locatable digraph has a single vertex with a loop, for which the claim is clearly true. If n = 2, one can check that there are three connected locatable digraphs of order 2 and in fact they all have OLD number 2 (see Figure 1). For each of them the claim is true.

Let n ≥ 3 and assume the result is true for all digraphs D of order m < n with γ OL (D) = m. Towards a contradiction, suppose that there is a digraph D of order n with γ OL (D) = n, which contains a double-forced vertex. Among all such digraphs of order n, let D = (V, A) be a digraph which has the smallest number of arcs.

Let z ∈ V be a double-forced vertex of D. By Corollary 8, there is a vertex x in D which is not locationforced, hence it is domination-forced. So, there is a vertex y ∈ V with N -(y) = {x} and xy is a forcing arc (possibly x = y and the arc is a loop). Since x is not location-forced, and there cannot be another vertex that has x as its unique in-neighbour (otherwise it would be an in-twin of y, contradicting the fact that D is locatable), we conclude that xy is the unique forcing arc which has x as its tail. Now, we claim that N + (x) = {y}. Indeed, otherwise, we can delete all non-forcing arcs from D which have x as their tails, to obtain a new digraph D ′ ; by Lemma 10 applied to D and x, which is not locationforced, we have γ OL (D ′ ) = n and the set of forcing arcs of D and D ′ are the same. Thus, all double-forced vertices of D remain double-forced in D ′ , in particular, there is at least one double-forced vertex in D ′ . But D ′ has at least one arc less than D, which contradicts the minimality of D in terms of the number of its arcs. (Moreover, if D ′ is not connected, we contradict the induction hypothesis applied to a connected component of D ′ containing a double-forced vertex.) Therefore, we have N + (x) = {y} as claimed. As n ≥ 3 and D is connected, this implies that x ̸ = y. Now, let D ′′ be the digraph obtained from D by contracting the arc xy. That is, we delete x and y and add a new vertex v xy that represents both x and y. Then, for each arc whose head is x or y (except the arc xy), we add an arc from its tail to v xy ; similarly, for each arc whose tail is x or y (except the arc xy), we add an arc from v xy to its head. Then, every domination-forced vertex of D (except x) remains dominationforced in D ′′ . Moreover, every location-forced vertex of D remains location-forced in D ′′ (note that v xy is domination-forced in D ′′ if y was domination-forced in D, and is location-forced if y was location-forced in D). Hence, γ OL (D ′′ ) = n -1 and the vertex z (or v xy if z = y) is double-forced in D ′′ , which contradicts the induction hypothesis. Thus, D does not exist, a contradiction which completes the proof.

Figure 1: The four connected locatable digraphs of order 1 and 2. Forcing arcs are dashed.

Structural properties of extremal digraphs

Theorem 12. Let D be a digraph of order n and D ′ be the subdigraph of D induced by the forcing arcs of D. Then, D is extremal if and only if D ′ is the disjoint union of directed cycles that spans the whole vertex set of D.

Proof. Assume γ OL (D) = n. By repeated use of Lemma 10, we deduce that D ′ is locatable and γ OL (D ′ ) = n. Thus, each vertex of D ′ is forced, has at least one in-neighbour, and at least one out-neighbour. In fact, by Proposition 11, each vertex of D ′ has exactly one out-neighbour. Thus, there is a total of n arcs in D ′ , and so, every vertex of D ′ has exactly one in-neighbour and one out-neighbour, and D ′ is the disjoint union of directed cycles.

Conversely, if D ′ is the disjoint union of directed cycles, then γ OL (D ′ ) = n. By Lemma 10, D and D ′ have the same set of forced vertices, thus γ OL (D) = n.

By Theorem 12, every vertex v of a digraph D of order n with γ OL (D) = n has a unique outgoing and a unique incoming forcing arc (possibly they are the same if v has a forcing loop).

Definition 13. For a vertex v of an extremal digraph D, we denote by f -(v) and f + (v) the unique inneighbour and out-neighbour of v, respectively, corresponding to the two unique incoming and outgoing forcing arcs incident with v (if v has a forcing loop, we have f

+ (v) = f -(v) = v).
Theorem 12 implies that in an extremal digraph D, every vertex appears in a directed cycle, thus we get the following corollary.

Corollary 14. Let D be a digraph of order n containing a source or a sink. Then, γ OL (D) ≤ n -1.

We also get the following corollary.

Corollary 15. If each vertex of a digraph D is forced, then D is locatable.
Proof. By Theorem 12, every vertex of D has an in-neighbour. Assume by contradiction that D contains two vertices x and y with the same in-neighbourhood. By Theorem 12, x has a forcing incoming arc, tx. Thus, there is an arc ty but by Proposition 11 ty is not forcing. Hence, t is not the only in-neighbour of y, and x, y have at least two in-neighbours. Thus, t is location-forced and there is a vertex z with Such a construction was previously defined in [START_REF] Foucaud | Bounds on identifying codes in terms of degree parameters[END_REF] in the context of identifying codes. We will now give some properties of H(D) when D is an extremal digraph. Proof. Since an arc xy in H(D) implies that the in-neighbourhood of x is strictly smaller than that of y, it is clear that H(D) is acyclic. Moreover, if some vertex x has two in-neighbours y, z in H(D), since f -(x) is unique and by the definition of H(D), then we would have that N -(y) = N -(x) \ {f -(x)} = N -(z), and thus y, z would be in-twins, contradicting the fact that D is locatable. Thus, H(D) is acyclic and each vertex has at most one in-neighbour, hence H(D) is the disjoint union of rooted directed trees as claimed.

N -(x) \ N -(z) = {t}. But this implies N -(y) \ N -(z) =
By Theorem 12, every vertex v of D has an incoming forcing arc from f -(v). By the definition of 3. Then, construct H(D) as a collection of vertex-disjoint rooted directed trees (note that such a tree may consist of a single vertex), as follows. The roots of the trees are precisely the out-neighbours of the vertices in V d . Moreover, for any vertex x of V l , its out-neighbour f + (x) has an in-neighbour in H(D).

H(D), if v is not a root of a tree of H(D), f -(v) is location-forced. If
N - D (x) = N - D (y) \ {f -(y)}.
Since the root r of T has only f -(r) as an in-neighbor, there are no further arcs in D incoming towards a vertex of T (otherwise there would be a similar arc towards the root r, contradicting the fact that it has only one in-neighbour). Thus, there are in fact no more arcs in D than the ones following the structure of H(D), and thus Step 4 completes the description of D.

Conversely, if D is constructed in this way, the digraph is clearly locatable and each vertex is forced, and thus D is indeed extremal.

An example of the construction of Theorem 18 is depicted in Figure 2. Figure 2(a) shows the choice of the directed cycles formed by the forcing arcs (two cycles (1, 3, 2) and (4)) as well as the partition into

V d = {1} and V f = {2, 3, 4}).

New proofs of known results

In this section, we show that the contents of the previous section enable us to give new proofs for already known results.

A new proof of Theorem 1

Recall the statement of Theorem 1.

Theorem (Theorem 1). For a connected, symmetric and reflexive locatable digraph D of order n, γ OL (D) = n if and only if n = 1.

We note that Corollary 8, which is directly derived from Theorem 7 by Bondy [START_REF] Bondy | Induced subsets[END_REF], in fact implies Theorem 1 (this gives a different proof than the one from [START_REF] Gravier | On graphs having a V \ {x} set as an identifying code[END_REF]).

Proof of Theorem 1. Let D be a connected, reflexive, symmetric and locatable digraph of order n. If γ OL (D) = n, by Proposition 5, every vertex of D is either location-forced or domination-forced. By Corollary 8, D has at most n -1 location-forced vertices, and so, it has at least one domination-forced vertex. However, since D is reflexive and symmetric, a domination-forced vertex of D is necessarily a vertex with no neighbours other than itself. Since D is connected, we must have n = 1.

A new proof of Theorem 2

Our tools can be used to give a new proof of Theorem 2 from [START_REF] Foucaud | Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets[END_REF] (the original proof uses induction), whose statement we recall below.

Theorem (Theorem 2). For a connected and reflexive locatable digraph D of order n without directed 2cycles, γ OL (D) = n if and only if the digraph obtained from D by removing all loops is the transitive closure of a rooted directed tree.

Proof of Theorem 2. It is not difficult to see that if D is obtained from the transitive closure of a rooted directed tree by adding a loop to each vertex, then γ OL (D) = n as the root of the tree is domination-forced, and each vertex is location-forced to locate itself from its parent in the tree.

For the other direction, let D be a connected reflexive locatable digraph of order n with no directed 2-cycle, and assume that γ OL (D) = n.

First of all, we claim that the forcing arcs in D are exactly its loops. Assume by contradiction that it is not the case, and there is a forcing arc from x to y with x ̸ = y. Then, there is a vertex z such that N -(y) \ N -(z) = {x} (thus, z / ∈ {x, y} since x is an in-neighbour of both x and y since there is a loop at x). Since there is a loop at both y and z, there is an arc from y to z and vice-versa, contradicting the fact that there is no directed 2-cycle in D. Thus, each forcing arc is a loop, and by Theorem 12, the set of forcing arcs of D is exactly its set of loops. Now, consider the digraph H(D) from Definition 16. By Theorem 17, it consists of a disjoint union of rooted directed trees. Since every vertex is dominated by itself through its loop, every domination-forced vertex is the root of one of the directed trees of H(D). Consider a location-forced vertex x of D, and assume its in-neighbour in H(D) is y. By the previous paragraph we have f -(x) = x and thus, since y has a loop, we must have the arc yx in D as well. Thus, H(D) is in fact a subdigraph of D. Moreover, for any two vertices x, y in the same rooted directed tree of H(D), where x is a descendant of y, we have the arc yx in D.

Moreover, we claim that there is a unique tree in H(D). For a contradiction, suppose there are at least two of them (each of which has a domination-forced vertex as its root). Recall that H(D) is a subdigraph of D. Since D is connected, there must be two trees T 1 and T 2 with an arc say, from a vertex x 1 of T 1 to a vertex x 2 of T 2 . But then, since the in-neighborhoods of vertices of T 2 only differ by vertices inside T 2 , x 1 must be an in-neighbour of all vertices of T 2 (including the root of T 2 ), and thus the root of T 2 is in fact not domination-forced, a contradiction.

This shows that D is obtained from the transitive closure of a rooted directed tree by adding a loop to each vertex, as claimed.

A new proof of Theorem 3

We next give a new proof using our structural theorems, that for every connected locatable symmetric and loop-free digraph of order n with γ OL (D) = n, the underlying graph of D is a half-graph (see below). We recall the definition of a half-graph: for any integer k ≥ 1, the half-graph H k is the undirected bipartite graph on vertex sets {v 1 , . . . , v k } and {w 1 , . . . , w k }, with an edge between v i and w j if and only if i ≤ j.

Theorem (Theorem 3). For a connected, symmetric and loop-free locatable digraph D of order n, γ OL (D) = n if and only if the underlying graph of D is a half-graph.

Proof of Theorem 3. Assume that D is a connected, locatable, loop-free and symmetric digraph of order n with γ OL (D) = n. By Theorem 12, we know that the set of forcing arcs of D induces a disjoint union of directed cycles.

First we show that all these directed cycles are, in fact, 2-cycles. Towards a contradiction, assume this is not the case, and let C be a directed cycle of forcing arcs of length other than 2. Since D is loop-free, there are no forcing loops, and so, C has length at least 3. Let c 1 , c 2 , . . . , c k be the vertices of C, ordered along the natural orientation of C. Since D is symmetric, each vertex of C has at least two in-neighbours, thus no vertex of C is domination-forced, and hence they are all location-forced. Thus, for each vertex

c i of C, there is a vertex c ′ i such that N -(c i ) \ {c i-1 } = N -(c ′ i ). Consider i = 2.
Since D is symmetric, we have c 3 which has an arc to c 2 , and thus, there are symmetric arcs between c 3 and c ′ 2 as well. Thus, since

N -(c 3 ) \ {c 2 } = N -(c ′
3 ), there must also exist symmetric arcs between c ′ 2 and c ′ 3 . However, since

N -(c 2 ) \ {c 1 } = N -(c ′
2 ) and c 1 ̸ = c 3 , there must be symmetric arcs between c 2 and c ′ 3 . But this contradicts the fact that N

-(c 3 ) \ {c 2 } = N -(c ′
3 ), and proves the claim that all forced-cycles are 2-cycles. By Corollary 8, we know that D contains at least one domination-forced vertex. Let v 1 be a dominationforced vertex of D and v 1 = f -(u 1 ). Since every forced-cycle of D is of length 2, we conclude that

u 1 = f -(v 1 ). Now, d -(u 1 ) = 1, since v 1 is domination-forced. Since D is symmetric, we have d + (u 1 ) = 1.
If u 1 is also domination-forced, since D is connected, then D is of order 2 and its underlying graph is the half-graph of order 2. Otherwise, u 1 is location-forced and thus there is a vertex

v 2 such that N -(v 1 ) \ N -(v 2 ) = {u 1 }. Now, let u 2 = f -(v 2 )
, and again, since the forced cycles of D are all 2-cycles, we also have

v 2 = f -(u 2 ). Since N -(v 1 ) \ N -(v 2 ) = {u 1 }, we also have the arc u 2 v 1 and (since D is symmetric) the arc v 1 u 2 .
If u 2 is domination-forced, then v 1 and v 2 have no additional in-neighbours. Thus, the only in-neighbour of v 2 is u 2 , which has at least two in-neighbours, and thus, v 2 cannot be domination-forced. Thus, v 2 is location-forced, and since

f -(u 2 ) = v 2 , there is a vertex u 3 such that N -(u 2 ) \ N -(u 3 ) = {v 2 }
. Thus, u 3 must have v 1 as an in-neighbour, and in fact we have u 1 = u 3 and there are no other vertices in D. Now, we are done since the underlying graph of D is a half-graph of order 4.

Otherwise, u 2 is location-forced, and since

u 2 = f -(v 2 ), there is a vertex v 3 such that N -(v 2 ) \ N -(v 3 ) = {u 2 }.
We can continue this process, building disjoint pairs of vertices (u i , v i ) forming the forcing 2-cycles of D, where u i has an outgoing arc and an incoming arc to and from each vertex v j , with j ≤ i. This goes on until we reach a domination-forced vertex u k . Then, the process stops. The vertex set of th obtained graph is {u 1 , . . . , u k } ∪ {v 1 , . . . , v k }, and there are two symmetric arcs between u i and v j if and only if i ≤ j. Thus, the underlying graph of D is precisely a half-graph of order 2k, which completes the proof. Lemma 23. Let D ∈ T n , T be the underlying tree of D and v be a leaf of T . Then at least one of the following conditions hold:

1. T contains a pendant path of length 2 whose leaf is contained in a forcing 2-cycle.

2. T contains a leaf which is included in a forcing loop.

Proof. We recall that by Theorem 12, every leaf belongs to a unique forcing cycle in D (of length at most 2). If T contains a pendant path of length 2, then its leaf is either contained in a forcing cycle of length 2 or of length one and hence D satisfies at least one of the mentioned conditions. Otherwise, T should not have any pendant path of length 2. Therefore, T contains two leaves adjacent to the same vertex. Now, using Theorem 12, at least one of these two leaves must have a forcing loop attached, which concludes the proof.

The case of a leaf with a forcing loop attached

Next, we give a recursive construction for digraphs D ∈ T n , which contain a forcing loop on a leaf. To this aim, we will use digraphs D ′ ∈ T n-1 .

Lemma 24. Let n > 2 be an integer, D ∈ T n and T be the underlying graph of D. Suppose that a is a leaf in T with a forcing loop attached and b is the unique neighbour of a in T . Letting

D ′ = D \ {a}, then D ′ ∈ T n-1 . Moreover, if ba ∈ A(D), then b is domination-forced in D and also in D ′ . If ab ∈ A(D), then f - D ′ (b) is domination-forced in D ′ , d + D (f - D (b)) = 1
Then D ∈ T n . Proof. First we note that if d + D ′ (f -(c)) = 1 (cases i and ii), then N + D ′ (f -(c)) = {c}.
So in these cases there is no vertex y such that N -(y) \ N -(c) = {f -(y)}. Hence, if the new digraph D is constructed by adding some new in-neighbours to c, this does not affect the forcing vertices of D ′ , other than f -(c). Thus, to prove that D is extremal in cases i and ii, it suffices to show that by adding the set of new arcs, each vertex from the set {a, b, c, f -(c)} is a forced vertex in D.

Moreover, in cases iii and iv, we do not add any in-neighbours to c, so in these cases as well it suffices to show that after adding the new arcs, each vertex from {a, b, c, f -(c)} is a forced vertex in D.

The characterization

As a conclusion of this section, we give our characterization theorem which shows how digraphs in T n can be constructed recursively, using extremal digraphs of smaller order. Definition 28. Let C 1 (T n ) be the set of all digraphs D ∈ T n+1 which are constructed from a digraph D ′ ∈ T n using one of the rules given in Lemma 25, and C 2 (T n ) be the set of all digraphs D ∈ T n+2 which are constructed from a digraph D ′ ∈ T n using one of the rules given in Lemma 27. Proof. For n ≤ 2, all connected locatable digraphs of these orders are those of Figure 1 and they are all extremal. Thus, assume next that n > 2.

By Lemma 25, we have C 1 (T n-1 ) ⊆ T n and by Lemma 27, we have C 2 (T n-2 ) ⊆ T n . Conversely, to see that T n ⊆ C 1 (T n-1 )∪C 2 (T n-2 ), assume that we have a digraph D in T n whose underlying tree is T . If D contains a forcing loop at a leaf of T , then Lemma 24 shows that D can be constructed from a digraph of T n-1 by one of the rules in Lemma 25 and thus D ∈ C 1 (T n-1 ). Otherwise, using Lemma 23, T contains a pendant path of length 2 whose leaf is contained in a forcing 2-cycle in D. Hence, by Lemma 26, D can be constructed from a digraph of T n-2 by one of the rules in Lemma 27 and thus D ∈ C 2 (T n-2 ).

We depict in Figure 4 all extremal digraphs of order at most 4, that were constructed using Theorem 29.

Conclusion

By studying structural properties of extremal digraphs with respect to OLD sets, we have been able to give new proofs of several existing results about both digraphs and undirected graphs, for both identifying codes and OLD sets. Indeed, OLD sets of general digraphs generalize all these problems. Thus, we believe that our results shed new light on this type of extremal problems.

We have also given a characterization of all such extremal digraphs, which, it appears, form a very rich class of digraphs. Even our recursive characterization for extremal di-trees, although of course more restricted than the general case, shows that there are many such extremal trees.

Proposition 11 .

 11 No extremal digraph contains a double-forced vertex.

  {t} and the arc ty should be forcing, contradicting Proposition 11.Definition 16. Given a digraph D, we define the digraph H(D) on vertex set V (D), where x has an arc to y if and only if there exists a vertex v of D that is location-forced, with N -(x) = N -(y) \ {v} (possibly, v = y, in which case y has a forcing loop; if v = x, then x has no loop but there is a forcing arc from x to y in D).

Theorem 17 .

 17 Let D be an extremal digraph.Then, H(D) is the disjoint union of rooted directed trees, where for each root r, f -(r) is domination-forced in D (and thus r has only one in-neighbour in D), and for each other vertex v, f -(v) is location-forced in D (and thus, v has an in-neighbour in H(D)).

  r is a root of a tree of H(D), then by the definition of H(D), f -(r) is not location-forced, and since D is extremal by Corollary 6, f -(r) is domination-forced. By the definition of H(D), each vertex v with an in-neighbour in H(D) has an incoming forcing arc wv where w = f -(v) is location-forced. This completes the proof. Using Theorem 12 and Theorem 17, one can show how all extremal digraphs can be built, as follows. Theorem 18. For any locatable digraph D of order n, we have γ OL (D) = n if and only if D can be constructed as follows. 1. First, choose a decomposition of n as a sum of positive integers n 1 , . . . n k , corresponding to the orders of the directed cycles C 1 , . . . , C k consisting of all forced arcs of D, and create the corresponding cycles. 2. Next, choose a partition of V (D) into a set V d of domination-forced vertices and a set V l of locationforced vertices, with |V d | ≥ 1.

4 .

 4 Finally, for each rooted directed tree T of H(D) and every vertex v of T , we create an arc from f -(v) to all descendants of v in T .Proof. Assume that D is extremal. By Theorem 12, the subdigraph D ′ of D induced by the forcing arcs of D is the disjoint union of directed cycles that spans the whole vertex set of D. This corresponds to the first step of the construction. Every vertex is forced, and by Proposition 11, no vertex is double-forced. Thus, there is a partition of V (D) into the set V d of domination-forced vertices and the set V l of location-forced vertices. This is Step 2 of the construction. Moreover, by Corollary 8, |V d | ≥ 1. By Theorem 17, the digraph H(D) is a collection of vertex-disjoint rooted directed trees where the roots of the trees are precisely the out-neighbours of the vertices in V d . Moreover, for any vertex x of V l , its out-neighbour f + (x) has an in-neighbour in H(D) (i.e. it is not a root of a tree of H(D)). This corresponds to Step 3 of the construction. Now, the arcs of D comply with the definition of H(D): for any vertex x of a tree T in H(D), the in-neighbourhood in D of each descendant of x in T contains the in-neighborhood of x in D, and moreover, for any arc xy of H(D),

Figure 2 (

 2 b) shows the set of rooted diected trees H(D) (in this case, it consists of a single tree T rooted at vertex 3, which is the out-neighbour of vertex 1, the only vertex in V d ). (Note that H(D) is not a subdigraph of D.) Finally, Figure2(c) shows the resulting extremal digraph obtained by adding to the set of directed cycles, for each vertex v in T , an arc from f -(v) to all descendants of v in T . That is, we add arcs from 1 = f -(3) to 1, 2 and 4 and from 3 = f -(2) to 1 (and no further arcs since 1 and 4 have no descendants in T ).

Figure 2 :

 2 Figure 2: An example of the construction from Theorem 18. The square vertex is the only one in V d ; the circled vertices are those in V l ; the dashed arcs are the forcing arcs; the wriggled arcs are those of H(D).

Lemma 25 .Figure 3 :

 253 Figure 3: Two extremal di-trees of order 3. Forcing arcs are dashed.

  i. As the vertices c and f -(c) are both domination-forced in D ′ , using Definitions 13 and 19, we conclude thatN - D ′ (f -(c)) = {c} and N - D ′ (c) = {f -(c)}. We claim that if D ′ has more than one vertex, then f -(c) ̸ = c. By contradiction, suppose that f -(c) = c,this means that there is a forcing loop at c. Since d -(c) = 1 and d + (f -(c)) = d + (c) = 1 and using the fact that D ′ is connected, we conclude that V (D ′ ) = {c}, which is a contradiction. Hence, the claim is true and f -(c) ̸ = c. Now, we prove that in this case, c remains domination-forced in D. To prove this, we note that N - D ′ (f -(c)) = {c} and c ̸ = f -(c). Therefore N - D (f -(c)) = {c}, which shows that c is domination-forced in D. Therefore, if A(D) = A(D ′ ) ∪ {bb, bc, ab, ba}, then N - D (a) = {b}, N - D (b) = {a, b} and N - D (c) = {f -(c), b}. Hence, b is domination-forced in D, a and f -(c) are both location-forced in D. If A(D) = A(D ′ ) ∪ {cb, bc, ab, ba}, then N - D (a) = {b}, N - D (b) = {a, c} and N - D (c) = {f -(c), b}. Hence, b is domination-forced in D, f -(c) and a are both location-forced in D (the latter because there is a vertex in D only dominated by c). If A(D) = A(D ′ ) ∪ {bc, ab, ba}, N - D (a) = {b}, then N - D (b) = {a} and N - D (c) = {f -(c), b}. Hence, b and a are both domination-forced in D and f -(c) is location-forced in D.

Finally,

  If A(D) = A(D ′ ) ∪ {cb, ab, ba}, then N - D (a) = {b}, N - D (b) = {a, c} and N - D (c) = {f -(c)}. Hence, b and f -(c) are both domination-forced in D and a is location-forced in D (because there is a vertex in D only dominated by c).In all cases, c remains domination-forced.Therefore, we conclude that each vertex of D is either domination-forced or location-forced which implies that D ∈ T n , as desired.ii. Since f -(c) is domination-forced in D ′ , N - D ′ (c) = {f -(c)}. First suppose that A(D) = A(D ′ ) ∪ {bb, bc, ab, ba}. Since N - D (b) = {a} ∪ N - D (a) and N - D (a) = {b}, we conclude that a is location-forced and b is domination-forced in D. Since N - D (c) = {f -(c)} ∪ N - D (a), f -(c)is location-forced in D and one can see that c remains location-forced in D. Therefore, in this case D ∈ T n . Now, suppose that A(D) = A(D ′ ) ∪ {bc, ab, ba}. Since N - D (b) = {a} and N - D (a) = {b}, we have that a and b are both domination-forced in D. On the other hand, N - D (c) = {f -(c)} ∪ N - D (a), so f -(c) is location-forced in D and again one can see that c remains location-forced in D. Hence, D ∈ T n .iii. Since c and f -(c) are both domination-forced in D ′ , using Definitions 13 and 19, we haveN - D ′ (f -(c)) = {c} and N - D ′ (c) = {f -(c)}. Considering N - D (a) = {b}, N - D (b) = {a, c}, N - D (f -(c)) = {c} and N - D (c) = {f -(c)}, itis easy to see that b, c and f -(c) are all domination-forced in D and a is location-forced. Hence, D ∈ T n as desired. iv. It is easy to see that b and c are domination-forced and f -(c) remains location-forced in D. Since c is domination-forced in D ′ , N - D (f -(c)) = N - D ′ (f -(c)) = {c}, hence N - D (b) = {a} ∪ N - D (f -(c)) and a is location-forced in D. Therefore, D ∈ T n .

Theorem 29 .

 29 Let n be a positive integer. If n ≤ 2, then all extremal digraphs of T 1 ∪ T 2 are shown in Figure1. If n > 2, then, we haveT n = C 1 (T n-1 ) ∪ C 2 (T n-2 ).

Figure 4 :

 4 Figure 4: All extremal di-trees with order at most 4. Forcing arcs are dashed.

* The first author's research was financed by the French government IDEX-ISITE initiative 16-IDEX-0001 (CAP 20-25) and by the ANR project GRALMECO (ANR-21-CE48-0004). The research of the second author was in part supported by a grant from IPM (No. 1402050116).

A recursive and constructive characterization of extremal di-trees

In this section, we characterize extremal di-trees, that is, (connected) extremal digraphs whose underlying graph is a tree. We are going to give a recursive construction for all of these digraphs. This characterization is more precise than the one from the more general Theorem 18 that holds for all extremal digraphs, and in particular, it enables us to easily construct all extremal di-trees of order n from the ones of orders n -2 and n -1 using simple operations.

We start with the following definitions.

Definition 19. For a positive integer n, we define T n as the set of extremal di-trees, that is, all locatable di-trees D of order n with γ OL (D) = n.

We note that when D is di-tree, then every forcing cycle of D is either of length 2 or of length 1. This implies that for every vertex v of D, f

For an undirected graph G, we say that an induced path with vertices

note there is no requirement on the degree of u 0 ). Lemma 20. Let D ∈ T n and T be the underlying tree of D. Then for each vertex

then u and v should have at least one common in-neighbour other than v, hence T contains a cycle of length 3, which is a contradiction. Otherwise, vertices v and u have at least have two common in-neighbours, so in this case T contains a cycle of length 4, which is again a contradiction. Hence d -(v) ≤ 2, as desired.

Recall that by Theorem 12, the forcing arcs of an extremal digraph D induce a disjoint union of directed cycles that spans the entire vertex set of D. If D is a di-tree, then these cycles are either loops or directed 2-cycles. In particular, if a vertex is loop-free, it is incident with a directed 2-cycle. Proof. Let v be a location-forced vertex of D. For contrary suppose that there exits a vertex x ̸ = f + (v) such that vx ∈ A(D). By Lemma 20, we have N -(x) = {f -(x), v}. Hence, f -(x) is not domination-forced and so it is location-forced. Therefore, there exists a vertex y such that N -(x) \ N -(y) = {f -(x)}. We conclude that N -(y) = {v}, this means that v is domination-forced which contradicts Proposition 11.

We next prove two structural lemmas.

Lemma 22. Let D ∈ T n and T be the underlying tree of D. Suppose that a is a leaf in T with a forcing loop attached to a. Then there is no cycle of length 2 in D which contains a.

Proof. Towards a contradiction, suppose that there is a cycle of length 2 containing the arcs ab and ba (by Theorem12, we know that none of these two arcs are forcing arcs). Since d -(a) = 2, we conclude that f -(a) = a is not domination-forced, and hence by Proposition 5, it is location-forced. Since aa is a forcing loop, we conclude that there exists a vertex c such that N -


Anna Béranger

Nicolas Dugué

Simon Guillot

Thibault Prouteau

Filtering communities in word co-occurrence networks to foster the emergence of meaning

Keywords: Word co-occurrence networks, community detection, word embedding, linguistics, interpretability

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

Introduction

In the field of Natural Language Processing (NLP), one of the main challenges is to represent the meaning of words into vectors, these vectors then being used as input to classification systems in order to solve various tasks such as part-ofspeech tagging, named entity recognition, machine translation, etc. Vectors that represent words are commonly designated as word embeddings: the meaning of words is embedded in a small latent space with dense vectors. Approaches to train such vectors are based on the distributional hypothesis. Harris defines this hypothesis, writing that "linguistic items with similar distributions have similar meanings". To train word embedding, one thus need to estimate these distributions using word co-occurrences from large corpora. The seminal approaches to train word embeddings are actually based on word co-occurrences matrix factorization [START_REF] Murphy | Learning effective and interpretable semantic models using non-negative sparse embedding[END_REF][START_REF] Pennington | Glove: Global vectors for word representation[END_REF][START_REF] Levy | Improving distributional similarity with lessons learned from word embeddings[END_REF]. Other popular approaches such as Word2vec [START_REF] Mikolov | Efficient estimation of word representations in vector space[END_REF] use neural networks to build lexical representations, thus approximating matrix factorization methods [START_REF] Levy | Neural Word Embedding as Implicit Matrix Factorization[END_REF]. Finally, transformer-based approaches [START_REF] Martin | Camembert: a tasty french language model[END_REF] and large language models based on these architectures [START_REF] Launay | Pagnol: An extralarge french generative model[END_REF] have demonstrated impressive performances, being able to contextualize word representations according to words' occurrences.

SINr (Sparse Interpretable Node Representations), the approach we introduced in Prouteau et al. [START_REF] Prouteau | Sinr: fast computing of sparse interpretable node representations is not a sin! In IDA[END_REF] is based on those recent progresses in NLP. However, it pursues an alternative path. Instead of focusing on performance, the method aims to train interpretable word vectors frugally. To do so, it leverages the distributional hypothesis in a rather direct manner, using word co-occurrence networks. Communities are then detected and considered as dimensions of the latent space. The word vector is finally extracted using the connectivity of its representing nodes to the communities extracted, in line with Harris' claim: we consider that words with similar distributions of links through communities have similar meanings. The model has proven its low compute requirement, it is indeed based on the Louvain algorithm [START_REF] Vincent D Blondel | Fast unfolding of communities in large networks[END_REF]. Furthermore, it was shown that dimensions of this model are mostly interpretable, the model being on-par with SPINE [START_REF] Subramanian | Spine: Sparse interpretable neural embeddings[END_REF], a competing state-of-the-art approach for interpretability [START_REF] Prouteau | Are embedding spaces interpretable? results of an intrusion detection evaluation on a large french corpus[END_REF]. Indeed, dimensions are not abstract as in conventional approaches: they are the communities uncovered, tangible groups of words [START_REF] Prouteau | Are embedding spaces interpretable? results of an intrusion detection evaluation on a large french corpus[END_REF]. Even though SINr does not focus strictly on performance, it is still an important goal. On the similarity task, the approach is on-par with SPINE, but slightly under-performs when compared to Word2vec.

In this paper, we show how to foster community filtering to significantly improve performances of SINr, allowing to catch up with Word2vec while preserving its interpretability and low compute properties, even lowering its memory footprint. We first describe SINr in more details Section 2. In Section 3, we analyze dimensions' activations and how they seem related to the distribution of community sizes. Using this analysis, we propose our community filtering method based on dimension activation to improve the model. Then, in Section 4, we detail the textual corpora used to train the word embedding approaches considered, and the similarity task that we use to evaluate model performances. We finally detail the results by showing that filtering communities by removing part of the head and tail of the dimensions activations distribution allows a significant improvement in results while reducing models' memory footprint.

SINr: interpretable word vectors based on communities

In this section, we first detail the SINr approach as we introduced it in [START_REF] Prouteau | Sinr: fast computing of sparse interpretable node representations is not a sin! In IDA[END_REF]. As far as we know, it is the first graph-based approach to train word embeddings, but like other approaches, it is based on the distributional hypothesis, adjusting Harris' formula by claiming that words with similar distributions of links through communities have similar meanings.

We start with an undirected weighted network, the word co-occurrence network, where words are vertices, and edges between nodes represent co-occurrences of words inside a sentence, and at a distance at most of w. Textual corpora were preprocessed to keep only meaningful words (see Fig 1a). Weights are associated to edges and represent the number of co-occurrences. We then filter our word co-occurrence network by setting to 0 the edges weights whose co-occurrence is not significant, according to the PMI (the ratio of the probability of nodes u and v co-occurring together divided by their probability of occurrence). This is very similar to the construction of a co-occurrence matrix, showing that SINr is related to the matrix factorization approaches such as [START_REF] Murphy | Learning effective and interpretable semantic models using non-negative sparse embedding[END_REF][START_REF] Levy | Improving distributional similarity with lessons learned from word embeddings[END_REF]. In matrix factorization, the next step is to factorize the matrix to reduce dimensionality and get dense vectors. In SINr, we use community detection with the Louvain algorithm to group words together and get the interpretable dimensions of our latent space (see Fig 1b). We use the multiscale γ parameter [START_REF] Lambiotte | Multi-scale modularity and dynamics in complex networks[END_REF] and set it to 60 in this paper: it allows uncovering small, thus consistent communities. We eventually calculate the distribution of the weighted degrees of each node through communities to get word embeddings, such as described in Figure 1c,1d. This distribution is computed according to the Node Recall introduced in [START_REF] Dugué | Bringing a feature selection metric from machine learning to complex networks[END_REF] and defined as follows. Given a vertex u, a partition of the vertices C = {C 0 , . . . , C j }, and C i the i th community so that 1 ≤ i ≤ j, the node recall of u considering the i th community is :

NR i (u) = d C i (u) d(u) with d Ci (u) = v∈Ci W uv .
To refine these vectors, we show in [START_REF] Guillot | Sparser is better: one step closer to word embedding interpretability[END_REF] that we can keep, for each vector, the 50 highest values, improving interpretability and lightening up the model.

Corpus before preprocessing: My cat eats mice. Your owl eats mice. This owl flies. A crow flies slower than an eagle. After preprocessing: cat eats mouse. owl eats mouse. owl flies. crow flies slower eagle. 3 SINr-filtered: sampling communities using activations

First, community sizes tend to follow a power-law distribution [START_REF] Vinh | Community structure: A comparative evaluation of community detection methods[END_REF]. We use the γ multiscale resolution parameter [START_REF] Lambiotte | Multi-scale modularity and dynamics in complex networks[END_REF] to uncover small consistent communities, but there are still a few communities bigger than the rest as shown in Figure 2. In this figure, we applied SINr to two corpora, BNC and UkWac which are described in details in Section 4. Furthermore, linguists have studied the distribution of words occurrences and co-occurrences in corpora. It has been shown that it follows Zipf's law [START_REF] Baroni | 39 distributions in text[END_REF], which is consistent with a power-law [START_REF] Adamic | Unzipping zipf's law[END_REF], commonly observed in complex networks. It means that some words would co-occur far more than others with the rest of the vocabulary, and a lot of them may co-occur very few with the rest of the vocabulary. Because communities are made of words following this power-law, and because communities sizes also follow a power-law, some communities may be much more connected with the rest of the graph than others, and some of them may be quite isolated. Let us recall that dimensions of our SINr model correspond to these communities. Thus, if we say that a dimension is activated by a word if this dimension's value is greater than 0 for this word vector, we expect the activation of dimensions by the word vectors to follow a power-law.

As we can see in Figure 3, the number of activations (non-zero values) follows a distribution that looks like a power-law. This is critical to understand how the model works and how we can improve its performances while reducing its memory footprint.

As stated by Subramanian et al. [START_REF] Subramanian | Spine: Sparse interpretable neural embeddings[END_REF], having dimensions activated by a large part of the vocabulary is not compatible with interpretability, which is a focus of our work: a dimension is interpretable if the set of words that activate it is consistent. Such heavily activated dimensions may be based on communities gathering very frequent words that appear in very different contexts, thus being Fig. 3: Distribution of the number of activations per dimension on BNC (left) and UkWac (right) corpora. The ordinate axis is in logarithmic scale. not consistent topically. We thus propose to remove these dimensions from the model, and we will see in Section 4 that it improves model performances.

We can also see that many dimensions are actually activated by only a few words. While these dimensions may be useful for very specific topics, they may not be useful for most of the vocabulary. They may also be noisy dimensions that penalize performances. We also propose to remove these dimensions from the models, and we will demonstrate in Section 4 that it notably reduces the memory footprint of the model (dividing the number of dimensions by 5) while preserving performances.

Experiments and results

Experimental setup

Task and baseline. We consider an intrinsic task to evaluate the performance of embeddings: the similarity task. In this task, we consider five datasets to evaluate our models: WS353 [START_REF] Agirre | A study on similarity and relatedness using distributional and WordNet-based approaches[END_REF], MEN [START_REF] Bruni | Multimodal distributional semantics[END_REF], SCWS [START_REF] Huang | Improving word representations via global context and multiple word prototypes[END_REF] and SimLex [START_REF] Hill | Simlex-999: Evaluating semantic models with (genuine) similarity estimation[END_REF] split in SimLex999 and SimLex665. Each dataset is made up of pairs of words associated with a similarity score that is a mean of ratings given by humans. The first three datasets comprise pairs of words, both representing word similarity (approximately synonymy, or at least substitutability, like "cat" and "feline") and word relatedness (much broader, encompasses pairs like "cup" and "coffee"). However, datasets differ regarding the parts of speech they include: WS353 only includes nouns, while MEN and SCWS include nouns, verbs and adjectives. Lastly, SCWS is designed to evaluate contextual representations, scores representing word similarity in different contexts: "bank" can be scored high with both "river" and "money" depending on the phrastic context presented to annotators. SimLex, on the other hand, is a dataset specialized on word similarity, which is more restrictive regarding the substitutability criterion, and allows for hyperonym-hyponym pairs to be closer than co-hyponyms. For example, in this dataset "father" and "parent" are rated at 7.07 on a scale of 10 regarding similarity, while "dad" and "mother" are at 3.55. Furthermore, SimLex does not rely on frequency information from a reference corpus to select its word pairs, it thus includes rarer words than WS353, MEN or SCWS. This dataset is of particular interest due to its difficulty, and its split with regard to parts of speech : SimLex999 being the whole dataset with noun-noun, adjective-adjective and verb-verb pairs, and SimLex665 being the noun subset. This split allows us to determine the validity of our modeling on different word categories, which probably follow different distributions of contexts.

Similarities in embedding spaces using cosine similarity are supposed to be correlated with human similarities, as shown in Figure 4. Correlation is computed with Spearman's definition: the closer to 1, the better. In order to assess the performances of our model, we also consider Word2vec, one of the most popular approaches to train word embeddings. We do not consider more recent state-ofthe-art approaches that allow to get better performances because our approach focuses on interpretability and low compute. Eventually, it may be used in more complex architectures, such as transformers, Corpora. We perform our evaluation on two text corpora :

w1
the written part of BNC [START_REF]British national corpus[END_REF], a collection of journalistic, academic and fictional texts totaling 100 million tokens ; -UkWac [START_REF] Baroni | The wacky wide web: A collection of very large linguistically processed web-crawled corpora[END_REF], a cleaned crawled corpus from the .uk internet domain with over 2 billion tokens.

Both of these corpora are classic for the similarity tasks. Their size, their content, and the way they are constituted is very different. By reproducing the experiments on such different corpora, we aim to show that the results may be generalized to any collection.

Preprocessing and models parameters. The text corpora are preprocessed with spaCy to improve the quality of cooccurrence information and reduce the vocabulary to be covered by the models. The text is tokenized and lemmatized, named entities are chunked, words shorter than three characters, punctuation and numerical characters are deleted. The minimum frequency to represent a type is set at 20 for BNC and 50 for UkWac. All models use a cooccurrence window of 5 words to the left and to the right of a target within sentence boundaries. Furthermore, as stated in Section 2, the multiscale resolution parameter γ is set at 60 for Louvain's community detection in SINr.

SINr-filtered approach. We first compute our SINr approach as described in Section 2. Then, by considering the distribution of activations per dimension, we explore the removal of the few very activated dimensions, and of the dimensions forming the long tail of this distribution. We explore the similarity performances regarding these removals and, in particular, the threshold used for these removals. The choice of thresholds is guided by performances on the word similarity evaluation task (see Figures 5,6).

Results

Baseline. In order to assess the performance of SINr-filtered, we also provide results for Word2vec, a reference approach which is not interpretable, and SINr, the original approach without filters on the communities. Results are averaged over 10 runs for the whole section. Table 1 show that SINr-filtered is always better than the original version, and that it catches up with Word2vec, even outperforming this baseline on MEN and WS353. 1: Summary of the results of competing models and of SINr and its filtered version, SINr-filtered, introduced in this paper.

We then show the effects of filtering using the distribution of activations on the SINr performance regarding the similarity evaluation.

Filtering the distribution's head. As one can see in Figure 5, model performances varies a lot with regard to the filter threshold. On the right, when the threshold is set to 12 000, there is actually no filtering. Filtering more and more, moving the threshold to the left until the best threshold 4000, allows to gradually increase performances of models for both UkWac and BNC. Between 4000 and 2000, results are rather plateauing. After 2000, significant information is removed, leading to a decrease in performance. Using the 4000 threshold allows catching up with Word2vec's performances, our reference. Indeed, the 4000 filter allows a gain of 5 points in performance for the MEN dataset (from 0.67 to 0.72 for BNC and from 0.70 to 0.75 for UkWac), and a slight gain of 2 points for the WS353 dataset (from 0.63 to 0.65 for BNC, from 0.68 to 0.70 on UkWac) and the SCWS dataset (from 0.56 to 0.58 for BNC, from 0.56 to 0.59 for UkWac). Such gains are statistically significant, and they are particularly interesting because they result from a simplification of the model, even if only 95 (resp. 90) dimensions are removed in average on the BNC (resp. UkWac) model using this filter. The SimLex dataset is much harder than the three others, for SINr but also for the reference model Word2vec. However, as one can see, filtering allows significant gain for SimLex also, especially for SimLex999 on BNC (from 0.20 to 0.25), and the results are better between 2000 and 4000 thresholds like for the other datasets. Filtering the distribution's long tail. The effect of filtering the long tail of the distribution of activations is quite different, as one can see in Figure 6. At left, no filter is applied, and increasing the filter does not lead to any gain in performances. Still, it is interesting to notice that filtering dimensions with less than 500 activations does not lead to any significant loss in information, on the five similarity datasets used for evaluation. Indeed, it actually divides by 5 the number of dimensions of the model, reducing its number of dimensions from roughly 6600 to 1200 on average for BNC, and from 5700 to 1100 for UkWac, thus allowing to drastically improve its memory footprint! Is filtering dimensions the same as filtering communities? As one can see in Figure 7, filters (more than 500 and less than 4000) applied using the number of dimensions have an expected effect on community distributions. Here, we assume that when a dimension is removed from the model, its community is also removed. We can see that removing dimensions with more than 4000 activations mostly removes big communities. This is especially the case for UkWac where the larger communities, those accounting for more than 150 words, are removed. For BNC, removed communities are not the largest, their size ranges from 60 to 80 words mostly. Similarly, removing dimensions with less than 500 activations tend to remove small communities. Still, most of the smallest communities are kept in the model while some larger are removed. These observations show that, even if the number of activations of a dimension and the size of its community are related, using the distribution of activations is different from using the distribution of the community sizes, showing the relevance of our approach. Singling out the subset of distinctive contexts. One may wonder if from one run of SINr to another, by filtering dimensions with more than 500 and less than 4000 activations, the vocabulary that forms communities that are kept is the same. It is surprising to notice that it is mostly the case: roughly 80% of the vocabulary kept is actually the same over ten runs when considering BNC and UkWac separately. However, this set is not the same from one corpus to another, only 35% of the vocabulary kept is actually common to BNC and UkWac. It seems to mean that these respective subsets of the vocabulary are essential to describe the meaning of words in these respective corpora. Those results, combined to the similarity improvements, point towards the notion that our filtering approach discriminates a subset of the dimensions that is the best fit to describe a given corpus. However, the evaluation results solely give insight on the subset of the lexicon covered by the similarity datasets, a subset that is heavily biased toward nouns, and especially frequent concrete nouns.

Conclusion

SINr is a graph-based approach to train word embedding which requires low compute and whose results are interpretable. In this paper, we show that we can significantly improve model performances and reduce its memory footprint by filtering its dimensions. Indeed, filtering the most activated dimensions allows gaining a few points on the similarity task for each dataset considered, showing that these dimensions are actually the bearer of noise into the model. This gain allows SINr performing on-par with Word2vec. Furthermore, filtering-out dimensions that are the least activated allows dividing the number of dimensions by 5 while preserving performances. We show that these filters relying on activations of the dimensions are somehow correlated with community sizes, but not completely, showing their relevance. Finally, we demonstrate that the vocabulary of communities that correspond to dimensions that are not filtered remains the same from one run of SINr to the other. We plan to experiment on other corpora but also on downstream tasks to confirm the ability of these results to generalize in a variety of contexts. Furthermore, it would be particularly interesting to test the ability of these filtered embeddings to model the meaning of very specialized vocabulary, to evaluate if removing dimensions affects the representation of these words.

  A graph G = (V, E, W ) partitioned in two communities. Bipartite projection of G into graph G′ = (⊤, ⊥, E, W ) along the communities. Weight on the edges is based on NR, the proportion of the weighted degree of each node related to the community. Adjacency matrix of G′, each row is a SINr embedding.

Fig. 1 :

 1 Fig. 1: SINr: words are represented based on the communities they are linked to.

Fig. 2 :

 2 Fig. 2: Distribution of community sizes on BNC (left) and UkWac (right) corpora. The ordinate axis is in logarithmic scale.

Fig. 4 :

 4 Fig. 4: Example of word similarity rating from the MEN dataset and cosine similarity between vectors.

Fig. 5 :

 5 Fig. 5: Similarity on BNC (left) and UkWac (right) corpora. Dimensions often activated are removed according to the threshold in abscissa.

Fig. 6 :

 6 Fig. 6: Similarity on BNC (left) and UkWac (right) corpora. Dimensions scarcely activated are removed according to the threshold in abscissa.

Fig. 7 :

 7 Fig. 7: Filtering effects on the community sizes distribution for BNC (left) and UkWac (right).

Acknowledgements

The work has been funded by the ANR project DIGING (ANR-21-CE23-0010).


O Patrakeev

Korablev

K S Olsen

F Montmessin

C B Boone

G C Toon

A Fedorova

A Trokhimovskiy

A Grigoriev

A Patrakeev

O Korablev

Spectroscopy and trace gas retrievals for the ExoMars Trace Gas Orbiter (TGO) Atmospheric Chemistry Suite mid-infrared (ACS MIR) solar occultation spectrometer using the JPL Gas Fitting software (GFIT)

Spectroscopy and trace gas retrievals for the ExoMars

Trace Gas Orbiter (TGO) Atmospheric Chemistry Suite mid-infrared (ACS MIR) solar occultation spectrometer using the JPL Gas Fitting software (GFIT)

The ExoMars Trace Gas Orbiter (TGO) intends to study the composition of the Martian atmosphere. It was jointly developed by ESA and Roscosmos and successfully entered orbit around Mars in October 2016. After a lengthy, but crucial, aerobreaking campaign, its orbit was nominally reduced to a nearcircular 400 km altitude, with a 2 hour period, in January 2018. There are four scientific instruments on TGO: the Atmospheric Chemistry Suite (ACS), the Nadir and Occultation for Mars Discovery (NO-MAD), the Colour and Stereo Surface Imaging System (CaSSIS), and the Fine-Resolution Epithermal Neutron Detector (FREND). This presentation will focus on trace gas retrievals for the mid-infrared (MIR) channel of the ACS instrument operating in solar occultation mode. The first solar occultation observations were made on April 21, 2018, with nominal science operations to follow. We will present the retrieval scheme, our evaluation of spectroscopic parameters, sensitivity to a priori data, results from retrievals for simulations of the Mars atmosphere, and spectral fitting results for the first set of solar occultation observations made by ACS MIR.

ACS is a set of three spectrometers that are designed to better characterize the atmosphere of Mars with unprecedented accuracy [START_REF] Korablev | The Atmospheric Chemistry Suite (ACS) of Three Spectrometers for the ExoMars 2016 Trace Gas Orbiter[END_REF]. It aims to detect and quantify unknown trace gases diagnostic of active geological or biological processes, to map their distribution and attempt to identify sources, and to refine our knowledge of the vertical distribution of major and minor atmospheric gases. It has three channels: near-infrared (NIR), thermal-infrared (TIRVIM) and MIR. The ACS MIR channel uses a novel concept for atmospheric studies: a cross-dispersion spectrom-eter combining an echelle grating with a wide blaze angle and secondary, steerable diffraction grating [START_REF] Korablev | The Atmospheric Chemistry Suite (ACS) of Three Spectrometers for the ExoMars 2016 Trace Gas Orbiter[END_REF]. It covers the wavenumber range of 2375-4340 cm -1 .

ACS MIR data is being processed by several groups. This presentation will focus on the data product generated at LATMOS using the Gas Fitting software (GFIT) maintained by NASA's Jet Propulsion Laboratory. GFIT if a part of the GGG software suite and is designed to be a multipurpose and robust spectral fitting suite (e.g., [START_REF] Sen | Balloon-borne observations of midlatitude fluorine abundance[END_REF][START_REF] Irion | Atmospheric Trace Molecule Spectroscopy (AT-MOS) Experiment Version 3 data retrievals[END_REF]. It was derived from early versions of the Occultation Display Spectra (ODS) software developed or the ATMOS spectrometer flown on the space shuttles [START_REF] Norton | ATMOS data processing and science analysis methods[END_REF]. It is currently used for the MkIV balloon missions [START_REF] Toon | The JPL MkIV interferometer[END_REF] and the Total Carbon Column Observing Network (TCCON) of ground-based FTSs [START_REF] Wunch | The Total Carbon Column Observing Network[END_REF].

GFIT computes volume absorption coefficients for each gas in a chosen spectral range, computes a spectrum line-by-line, and fits the computed spectrum to the measured spectrum using a non-linear Levenberg-Marqhardt minimization. The state vector contains the continuum level and tilt, and volume mixing ratio (VMR) scaling factors (VSFs) for each target gas. GFIT is capable of fitting multiple gases at the same time. The VSF is a multiplicative scaling factor applied to the a priori VMR vertical profile. In principle, GFIT only modifies the magnitude, and not the shape of, the a priori VMR vertical profile. However, in solar occultation mode, the a priori can be scaled for each observed spectrum at each tangent altitude. To retrieve a VMR vertical profiles for a target gas from a set of solar occultation spectra, the set of retrieved slant columns abundances from each observation are inverted with calculated slant column paths EPSC Abstracts Vol. 12, EPSC2018-916, European Planetary Science Congress 2018 c Author(s) 2018

EPSC

European Planetary Science Congress traced through the atmosphere using a linear equation solver.

Two major spectroscopic line lists, HITRAN and GEISA, have been recently updated.

Both the 2015 edition of the GEISA spectroscopic database [START_REF] Jacquinet-Husson | The 2015 edition of the GEISA spec-troscopic database[END_REF] and the 2016 edition of the HITRAN spectroscopic database [START_REF] Gordon | The HITRAN2016 molecular spectroscopic database[END_REF] feature significant changes to the spectroscopic parameters for CO 2 . These changes were developed to support greenhouse gas measurements at Earth by TCCON, the Greenhouse Gases Observing Satellite (GOSAT) and the Orbiting Carbon Observatory (OCO-2). On Mars, while the average surface pressure is roughly 200 times less than Earth's, the VMR of CO 2 is over 2000 times that of Earth. Therefore, CO 2 absorption lines in solar occultation spectra are can be larger for Mars than for Earth, and minor changes to the spectroscopic parameters can lead to large differences in the calculated spectra. To determine whether these changes lead to improved spectral fits, we have applied both databases, as well as HITRAN 2012 [START_REF] Rothman | The HITRAN2012 molecular spectroscopic database[END_REF] to spectral fitting of Earth-observing solar occultation spectra recorded by the Atmospheric Chemistry Experiment FTS (ACE-FTS) [START_REF] Bernath | Atmospheric Chemistry Experiment (ACE): Mission overview[END_REF]. We have also investigated the effects of spectroscopic parameters recently made available for air-broadening parameters in a CO2-rich atmosphere. Parameters for some gases have been compiled by HITRAN (CO, SO 2 , NH 3 , HF, HCl, OCS, and C 2 H 2 ) [START_REF] Li | Rovibrational Line Lists for Nine Isotopologues of the CO Molecule in the X 1 Σ + Ground Electronic State[END_REF][START_REF] Wilzewski | H2, He, and CO2 line-broadening coefficients, pressure shifts and temperature-dependence exponents for the HITRAN database. Part 1: SO2, NH3, HF, HCl, OCS and C2H2[END_REF], while parameters for water vapour have been made available by [START_REF] Gamache | A spectral line list for water isotopologues in the 1100-4100 cm -1 region for application to CO2-rich planetary atmospheres[END_REF] and [START_REF] Devi | Line parameters for CO2-and self-broadening in the ν3 band of HD 16 O[END_REF]. We will present the results of our validation of HITRAN 2016 and GEISA 2015, and also show the effects that CO 2 broadening parameters have on synthetic Mars spectra.

A first attempt at spectral fitting will be done using climatological models from the Mars Climate Database [START_REF] Forget | Improved general circulation models of the Martian atmosphere from the surface to above 80 km[END_REF][START_REF] Millour | MCD/GCM development Team: The Mars Climate Database (MCD version 5.2)[END_REF]. New observations of temperature and pressure made by the Mars Reconnaissance Orbiter's Mars Climate Sounder and the TIRVIM channel will be assimilated into the LMD General Circulation Model. When a more accurate assimilation is ready, the retrievals will be reprocessed using the updated a priori vertical profiles of temperature, pressure, CO 2 VMR, and H 2 O VMR. Vertical profiles of temperature and pressure will also be retrieved by simultaneous observation made with ACS NIR and TIRVIM. These will be used to produce a third version of our MIR data product. As the mission progresses, we will quantify the differ-ences among sources of a priori data, and study their effects on retrievals.

Much work has been done to investigate the limits of the retrieval algorithm by generating synthetic spectra for different atmospheric conditions (temperature, pressure, dust loading, and trace gas abundances). Noise is added to the spectra, they are resampled to a uniform fitting grid, and spectral fitting is performed using generic a priori to see how well the trace gas VMR vertical profiles used to create the synthetic spectra are reproduced. We found that given accurate temperature and pressure a priori, and a CH 4 abundance between 2-6 ppbv, we can accurately reconstruct the vertical profiles of CH 4 in the presence of noise. However, at low altitudes, due to signal attenuation from dust and interference from strong CO 2 absorption features, our retrieval becomes less accurate when the dust is high. Similarly, at high altitudes, where absorption line depths approach the magnitude of the noise, our retrieved profiles diverge from the true state of the atmosphere.

Since the end of April 2018, ACS MIR has been recording sets of solar occultation spectra. We will present our initial investigations into processing and fitting the data, focusing on the spectra and the goodness of fit for target gases in selected micro-windows. We will also present the latest state of our data processing and current best estimates of the composition and vertical structure of the atmosphere as estimated using GGG and ACS MIR.