Keywords: box-totally dual integral polyhedron, quasi-bipartite graph, perfect matching polytope, equimodular matrix. i

In this thesis, we study box-totally dual integral (box-TDI) polyhedra associated with several problems and totally equimodular matrices. Moreover, we study the complexity of some fundamental questions related to them.

We start by considering totally equimodular matrices, which are matrices such that, for every subset of linearly independent rows, all nonsingular maximal submatrices have the same determinant in absolute value. Despite their similarities with totally unimodular matrices, we highlight several differences, even in the case of incidence and adjacency matrices of graphs.

As is well-known, the incidence matrix of a given graph is totally unimodular if and only if the graph is bipartite. However, the total equimodularity of an incidence matrix depends on whether we consider the vertex-edge or the edge-vertex representation. We provide characterizations for both cases. As a consequence, we prove that recognizing whether a given polyhedron is box-TDI is a co-NP-complete problem.

Characterizing the total unimodularity or total equimodularity of the adjacency matrix of a given bipartite graph remains unsolved, while we solved the corresponding problem in the case of total equimodularity when the graph is nonbipartite.

In a later part of this work, we characterize the graphs for which the perfect matching polytope (PMP) is described by trivial inequalities and the inequalities corresponding to tight cuts. Tight cuts are defined as cuts that share precisely one edge with each perfect matching. We then prove that any graph for which the corresponding PMP is box-TDI belongs to this class. As a consequence, it turns out that recognizing whether the PMP is box-TDI is a polynomial-time problem. However, we provide several counterexamples showing that this class of graphs does not guarantee the box-TDIness of the PMP.

Lastly, we present necessary conditions for the box-TDIness of the edge cover polytope and characterize the box-TDIness of the extendable matching polytope, which is the convex hull of the matchings included in a perfect matching.

Résumé

Dans cette thèse, nous étudions les polyèdres total dual box-intègraux (box-TDI) associés à plusieurs problèmes et matrices totalement équimodulaires. De plus, nous étudions la complexité de certaines questions fondamentales liées à ces polyèdres.

Nous commençons par considérer les matrices totalement équimodulaires, qui sont des matrices telles que, pour chaque sous-ensemble de lignes linéairement indépendantes, toutes les sousmatrices maximales non-singulières ont le même déterminant en valeur absolue. Malgré leurs similitudes avec les matrices totalement unimodulaires, nous mettons en évidence plusieurs différences, même dans le cas des matrices d'incidence et d'adjacence des graphes.

Comme on le sait, la matrice d'incidence d'un graphe donné est totalement unimodulaire si et seulement si le graphe est biparti. Cependant, la totale équimodularité d'une matrice d'incidence dépend du fait que nous considérons la représentation sommet-arête ou arête-sommet. Nous fournissons des caractérisations pour les deux cas. En conséquence, nous prouvons que reconnaître si un polyèdre donné est box-TDI est un problème co-NP-complet.

La caractérisation de la totale unimodularité ou de la totale équimodularité de la matrice d'adjacence d'un graphe biparti donné reste non résolue, alors que nous avons résolu le problème correspondant dans le cas de la totale équimodularité lorsque le graphe est non-biparti.

Dans une derniere partie, nous caractérisons les graphes pour lesquels le polytope des couplages parfaits (PMP) est décrit par des inégalités triviales et des inégalités correspondant à des coupes serrées. Les coupes serrées sont définies comme des coupes qui partagent précisément une arête avec chaque couplage parfait. Nous prouvons ensuite que tout graphe pour lequel le PMP correspondant est box-TDI appartient à cette classe. En conséquence, reconnaître si le PMP est box-TDI est un problème résoluble en temps polynomial. Cependant, nous fournissons plusieurs contre-exemples montrant que cette classe de graphes ne garantit pas la box-TDIness du PMP.

Enfin, nous présentons des conditions nécessaires pour un polytope de couverture des arêtes pour etre box-TDI et caractérisons quand le polytope des couplages extensibles est box-TDI, qui est l'enveloppe convex des couplages inclus dans un couplage parfait.

Mots clés: polyèdre total dual box-intègral, graphe quasi-bipartite, polytope des couplages parfaits, matrice équimodulaire.

iii

Introduction

Preface

Among the many approaches to solving combinatorial optimization problems, the polyhedral approach stands out as one of the most effective. The core idea behind this approach is to transform the given combinatorial optimization problem into a linear program, which can be solved efficiently. This transformation is achieved by describing the convex hull of feasible solutions using a system of linear inequalities.

A key concept in the polyhedral approach is (of course) the notion of polyhedron, defined as the intersection of a finite number of half-spaces. Polyhedra are employed to represent feasible solutions and constraints in discrete problems. Vertices, edges, and facets of a polyhedron correspond to specific configurations or relationships within the optimization problem.

The polyhedral approach in combinatorial optimization has significantly impacted the field by offering a geometric and algebraic understanding of discrete optimization problems. It has proven instrumental in developing efficient algorithms and providing theoretical insights into problem structures and complexities.

The origins of the polyhedral approach can be attributed to George Dantzig's pioneering work on linear programming, specifically his introduction of the simplex algorithm in 1947. By leveraging the geometric structure of linear programming problems through traversal along the edges of polytopes, Dantzig's algorithm provided practical solutions and sparked interest in studying polyhedral combinatorial structures.

Over the ensuing decades, researchers recognized the broader applicability of the polyhedral approach beyond linear programming. They began investigating polyhedral structures associated with various combinatorial optimization problems, such as network flows, integer programming, and graph theory. This led to the development of a comprehensive theory aiming to characterize fundamental polyhedra related to different problem classes.

Polyhedral approaches gained further momentum with Jack Edmonds' introduction of total unimodularity in the 1960s (which is a very special case of total equimodularity which is probably the core of this thesis). Total unimodularity plays a central role in combinatorial optimization as it enables the efficient solution of integer programming problems, by ensuring that the associated polyhedra have integral vertices, i.e. every vertex as integer coordinates, total unimodularity allows for the development of efficient algorithms, that is polynomial algorithms.

Edmonds also proved that certain classes of integer programs could be described by integral polyhedra, among which the matching polytope is probably the most known.

Another significant development was the introduction of matroids, a polyhedral combinatorial structure capturing essential independence properties of combinatorial problems. Matroids provide combinatorial characterizations of associated polyhedra and have been applied to various optimization problems, including matching, spanning trees, and network flows.

Introduction

We provide an introductory survey of box-total dual integrality, exploring its core results and applications in polyhedral geometry and linear programming. As a summary of the principal results, the aim of this introduction is not to replace the main content of the chapters. All definitions stated here and all necessary results for the prosecution of the work will be restated independently in dedicated sections.

Totally dual integral systems were introduced in the late 70's and serve as a general framework for establishing various min-max relations in combinatorial optimization [START_REF] Schrijver | Theory of linear and integer programming[END_REF]. A rational system of linear inequalities Ax ≤ b is totally dual integral (TDI) if the minimization problem in the linear programming duality relation: max{c x : Ax ≤ b} = min{b y : A y = c, y ≥ 0} admits an integer optimal solution for each integer vector c such that the maximum is finite. Such systems Ax ≤ b define every integer polyhedron, whenever b is integral [START_REF] Edmonds | A min-max relation for submodular functions on graphs[END_REF].

A stronger property is the box-total dual integrality, where a system Ax ≤ b is box-totally dual integral (box-TDI) if Ax ≤ b, ≤ x ≤ u is TDI for all rational vectors and u (with possible infinite components). General properties of such systems can be found in Cook [START_REF] Cook | Operations that preserve total dual integrality[END_REF] and Section 22.4 of Schrijver [START_REF] Schrijver | Theory of linear and integer programming[END_REF].

Box-TDI systems are intimately related to totally unimodular matrices. A matrix is totally unimodular if every subset of linearly independent rows forms a unimodular matrix, a matrix being unimodular if it has full row rank and all its nonzero maximal minors have value ±1. A matrix A is totally unimodular if and only if the system Ax ≤ b is box-TDI for each rational vector b [59, Page 318].

Until recently, the vast majority of known box-TDI systems were systems associated with totally unimodular matrices. For instance, König's Theorem [START_REF] König | Gráfok és mátrixok[END_REF] can be seen as a consequence of the fact that the vertex-edge incidence matrix of a graph is totally unimodular if and only if the graph is bipartite [START_REF] Hoffman | Integral Boundary Points of Convex Polyhedra[END_REF].

In the last two decades, several new box-TDI systems were exhibited. Chen, Ding, and Zang [START_REF] Ding | The complexity of recognizing linear systems with certain integrality properties[END_REF] characterized box-Mengerian matroid ports. In [START_REF] Chen | The box-TDI system associated with 2-edge connected spanning subgraphs[END_REF], they provided a box-TDI system describing the 2-edge-connected spanning subgraph polyhedron for series-parallel graphs. Ding, Tan, and Zang [28] characterized the graphs for which the Edmonds system defining the matching polytope [START_REF] Edmonds | Maximum matching and a polyhedron with 0,1-vertices[END_REF], which is always TDI as shown by Cunningham and Marsh [START_REF] Cunningham | A primal algorithm for optimum matching[END_REF], is box-TDI. Ding, Zang, and Zhao [START_REF] Ding | On box-perfect graphs[END_REF] introduced new subclasses of box-perfect graphs. Cornaz, Grappe, and Lacroix [START_REF] Cornaz | Trader multiflow and box-TDI systems in series-parallel graphs[END_REF] provided several box-TDI systems in series-parallel graphs. More recently, these graphs have also been characterized by the box-TDIness of their flow cone [START_REF] Barbato | The Schrijver system of the flow cone in series-parallel graphs[END_REF] and that of their kxi CONTENTS edge-connected polyhedron [START_REF] Barbato | Box-total dual integrality and edge-connectivity[END_REF]. These last two results use characterizations of box-TDI polyhedra given by Chervet, Grappe, and Robert [START_REF] Chervet | Box-total dual integrality, box-integrality, and equimodular matrices[END_REF].

As stated before, every integer polyhedron can be defined by a TDI system. Yet, the statement no longer holds if we replace TDI by box-TDI. A polyhedron that can be described by a box-TDI system is a box-TDI polyhedron, and every TDI system describing it is actually box-TDI [START_REF] Cook | On box totally dual integral polyhedra[END_REF]. Box-TDI polyhedra characterize the following generalization of totally unimodular matrices. A matrix is totally equimodular if every subset of linearly independent rows forms an equimodular matrix, a matrix being equimodular if it has full row rank and all its nonzero maximal minors have the same absolute value. A matrix A is totally equimodular if and only if the polyhedron {x : Ax ≤ b} is box-TDI for each rational vector b [START_REF] Chervet | Box-total dual integrality, box-integrality, and equimodular matrices[END_REF].

Several complexity results relative to TDIness and box-TDIness are known. Deciding whether a system Ax ≤ b is TDI or whether it is box-TDI are two co-NP-complete problems [START_REF] Ding | The complexity of recognizing linear systems with certain integrality properties[END_REF]. The first problem remains co-NP-complete even for conic systems [START_REF] Pap | Recognizing conic TDI systems is hard[END_REF], that is, when b = 0. A tractable case for the recognition of box-TDI systems is when A is totally unimodular, since total unimodularity can be tested in polynomial time [START_REF] Seymour | Decomposition of regular matroids[END_REF].

Overview of the document

In Chapter 1, we provide all the fundamental definitions and essential components necessary to understand the contents of the subsequent chapters.

In Chapter 2, we analize some classical operation on matrices preserving total unimodularity to better distinguish totally equimodular matrices from the totally unimodular ones. These operations were used by Seymour [START_REF] Seymour | Decomposition of regular matroids[END_REF] to decompose regular matroids. Ultimately, we discovered several distinctions between the two classes.

Incidence matrices and adjacency matrices, which are fundamental classes of 0, 1-matrices, receive particular attention. In this regard, we prove that the edge-vertex incidence matrix of a graph is always totally equimodular, while the vertex-edge incidence matrix is totally equimodular if and only if the graph is a circuit or bipartite. Then, we investigate more general properties of box-TDI polyhedra. Despite their strong properties and connection with integrality, box-TDI polyhedra do not offer advantages in terms of complexity. Karp [START_REF] Karp | Reducibility among combinatorial problems[END_REF] indeed showed that finding an integer optimal solution for the edge relaxation of the stable set polytope (ERSSP) is an NPhard problem. Our result on the total equimodularity of the edge-vertex incidence matrix implies that the ERSSP is always a box-TDI polytope. This proves that solving integer programming over box-TDI polyhedra is generally NP-hard.

In 2008, Ding et al. [START_REF] Ding | The complexity of recognizing linear systems with certain integrality properties[END_REF] proved that recognizing whether a given system is box-TDI is a co-NP-complete problem. Since being a box-TDI system is a sufficient but not necessary condition for the associated polyhedron to be box-TDI, we explore the complexity of recognizing box-TDI polyhedra. It turns out that the complexity class is the same. This work is primarily a study of the geometric properties of the faces of a specific class of polyhedra.

Additionally, we characterize when the adjacency matrix of nonbipartite graphs is totally equimodular. All corresponding recognition problems can be solved in polynomial-time.

In Chapter 3, starting from our hardness result on box-TDI polyhedra, we delve into the theory of the edge cover polytope of a graph and attempt to characterize a particular face of it, having xii CONTENTS notable self-standing interest, known as the perfect matching polytope (PMP). The work of Ding et al. [28] in 2018 provides a characterization for the box-TDIness of the matching polytope, for which the (PMP) is a face. Hence, the characterization by Ding et al. [28] offers sufficient but not necessary conditions for the box-TDIness of the PMP.

Subsequently, we characterize the family of graphs whose PMP can be described by the intersection of nonnegativity constraints and the affine hull. In fact, it turns out that this class of graphs is a superclass of those whose PMP is box-TDI. Thus, testing the box-TDIness of the PMP can be reduced to testing the box-TDIness of its affine hull. Leveraging this finding, we successfully prove that recognizing whether the PMP of a given graph is box-TDI can be tested in polynomial-time.

This result contributes to our understanding of the structural properties of the PMP and provides an efficient algorithmic and geometric approach for identifying box-TDI instances within this specific context.

We conclude this manuscript by presenting necessary conditions for the box-TDIness of the edge cover polytope and by characterizing the box-TDIness of the extendable matching polytope, which is the convex hull of the matchings included in a perfect matching.

xiii Chapter 1

Preliminaries 1.1 Preliminaries on graphs

This section serves as introduction to graph theory. We begin with fundamental definitions and the establishment of standard matrices used to represent graph structures. Additionally, we delve into an in-depth examination of matching covered graphs and the associated decomposition techniques.

Graphs play a pivotal role in diverse domains due to their versatile significance. In various contexts, they offer a powerful and intuitive way to model and analyze complex relationships, patterns, and networks. Their value extends significantly in operations research, where they become indispensable for representing and understanding intricate operational systems like supply chains, transportation networks, and project scheduling. By utilizing graphs, researchers can optimize processes, allocate resources effectively, and perform critical path analysis, thereby enhancing efficiency, reducing costs, and making better decisions in real-world applications.

Definitions and notations

We start our discussion by introducing undirected graphs, which lay the foundation for understanding more complex structures, such as directed graphs.

Undirected graphs

An undirected graph (or simply a graph) is a pair G = (V, E), where V is a finite set, and E is a collection of unordered pairs from V . The elements of V are referred to as vertices (also known as nodes or points in the literature). The elements of E are known as edges (or lines). For an edge {u, v}, the vertices u and v are termed extremities, and the edge covers its extremities (alternatively, we say that {u, v} is incident to u and v).

Edges whose extremities coincide are referred to as loops. Two edges are incident if they share exactly one extremity, and parallel if they share both extremities. Two vertices are adjacent if an edge covers both of them. A graph without loops or parallel edges is termed simple. Instead of representing an edge as {u, v}, we prefer the concise notation uv.

For a set of vertices W ⊂ V , let E(W ) denote the set of edges with both extremities in W . Given F ⊆ E, V (F ) is the union of vertices covered by each edge in

F . A graph G = (V , E ) is a subgraph of G if V ⊆ V and E ⊆ E(V ), a induced subgraph if E = E(V ), and a spanning subgraph if the edges of G cover all vertices of G, i.e., V (E ) = V .
The closed neighborhood of a set of vertices U is the union of U with the vertices adjacent to its elements, and is denoted as N (U ). Conversely, the open neighborhood (or simply neighborhood ) is N (U ) \ U , and is denoted as N (U ). The elements of the neighborhood are referred to as neighbors. A vertex v for which N (v) = N (u) with respect to some vertex u is called a twin of u1 . If no specific vertex needs to be mentioned, we simply refer to it as 'a twin'. We define the operation of adding a twin to refer to replacing a graph with a new one that includes an additional twin.

The number of edges in G that cover a vertex v is known as the degree of v, denoted as d G (v) or d(v) when G is clear from the context. An edge is pendant if exactly one of its extremities has a degree of 1. Let v be a vertex of G. A star is a set of edges of covering v and v is the center of the star. Similar to twins, we define the operation of adding a star to G,to refer to replacing a graph with a new one that includes an additional nonisolated vertex. It is noteworthy that adding a star with a degree of 1 is equivalent to 'adding a pendant'.

A walk in a graph is a finite sequence (v 1 , e 1 , v 2 , . . . , e k , v k+1 ), where e i is an edge covering v i and v i+1 . The first and last vertices of the walk are known as the extremities of the walk, and we also say that the walk connects its extremities. An u, v-walk is a walk whose extremities are the vertices u and v. The length of a walk is the number of edges it contains. A walk is classified as odd or even based on its length. A walk is closed when its extremities coincide.

A trail is a walk in which all edges are distinct. If the trail is closed, it is referred to as a cycle. For simplicity, we often identify a trail with its edges. For a graph G, the odd tulgeity is the maximum number of vertex-disjoint odd cycles and is denoted τ (G). A path is a trail with distinct vertices v 2 , . . . , v k . If v 1 = v k+1 , it is termed an ear ; otherwise, the path is closed and referred to as a circuit. When a circuit

C satisfies E(V (C)) = C, it is called a hole 2 .
A graph is connected if for every couple of vertices there is a path connecting them. A graph is k-connected, where k is a positive integer, if for every subset of vertices of size k -1, the graph obtained by removing these vertices is connected. Analogously, a graph is k-edge-connected if for every subset of edges of size k -1, the graph obtained by removing these edges is connected.

For a subset X of vertices the cut δ(X) is the set of edges having precisely one extremity in X, and X and V \ X are the shores of the cut. A cut is trivial if one of its shores is a singleton. Thus, the degree of a vertex is nothing but the cardinality of its trivial cut. For X ⊆ V of a graph G, contracting X to a single vertex x, means replace X with x such that δ(X) = δ(x), and we denote the graph obtained from G after contracting X as G/X. The two graphs G/X and G/(V \ X) are referred to as the two δ(X)-contractions of G.

A matching is a subset of pairwise nonincident edges, while a stable set is a set of pairwise nonadjacent vertices. An edge cover of a graph is a set of edges covering all vertices. A perfect matching of a graph is a matching that is also an edge cover. A matching M in a graph G is extendable if there exists a perfect matching M of G for which M ⊆ M . By definition, all perfect matchings and all the proper subsets of a perfect matching are extendable. For instance, every edge belonging to a perfect matching is extendable.

Finally, given two graphs G = (V, E) and H = (W, F ), a bijective function f from V to W is called isomorphism if both f and f -1 preserve the number of edges covering each pair of vertices. If an isomorphism exists, G and H are said to be isomorphic.

In this work, all graphs are undirected unless differently indicated. Without loss of generality, we assume all graphs to be simple, connected, and to have at least one edge, as our results extend immediately to general undirected loopless graphs.

Directed graphs

A directed graph, or digraph for short, is denoted as D = (V, A), where V is a nonempty finite set, and A is a finite collection of ordered pairs of V . Just like with graphs, the elements of V are referred to as vertices, points, or nodes, while the elements of A are known as arcs.

The undirected graph obtained from D by ignoring the direction on the arcs is called underlying graph of D.

In contrast to undirected graphs, directed graphs add orientations to the pairs. An arc uv is described as leaving u and entering v. When we refer to a flow, we are talking about a positively valued function assigned to the arcs. If x represents a flow, x(uv) is incoming for v and outgoing for u, aligning with the direction of the arcs.

For a pair of vertices s and t, an s, t-flow signifies a flow over the arcs that is conservativemeaning the sum of incoming flows of a vertex different from s and t equals the sum of outgoing flows. A flow x is subject to a specific capacity, which is another positively valued function assigned to the arcs, imposing element-wise upper bounds to the flow.

An s, t-path is a path (s, su 1 , u 1 , . . . , u n-1 t, t) within the context of digraphs. It is important to note that in digraphs, this definition takes on an entirely new significance compared to analogous definitions in graphs, since the arcs are oriented. In addition, an s, t-cut is defined as a set of arcs intersecting with all s, t-paths and whose corresponding edges in the underlying graph are a subset of a cut whose deletion disconnects s from t.

Families of graphs present in this work

A forest is a graph that has no circuit, in the sense that none of its subgraphs is a circuit.

A connected forest is a tree (see Figure 1.1 a)).

A super class of forests is formed by bipartite

graphs. A graph G = (V, E) is bipartite if there exists a partition (U, W ) of V such that E(U ) = E(W ) = ∅.
Equivalently, a graph G is bipartite if has no odd cycles. Another characterization says that a graph is bipartite if and only if it is 2-colorable, that is, we can color all vertices by the use of just two colors such that no edge is spanned by two vertices of the same color. In Figure 1 A graph on n vertices is complete, denoted by K n , if for every pair of vertices u = v, then uv is an edge of the graph (see Figure 1.1 c)). A subgraph on U is a clique if it is induced by U and it is complete. When a bipartite graph with vertex partition (U, W ), and |U | = n and |V | = m, is such that for every vertex v in U or V , N (v) equals W or U , we call it complete bipartite graph and we denote it by K n,m A graph is planar if it can be drawn on the plane such that no two edges, drawn as lines, meet in their internal points (see Figure 1.1 a), b) and e)). We recall the fundamental result of Kuratowski [START_REF] Kuratowski | Sur le problème des courbes gauches en topologie[END_REF] which states that a graph is planar if and only if it has no subgraph which comes from K 5 (Figure 1.1 c)) and K 3,3 (Figure 1.1 d)) by subdividing every edge in a path.

A graph is Eulerian if there exists a path that contains every edge exactly once. When this path is open then it has precisely two vertices of odd degree (Figure 1.1 b)) and we say that is an opened Eulerian graph. While every vertex has even degree when it is closed and we say that it is a closed Eulerian graph (see Figure 1

.1 c)).

A wheel is a graph formed by a circuit and a vertex adjacent to all vertices of the circuit. If it has k + 1 vertices, we say having order k and we denote it by W k (see Figure 1.1 e)).

The Möbius ladder of order n is the graph on vertices v 1 , . . . v 2n such that if e belongs to its edges, then e ∈ C 2n or e = v i v j , where j is the rest of the division of i + n by 2n (see Figure 1.1 f)). Note that the Möbius ladder is bipartite if and only if n is odd.

a) b) c) d) e) f)

Matrices encoding graphs' structures

First, let us establish the notation and define a few concepts. For a given matrix A, A i and A i denote the i-th column and i-th row of A, respectively. In a given matrix, a minor is the determinant of any square submatrix. When the latter has the maximal size, the associated minor is maximal. A base of a matrix A is a submatrix formed by a maximal family of linearly independent columns of A. In most of the cases here, the treated matrices have full row rank; hence, a basis for such a matrix is a maximal nonsingular submatrix. Given a finite set U and a subset U , the characteristic vector of U , denoted as χ U , is a vector of R |U | such that χ U e = 1 if e ∈ U and 0 otherwise. When U is the set of vertices of a graph and e is an edge, we call χ e the incidence vector of e, as χ e u is 1 if and only if the edge e is incident to the vertex u.

Adjacency matrices

The adjacency matrix of G is the matrix, denoted by A G , whose rows and columns are indexed by the vertices of G, and where the entry in position (u, v) is the number of edges between u and v. Briefly, the rows of A G are the characteristic vectors of the cuts of the vertices of G. When G is simple, A G is a 0, 1-matrix. By definition, it follows immediately that adjacency matrices are symmetric up to permutation of rows and columns, and that, when it is the case, all elements in the diagonal are zeros. The two following observations are folklore:

Observation 1.1. Let G be a induced subgraph of G, then A G is a submatrix of A G .
Let G be a bipartite graph, and U and W be its vertex partition sets. Suppose that |U | ≤ |W | The bipartite representation of G is the matrix, denoted by B G , whose rows and columns are indexed by the elements of U and V , respectively, and where the entry in position (u, v) is the number of edges between u and v (see Example 1.2).

Example 1.2. The bipartite representation of the graph illustrated in Figure 1.2 is the matrix Observation 1.3. Let G be a bipartite graph. Then, A G , can be written, up to rows and columns permutation, as:

v1 v3 v5 v7     1 0 0 0 v2 1 0 0 1 v4 0 1 0 0 v6 . v 1 v 2 v 3 v 4 v 5 v 6 v 7
B G 0 0 B G .

Incidence Matrices

The incidence matrix of a graph G is the matrix, denoted by A G , whose rows and columns are indexed by the vertices and edges of G respectively, and where the entry in position (u, e) is the 1 if e covers u and 0 otherwise. Similarly to adjacency matrices the columns of A G are the characterisic vectors of the edges of G.

In the case of digraphs, the incidence matrix is a 0, ±1-matrix, whose 1s corresponds to the outgoing edges while -1s the incoming ones.

We say that the incidence matrix of C n is in canonical form if rows and columns are ordered by following sequence of the circuit (v 1 , e 1 , v 2 , . . . , v n = v 1 ), that is of the form

e1 e2 . . . en           1 0 . . . 1 v1 1 1 0 v2 . . . . . . . . . 0 0 . . . 1 1 vn .
The concept of a canonical form is not widely used in literature. However, we employ it in Section 2.3.1 to facilitate the recognition of specific patterns in the case of adjacency matrices when reordering rows and columns in a convenient manner.

Network matrices

Let D = (V, A) be a digraph and T = (V, A ), where A ⊆ A, be a directed tree. The network matrix of T , say M T , is the matrix whose rows and columns are indexed by A and A respectively, and whose entries are defined by:

(M T ) (v,w) a =       
+1, if the unique v, w-path passes throught a forwardly, -1, if the unique v, w-path passes throught a backwardly, 0, otherwise.

Matching covered graphs

Now, we introduce a fundamental class of graphs that plays a crucial role in describing the perfect matching polytope of any graph, which will be the main topic of Chapter 3.

A graph is matching covered if it is connected and each of its edges belongs to a perfect matching. Examples of matching covered graphs are: even circuits, odd wheels, K 4 , K 3,3 , and Möbius ladders.

Since, for every edge that does not belong to a perfect matching, the associated trivial inequality is tight, the perfect matching polytope can be studied by focusing on all connected components that arise by removing the edges that are not extendable.

The following observation express it more properly.

Observation 1.4. Let G be a graph having a perfect matching, and e 1 , . . . , e k all the edges of G that are not extendable. Then, all the connected components of the graph G \ {e 1 , . . . , e k } are matching covered. Moreover, P PM (G) equals the Cartesian product of their perfect matching polytopes.

Barriers cut and 2-separation cuts

In the context of matching covered graphs, a pivotal role is played by barriers, and we describe them here. The subsequent Theorem 1.6 of Lovász which characterizes matching covered graphs is a direct consequence of the widely known Tutte's Theorem that we recall here. Theorem 1.5 (Tutte [START_REF] Tutte | The factorization of linear graphs[END_REF]). A graph G = (V, E) has a perfect matching if and only if |O(G \ S)| ≤ |S| for all S ⊆ V . Theorem 1.6 (Lovász [START_REF] Lovász | Matching structure and the matching lattice[END_REF]). A graph G = (V, E) having a perfect matching is matching covered if and only if all barriers are stable sets. Another interesting case is represented by the class of cuts named 2-separation cut that we define below.

Let u, v be two vertices of a matching covered graph G such that G \ {u, v} has precisely two connected components, say G 1 and G 2 , which are even. Then, V (G 1 ) ∪ {u} and V (G 2 ) ∪ {v} (resp. V (G 2 ) ∪ {u} and V (G 1 ) ∪ {v}) are the shores of the 2-separation cut δ(V (G 1 ) ∪ {u}) (resp. δ(V (G 2 ) ∪ {u})). Moreover, we say that δ(V (G 1 ) ∪ {u}) (resp. δ(V (G 2 ) ∪ {u})) is a 2-separation cut with respect to u and v.

By construction any 2-separation cut shares the property of Remark 1.7 with respect perfect matchings.

Both barrier cuts and 2-separation cuts are related to the study of the perfect matching polytope. In fact, they lead to unique decomposition algorithms due to the work of Edmonds, Lovás and Pulleyblank [START_REF] Edmonds | Brick decompositions and the matching rank of graphs[END_REF] first, and of Lovász [START_REF] Lovász | Matching theory[END_REF] later, which links the dimension of the perfect matching polytope with the number of the fundamental pieces obtained by such decompositions.

Brick decomposition

We dedicate this space for the first decomposition technique for matching covered graphs presented in literature and due to Edmonds, Lovás and Pulleyblank [START_REF] Edmonds | Brick decompositions and the matching rank of graphs[END_REF].

We also take the opportunity to explain certain ideas without burdening the reading with definitions, which will be integrated in the next section in a more general framework.

Barriers characterize matching covered graphs by Theorem 1.6, and the corresponding barrier cuts as well as 2-separation cuts posses the property mentioned in Remark 1.7. This property allows us to treat them as vertices, since they share such a "tightness" property with respect to perfect matchings. A graph is bicritical if by removing any couple of vertices the new graph obtained has a perfect matching. Based on these notions, Edmonds et al. [START_REF] Edmonds | Brick decompositions and the matching rank of graphs[END_REF] introduced an algorithm known as "brick decomposition". Consider a nonbicritical matching covered graph G. Choose a maximal inclusion-wise barrier and consider all possible graphs obtained after contracting one of the shores of the corresponding barrier cuts. If any of these contractions yields a nonbicritical graph, repeat the process with this contracted graph. This series of steps will eventually yield a list denoted as L(G), consisting of bicritical graphs.

The list L(G) might encompass 3-connected bicritical graphs, which do not allow further decomposition through this process. Additionally, the list could encompass non-3-connected bicritical graphs with more than 2 vertices. This latter category can be decomposed by contracting once again with respect to the shores of the 2-separation cuts.

To conclude, the list of graphs containing more than 2 vertices is referred to as the bricks list, as the resulting graphs are irreducible with respect to this process (see Figure 1.4 for an example).

However, in the next section we will introduce an alternative definition for bricks. Our distinction is oriented in classifying these irreducible graphs as either bipartite or nonbipartite as they play different roles in the context of box-TDIness.

Edmonds et al. [START_REF] Edmonds | Brick decompositions and the matching rank of graphs[END_REF] proved that, up to edge multiplicity, the list of bricks obtained is unique and independent from the family of barriers and 2-sepration cut adopted. Furthermore, this list remains unaffected by the sequence's order. Lastly, Naddef [START_REF] Naddef | Rank of maximum matchings in a graph[END_REF] proved that the list of cuts used in this procedure is laminar (sometimes also called cross-free), where a family of cuts F is laminar if for every couple δ(X), δ(Y

) ∈ F is such that one among X ∩ Y, X ∩ (V \ Y ), (V \ X) ∩ Y , and (V \ X) ∩ (V \ Y )
is empty. So, two cuts are laminar if and only if one of the shore of the first is a subset of one of the shore of the second.

U U G U 1 U 2 G/U U 1 U 2 G/U G/U /U 2 G/U /U 1 G/U/U 2 G/U/U 1

Tight cut decomposition

Here, we introduce an alternative algorithm that is useful for determining the list of bricks in a matching covered graph. This technique relies on the previously mentioned concept of "tightness" for cuts, which typically encompasses various families of odd cuts.

Let G be a matching covered graph. A cut C of G is tight if |C ∩ M | = 1 for every perfect matching M of G. If C is nontrivial, then both of the C-contractions are matching covered graphs strictly smaller than G.

A matching covered graph is a brace if it is bipartite and has no nontrivial tight cuts. A brick if it is nonbipartite. Lovász showed in [START_REF] Lovász | Matching structure and the matching lattice[END_REF] that a brick is 3-connected and by removing any couple of vertices the resulting graph has a perfect matching, that is bicritical.

Typical examples of bricks are K 4 , C 6 := K 6 \ C 6 (see Figure 1.5), odd wheels and Möbius ladders of even order, while typical examples of braces are K 3,3 and Möbius ladders of odd order [START_REF] De Carvalho | On a conjecture of lovász concerning bricks: I. the characteristic of a matching covered graph[END_REF].

Lovász [START_REF] Lovász | Matching structure and the matching lattice[END_REF] showed that all maximal inclusion-wise families of nontrivial laminar tight cuts of a given matching covered graph have the same cardinality. Moreover, once chosen one of these families, recursively contracting the graph with respect to both of the shores of every tight cut brings a list of braces and bricks which is unique up to the multiplicity of the edges. This procedure is a tight cut decomposition [START_REF] Lovász | Matching structure and the matching lattice[END_REF]. We refer to the elements of a tight cut decomposition of G as the bricks and braces of G. As said before, tight cuts can be chosen to be laminar, moreover, this structure allows us to identify the inheritance property stated below.

Theorem 1.8 (Edmonds et al. [START_REF] Edmonds | Brick decompositions and the matching rank of graphs[END_REF]). Let G be a matching covered graph and G a matching covered graph obtained by contracting some shore of G.

Then, if C is a tight cut of G , C is a tight cut of G. Moreover, if D is a tight cut of G and D is a cut of G , then, D is a tight cut of G .
Special cases of tight cuts are barrier cuts and 2-separation cuts. A tight cut is an ELP-cut if it is a barrier cut or a 2-separation cut. In the same work, Edmonds, Lovász, and Pulleyblank [START_REF] Edmonds | Brick decompositions and the matching rank of graphs[END_REF] also proved that if G has a nontrivial tight cut, then there exists a nontrivial ELP-cut which is laminar with it. By recursively applying this result to the contractions with respect to ELP-cuts one ends up with a list of bricks and braces. In recent literature (see, for instance, [START_REF] Chen | Laminar tight cuts in matching covered graphs[END_REF]), this particular choice of tight cut decomposition is called ELP-cut decomposition and is nothing but the brick decomposition itself. Moreover, this is a polynomial-time algorithm [START_REF] Edmonds | Brick decompositions and the matching rank of graphs[END_REF].

It is worth of a remark that not every tight cut is an ELP-cut (see (c) of Figure 1.6).

The importance of barrier and 2-separation cuts

The tight cut decomposition generalizes the brick decomposition. However, recent results [START_REF] Zhao | A note on tight cuts in matching-covered graphs[END_REF] highlighted the significance of the latter. Theorem 1.9 (Edmonds et al. [START_REF] Edmonds | Brick decompositions and the matching rank of graphs[END_REF]). Let C be a tight cut of a matching covered graph G. Then, there exists an ELP-tight cut C which is laminar with C.

The following Theorem 1.10 is rephrased from Theorem 3 of [START_REF] Zhao | A note on tight cuts in matching-covered graphs[END_REF].

Theorem 1.10 (Zhao and Chen [START_REF] Zhao | A note on tight cuts in matching-covered graphs[END_REF]). If a matching covered graph has a nontrivial tight cut C which is not an ELP-cut, then there is an ELP-cut decomposition such that, if C is a cut of some graphs in the sequence constructed during the process, C is a 2-separation cut.

Thus, Theorem 1.9 along with Theorem 1.10 highlight the importance of the ELP-cuts: every tight cut can be reduced to an ELP-cut.

Braces existence

For bipartite graphs several results concerning the tight cut decomposition and the perfect matching polytope are known. Here, we summarize some of them.

Theorem 1.11 (See, for instance, Section 37.4 of [START_REF] Schrijver | Combinatorial Optimization: Polyhedra and Efficiency[END_REF]). Let G be a matching covered graph. Then, G is bipartite if and only if it has no bricks.

In other words, Theorem 1.11 states that for a bipartite matching covered graph G, the tight cut decomposition of G gives only braces. Observation 1.12. If a matching covered graph G has a barrier cut, then the list of braces of G is nonempty.

Proof. Let S be a barrier of G, and suppose that every component of G \ S is nonbipartite, as otherwise any contraction with respect the tight cuts associated to S would be a brace. By contracting all shores of G corresponding to the components of G \ S, we obtain a graph, say G S , which is bipartite, since S and G S \ S are both stable sets by Theorem 1.6. Thus, the tight cut decomposition of G gives a brace by Theorem 1.11.

Odd cycle property

Let F be a family of laminar nontrivial tight cuts of a matching covered graph G. A tight cut of F has the odd cycle property if for both of the shores the graph obtained after contracting one of them and all maximal shores of F that are subsets of the other one is nonbipartite. The family F has the odd cycle property if every cut in F has it. Thus, if F is also maximal inclusion-wise among the families of tight cuts with the odd cycle property, then G has |F | + 1 bricks. To simplify, consider tight cuts with the odd cycle property as cuts such that both of the corresponding contractions contain fewer bricks than the original graph.

A matching covered graph whose tight cut decomposition produce precisely one brick is a near-brick. Of course, bricks are near-bricks. For example, no tight cut in a near-brick has the odd cycle property, as follows by definition of near-brick, by applying Theorem 1.11. While, in a matching covered graph having k bricks whose tight cuts are associated with a barrier, say S, of k vertices, the corresponding k -1 barrier cuts have the odd cycle property, since by contracting k -1 shores not including S we obtain a near-brick.

If F is maximal inclusion-wise respect to the family of tight cuts having the odd cycle property but not respect all tight cut families is equivalent to say that the list obtained by the tight cut decomposition respect to F is a (nonunique) list of near-bricks.

In their work, Edmonds et al. [START_REF] Edmonds | Brick decompositions and the matching rank of graphs[END_REF] also described the operation of splicing, which characterize near-bricks. Here, we do not need that but as a consequence we have the following. Theorem 1.13 (Edmonds et al. [START_REF] Edmonds | Brick decompositions and the matching rank of graphs[END_REF]). In a near-brick all tight cuts are barrier cuts.

Near-brick Decomposition

In the domain of matching covered graphs, a conventional methodology involves a systematic analysis of the constituent bricks, with the intention of discerning inherent graph properties. However, within certain contextual frameworks, the characteristics exhibited by near-bricks overshadow those attributed to the traditional bricks.

If F is maximal inclusion-wise with respect to the family of tight cuts having the odd cycle property but not respect all tight cut families is equivalent to say that the list obtained by applying the same procedure of the tight cut decomposition with respect to F is a nonunique list of nearbricks. Thus, sometimes, we will talk about the near-brick of a certain matching covered graph instead of the bricks.

Ear decomposition procedure

An odd ear of a graph is an ear having odd length. In [START_REF] Lovász | Ear-decompositions of matching covered graphs[END_REF], has been described the so-called ear decomposition procedure. Starting from K 2 , every matching covered graph can be reached by a sequence of matching covered graphs obtained by iteratively adding one or two odd ears at each iteration.

A graph H is a fully odd subdivision of a graph G if H is obtained from G by subdividing each edge of G into a path of odd length (possibly the length is one). Each fully odd subdivision can be obtained by replacing an edge with a path of length three iteratively.

Theorem 1.14 (Lovász [51]). Every nonbipartite matching covered graph is the last graph in a sequence of matching covered graphs obtained from K 2 by adding one or two odd ears at each iteration. Moreover, either the second graph in the sequence is a fully odd subdivision of K 4 or the third is a fully odd subdivision of C 6 .

Since by removing a vertex from a fully odd subdivision of K 4 and C 6 the resulting graph is still nonbipartite, Theorem 1.14 implies the following.

Corollary 1.15. Let G = (V, E) be a nonbipartite matching covered graph. Then, G \ {v} is nonbipartite for every v ∈ V .

We now delve into the meaning of Theorem 1.14. First, consider matching covered graphs that exhibit symmetry, such as K 4 and C 6 . The ear decomposition procedure can be initiated from any edge of these graphs and conclude with the selected graph. Therefore, it is more appropriate to discuss a sequence of ear decomposition procedures rather than singularly focusing on the ear decomposition procedure itself.

Additionally, Theorem 1.14 might lead the reader to speculate that if a sequence of ear decomposition procedures for a given matching covered graph steps into a fully odd subdivision of K 4 (resp. C 6 ), then all sequences lead to K 4 (resp. C 6 ). However, the subsequent example demonstrates that this assumption is false.

Example 1.16. Figure 1.7 illustrates a graph where, starting from the edge e, we can generate a sequence first completing the upper part, resulting in K 4 , and subsequently the lower part, yielding C 6 . Conversely, starting once again from e, we can initially complete the lower side and subsequently the upper one. Therefore, we have showed two distinct sequences of the ear decomposition procedure that initiate from the same edge but diverge by completing first K 4 and C 6 respectively.

Solid graphs

A cut C of a matching covered graph G is a separating cut if both of the C-contractions of G are also matching covered. Every tight cut of a matching covered graph is also separating. In general, not every separating cut is tight.

For example, in C 6 , the cut formed by the vertices of any triangle is separating despite C 6 being a brick.

Deciding whether a given brick is free of separating cut is a co-NP problem [START_REF] Lucchesi | On two unsolved problems concerning matching covered graphs[END_REF]. 3 However, when the bricks are planar can be checked in polynomial time [START_REF] De Carvalho | How to build a brick[END_REF]. The following lemma is a characterization of separating cuts. Lemma 1.17 (de Carvalho et al. [START_REF] De Carvalho | On a conjecture of lovász concerning bricks: I. the characteristic of a matching covered graph[END_REF]). Let G be a matching covered graph. A cut C of G is separating if, and only if, for each edge e of G, there exists a perfect matching that contains e and just one edge in C.

A matching covered graph is solid if it has no separating cuts other than tight cuts. All bipartite matching covered graphs are solid. In [START_REF] De Carvalho | On a conjecture of lovász concerning bricks: I. the characteristic of a matching covered graph[END_REF] the authors also introduced the notion of characteristic of a matching covered graph. Briefly, it counts the minimum number of edges among all nontight separating cuts have in common with all perfect matchings. Then, they proved that the characteristic of a matching covered graph is the minimum of the characteristics among all its bricks. Finally, it follows that a matching covered graph has no separating cuts different from the tight cuts if and only if all its bricks are solid. Here, we highlight their result for reference later.

Theorem 1.18 (de Carvalho et al. [START_REF] De Carvalho | On a conjecture of lovász concerning bricks: I. the characteristic of a matching covered graph[END_REF]). A matching covered graph is solid if and only if all its bricks are solid.

A stronger characterization is given for bricks.

Theorem 1.19 (de Carvalho et al. [START_REF] De Carvalho | The perfect matching polytope and solid bricks[END_REF]). A brick G is nonsolid if and only if there exist two vertex-disjoint odd circuits

C 1 and C 2 such that G \ V (C 1 ∪ C 2 ) has a perfect matching.
Theorem 1.19 implies that odd intercyclic bricks are solid. Examples of solid graphs are bipartite matching covered graphs, odd wheels, and Möbius ladders of even order [START_REF] De Carvalho | How to build a brick[END_REF]. In particular, planar solid bricks are well-known.

Theorem 1.20 (de Carvalho et al. [START_REF] De Carvalho | How to build a brick[END_REF]). A solid brick is planar if and only if it is K 4 or an odd wheel.

The following Theorem provide a more general result than for bricks.

Theorem 1.21 (de Carvalho et al. [START_REF] De Carvalho | On a conjecture of lovász concerning bricks: I. the characteristic of a matching covered graph[END_REF]). Any odd intercyclic matching covered graph is solid.

Observation 1.22. Let G be a near-brick and B be its brick. If G is odd intercyclic, then so is B.

Proof. Suppose by contradiction that B contains two vertex-disjoint odd circuits C 1 and C 2 .

Since G is a near-brick no tight cut of G has the odd cycle property. Thus, if δ(U ) is tight such that U ∩ V (B) = ∅, and C1 and C2 are two circuits of

G such that G[ C1 ]/U = C 1 and G[ C2 ]/U = C 2 , then G[ C1 ]/(V \ U ) and G[ C2 ]/(V \ U ) are bipartite.
Hence, the lengths of C1 and C2 equal the lengths of C 1 and C 2 plus an even positive number respectively, and G is not odd intercyclic, a contradiction. This concludes our introduction to graph theory. The next section is devoted to introducing the main subject of this manuscript, which is polyhedra.

Preliminaries on polyhedra

Polyhedra along with matrices are the main objects of this work. In this section we introduce the key concepts such as polyhedra and their integrality. Furthermore, in the latter part, we delve into the desiderable property and main subject of this work: box-Total Dual Integrality. We also recall several polyhedral and matricial characterizations due to several authors.

Polyhedra and integrality properties

Integrality is a desirable property of polyhedra due to its relevance in numerous combinatorial and real-world problems. Nevertheless, understanding whether a given polyhedron is integer is a very challenging task (NP-complete [START_REF] Karp | Reducibility among combinatorial problems[END_REF]). Furthermore, we also introduce polarity, which provides a kind of duality for polyhedra, which exhibits intriguing connections with box-total dual integrality.

Polyhedra

A polyhedron is the set of points satisfying a system of linear inequalities, that is {x : Ax ≤ b}. When for every point x of a polyhedron P there is no direction u such that x + tu belongs to P for every positive scalar t, we say that P is bounded. A bounded polyhedron is called polytope. A face of a polyhedron P = {x : Ax ≤ b} is the polyhedron obtained by imposing equality on some inequalities in the description of P .

Let F be a face of P . An inequality

a i x ≤ b i of the system Ax ≤ b is tight for F if F ⊆ {x : a i x = b i }, and we denotes with A F x ≤ b F the inequalities from Ax ≤ b that are tight for F .
The dimension of a face equals the dimension of its affine hull. Faces whose dimension is maximal are called facets. A vertex is a face of dimension 0.

A matrix M is face-defining for a face F of P if it has full row rank and the affine space generated by F can be written as {x : M x = d} for some vector d of appropriate size. These matrices turns out to be useful to characterize box-TDI polyhedra (see Section 1.2.2). If P ⊆ R n and F is a face of P , then, the dimension of F is n -rank(M ), where M is a face-defining matrix of F .

The lineality space of {x : Ax ≤ b} is the linear space given by Ax = 0. When the dimension of the lineality space is 0 the polyhedron is said pointed. A polyhedron is pointed if and only if it includes no straight line. Equivalently, if it differs from the empty set, it has vertices.

Finally, a polyhedron in R n is full-dimensional if the dimension of its affine hull is n.

Cones

A polyhedral cone is the set of points satisfying a linear system of the form Ax ≤ 0. Since all objects that we investigate are polyhedra, we simply talk about cones. A cone C can also be described as the set of nonnegative combinations of a finite set of vectors R, that is C = {x : x = α i R i , α i ≥ 0}, and we say that C is generated by R. The vectors in R whose removal modifies the cone are called rays. Thus, rays form the minimal family of vectors of R needed to describe C. A conic polyhedron is a polyhedron that is a cone up to translation, that is

C = {t + x : Ax ≤ 0, for some t ∈ R n }. Of course, C is a conic polyhedron if C = {x : Ax ≤ At , for some t ∈ R n }.
For a given face F of a polyhedron P = {x : Ax ≤ b} the tangent cone of F is the conic polyhedron C F = {x : A F x ≤ b F }. Whenever F is a minimal inclusion-wise face of P , C F is called minimal tangent cone of P . Every polyhedron is the intersection of its minimal tangent cones

Polarity

The polar of a cone C = {x : Ax ≤ 0} is the cone C * = {x : z x ≤ 0, for all z ∈ C}. Equivalently, C * is the cone generated by the columns of A .

Two other types of polarity were introduced by Fulkerson [START_REF] Fulkerson | Blocking and anti-blocking pairs of polyhedra[END_REF]. For any polyhedron P the blocking polyhedron is B(P ) = {z : z x ≥ 1 for all x in P }. Analogously, the anti-blocking polyhedron is A(P ) = {z : z x ≤ 1 for all x in P }.

For these three notions it is true that C * * = C, B(B(P )) = P and A(A(P )) = P [START_REF] Schrijver | Theory of linear and integer programming[END_REF].

Dominants

The dominant of a polyhedron P , denoted by dom(P ), is the polyhedron {y : y ≥ x, x ∈ P }. By definition, dom(P ) is the Minkowski sum of P with the cone

R n ≥0 = {x : x ≥ 0}, that is {y : y = x + t, x ∈ P, t ∈ R n ≥0 }.
Similarly, the submissive of a polyhedron, denoted sub(P ), is the set of nonnegative points obtained by the Minkowski sum of P with R n ≤04 . See Figure 1.9.

The following characterization of the dominant is due to Cunningham and Green-Krotki [START_REF] Cunningham | Dominants and submissives of matching polyhedra[END_REF].

Theorem 1.23 (Cunningham and Green-Krotki [START_REF] Cunningham | Dominants and submissives of matching polyhedra[END_REF]). Let P = {x : Ax ≤ b} be a nonempty polyhedron. Then, dom(P ) = {x : w Ax ≤ w b for every w such that w ≥ 0, w A ≥ 0}.

A similar result also holds for the submissive since sub(P ) = -dom(-P ) ∩ {x : x ≥ 0}.

Integrality and boxes

A polyhedron is integer if all its vertices are integer. Equivalently, a polyhedron is integer if and only if it is the convex hull of integer points. Furthermore, integer polyhedra can be characterized by linear optimization, in fact, a polyhedron P ⊆ R n is integer if and only if Z n ∩argmax{w x : x ∈ P } = ∅ for every vector w. A polyhedron is box-integer if it is integer and the intersection with the "box" {x : ≤ x ≤ u} is integer for every integer vector and u.

Figures 1.10 (cases a) and b)), and 1.11 show two integer polytopes, the first is box-integer while the second is not.

The polyhedron P is the k-dilation of P = {x : Ax ≤ b} if P = {kx : x ∈ P }, where k ∈ Z ≥0 . We denote the k-dilation of the polyhedron P as kP . By definition it follows that kP = {x : Ax ≤ kb}.

A polyhedron P is principally box-integer if all k-dilations, k ∈ Z ≥0 , that are integer are also box-integer. When P is also integer, we call it fully box-integer (as example see Figure 1.10 c)).

Total dual integrality and box-total dual integrality

Total dual integrality and its consequent concept of box-total dual integrality play pivotal roles in the field of combinatorial optimization. Virtually every major work in polyhedral combinatorics and combinatorial optimization features a dedicated chapter addressing this fundamental subject. This prominence arises from the myriad applications in recognition problems, intricate connections with diophantine equations and other compelling algebraic topics, as well as its profound implications within polyhedral geometry, intertwining seamlessly with the notion of integrality. Moreover, under certain conditions, the latter concept of box-total dual integrality even enables the development of efficient algorithms to tackle challenging problems.

A linear system Ax ≤ b is totally dual integral (TDI) if whenever min{b y : A y ≥ w, y ≥ 0} for w integral vector, has an optimal solution, it has an integer optimal solution. For readers that are familiar with the terminology of primal and dual problems, TDI systems are precisely those systems for which, for any integer vector cost of the primal, the corresponding dual has an integer optimal solution whenever the optimum is finite. Every linear system is actually reducible to a TDI system up to scalar multiplication, that is every polyhedron can be described by a TDI system. In fact, if k is a multiple of all minors of A, then the equivalent system 1 k Ax ≤ 1 k b is TDI, since the polyhedron associated to the dual problem is described by A y = kw, y ≥ 0.

Since recognizing whether a given polyhedron is integer is an NP-hard problem [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF], mathematicians have been pushed to find several theoretical properties furnishing sufficient conditions for being integer, TDIness is one of them. Theorem 1.24 (Edmonds and Giles [START_REF] Edmonds | A min-max relation for submodular functions on graphs[END_REF]). Let Ax ≤ b be a TDI system. Then, b can be chosen integer if and only if the polyhedron P = {x : Ax ≤ b} is integer.

Moreover, TDIness also provides essential conditions for the integrality of a polyhedron. Theorem 1.25 (Section 22.4, [START_REF] Schrijver | Theory of linear and integer programming[END_REF]). A rational polyhedron P is integral if and only if there is a TDI-system Ax ≤ b with P = {x : Ax ≤ b} and b integral.

In 2011, Julia Pap [START_REF] Pap | Recognizing conic TDI systems is hard[END_REF] proved that even in the restricted scenario of determining whether a conic system (a system describing a cone) is TDI, is a co-NP-complete problem. For the general case of a TDI system, Ding et al. [START_REF] Ding | The complexity of recognizing linear systems with certain integrality properties[END_REF] established that the corresponding decision problem is also co-NP-complete.

A linear system is box-totally dual integral (box-TDI) if the resulting system remains TDI when any rational 'box' ≤ x ≤ u is added. As for TDI systems, recognizing whether a system is box-TDI is a co-NP-complete problem as well [START_REF] Ding | The complexity of recognizing linear systems with certain integrality properties[END_REF].

Furthermore, box-TDI systems offer strong min-max properties, which are particularly relevant in the context of (integer) linear programming and combinatorial optimization. Let us recall two well-established results that stem from the box-TDIness of the linear systems employed to formulate these problems. Given two vertices s and t of a digraph, the MaxFlow-MinCut Theorem states that the maximum s, t-flow equals the minimum sum of the capacities of the arcs of an s, t-cut.

However, Fulkerson's proof of the MaxFlow-MinCut Theorem is based on his theory on blocking pairs [START_REF] Schrijver | Theory of linear and integer programming[END_REF] (corresponding to an enrichment on blocking polyhedra discussed in the previous section).

For a given a bipartite graph the Köenig's Theorem states that the size of the minimum vertex cover equals the size of a maximum matching [START_REF] König | Gráfok és mátrixok[END_REF]. The original proof behing this result is purely graph theory based.

Box-TDIness is a self-standing topic which is a core for min-max relations. The interested reader can check [START_REF] Cornuéjols | Combinatorial Optimization: Packing and Covering[END_REF] for more information about this kind of relations in the specific case of 0, 1-matrices.

On the contrary to what happend to TDI systems, not every polyhedron can be described by this kind of systems. Cook [START_REF] Cook | Operations that preserve total dual integrality[END_REF] proved that being box-TDI is a property of the polyhedron, thus box-TDIness is actually a geometrical property.

Theorem 1.26 (Cook [15]). Let P be a polyhedron described by a box-TDI system. Then, every TDI system describing it is also box-TDI.

Theorem 1.26 justifies the following. Definition 1.27. A polyhedron is box-TDI if it can be described by a box-TDI system.

In Section 2.2.3, we prove that also recognizing whether a given polyhedron is box-TDI is a co-NP-problem.

Characterizations of box-total dual integrality

We provide a summary of various characterizations for box-TDI polyhedra, distinguishing between those rooted in polyhedral concepts and those relying on matrix-based approaches.

Polyhedral characterizations

Chervet et al. [START_REF] Chervet | Box-total dual integrality, box-integrality, and equimodular matrices[END_REF] gave several characterizations for box-TDI polyhedra; in this section, we give only those that best fit in our context. We start with general results for polyhedra and conclude the list with some results specific to cones.

Theorem 1.28 (Chervet et al. [START_REF] Chervet | Box-total dual integrality, box-integrality, and equimodular matrices[END_REF]). A polyhedron is box-TDI if and only if it is principally box-integer.

Corollary 1.29 (Chervet et al. [START_REF] Chervet | Box-total dual integrality, box-integrality, and equimodular matrices[END_REF]). An integer polyhedron is box-TDI if and only if it is fully box-integer.

Theorem 1.30 (Chervet et al. [START_REF] Chervet | Box-total dual integrality, box-integrality, and equimodular matrices[END_REF]). A polyhedron is box-TDI if and only if every minimal tangent cone is box-TDI.

Moreover, box-TDI polyhedra have the following property.

Theorem 1.31 (Cook [16]). The dominant and the submissive of a box-TDI polyhedron are box-TDI polyhedra.

Theorem 1.32 (Chervet et al. [START_REF] Chervet | Box-total dual integrality, box-integrality, and equimodular matrices[END_REF]). Let C be a cone, then the following statements are equivalent.

C is box-TDI;

C is box-integer;

C * is box-TDI; C * is box-integer.

Matricial characterizations

For a long time box-total dual integrality has been considered just an extension of total unimodularity, where for a matrix being totally unimodular means that every nonzero minor is ±1. In fact, until recently, the vast majority of known systems being box-TDI were determined by the total unimodularity of the corresponding matrix. Here we give some new definition, arised in the work on box-TDIness of Chervet et al. [START_REF] Chervet | Box-total dual integrality, box-integrality, and equimodular matrices[END_REF].

We recall a classical definition in combinatorial optimization. A matrix is unimodular if all its nonzero maximal minors are ±1. Therefore a total unimodular matrix is nothing but a matrix such that all sets of linearly independent rows form unimodular matrices.

Unimodular matrices can be generalized as follows. A n × m rational matrix, with n ≤ m, is equimodular if it has full row rank and all its nonzero minors of order n have the same absolute value. A matrix is totally equimodular if every subset of linearly independent rows is equimodular. By definition, it follows that every nonzero entry in a row of a totally equimodular matrix has the same absolute value. Thus, we will assume a totally equimodular matrix to be a 0, ±1-matrix, as we can always normalize any totally equimodular matrix by dividing each row by its corresponding nonzero value.

Totally unimodular matrices has been largely studied. Schrijver [START_REF] Schrijver | Theory of linear and integer programming[END_REF] gives the following historical line: Auslander and Trent [START_REF] Auslander | Incidence matrices and linear graphs[END_REF][START_REF] Auslander | On the realization of a linear graph given its algebraic specification[END_REF], Gould [START_REF] Gould | Graphs and vector spaces[END_REF], Tutte [START_REF] Tutte | An algorithm for determining whether a given binary matroid is graphic[END_REF], and Bixby and Cunningham [START_REF] Bixby | Converting linear programs to network problems[END_REF] describe polynomial-time algorithms to test if a certain given matrix is totally unimodular. Finally, Seymour [START_REF] Seymour | Decomposition of regular matroids[END_REF] showed a decomposition techinque that implies the existence of a polynomial-time algorithm to recognizing whether a given matrix is totally unimodular.

The subsequent theorem links these concepts from a matricial point of view.

Theorem 1.33 (Heller [40]). For a full row rank r × n matrix A, the following statements are equivalent.

A is equimodular;

For each nonsingular r × r submatrix B of A, B -1 A is integer; For each nonsingular r × r submatrix B of A, B -1 A is a 0, ±1-matrix;
For each nonsingular r × r submatrix B of A, B -1 A is totally unimodular; There exists a nonsingular r × r submatrix B of A such that B -1 A is totally unimodular.

As observed in [START_REF] Chervet | Box-total dual integrality, box-integrality, and equimodular matrices[END_REF], a consequence of Theorem 1.33 is that testing equimodularity can be done in polynomial time. Indeed, by Theorem 1.33, equimodular matrices are totally unimodular up to a basis change, and checking total unimodularity can be done in polynomial time [START_REF] Seymour | Decomposition of regular matroids[END_REF].

As the primary focus of this work is the box-TDIness of polyhedra, we establish the connections among these concepts.

Theorem 1.34 (Chervet et al. [START_REF] Chervet | Box-total dual integrality, box-integrality, and equimodular matrices[END_REF]). A polyhedron P is box-TDI if and only if every face-defining matrix of P is equimodular. Equivalently, a polyhedron is box-TDI if and only if every face can be described by an equimodular matrix.

Remark 1.35. The results by Chervet et al. are highly significant. They proved that a polyhedron is box-TDI if and only if every face can be described by a minimal system whose corresponding matrix is equimodular. This provides a matrix-based interpretation of the observation that every face of a box-TDI polyhedron is also box-TDI.

In our proofs, we will often use Theorem 1.34 combined with the following observation.

Observation 1.36 (Chervet et al. [START_REF] Chervet | Box-total dual integrality, box-integrality, and equimodular matrices[END_REF]). A full row rank matrix M is face-defining for a face F of a polyhedron P ⊆ R n if and only if there exist a vector d and a set H ⊆ F ∩ {x : M x = d} of dim(F ) + 1 affinely independent points such that |H| + rank(M ) = n + 1.

By Theorem 1.34, every polyhedron whose constraint matrix is totally equimodular is box-TDI. It turns out that this characterizes totally equimodular matrices.

Theorem 1.37 (Chervet et al. [START_REF] Chervet | Box-total dual integrality, box-integrality, and equimodular matrices[END_REF]). A matrix A of Q m×n is totally equimodular if and only if the polyhedron {x :

Ax ≤ b} is box-TDI for all b ∈ Q m .
Totally equimodular matrices are to box-TDI polyhedra what totally unimodular matrices are to box-TDI systems.

Theorem 1.38 (Hoffman et al. [START_REF] Hoffman | Integral Boundary Points of Convex Polyhedra[END_REF]). A matrix A of Z m×n is totally unimodular if and only if the system Ax ≤ b is box-TDI for all b ∈ Q m .

Preliminaries on and complements to equimodularity

This section serves as introduction to various concepts connected to equimodularity and their interconnections. While some of these concepts are well-established in the literature, others have emerged more recently. We start by summarizing several widely known results connecting total unimodularity and matrices representing graph structures. Following that, we delve into the definitions that are closely tied to TDIness and box-TDIness, sharing notable similarities. We conclude this section by complementing the definitions of total equimodularity and unimodularity with other concepts, such as minimally nontotal unimodularity, for instance.

Total unimodularity and graphs

This section is devoted to well-known results on totally unimodular matrices encoding graphs' structures, the aim is, simply, for complementing what we saw until now on graphs.

Incidence matrix of digraphs

According to Schrijver [START_REF] Schrijver | Theory of linear and integer programming[END_REF]Section 19.3], the total unimodularity of the incidence matrix of a digraph was studied by Poincaré at the beginning of twentieth century and afterwards revisited by several authors during the 1950s, here we provide [START_REF] Dantzig | On the max flow min cut theorem of networks[END_REF] as a reference.

Theorem 1.39 (Dantzig and Fulkerson [START_REF] Dantzig | On the max flow min cut theorem of networks[END_REF]). The incidence matrix of a digraph is totally unimodular.

Adjacency matrix of signed graphs

Commoner [START_REF] Commoner | A sufficient condition for a matrix to be totally unimodular[END_REF] showed sufficient conditions for the adjacency matrix of a signed bipartite graph to be totally unimodular, where a signed bipartite graph is a bipartite graph in which each edge is given a weight of -1 or +1, and its adjacency matrix is a 0, ±1-matrix, whose entries A i j are 1 or -1 if v i v j has weight 1 or -1, respectively, and 0 otherwise. Theorem 1.40 (Commoner [12]). Let G be a signed bipartite graph. If the sum of the edge weights over each cycle of G is divisible by 4, then its signed adjacency matrix is totally unimodular.

The graph in Figure 1.12 shows that the converse of Theorem 1.40 fails, since the summation of the edge weights over the subgraph C 6 is 6.

Network matrices

We end this section with a classical result of Tutte on the class of network matrices. The interested reader can find the proof in [START_REF] Schrijver | Theory of linear and integer programming[END_REF]Section 19.3].

Theorem 1.41 (Tutte [START_REF] Tutte | Lectures on matroids[END_REF]). The network matrix is totally unimodular.

Total dual integrality and dyadicness

In this section we summarize some results related to dyadic numbers and vectors, where dyadic numbers are precisely those rational numbers that have a finite binary representation.

Dyadic numbers and total dual dyadicness

A vector is p-adic if each of its entries is of the form a/p k for some integers a, k with k ≥ 0 and p prime. When p = 2, we call the vector dyadic.

Similarly to total dual integrality we define a system Ax ≤ b to be totally dual p-adic if whenever min{b y : A y = w, y ≥ 0} for w integral, has an optimal solution, it has a p-adic optimal solution.

Abdi et al. [START_REF] Abdi | Total dual dyadicness and dyadic generating sets[END_REF] have shown that, when a system is TDI and the corresponding polyhedron is pointed, then, the system is p-adic and q-adic for p = q. Moreover, they proved the following integrality sufficient condition, which is less restrictive than TDIness.

Theorem 1.42 (Abdi et al. [START_REF] Abdi | Total dual dyadicness and dyadic generating sets[END_REF]). Let P = {x : Ax ≤ b} a pointed polyhedron. If Ax ≤ b is p-adic and q-adic, for p = q, then P is integer.

Interestingly, as a stronger converse of Theorem 1.42, according to Schrijver [START_REF] Schrijver | Combinatorial Optimization: Polyhedra and Efficiency[END_REF], Seymour stated the following conjecture.

Conjecture 1.43. Let A be a 0, 1-matrix. If Ax ≥ 1, x ≥ 0 defines an integral polyhedron, then it is totally dual dyadic.

On the contrary to TDIness, not all polyhedra are p-adic for some p, where for a polyhedron being p-adic means that every nonempty face contains a p-adic point. Although this definition seems to be not congruent with the one given for box-TDI polyedra, the following result by Abdi et al. shows that the comparison is correct.

Theorem 1.44 (Abdi et al. [START_REF] Abdi | Total dual dyadicness and dyadic generating sets[END_REF]). Let A and b be an integral matrix and vector respectively. If Ax ≤ b is totally dual p-adic, for some prime p, then the polyhedron {x : Ax ≤ b} is p-adic.

The last theorem legitimizes a comparison between total dual p-adicness and box-TDIness, and this will be the topic of Section 2.1.2.

TDIness, half-integrality and dyadicness

A vector is half-integral if its components are 0, ±1/2, ±1. A system is totally dual half-integral if whenever min{b y : A y = w, y ≥ 0} for w integral, has an optimal solution, it has a halfintegral optimal solution. Of course totally dual half-integral systems are a special case of total dual dyadicness. Despite this fact, total dual half-integral system are a notable class deserving a mention due to their connection with the matching polytope [START_REF] Cunningham | A primal algorithm for optimum matching[END_REF]. The latter will be discuss in the last chapter.

Finally, dyadic and half-integral vectors present an intriguing relation with TDI systems as stated in the following. for each vector y ≥ 0 with y A integral, there exists a dyadic vector y ≥ 0 with y A = y A; for each {0, 1 2 }-vector y with y A integral, there exists an integral vector y ≥ 0 with y A = y A and y b ≤ y b.

Complements to unimodularity and equimodularity

In this section, we discuss several objects related to equimodularity.

First, we define two classes of matrices: minimally nontotally unimodular matrices and principally unimodular matrices. Both of these classes are found to be useful in Chapter 2 for studying the properties of total equimodular matrices and total unimodular adjacency matrices.

Second, we provide a brief overview of linear Diophantine systems, a topic widely explored in number theory and algebra. These systems aim to find integer solutions, and unimodularity provides sufficient conditions for determining the solution set.

Lastly, we introduce the Smith normal form of a matrix. This form is uniquely defined for any given rational matrix and allows us to find a reduced basis for a lattice.

Minimally nontotal unimodularity

A matrix is minimally nontotally unimodular if by removing any row the obtained matrix is totally unimodular. Minimally nontotally unimodular matrices are a special case of totally equimodular matrices.

Theorem 1.46 (Camion [8]). Let A be a matrix which is not minimally nontotally unimodular matrix. Then A is square, det(A) = ±2, and A -1 has only ±1/2 entries. Moreover, each row and each column of A has an even number of nonzero entries and the sum of all entries in A is congruent 2 mod 4.

Patrick Chervet and Roland Grappe (personal correspondence) used the aforementioned classes of matrices to prove a decomposition theorem for totally equimodular matrices, and then they use it to provide a polynomial-time recognition algorithm for full row rank totally equimodular matrices.

Principal unimodularity

We introduce a relatively lesser-known concept that establishes connections to total unimodularity, which we will elaborate upon in the subsequent sections devoted to the study of the total equimodularity of the adjacency matrix. A n × n matrix is principally unimodular if, for any set of indices J ⊆ {1, . . . , n}, all minors obtained by removing the rows and columns corresponding to J are 0, ±1. This last family of matrices arise in the context of adjacency matrices and is defined by Akbari et al. in [START_REF] Akbari | On unimodular graphs[END_REF]. Generally, principally unimodular matrices are not totally unimodular (an example is the matrix

   1 1 1 0 1 -1 0 1 1   )
, but in the case of adjacency matrices [START_REF] Akbari | On unimodular graphs[END_REF].

Diophantine equations and lattices

Now, we introduce some results from elementary number theory concerning linear Diophantine equations and lattices. The relation between these two concepts and unimodularity has been well studied, and our aim is to clarify a part of this connection.

According to Schrijver [START_REF] Schrijver | Theory of linear and integer programming[END_REF]Chapter 4], most of the theory developed on lattices and Diophantine equations is attributed to Hermite and Minkowski. These equations, named after the ancient Greek mathematician Diophantus, involve finding integer solutions to polynomial equations. Diophantine equations also pose challenges in real-world applications.

Undoubtedly, the most famous Diophantine equation is Fermat's last theorem.

Diophantine equations are equations, typically polynomial, in two or more unknowns with integer coefficients, for which the only solutions of interest are the integer ones. A Diophantine equation is linear if all monomials have degree 1.

A lattice is a set given by integer combinations of a family of vectors of Q n . For a set of vectors V we denote as lattice(V ) = { v∈V λ v v : λ v ∈ Z for all v ∈ V } the corresponding lattice. For a matrix A we denote as lattice(A) the lattice generated by its columns.

Up to scalar multiplication, rational matrices can be seen as integer ones. Thus, the following theorem give us sufficient and necessary condition for a system of linear Diophantine equations to have solutions for any integer right-hand side.

Theorem 1.47 (Section 4.1, [START_REF] Schrijver | Theory of linear and integer programming[END_REF]). Let A be an integer m × n matrix of full row rank. Then the following are equivalent: the greatest common divisor of the nonzero minors of A of order m is 1;

the system Ax = b has an integer solution x, for each integer vector b;

for each vector y, if yA is integer, then y is integer.

In the case of unimodular matrices Theorem 1.47 certifies the existence of infinite solutions for any associable system of linear Diophantine equations having integer right-hand side. Anyway does not explicitly provide the form of the solution set. Finally, we can exploit the connection between Diophantine equations, lattices and unimodular matrices.

Theorem 1.48 (Section 4.1, [START_REF] Schrijver | Theory of linear and integer programming[END_REF]). Let A be a nonsingular matrix of size n. Then the following are equivalent:

A is unimodular;

A -1 is unimodular; lattice(A) = Z n .
We conclude this section with another result of Heller readjusted in the context of equimodularity.

Theorem 1.49 (Heller [40]). Let A be a full row rank matrix. Then A is equimodular if and only if for each base B of A lattice(B) = lattice(A).

Smith normal forms

In the same chapter dedicated to Diophantine equations, Schrijver introduce ( [59, Section 4.4]) the so called Smith normal form, whose existence implies the widely known algebraic result of Kronecker stating that each finite abelian group is the direct product of cyclic groups.

Smith [START_REF] Smith | On systems of linear indeterminate equations and congruences[END_REF] proved that any rational matrix can be reduced to a unique rational matrix of the form D 0 0 0 , where D is a nonsingular diagonal matrix whose nonzero entries d 1 , . . . d l are such that d i > 0 for all i and d 1 |d 2 | . . . |d l . We call such a matrix Smith normal form. Note that, for a rational matrix A, l = rank(A). Moreover, for every rational matrix A of rank l and for every 1 ≤ i ≤ l the product d 1 . . . d i is the greatest common divisor of all minors of order i. For this reason the elements d 1 , . . . d l are called elementary divisors of A. More details on the Smith normal form are available in [START_REF] Schrijver | Theory of linear and integer programming[END_REF]Section 4.4], while a recent survey on its applications in combinatorics is [START_REF] Stanley | Smith normal form in combinatorics[END_REF].

In [START_REF] Grossman | On the minors of an incidence matrix and its smith normal form[END_REF], the authors explicitly exhibit the Smith normal form of any incidence matrix.

Theorem 1.50 (Grossman et al. [START_REF] Grossman | On the minors of an incidence matrix and its smith normal form[END_REF]). The elementary divisors of an incidence matrix of a connected graph on n vertices are

d 1 = • • • = d n-1 = 1, d n = 2.

Preliminaries on algorithms and complexity

Informally, when students think about the complexity of a problem, they often ask questions like "how difficult is it to solve?" However, these questions are tricky because they lack a precise definition and can have different answers depending on the considered aspects. A more appropriate question would be, "given a specific method to solve a problem, how much time is needed to solve any possible instance?" However, in complexity theory one of the main tasks is finding evidence and simpler answers, such as "yes" or "no", related to specific properties. These types of problems are known as decision problems.

Our work focuses more on geometric and combinatorial aspects. However, our results also have complexity implications, as they have enabled us to derive the complexity of several problems. Hence, we now present certain basics of complexity theory we use to state our complexity results. For further reading on complexity, we recommend the book [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. In this section, we provide an introduction to the fundamental concepts of this branch of computer science, with many classical results based on the work of Cook [START_REF] Cook | The complexity of theorem-proving procedures[END_REF], Edmonds [START_REF] Edmonds | Covers and packings in a family of sets[END_REF], and Karp [START_REF] Karp | Reducibility among combinatorial problems[END_REF].

Counterintuitively to what some readers might expect, despite the finite number of solutions to combinatorial optimization problems, the time required to find a solution can often increase dramatically with respect to the size of the problem.

A problem can be defined as a query with various input parameters, for which we seek an appropriate answer. To define a problem, we provide a general description of its parameters and establish a set of properties that a solution must satisfy. By assigning specific values to the input parameters, we create an instance of the problem.

On the other hand, an algorithm is a finite set of rules designed to find (and possibly facilitate the computation of) a solution for every instance of a given problem. Each rule requires executing a specific number of operations, which may occur repeatedly based on the computational state. We refer to an operation as elementary if its execution time can be bounded by a constant value. Examples of elementary operations include arithmetic calculations and data exchange between entities. The execution of an algorithm results in a sequence of elementary operations. The size of an instance refers to the total amount of data needed to accurately describe the instance itself.

An algorithm whose instances have size n is said to be in O(f (n)) (big O with respect to f ) if the number of elementary operations required to solve any instance is bounded from above by kf (n) for all n ≥ n 0 , where k is a constant and n 0 in Z ≥0 . When f is a polynomial, we say that the algorithm is polynomial. If for a given problem there exists a polynomial algorithm designed to solve it, this problem is polynomial-time solvable.

A decision problem belongs to the complexity class NP (NP stands for Nondeterministic Polynomial algorithms) if the answer "yes" can be certificate in polynomial time. Similarly, a decision problem belongs to the complexity class co-NP if the answer "no" can be certificate in polynomial time. It is worth noting that having a polynomial algorithm to find a solution implies having a polynomial certificate that answers "yes" or "no," but it is uncertain if the converse is true. Polynomial algorithms belong to NP∩co-NP, but it is not known if the two classes coincide.

A decision problem P 1 is polynomial reducible to another one P 2 if there exists a polynomial algorithm which produces an instance of P 2 for every instance I of P 1 whose answer is "yes" if and only if the answer to I is "yes".

Among the NP (co-NP) problems, the ones considered the most challenging to solve are called NP-complete (co-NP-complete), where a problem being NP-complete (co-NP-complete) if all NP (co-NP) problems are polynomial reducible to it.

At this point it looks clear that polynomial algorithms do not primarly aim to solve decision problems, they precisely seek for a solution, thus, they can also "exhibit properties". In Garey-Johnson's book, the kind of problems for which we are looking for a solution for a given instance are called search problems. So, as for decision problems we need to define the complexity of an algorithm looking for a solution of a search problem (a minimization problem for instance). NPhard problems are a class of computational problems that are at least as difficult as the hardest problems in the class NP. In other words, solving an NP-hard problem would allow us to solve any problem in NP efficiently.

An NP-hard problem is considered computationally challenging because it usually requires an exponential amount of time to solve as the input size increases. These problems often involve optimization or decision-making tasks that seek the "best" or "optimal" solution among a large number of possibilities.

A useful example of an NP-hard problem for this manuscript is integer linear optimization. Integer linear optimization involves optimizing a linear objective function subject to a set of linear constraints, where the variables must take on integer values. Intuitively, solving integer linear problems is NP-hard because the set of integer solutions might be extremely small compared to the set of fractional ones.

For completness, we provide two widely known examples of well-known integer linear optimization problems that are also NP-hard. However, we will not treat them in the subsequent chapters.

Traveling Salesman Problem (TSP): Given a set of cities and their pairwise distances, the TSP asks for the shortest possible route that visits each city exactly once and returns to the starting city. Finding the optimal solution to the TSP becomes increasingly difficult as the number of cities grows, making it an NP-hard problem.

Graph Coloring Problem: Given an undirected graph, the graph coloring problem aims to assign colors to the vertices of the graph such that no two adjacent vertices share the same color, using the fewest number of colors possible. Determining the minimum number of colors needed to color a graph is an NP-hard problem.

These examples illustrate the complexity and difficulty of NP-hard problems, as they often require exhaustive search or sophisticated algorithms to find optimal solutions.

Chapter 2

Equimodularity of graph matrices 2.1 Generalities on totally equimodular matrices 2.1.1 Operations preserving and destroying (total) equimodularity

The operations that we will analize are well studied in the case of total unimodularity. For total unimodularity all results positively hold and an interested reader can check it on the Schrijver's book [START_REF] Schrijver | Theory of linear and integer programming[END_REF]. On the contrary, several operations considered here do not preserve total equimodularity.

Elementary operations

The operations treated here are known as elementary operations.

Theorem 2.1. The following operations over a matrix preserve equimodularity:

1. permuting rows or columns; 2. multipling a row or column by -1;

3. adding an all-zero row or column; 4. adding the row ±χ i ; 5. repeating a row or column.

Proof. 1. Recall that for any matrix A, every row (resp. column) permutation is obtained by left (resp. right) multiplication with a permutation matrix applied to A. Moreover, if P is a permutation matrix, then det(P ) = sign(π), where π is a permutation uniquely identified by P .

From the well-known Binet's formula, we have det(P A) = sign(π) det(A) (resp. det(AP ) = det(A)sign(π)) for every permutation matrix P .

2. Recall that the determinant of a matrix is a multilinear operator with respect to its rows and columns. That is, for every matrix A, det

α 1 A 1 , . . . , α n A n = α i • . . . • α n det(A)
, and the same holds for rows. Therefore, multiplying a row or a column of an equimodular matrix by -1, it results in a change of sign for some minor. However, this change in sign does not affect the equimodularity of the matrix, as the definition concerns only absolute values.

3. Recall that any maximal submatrix that contains an all-zero row or column is singular, meaning its determinant is zero. Thus, adding an all-zero row or column to an equimodular matrix does not affect the equimodularity of the matrix, as all new minors obtained are zero.

Let M be a maximal submatrix of A =

A χ i , where A is an n × m equimodular matrix. If M does not include column A i , then its determinant is zero, since M n+1 is an all-zero row by construction. Otherwise, if M includes A i , employing Laplace's rule to compute the determinant over the n+1 row, which has a unique nonzero entry by construction, yields

| det(M )| = | det(M )|,
where M is a maximal submatrix of A. Thus, the equimodularity of A follows from the one of A, since all its maximal minors have the same absolute value of those of A.

5. We establish this only for the case of repeating a column as similar consideration applies to achieve the same result for repeating a row. Let M be a maximal submatrix of A = A A i , where A is equimodular. If M is nonsingular, then it does not contains any repeated columns, and, by construction, there exists a maximal submatrix M of A such that M = M P , where P is a permutation matrix. Finally, by 1, all maximal nonzero minor of A have the same determinant absolute value. Since total equimodularity is nothing but the equimodularity of every subset of rows, we have the following.

Corollary 2.2. The operations of Theorem 2.1 preserve total equimodularity.

Other basic operations

We recall that the operation of pivoting a matrix is replacing the matrix

α b c D with α -1 α -1 b -α -1 c D -α -1 cb ,
where α is a nonzero scalar, b and c are vectors, and D a matrix of appropriate size.

Pivoting preserves total unimodularity [59, Section 19.4], but does not preserve total equimodularity.

Example 2.3. The matrix

A =      1 1 0 1 1 1 0 1 1 1 1 0 0 0 1 1     
, is totally equimodular. Note that by partitioning A with the notation used for defining pivoting we have: α = 1, D is the canonical form of C 3 , and b and d have been chosen by duplicating the first row and first column of D respectively.

The pivoting of A is the matrix

à =      1 1 0 1 -1 0 1 -1 -1 0 1 -1 0 0 1 1      .
The last two rows of à form a nonequimodular matrix, since

-1 1 0 1 = -1 while 1 -1 1 1 = 2.
Thus, Ã is not totally equimodular.

Another classical matrix operation is taking the transpose of a given matrix. However, if A is an n × m, with m ≥ n, equimodular matrix, the matrix A has full row rank if and only if n = m. Consequently, this case lacks substantial interest. On the contrary, the study of total equimodularity can be more justifiable.

Example 2.4 shows that taking the transpose does not preserves totally equimodular matrices.

Example 2.4. To conclude this list, we consider the operation corresponding to 4. of Theorem 2.1 but for columns. That is adding to a given equimodular matrix the column ±χ i . Example 2.5 shows that this operation does not preserve equimodularity.

Let A = M 1 M 2 N 1 N
Example 2.5. Let A be an n × n minimally nontotally unimodular, then | det(A)| = 2, and every column of A has an even number of 1s, by Theorem 1.46. By Laplace's rule for determinant calculation, | det

A 1 . . . A n-1 χ i | = | det A 1 . . . A n-1 |
, where A j is obtained from A j by removing the i-th entry. By definition of minimally nontotal unimodularity,

det A 1 . . . A n-1 = ±1.
Thus, the matrix A χ i is not equimodular.

Matrix compositions: 1-sum and 2-sum Total unimodularity is preserved under the following matrix compositions which are used for recognizing in polynomial time whether a given matrix is totally unimodular [START_REF] Schrijver | Theory of linear and integer programming[END_REF].

The 1-sum or direct sum of two matrices A and B is the matrix having A and B as blocks The 1-sum preserves totally equimodularity on the contrary to the 2-sum.

in the principal diagonal, that is A 0 0 B .
Theorem 2.6. The direct sum of two equimodular matrices is an equimodular matrix.

Proof. Any base of the direct sum A 0 0 B is of the form M 0 0 N , where M and N are bases of A and B respectively, and its determinant is det(M ) det(N ). Since A and B are equimodular, the determinant absolute value depends on A and B, and not on the specific choice of the respectively bases.

Since the total equimodularity of a matrix is nothing but the equimodularity of every set of linearly independent rows, we have the following.

Corollary 2.7. The direct sum of two matrices preserves total equimodularity. Unlike the direct sum, the 2-sum does not preserve total equimodularity, as we show in the subsequent Example 2.8.

B = 1 1 1 -1 is the matrix 1 1 1 0 1 -1 which is not equimodular as 1 1 0 1 = 1 and 1 1 1 -1 = -2.
It is worth noting that this example can be generalized to any pair of equimodular matrices where matrix A occupies the lower right corner, and matrix B occupies the upper left corner.

Determinants of totally equimodular matrices

In this section we talk about various matricial properties of total equimodularity. We first introduce the family of Hadamard matrices whose are ±1-matrices with strong geometric properties. However, even if in small dimension many Hadamard matrices are total equimodular we show an infinite family of them not being totally equimodular. Then we discuss about determinants and corresponding bounds of totally equimodular matrices. We show that certan bounds are atteined and a connection with dyadic polyhedra arise.

Hadamard matrices

A well-known family of ±1-matrices is the Hadamard matrices, where being a Hadamard matrix means that the rows (resp. columns) are mutually orthogonal. Thus, a matrix H of size n is Hadamard if H H = nI n . Certain Hadamard matrices are relevant in data processing [START_REF] Horadam | Hadamard matrices and their applications[END_REF]. The Hadamard's inequality states that det(A) ≤ A 1 . . . A n , for every squared matrix A such that |A i j | ≤ 1 for all i and j. The Hadamard's inequality is tight if and only if A is Hadamard and the right-hand side is n n/2 . Hadamard matrices already appeared in the classical work of Sylvester [START_REF] Sylvester | Thoughts on inverse orthogonal matrices, simultaneous signsuccessions, and tessellated pavements in two or more colours, with applications to newton's rule, ornamental tile-work, and the theory of numbers[END_REF] in 1867, where he noted that in the case of a ±1-matrix H whose rows are mutually orthogonal, then the matrix H H H -H has the same properties. Matrices of this kind are called Sylvester-Hadamard.

Up to sign multiplication and permutaion of rows and columns, every Hadamard matrix of size greater or equal than 4 has

M =      1 1 1 1 1 -1 1 -1 1 1 -1 -1 1 -1 -1 1     
, which is a totally equimodular matrix, as a submatrix [START_REF] Seberry | The maximal determinant and subdeterminants of ±1 matrices[END_REF].

However, one can check that the Sylvester-Hadamard matrix obtained by imposing H = M is not totally equimodular.

As this composition can be repeated an arbitrary number of times, we have the following. Theorem 2.9. There exists an infinite family of Sylvester-Hadamard matrices that are not totally equimodular.

Determinants and total equimodularity

First, we investigate the matricial connection between totally equimodular matrices and total unimodularity. Theorem 2.10. A totally equimodular matrix is totally unimodular if and only if its maximal minors are ±1.

Proof. (⇒) Follows by definition of totally unimodularity.

(⇐) We equivalently prove that if A is full row rank and totally equimodular, then all minors are bounded by ±1. Let B be a base of A. Since A is a 0, ±1-matrix, det(B) = k det(B ), where k is an appropriate integer depending on the row chosen for developing the determinant, and B a base of the completion of A to such a row. Since det(B) = 1, then |k| = | det(B )| = 1.

On the contrary to the general case that we will present in Corollary 2.26, the latter theorem gives a first tractable case for finding a maximal minor of a total equimodular matrix.

Continuing in the same vein, we want to enrich the understanding of the structure of totally equimodular matrices. A part of the results here illustrated has been gently shared by Roland Grappe which is writing a paper on this subject with Patrick Chervet.

Let A = α b c D , the Gauss-Jordan pivoting of A is the matrix A = 1 α -1 b 0 D -α -1 cb .
Observation 2.11. Gauss-Jordan pivoting preserves equimodularity.

Proof. Recall that adding or subtracting a row to another one do not affect the value of the determinant. Thus, since Gauss-Jordan pivoting is nothing but sign multiplication and adding or subtracting 1 b to all rows for which c i = 0, all basis of the new matrix have the same determinant absolute value of the old ones. Lemma 2.12 (Chervet, Grappe). Let A = α b c D be an equimodular matrix with α = 0. Then, the submatrix D -α -1 cb of the Gauss-Jordan pivoting of A is equimodular.

Proof. Let M be a base of the Gauss-Jordan pivoting of A with column index I, with 1 ∈ I, and

N the submatrix of M . That is, N is a base of D. Then, det(N ) = α -1 det(M ) = sign(α) det(M ).
Let M be base of A columns I \{1}∪{j} for some j not in I. Then, we can apply Gauss-Jordan pivoting with respect to some nonzero entry of A j on M to find the corresponding submatrix, say N , of D. Since changing a column per time we can retrieve all bases of D -α -1 cb , we conclude that they have the same determinant absolute value. By Lemma 2.12 applied to every subset of linearly independent rows we can derive the corresponding result for total equimodularity. Corollary 2.13 (Chervet, Grappe). Gauss-Jordan pivoting preserves total equimodularity.

The subsequent theorem is a nice and nontrivial generalization of Theorem 2.22 which is specific for incidence matrices.

Theorem 2.14 (Chervet, Grappe). The determinant of a nonsingular totally equimodular matrix is a power of ±2.

Proof. Let A be a totally equimodular matrix. We prove it by induction over the number of rows. By Gauss-Jordan pivoting A, the submatrix A = D -cb is totally equimodular by Corollary 2.13. Thus, for every row of A nonzero entries are equal up to the sign. Moreover, they rise by adding or subtracting a 0, ±1-vector to another, and hence for any row the entries are 0, ±1 or 0, ±2. When the entries are 0, ±2, we can divide the row by 2 (preserving total equimodularity), and we denote the matrix obtained from A by normalizing all entries as A".

Finally, | det(A)| = 2 p | det(A")| = 2 p+q , where p is the number of rows that we had to divide by 2, while | det(A")| = 2 q by induction.

Throught this set of results they also proved the following. Theorem 2.15 (Chervet, Grappe). Recognizing whether a given nonsingular matrix is totally equimodular can be done in polynomial-time.

Generally, determining if a matrix is totally equimodular is a co-NP problem, since it suffices to show that a given full row rank submatrix is nonequimodular. Since decomposition techinques for matrices usually refers to finding certain proper submatrices with certain minimality or maximality properties, Corollary 2.26 lead me to believe that the general case is hard.

Conjecture 2.16. Recognizing whether a given matrix is totally equimodular is co-NP-complete.

Note that from the proof of Theorem 2.14 we can also deduce that a trivial upper bound for the maximal possible value of the determinant of a total equimodular matrix is 2 n(n-1)/2 , where n is the size of the matrix. This follows from the multilinearity of the determinant and the fact that we can apply pivoting at most n -1 times and, at iteration i, we have to divide by 2 at most n -i -1 rows. Hence, the exponent is the sum of all numbers from 1, . . . , n -1.

However, such bound cannot be tight, since 2 n(n-1)/2 is strictly greater than n n/2 for all n ≥ 2, which is the upper bound of given by the Hadamard's inequalities, which is valid for determinants of matrices whose entries are rationals between -1 and 1.

Total equimodularity and dyadicness

We now briefly establish a connection between total equimodularity and dyadicness. Theorem 2.17 (Abdi et al. [START_REF] Abdi | Total dual dyadicness and dyadic generating sets[END_REF]). Let A be a matrix such that all minors absolute values are a power of 2. Then the polyhedron {x : Ax ≤ b} is dyadic.

Thanks Theorem 2.17, Theorem 2.14 creates a connection between box-TDIness and total dual dyadicness.

Corollary 2.18. Let P = {x : Ax ≤ b}. Then, P is dyadic if A is totally equimodular.

Smith normal form

We end this section by giving a weak formulation of the Smith normal form of a totally equimodular matrix.

Theorem 2.19. Let A be a totally equimodular matrix. Then, the elementary divisors of A are powers of 2. Moreover, for every 1 ≤ i ≤ rank(A) there exists set I of row indices with |I| = i such that for every base

B of A I , det(B) = d 1 . . . d i .
Proof. Follows directly by Theorem 2.14 and definition of greatest common divisor. Finding the Smith normal form of a given matrix can be done in polynomail-time [START_REF] Schrijver | Theory of linear and integer programming[END_REF]Section 4.4]. This imply the following.

Corollary 2.20. The lower bound among the maximal minors of a totally equimodular matrix can be found in polynomial-time. Moreover, this lower bound is d 1 . . . d l , where l is the rank of the matrix.

Equimodularity and total equimodularity of incidence matrices

In this section, we characterize when the incidence matrix of a graph is totally equimodular. Since total equimodularity is not preserved under taking the transpose, this section is divided in two parts: edge-vertex incidence matrices and vertex-edge incidence matrices. Odd circuits are involved in the value of the determinants of incidence matrices.

Theorem 2.21 (Grossman et al. [START_REF] Grossman | On the minors of an incidence matrix and its smith normal form[END_REF]). For a connected graph G with n vertices and n edges,

| det(A G )| is equal to 0 if G is bipartite, and 2 otherwise.
Theorem 2.21 arises from the observation that, since G is connected, it has precisely one circuit. Consequently, the determinant (in absolute value) of its incidence matrix depends on the parity of this circuit. In the same work, Grossman et al. characterize all minors of an incidence matrix.

Theorem 2.22 (Grossman et al. [START_REF] Grossman | On the minors of an incidence matrix and its smith normal form[END_REF]). Let G be a graph. Then the absolute value of every nonzero minor of A G is a power of 2 and, for every 0 ≤ k ≤ τ (G), there exists a minor of A G with absolute value 2 k . Furthermore, Theorem 2.22 can be employed to retrieve a well-known result that characterizes bipartite graphs, commonly recognized as Hoffman and Kruskal's Theorem [START_REF] Hoffman | Integral Boundary Points of Convex Polyhedra[END_REF].

Theorem 2.23 (Hoffman et al. [START_REF] Hoffman | Integral Boundary Points of Convex Polyhedra[END_REF]). The incidence matrix of a graph is totally unimodular if and only if the graph is bipartite.

In our proofs, we will utilize the following lemma (which is a specific instance of Example 2.5) to prove that a matrix lacks equimodularity. Lemma 2.24. For an odd circuit C, the matrix A C χ u , for some u ∈ V (C), has full row rank but is not equimodular.

Proof. Reordering the rows and the columns of A C χ u , we may assume that the matrix is as follows.

           1 1 1 1 . . . . . . 1 1 1 1 1            A C χ u
Since C is an odd circuit, | det(A C )| = 2, hence A C χ u has full row rank. Moreover, the last |C| columns form a lower triangular matrix with 1s on the main diagonal, thus they have determinant 1. Therefore, the matrix is not equimodular.

Edge-vertex incidence matrices

Recall that the edge-vertex incidence matrix of a graph is totally unimodular if and only if the graph is bipartite. This extends to all graphs as follows in the more general context of total equimodularity.

Theorem 2.25. The edge-vertex incidence matrix of a graph is totally equimodular.

Proof. Let G = (V, E) be a graph and let M be a full row rank matrix formed by a subset of k rows of the edge-vertex incidence matrix of G. Let us prove that M is equimodular by induction on its number of rows: the base case is when M has one row, and then M is equimodular since a row has only values in {0, 1}. The matrix M encodes a subgraph H = (V, F ) of G with k = |F | edges.

We The column of u in M contains a single one, in uv's row, where v is the neighbor of u in H. Let M be the matrix obtained from M by removing uv's row. Note that M has full row rank since M has it. A nonsingular k × k submatrix N of M has to contain at least one of u and v, as otherwise it has only zeros in uv's row. When N contains exactly one of them, then develop with respect to uv's row. When N contains both of them, then develop with respect to u's column. In both cases, the determinant of N is equal to a maximal nonzero minor of M , up to the sign. By the induction hypothesis, M is equimodular, so all these determinants are equal in absolute value. Therefore, so are the nonzero k × k determinants of M , and M is equimodular.

In [START_REF] Grossman | On the minors of an incidence matrix and its smith normal form[END_REF], the authors proved that the problem of determining the maximum absolute value of a minor of a given incidence matrix is NP-hard. Hence, Theorem 2.25 implies the following.

Corollary 2.26. Determining the maximum absolute value of a minor of a totally equimodular matrix is NP-hard.

As a consequence of Corollaries 2.26 and 2.18, we have the following (note that this result can be immediately retrieved using Theorems 2.22 and 2.17).

Corollary 2.27. Determining the maximum absolute value of a minor of a matrix describing a dyadic polyhedron is NP-hard.

Vertex-edge incidence matrices

In contrast to edge-vertex incidence matrices, vertex-edge incidence matrices of graphs are rarely totally equimodular. We characterize below the classes of graphs for which they are. We also characterize when these matrices are equimodular. Note that when the graph G is bipartite the incidence matrix of G does not have full row rank by Theorem 2.21. Otherwise, the absolute value of the determinant of a square incidence matrix is 2 k , where k ≥ 1 is the number of vertex-disjoint odd circuits [START_REF] Grossman | On the minors of an incidence matrix and its smith normal form[END_REF]. Therefore, to get an equimodular vertex-edge incidence matrix, one should forbid the existence of maximal submatrices whose corresponding subgraph has multiple vertex-disjoint odd circuits. It turns out that it is an equivalence, as proved below.

Theorem 2.28. The vertex-edge incidence matrix of a connected nonbipartite graph G = (V, E) is equimodular if and only if G has no two vertex-disjoint odd circuits.

Proof. Note that every maximal nonsingular submatrix of a vertex-edge incidence matrix induces a spanning subgraph of G having |V | edges. Since a spanning tree of G has |V | -1 edges, this subgraph contains a circuit.

(⇒) Suppose that G has two vertex-disjoint odd circuits C 1 and C 2 , and let e 1 and e 2 be edges of C 1 and C 2 , respectively. Since G is connected, there exists a spanning tree T of G containing (⇐) Suppose that G is not bipartite and has no two vertex-disjoint odd circuits. Note that since G is connected, it contains a nonbipartite connected spanning subgraph H with |V | edges. By Theorem 2.21, we have | det(A H )| = 2 and A G has full row rank. This holds for every nonbipartite connected spanning subgraph with |V | edges. The other spanning subgraphs of G with |V | edges are either connected and bipartite or a product of smaller minors corresponding to connected subgraphs. In the first case, the associated minor is zero by Theorem 2.21. In the second case, by Theorem 2.21 and the fact that G has no two vertex-disjoint odd circuits, one of these smaller minors is zero. Therefore, every maximal minor of A G belongs to {-2, 0, 2}, and A G is equimodular. Theorem 2.28 gives a characterization of graphs with more than one vertex-disjoint odd circuit in terms of equimodularity. A graph-theorethic characterization of these graphs was given by Lovász [START_REF] Seymour | Matroid minors[END_REF] (a proof can be found in [START_REF] Kawarabayashi | A simpler proof for the two disjoint odd cycles theorem[END_REF]), and they also appear in the context of extended formulations [START_REF] Conforti | Extended formulations for stable set polytopes of graphs without two disjoint odd cycles[END_REF] and unimodular covers [START_REF] Haase | Existence of unimodular triangulations -positive results[END_REF]. In particular, since equimodularity can be tested in polynomial time [START_REF] Chervet | Box-total dual integrality, box-integrality, and equimodular matrices[END_REF], Theorem 2.28 provides another polynomial-time algorithm for their recognition [START_REF] Kawarabayashi | Odd cycle packing[END_REF].

C 1 ∪ C 2 \ {e 1 , e 2 }.
Theorem 2.29. The vertex-edge incidence matrix of a connected graph G = (V, E) is totally equimodular if and only if G is an odd hole or a bipartite graph.

Proof. (⇒) Suppose that G is neither bipartite nor an odd hole. Then, G contains an odd hole C and two edges uv and uw in C and δ(V (C)), respectively.

The submatrix of A G restricted to the rows associated with V (C) can be reordered such that the first |C| + 1 columns form the matrix A C χ u . By Lemma 2.24, it has full row rank but is not equimodular. This implies that A G is not totally equimodular. (⇐) If G is bipartite, then A G is totally unimodular by Theorem 2.23, and hence totally equimodular. Now, if G is an odd hole, then A G is also the edge-vertex incidence matrix of an odd hole, and hence is totally equimodular by Theorem 2.25. By Theorem 2.29, deciding whether a vertex-edge incidence matrix is totally equimodular can be done in polynomial time. This might be a first step towards the complexity of recognizing totally equimodular matrices, which is an open problem raised in [START_REF] Chervet | Box-total dual integrality, box-integrality, and equimodular matrices[END_REF].

Complexity consequences

In this section, we study the complexity of some fundamental questions regarding box-totally dual integral (box-TDI) polyhedra. First, although box-TDI polyhedra have strong integrality properties, we prove that Integer Programming over box-TDI polyhedra is NP-complete, that is, finding an integer point optimizing a linear function over a box-TDI polyhedron is hard. Second, we complement the result of Ding et al. [START_REF] Ding | The complexity of recognizing linear systems with certain integrality properties[END_REF] who proved that deciding whether a given system is box-TDI is co-NP-complete: we prove that recognizing whether a polyhedron is box-TDI is co-NP-complete.

Quasi-bipartite graphs

The definition of bipartite graphs can be generalized as follows. A graph G is quasi-bipartite if for each odd circuit C of G, the graph G \ V (C) has at least one isolated vertex. These graphs characterize the box-TDIness of the system given in the following theorem, where K 4 denotes the complete graph with 4 vertices. Theorem 2.30 (Ding et al. [START_REF] Ding | The complexity of recognizing linear systems with certain integrality properties[END_REF]). Given a connected graph G, the system

A G x ≥ 1, x ≥ 0 is box-TDI if and only if G is a quasi-bipartite graph different from K 4 .
Remark 2.31. In [START_REF] Ding | The complexity of recognizing linear systems with certain integrality properties[END_REF], the definition of quasi-bipartite graphs differs from our, since they consider cycles instead of circuits. Indeed, Ding et al. define quasi-bipartite graphs as precisely those graphs for which the deletion of the vertices of any odd cycle produce a connected component which is an isolated vertex. Thus, the family that we are considering is a subfamily of the one described by Ding et al. as one can see in Figure 2.1. In fact, if one conseider all the edges of the graph labeled with b), they form an odd cycle, say C. By deleting V (C) no isolated vertex arise; that is, the two notions differs to parallel edges. However, the complexity class of the two recognition problems is the same, since removing all parallel edges is strictly polynomial. When talking about box-TDIness of polyhedra we have to keep in mind that the main point are equimodular face-defining matrices, thus, our choice of redefining this class of graphs is a consequence of 5. of Theorem 2.1. In what follows, we provide several complexity results based on the characterization of total equimodularity of incidence matrices devised in the previous section.

Edge relaxation of the stable set polytope

Given a graph G = (V, E), a stable set is a set of pairwise nonadjacent vertices. The polytope {x ∈ R V : A G x ≤ 1, x ≥ 0} is called the edge relaxation of the stable set polytope of G and its integer points are precisely the characteristic vectors of the stable sets of G.

By Theorems 1.37 and 2.25, every polyhedron of the form {x ∈ R V : A G x ≤ b} with b rational is box-TDI. As adding x ≥ 0 preserves box-TDIness, we have the following.

Corollary 2.32. The edge relaxation of the stable set polytope is box-TDI.

Since finding a maximum stable set in a given graph is NP-hard [START_REF] Karp | Reducibility among combinatorial problems[END_REF], Corollary 2.32 implies that integer programming over a box-TDI polyhedron is NP-hard.

Corollary 2.33. Given a box-TDI polyhedron P and a cost vector c, finding an integer point x maximizing c x over P is NP-hard.

Edge relaxation of the edge cover dominant

Since multiplying a row by -1 preserves total equimodularity, by Theorems 1.37 and 2.29, when G is an odd hole or a bipartite graph, the polyhedron {x ∈ R E : A G x ≥ 1} is box-TDI. It turns out that the converse holds.

Theorem 2.34. Given a connected graph G = (V, E), the polyhedron {x ∈ R E : A G x ≥ 1} is box-TDI if and only if G is an odd hole or a bipartite graph. Proof. To prove the reverse direction, suppose that G is neither an odd hole nor a bipartite graph. Let us build a subgraph H = (V, F ) of G for which the polytope is not box-TDI. Since

{x ∈ R F : A H x ≥ 1} is the projection onto F of {x ∈ R E : A G x ≥ 1} intersected with the box {x e = 0, for all e ∈ E \ F }, this will imply that {x ∈ R E : A G x ≥ 1} is not box-TDI.
Since G is connected, it contains an odd hole C with δ(V (C)) nonempty. Denote by U the set of vertices of V \ V (C) whose neighbors are all in V (C). Let S be a subset of δ(U ) such that each vertex of U is covered by exactly one edge of S. Let F = (E \ δ(U )) ∪ S and H = (V, F ) (Figure 2.2 illustrates the given partition of the graph for C = C 7 ).

Let M be the |V (C)| × |F | matrix formed by the rows of A H associated with the vertices of V (C). By considering the columns of M associated to C and an edge of δ(V (C)), observe that M contains a matrix of the type A C χ u for some u ∈ V (C). Therefore, by Lemma 2.24, M has full row rank but is not equimodular.

We now show that M is face-defining for a face of P = {x ∈ R F : A H x ≥ 1}. Since M has full row rank, by Observation 1.36 it is sufficient to exhibit |F | -|V (C)| + 1 affinely independent points of the face Q = P ∩ {x : M x = 1} of P . Let K = F \ (C ∪ δ(C)), we define:

p 0 = 1 2 χ C + χ S∪K + 1 2 u∈V (C) |δ(u) ∩ S|(χ Lu -χ C\Lu ),
where L u is the unique perfect matching of the path C \ δ(u). Then, we define two types of points:

p e = p 0 + χ e ,
for each e ∈ K,

q uv = p 0 + χ uv + 1 2 (χ Lu -χ C\Lu ), for each uv ∈ δ(V (C)) with u ∈ V (C).
Together with p 0 , the points p are affinely independent because p e -p 0 = χ e , for each e in K. Adding the points q maintains affine independency since q uv is the only point with uv's coordinate different from 1.

Moreover, all these points belong to Q since they satisfy x(δ(u)) = 1 for all u ∈ V (C) and x(δ(v)) ≥ 1 for all v ∈ V \ V (C). To see this, note that for each u in V (C), χ Lu -χ C\Lu satisfies x(δ(u)) = -2 and x(δ(v)) = 0 for all v = u. The number of points

p is |K| + 1 = |F | -|V (C)| -|δ(V (C))| + 1
and the number of points q is |δ(V (C))|, hence M is a face-defining matrix of P .

The matrix M is nonequimodular and face-defining for a face of P . Therefore, the latter is not box-TDI by Theorem 1.34, and neither is {x ∈ R Given a graph G = (V, E), an edge cover is a set of edges covering each vertex. The polytope {x ∈ R E : A G x ≥ 1, x ≥ 0} is called the edge relaxation of the edge cover dominant of G and its binary points are precisely the characteristic vectors of the edge covers of G.

E : A G x ≥ 1}. C H U V \ (U ∪ V (C)) . . . . . .
By Theorem 2.34, the edge relaxation of the edge cover dominant of an odd hole or a bipartite graph is box-TDI. The converse does not hold, because adding x ≥ 0 might cut off faces defined by nonequimodular matrices, such as the one given in the proof of Theorem 2.34. The following result gives the larger class of graphs to be considered to get the converse. Proof. Let P G denote the edge relaxation of the edge cover dominant of G. (⇐) By Theorem 2.30, if G is a quasi-bipartite graph different from K 4 , then the system

A G x ≥ 1, x ≥ 0 is box-TDI, hence P G is box-TDI.
If G is an odd hole, P G is the intersection of the polyhedron stated in Theorem 2.34 with the box {x : x ≥ 0}. Theorem 2.34 and the definition of box-TDI polyhedra imply that P G is box-TDI.

(⇒) Let us show that P K4 is not box-TDI. By definition, P K4 = {x : A K4 x ≥ 1, x ≥ 0}, where

A K4 =      1 1 1 0 0 0 1 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1      .
The full row rank matrix formed by the last three rows of A K4 , say B, is not equimodular because the determinant of the first three columns is 1, whereas that of the last three is 2. Moreover, the four points z 1 = (1, 0, 0, 0, 0, 1) , z 2 = (0, 1, 0, 0, 1, 0) , z 3 = (0, 0, 1, 1, 0, 0) and z 4 = (1, 1, 1, 0, 0, 0) belong to P G , satisfy Bx = 1, and are affinely independent. Therefore, by Observation 1.36, B is a face-defining matrix of P K4 . This implies that P K4 is not box-TDI by Theorem 1.34.

To complete the proof there remains to show that P G is not box-TDI when G is neither quasibipartite nor an odd hole. In this case, there exists an odd circuit C such that G\V (C) is nonempty and has no isolated vertices. If C has a chord e, then C ∪ {e} contains a smaller odd circuit C . Since C \ C is a path of length at least two, G \ V (C ) has no isolated vertices. Therefore, we may assume that C is an odd hole.

Let M be the submatrix of A G formed by the rows associated with the vertices of V (C). By construction, δ(V (C)) is nonempty, hence M contains A C , χ u , for some u ∈ V (C). By Lemma 2.24, M is not equimodular.

We show that M is a face-defining matrix of P G . Since M has full row rank, by Observation 1.36 it is sufficient to exhibit |E| -|V (C)| + 1 affinely independent points of the face F = P G ∩ {x : M x = 1} of P G . We exhibit the same points as in the proof of Theorem 2.34, the difference is that, here, the set U is empty since there are no isolated vertices when removing V (C):

p 0 = 1 2 χ C + χ K ,
p e = p 0 + χ e , for each e ∈ K,

q uv = χ uv + χ Lu + χ K , for each uv ∈ δ(V (C)) with u ∈ V (C).
As shown in the proof of Theorem 2.34, these points are affinely independent and satisfy A G x ≥ 1, M x = 1. Since these points also satisfy x ≥ 0, they belong to the face P G ∩{x : M x = 1} for which M is a face-defining matrix. By Theorem 1.34, P G is not box-TDI. Theorem 2.35 implies that recognizing box-TDI polyhedra is co-NP-complete since recognizing quasi-bipartite graphs is [START_REF] Ding | The complexity of recognizing linear systems with certain integrality properties[END_REF].

Corollary 2.36. Recognizing box-TDI polyhedra is co-NP-complete.

Equimodularity and total equimodularity of adjacency matrices

Symmetric matrices often possess stronger properties than others. They form algebraic groups and also possess unique decomposition techniques. Even more, 0, 1-matrices often preserve very rare structures, so one might expect that the class of totally equimodular adjacency matrices might represent a more interesting and vast case than totally equimodular vertex-edge incidence matrices. However, despite these facts, we demonstrate that adjacency matrices are rarely totally equimodular. Furthermore, characterizing when the adjacency matrix of a given bipartite graph is totally equimodular or totally unimodular remains an open problem.

In this section when the incidence matrix of a circuit is mentioned, it is always considered in canonical form. Furthermore, to prove that the adjacent matrix of a graph G is not totally equimodular, we will generally exhibit an induced subgraph H of G whose adjacent matrix is not totally equimodular. We then introduce the following observation. Its proof is based on Observation 1.1 and the definition of totally equimodular matrices.

Observation 2.37. Let H be a graph whose adjacent matrix is not totally equimodular. Then, the adjacent matrix of any graph containing H as an induced subgraph is not totally equimodular.

Akbari et al. [START_REF] Akbari | On unimodular graphs[END_REF], characterize the total unimodularity of the adjacency matrix (note that the equivalence between 1. and 3. directly follows by applying the 1-sum to Observation 1.3). Theorem 2.38 (Akbari et al. [START_REF] Akbari | On unimodular graphs[END_REF]). Let G be a graph. The following are equivalent:

1. A G is totally unimodular; 2. A G is principally unimodular;

The bipartite representation of G is totally unimodular.

The following result can be retrieved by reordering the columns as we do in many proofs of this section and by applying the well-known formula to compute the determinant of a block matrix.

Theorem 2.39 (Akbari et al. [START_REF] Akbari | On unimodular graphs[END_REF]). The determinant absolute value of

A Cn is 1 if n ≡ 4 0, is 2 if n is odd, and is 4 if n ≡ 4 2.

Operations on graphs that preserve total equimodularity

From now on, we will exploit the fact that a circuit corresponds to a planar graph, by following a clockwise order on the vertices. This will allow us to highligth structure similarities between adjacency matrices and incidence matrices.

Adding twins

Theorem 2.40. Let G = (V, E) be a graph and H be the graph obtained from G by adding a twin, say v, of a vertex u ∈ V . Then, A H is totally equimodular (resp. totally unimodular) if and only if A G is.

Induced circuits congruent 2 mod 4 Lemma 2.47. Let I ⊆ {1, . . . , n} containing 1, such that n -|I| is even and for each couple p, q ∈ I, such that p and q are consecutive with respect to I, then p-q is odd. Then, the determinant of the n × n matrix D(I, n) = χ I , χ {1,2} , . . . , χ {n-1,n} is 1 if n is odd and 0 otherwise.

Proof. We prove it by induction over n. When n = 1, then I = {1} and D({1}, 1) = 1 , thus det(D({1}, 1)) = 1. Let the statement be true for every positive integer k ≤ n -1, with n > 1. We prove it for n by calculating the determinant of D(I, n) by using the Laplace's rule over the last row.

Let m be the maximum in I. When n = m, then there are precisely two nonzero entries in the last row of D(I, n): the first one and the last one. By definition, the complement matrix of (⇒) Let G = (V (C n ), C n ) and H the graph obtained by adding a star s to G. Theorem 2.44, implies that d(s) ≥ 2. Since A H is totally equimodular, by Theorem 2.44 and Observation 2.37, no hole of length k ≡ 4 0 and different from G is induced by the vertices of H. Thus, if s is not a twin, every hole different from G in H has length divisible by 4. Hence, H is bipartite.

D(I, n) 1 n in D(I,
We prove that A H is not totally equimodular by proving that the bipartite representation B H has full row rank but it is not equimodular. Let indexing clockwise from 1 to n all vertices of V (C n ) starting from a vertex adjacent to s, while indexing s by 0. Let us sort the columns by the increasing order of the even indices and the rows by the odd one, by construction, B H has size n/2 × (n/2 + 1). Moreover, the first n columns of B H form a matrix belonging to the family D(S, n 2 ) of Lemma 2.47, where S is the set of indices such that χ S = (B H ) 1 . In fact, the distance between two vertices j and i adjacent to 0 and contiguous, in the sense that for a vertex k for which j ≤ k ≤ i then k ∈ N (s), is always a multiple of 4 by Theorem 2.44 as stated before. Since n ≡ 4 2, n 2 is odd and det(D(S, n

2 )) = 1. The last n columns form the matrix A C n 2 whose determinant absolute value is 2, since n 2 is odd. Thus, B H has full row rank but it is not equimodular, that is B H and A H are not totally equimodular.

Corollary 2.49. Let s be a star for C n , with n ≡ 2 mod 4. Then, A Cn∪{s} is totally equimodular if and only if either C n ∪ {s} is a circuit with a twin. Induced circuits congruent 0 mod 4 It can be observed that all the graphs illustrated in Figure 2.3 are closed Eulerian and contains C 6 as a subgraph (generally, not induced). This aligns with the results summarized by Padberg [START_REF] Padberg | Total unimodularity and the euler-subgraph problem[END_REF], which we report here.

A matrix A is Eulerian if 1 A = 0 (mod 2) and A1 = 0 (mod 2). Examples of Eulerian matrices are the incidence matrices of circuits of any length. Eulerian matrices characterize total unimodularity as follows.

Theorem 2.50 (Camion [8]). A 0, ±1-matrix is totally unimodular if and only if it contains no nonsingular Eulerian submatrix.

Note that Theorem 2.50 generalize many results of this chapter. Nevertheless our results are more focused in graph structures.

Another statement from the same paper best fits our purpose.

Theorem 2.51 (Padberg [START_REF] Padberg | Total unimodularity and the euler-subgraph problem[END_REF]). A 0, ±1-matrix is totally unimodular if and only if for every Eulerian submatrix A , 1 A 1 = 0 (mod 4).

Corollary 2.52 (Padberg [START_REF] Padberg | Total unimodularity and the euler-subgraph problem[END_REF]). Let G be a bipartite graph containing no closed Eulerian subgraph of length congruent 2 mod 4. Then, A G is totally unimodular.

Corollary 2.52 immediately gives the following.

Corollary 2.53. Let G be a bipartite graph which is opened Eulerian. If all circuits have length congruent 0 mod 4 and do not share any edge, then A G is totally unimodular.

The converse of Corollary 2.52 does not hold as one can see in the subsequent example.

Example 2.54. The bipartite representation of G can be expressed as follows:

B G =    1 1 0 1 1 1 0 1 1    .
Through direct calculation, it can be verified that B G is totally unimodular. To conclude, we allocate space to two conjectures that pertain more generally to totally equimodular matrices. These conjectures arise from the counterexamples here discussed and the corollaries mentioned above.

Conjecture 2.55. The bipartite representation of a closed Eulerian bipartite graph is minimally nontotally unimodular if and only if it has a circuit of length congruent 2 mod 4 as a subgraph.

Conjecture 2.56. The adjacency matrix of a bipartite graph obtained by adding a star to C 4n , with n positive integer, is totally unimodular if and only if it contains no induced circuit of length congruent 2 mod 4.

Note that the sufficiency of Conjecture 2.56 is a consequence of Theorem 2.44. While the necessity is way harder. However, an approach to tackle the proof would be as follows.

Let us write the bipartite representation of such a graph as follows:

B = A C2n χ N (s) .
By Lemma 2.47, the submatrix obtained by removing the first column from B is totally unimodular and has no full row rank. Theorem 2.43 implies that the submatrix, obtained by removing the last column is a totally unimodular matrix, and it has no full row rank by Theorem 2.22. Thus, B has no maximal minor different from zero.

Additionally, it seems fair to state that every nonmaximal submatrix of B can be seen as a submatrix of these two or of another graph on less vertices respecting the same hypothesis. If this latter part can be proven to be true, then B would be totally unimodular.

Adjacency matrices of nonbipartite graphs

We end this chapter by characterizing the graphs for which the adjacency matrix is totally equimodular.

Complete graphs

Lemma 2.57. The adjacency matrix of a complete graph having more than 3 vertices is not totally equimodular.

Proof. Let K n be the complete graph on n vertices. Note that, for all n ≥ 5, K 4 is induced by every 4-tuple of vertices in K n . Thus, by Observation 2.37, to prove the statement it suffices to show that A K4 is not totally equimodular. Let us write A K4 as

     0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0      .
The matrix A formed by the last three rows of A K4 is not equimodular, since | det

A 1 A 2 A 3 | = 1 and | det A 2 A 3 A 4 | = | det A C3 | = 2.
Thus, A K4 is not totally equimodular.

Since cliques are induced subgraphs we have the following.

Corollary 2.58. The adjacency matrix of graph having a clique on four or more vertices is not totally equimodular.

Chapter 3

Polyhedral properties of perfect matchings

Affine Hull of Perfect Matchings

This section introduces the perfect matching polytope and its corresponding affine hull. We begin by presenting classical results primarily attributed to Edmonds, Lovász, and Pulleyblank, which provide insights into the dimension of this affine hull. We then introduce a matrix termed the PMP-matrix, which serves as a natural extension of the vertex-edge incidence matrix within the context of matching covered graphs. Indeed, a PMP-matrix of a graph G augments the vertex-edge incidence matrix of G by including rows corresponding to some nontrivial tight cuts. Furthermore, when G is solid, the column decomposition with respect to a base of a PMP-matrix encodes one or more weighted walks having as extremities those of the corresponding edge (similarly to the vertex-edge incidence matrix). In the second part, we outline the chosen description for this polytope and complement the result of de Carvalho et al. [START_REF] De Carvalho | The perfect matching polytope and solid bricks[END_REF] on solid graphs.

The dimension of the affine hull of perfect matchings

Let F be a maximal family of laminar tight cuts having the odd cycle property of a matching covered graph G = (V, E). We recall that a family of laminar tight cuts have the odd cycle property, if any chosen sequence of contractions with respect to this family brings to a nonbipartite matching covered graph (that is all graphs in the list raised by the contraction process are nonbipartite).

Naddef proved [START_REF] Naddef | Rank of maximum matchings in a graph[END_REF] that the matrix whose rows are associated with the trivial tight cuts and F has full row rank. Lovász proved [START_REF] Lovász | Matching structure and the matching lattice[END_REF] that for a matching covered graph, the maximum number of linear independent perfect matchings is

|E| -|V | -|F | + 1.
The aforementioned works lead us to refer to the matrix associated with the system A G x = 1, A F x = 1, where the rows of A F are the characteristic vectors of the elements of F , as the PMPmatrix of G with respect to F . Sometimes we will simply say a PMP-matrix of G without specifing the associated family of tight cuts. We will better legitimize this definition in the following section (note that a PMP-matrix of G in this context is a natural extension of its incidence matrix). Finally, we reformulate this result of Lovász keeping in mind the importance of finding facedefining matrices for studying box-TDIness as follows.

Theorem 3.1. For a matching covered graph G, every PMP-matrix of G is face-defining for the affine hull of the perfect matchings. In other words, Observation 3.2, states that the equimodularity of the PMP-matrix does not depend on the family of tight cuts chosen for the tight cut decomposition.

A first property of the PMP-matrix is due to Theorem 1.8 and the definition of tight cut that give the following. Observation 3.3. Let G be a matching covered graph and F be a family of laminar tight cuts having the odd cycle property which is maximal inclusion-wise. Moreover, let F ⊆ F the family tight cuts inherited from G after contracting a set of vertices U such that δ(U ) ∈ F . Then, the PMP-matrix of G/U with respect to F is a submatrix of the one of G with respect to F .

Perfect matching polytope

Here, we restrict ourselves to a brief introduction of the perfect matching polytope which, for necessity, will become, along with its description for certain graph classes, the pivotal argument of this chapter.

The perfect matching polytope of a graph G = (V, E), denoted by P PM (G), is the convex hull of the incidence vectors of all perfect matchings of G. The system

       x(δ(U )) ≥ 1, for each U ⊆ V, with |U | ≥ 3 odd, A G x = 1, x ≥ 0, (3.1)
describes P PM (G) as proved in [START_REF] Edmonds | Maximum matching and a polyhedron with 0,1-vertices[END_REF].

Perfect matching polytope of solid graphs

To investigate the box-TDIness of the perfect matching polytope, an understanding of the class of solid graphs becomes essential for comprehending the problem's structure. In this context, we demonstrate that when a graph is solid, the description of the perfect matching polytope becomes simpler, compact as for bipartite graphs. Note that, a similar result cannot be found for all graphs, in fact, the perfect matching polytope cannot be described by a compact formulation [START_REF] Rothvoss | The matching polytope has exponential extension complexity[END_REF].

It is well-known that the perfect matching polytope of a bipartite graph can be characterized by the equalities corresponding to trivial tight cuts and trivial inequalities, as referenced in [START_REF] De Carvalho | On a conjecture of lovász concerning bricks: I. the characteristic of a matching covered graph[END_REF]. (For a more comprehensive understanding of the perfect matching polytope of bipartite graphs, we recommend [START_REF] Lovász | Matching theory[END_REF]). The authors in [START_REF] De Carvalho | The perfect matching polytope and solid bricks[END_REF] also characterize the class of matching covered graphs for which the perfect matching polytope can be described using the same inequalities. This outcome emerges as a specialized instance of Theorem 3.5.

Theorem 3.4 (de Carvalho et al. [START_REF] De Carvalho | The perfect matching polytope and solid bricks[END_REF]). The perfect matching polytope of a near-brick is described by the system A G x = 1, x ≥ 0 if and only the corresponding brick is solid.

Following the outline of their proof of Theorem 3.4, we characterize the matching covered graphs for which the perfect matching polytope is described by a PMP-matrix. Our result extends Theorem 3.4 to all matching covered graphs. Theorem 3.5. Let A be a PMP-matrix of a matching covered graph G. Then,

P PM (G) = {x : Ax = 1, x ≥ 0} if and only if G is solid.
Proof. (⇒) Suppose that G is not solid. Then, there exists a separating cut C which is not tight, and hence a perfect matching M of G such that |M ∩ C| > 1. By Lemma 1.17, since C is separating, for every edge e there exists a perfect matching M e for which |M e ∩ C| = 1. Then,

let p = 1 |M |-1 (( e∈M χ Me ) -χ M ). By construction, p ∈ {x : Ax = 1, x ≥ 0}, where the equality holds since x(δ(v) ∩ ( e∈M )) = |M |. But, p χ C < 1, hence p ∈ P PM (G).
(⇐) Suppose that {x : Ax = 1, x ≥ 0} has a non integer vertex p. Let C be the family of the odd cuts such that the associated inequality cuts off p, and M the family of all perfect matching of G. Let δ(U ) be a cut in C such that there exists no cut

C ∈ C for which |C ∩ M | ≤ |δ(U ) ∩ M | for all M in M and |C ∩ M | < |δ(U ) ∩ M | for some M ∈ M . Note that by definition of C , δ(U )
is not a tight cut. Theorem 3.9. Let G be a matching covered graph having k bricks. Moreover, let Ĝi , for i = 1, . . . , k be the graphs obtained from the graphs resulting from a near-brick decomposition of G by removing all vertices obtained by contraction. If all Ĝi are nonbipartite, then, for every PMPmatrix, there exists a maximal minor of absolute value equal to 2 k i=1 τ ( Ĝi) .

Proof. We prove it by induction over the number bricks. When k = 1, G is a near-brick, and, hence every PMP-matrix reduce to A G . Since G is a near-brick no vertex has to be removed. By Theorem 2.22, there exists a maximal minor absolute value equal to 2 τ (G) .

Suppose that G has k > 1 bricks and that the statement is true for all matching covered graphs with at most k -1 bricks. Let U be a minimal inclusion-wise shore with respect a family of laminar tight cuts, say F , of G having the odd cycle property and being maximal inclusion-wise.

By Observation 3.3, if A is the PMP-matrix of G with respect to F , then A = A 0 D A G[U ]
,

where A is the PMP-matrix of G/U associated with F \ δ(U ) and D an appropriate 0, 1-matrix. It is worth noting that the sum k i=1 τ ( Ĝi ) is a lower bound for the odd tulgeity of G, since Ĝi is a subgraph of G for every i. However, finding the odd tulgeity of a graph is a well-known NP-hard problem [START_REF] Grossman | On the minors of an incidence matrix and its smith normal form[END_REF].

By Corollary 1.15, G[U ] is nonbipartite. Moreover, if v is the vertex of G/(V \ U ) after contracting V \ U , G[U ] = G/(V \ U ) \ {v}
The following example highlight the necessity of requiring all Ĝi in Theorem 3.9 to be nonbipartite.

Example 3.10. We prove that any PMP-matrix of G has no maximal minors of absolute value equal to 4 (that is 2 τ (G) ), where G is the graph of Figure 3 Lastly, by Theorem 2.22, since a PMP-matrix is a 0, 1-matrix, we have the following. Theorem 3.11. Let G be a matching covered graph. Then, for every PMP-matrix of G, there exists a maximal minor absolute value which is an integer multiple (possibly zero) of 2 τ (G) .

The Smith normal form of a PMP-matrix

Inspired by the result of Grossman et al. [START_REF] Grossman | On the minors of an incidence matrix and its smith normal form[END_REF], we aim to describe the Smith normal form of a PMPmatrix of a nonbipartite graph, as the case of bipartite graphs coincide with the one presented in [START_REF] Grossman | On the minors of an incidence matrix and its smith normal form[END_REF].

Let G = (V, E) be a nonbipartite matching covered graph with k bricks and F a maximal Let M be a base of a PMP-matrix and G[M ] be the corresponding structure counting vertices, edges and cuts encoded in M . That is, G[M ] is the triplet (V , E , F ), such that the elements of V ⊆ V and those of F correspond to the vertices of G and the cuts of F indexing the rows of M respectively, while the elements of E correspond to the edges of E indexing the columns of M . Please note that G[M ] is generally neither matching covered nor a graph. Indeed, when a column of M has precisely one 1 associated with a vertex, it corresponds to what we call half-edge. If the 1s in the columns are exclusively associated with nontrivial tight cuts of G we refer to them as ghost edges. Of course, it is not appropriate to claim that the inherited cuts from G are tight as G[M ] is not matching covered. Our conclusions are solely drawn from the fact that G[M ] has no particular properties beyond rising from a matching covered graph, which forms our underlying hypothesis. Lastly, up to ghost edges, we focus exclusively on the case of a connected G[M ], as extending it to the disconnected case is straightforward.

First, let consider the case when G[M ] is a graph, possibly enriched with the inherited cuts.

That is, there exists a subfamily of cuts F with respect to the one chosen for the tight cut decomposition of G, indexing some rows of M . We prove over the number of bricks that det(M ) is even. If k = 1, every PMP-matrix equals A G , thus, the statement is true by Theorem 1.50. Let us suppose that G has k > 1 bricks. In the case that F = ∅, M represents a base of A G , and we conclude the argument by applying Theorem 1.50. Now, assuming F = ∅, we proceed to expand the determinant using the Laplace's rule on a row of M corresponding to a cut in F . This process results in a signed summation of minors obtained by sequentially deleting columns, representing edges in the cut. This approach yields a collection of graphs, which may have multiple connected components enriched by nontrivial cuts. If necessary, we can repeat this process for other cuts. Importantly, these graphs arise from matching covered graphs with strictly fewer than k bricks.

As a result, the determinant becomes a recursively signed summation over minors corresponding to these graphs, whose connected components respect the induction hypothesis. Consequently, all these minors are even, leading to the conclusion that (*) det(M ) is even. Now we consider the case when G[M ] is not a graph; that is, G[M ] has at least one half-edge or a ghost edge.

We develop the determinant in a manner similar to the previous case, noting that during the process, when a half-edge pertains precisely to a single cut of the subgraph obtained in the sequence, it can be treated as an edge with one of its endpoints being the cut.

It is also important to note that since M is square and k-1 (the size of a maximal incusion-wise family of tight cuts of G having the odd cycle property) is strictly smaller than |V |, all nonzero minors correspond to graphs without half-edges or ghost edges, which arise from matching covered graphs with strictly fewer than k bricks.

Consequently, applying the previously established (*), we conclude that det(M ) is even.

Perfect matchings and box-total dual integrality

Several notable works have been published on the perfect matching polytope, including the previously mentioned works of Naddef [START_REF] Naddef | Rank of maximum matchings in a graph[END_REF], Edmonds et al. [START_REF] Edmonds | Brick decompositions and the matching rank of graphs[END_REF], Lovász [START_REF] Lovász | Matching structure and the matching lattice[END_REF], and the more recent work by de Carvalho et al. [START_REF] De Carvalho | The perfect matching polytope and solid bricks[END_REF].

In the first two papers, the authors presented efficient algorithms for determining the dimension of the affine hull of perfect matchings in a given graph. In the third paper, Lovász provided a description of the lattice of perfect matchings. In the fourth paper, de Carvalho et al. characterized the class of graphs for which the perfect matching polytope is described by trivial inequalities and the inequalities associated with trivial cuts. However, to the best of our knowledge, besides the bipartite case, the box-TDIness of this polytope remains unknown.

In this context, we begin by revisiting a result by Cunningham and Marsh [START_REF] Cunningham | A primal algorithm for optimum matching[END_REF] concerning the TDIness of Edmonds' system that describes the matching polytope. This result implies that the problem of identifying a box-TDI system describing the perfect matching polytope can be reduced to identifying the graphs for which the perfect matching polytope is box-TDI.

Following this, we demonstrate that Lovász's ear decomposition [START_REF] Lovász | Matching structure and the matching lattice[END_REF] cannot effectively characterize the box-TDIness of the perfect matching polytope. Furthermore, in the subsequent subsections, we provide a characterization of when the perfect matching polytope of a near-brick is box-TDI and offer substantial insights on how to extend this result to all matching covered graphs.

A TDI system for the perfect matching polytope

In Section 3.1.2 we described the perfect matching polytope by using the system 3.1. However, the perfect matching polytope can be described also by the system

       x(E(U )) ≤ (|U | -1)/2, for each U ⊆ V with |U | ≥ 3 odd, A G x = 1, x ≥ 0, (3.2)
which is obtained by setting to equality the inequality corresponding to the trivial cuts of the well-known Edmonds' system [START_REF] Edmonds | Maximum matching and a polyhedron with 0,1-vertices[END_REF].

Cunningham and Marsh [START_REF] Cunningham | A primal algorithm for optimum matching[END_REF] proved that the Edmonds' system is always TDI, hence so is System 3.2. However, in what follows, we will use System 3.1 to study the box-TDIness of the perfect matching polytope, despite the fact that System 3.1 often is not TDI (even in the special case of a perfect matching polytope which is box-TDI). One example is the following.

Example 3.14. Consider the problem of minimizing the linear function w = 1 subject to the system 3.1 for K 4 . Then, the dual problem describes the maximum stable set subject to the edge relaxation of the stable set polytope, whose optimum 1 2 1 which, of course, is not integer. So System 3.1 is not TDI.

On the other hand, system 3.1 for K 4 can be reduced to x(δ(u)) = 1 for all u ∈ V (K 4 ) and nonnegativity constraints (because U = V \ {u}, for all U ⊆ V (K 4 ) for which |U | ≥ 3, and follows from the equality δ(U ) = δ(V \ U ), valid for any graph and subset of vertices U of V ).

Since K 4 has precisely three perfect matching, there is no hope to find a face-defining matrix which is a submatrix of A K4 .

One can check that A K4 is equimodular, thus, the affine hull of P PM (K 4 ) is box-TDI. Now, since being box-TDI is preserved by adding boxes, adding nonnegativity constraints preserves the box-TDIness. Thus, P PM (K 4 ) is box-TDI.

Fully odd subdivision and odd ears

Fully odd subdivision Theorem 3.15. Let H be a graph obtained from a graph G = (V, E) by replacing one edge with a path of length three. Then, P PM (H) is box-TDI if and only if P PM (G) is.

Proof. (⇒) We equivalently prove that if P PM (G) is not box-TDI, then neither is P PM (H). Since P PM (G) is not box-TDI, by Theorem 1.34, there exists a face-defining matrix M of P PM (G) which is not equimodular. Moreover, let uv be the edge of G replaced by the path (uu , u v , v v) in H. For every inequality of the form

x(δ(U )) ≥ 1 (3.3)
of the subsystem M x ≤ d of the system (3.1) for G, consider the inequality

x(δ(U )) ≥ 1, (3.4)
where U is (U ∪ {u , v })∪ if {u, v} ⊆ U and U otherwise. By construction, any inequality of this type belongs to the system (3.1) for H.

Let M x ≤ d be the subsystem of the system (3.1) for H obtained by considering all the inequalities of the form (3.4) for each inequality (3.3) together with the two inequalities associated with u and v . By construction, M is not equimodular, since the entries corresponding to the rows {u } and {v }, and the columns corresponding to uu and v v forms a 2 × 2 identity matrix that can be used to complement all bases of M which is not equimodular by assumption.

We prove that M is face-defining for a face of P PM (H). Briefly, the argument follows from a bijection between the perfect matchings of G and those of H.

Since M is a face-defining matrix of P PM (G), there exists a set S of size |E| -rank(M ) + 1 of affinely independents points of the face for which M is face-defining. As shown above M has full row rank and rank

(M ) = rank(M ) + 2. Since |E(H)| = |E(G)| + 2, it is sufficient to exhibit |E| -rank(M ) + 1 affinely independents points satisfying {x : M x = d } ∩ P PM (H). Let S = {x ∈ R E+2 : x e = x e , for each e ∈ E \ {uv}, x uu = x v v = 1 -x u v = x uv , for all x ∈ S}.
That is, S is obtained by augmenting every perfect mathing in S to a perfect matching of H by adding either the edges uu and v v or u v depending on the presence of uv. By construction, S is a family of incidence vector of matching of H such that M x = d for each x ∈ S and its element are affinely independent by construction. Thus, M is a face-defining matrix of P PM (H).

To conclude, M is not equimodular and is a face-defining matrix for P PM (H). Thus, P PM (H) is not box-TDI by Theorem 1.34.

(⇐) Following the definition one can check that, P PM (G) is the projection of P PM (H) over the space of the variables corresponding to E(H) \ {u v , v v} and then identifying uu with uv. Thus, if P PM (H) box-TDI, then so is P PM (G).

Adding an odd ear

Adding an odd ear is a fundamental operation characterizing matching covered graphs as stated in Theorem 1.14. Observation 3.16. Adding an odd ear to a graph is equivalent to adding an edge between the extremities of the corresponding ear and then replacing it with an odd path.

From Theorem 3.15, Observation 3.16, and by noting that adding edges preserves the nonbox-TDIness of the perfect matching polytope as every face-defining matrix of the original graph can be augmented by setting to zero the inequalities corresponding to the new edges, we have the following.

Corollary 3.17. Let H be a graph obtained from a graph G by adding an odd ear. Then, if P PM (H) is box-TDI, then P PM (G) is.

Proof. If G is obtained from G by adding an edge e, then if P PM (G) is not box-TDI because P PM (G) = P PM (G ) ∩ {x e = 0}. The result then follows from Observation 3.16 and Theorem 3.15.

The following example shows that the converse of Corollary 3.17 fails.

Example 3.18. P PM (C 4 ) = {x : A C4 x = 1, x ≥ 0} is box-TDI by Theorems 2.23 and 1.34, while P PM (C 6 ) is not, by Theorems 1.34 and 2.28, since the affine hull of P PM (C 6 ) equals {x :

A C6 x = 1, x ≥ 0}.
On the other hand, C 6 is obtained from C 4 by properly adding three odd ears. That is, the converse of Corollary 3.17 does not hold.

We briefly introduce two different and stronger possible assumptions, which we shall prove unfruitful right after, on the ear decomposition of a matching covered graph that might yield box-TDIness:

1. Example 3.18 is the smallest in terms of both the number of edges and vertices that can be considered. However, it begins with a bipartite graph and concludes with a nonbipartite one. Consequently, one might wondering if, for instance, fixing the number of bricks, might yield favorable results.

2. Since Theorem 1.14 weakly characterizes the sequence of steps to follow in order to obtain a specific matching covered graph by initiating from an edge, one might infer that the box-TDIness of matching covered graphs can be characterized through the utilization of forbidden nonbipartite odd minors 1 , where an odd minor of a graph G is a graph for which exists a fully odd subdivision being a subgraph of G. Furthermore, Example 1.16 shows that there are graphs having both K 4 and C 6 as odd minors. Therefore, one can speculate that if a matching covered graph has as odd minor one of these two but not both, then box-TDIness can hold.

The following example shows that the assumptions 1. and 2. do not hold. We begin by characterizing the total equimodularity of the PMP-matrices, which correspond to a graph class that is overly restrictive for identifying all box-TDI perfect matching polytopes. Indeed, it is not difficult to find examples of the latter, for which the corresponding PMP-matrices are not totally equimodular. In fact, the situation is even more drastic, as explained in Theorem 3.20 below.

By definition, all PMP-matrices contains the vertex-edge incidence matrix, and this matrix is not equimodular except in cases where the graph is odd intercyclic (as established in Theorem 2.28). This observation and Theorems 1.11 and 2.23 lead to the subsequent equivalences.

Box-TDIness of near-bricks

We remark that Corollary 3.6 implies that the perfect matching polytope of a bipartite graph is box-TDI, since the incidence matrix is totally unimodular (which is a well-known result, in fact, total unimodularity implies Corollary 3.6). The first intuition would urge that solid graphs are the best candidates for the study of the box-TDIness of the perfect matching polytope. Unfortunately, it turns out differently as we prove in the following.

Theorem 3.21. The perfect matching polytope of a near-brick is box-TDI if and only if it is odd intercyclic.

Proof. Let G = (V, E) be a near-brick.

(⇒) We equivalently prove that if G has two vertex-disjoint odd circuits, then P PM (G) is not box-TDI. Suppose that G contains two vertex-disjoint odd circuits. Since G is a near-brick, A G is a PMP-matrix. By Theorem 3.1, A G is face-defining for P PM (G), but it is not equimodular by Theorem 2.28. Thus, P PM (G) is not box-TDI by Theorem 1.34.

(⇐) Suppose that G is odd intercyclic. Then, by Observation 1.22 and Theorem 1.19, its brick is odd intercyclic, hence, is a solid graph. By Theorem 3.4 and Theorem 2.28, A G is an equimodular face-defining matrix of P PM (G). Thus, P PM (G) = {x : A G x = 1} ∩ {x : x ≥ 0} is box-TDI by Theorem 1.34 and definition of box-TDIness.

Box-TDIness implies odd intercyclic near-bricks

The following Example 3.22, which exhibits a solid near-brick whose brick is odd intercyclic but whose perfect matching polytope is not box-TDI, clarifies necessary conditions to extend Theorem 3.21 to all matching covered graphs. Indeed, several similar examples can be constructed by starting from an odd intercyclic brick, by "splitting" a vertex to a nontrivial barrier which might produce a new matching covered graph having more vertex-disjoint odd circuits.

Example 3.22. As observed in Section 1.1.2 the graph G of Figure 1.8 is a near-brick. As a consequence of Theorem 3.21, P PM (G) = {x : A G x = 1, x ≥ 0} is not box-TDI. Thus, Theorems 2.28 and 3.1 implies that P PM (G) is not box-TDI. However, as already noticed in the same section, the tight cut decomposition of G terminates by giving two elements: the brick W 5 and the brace C 4 . Theorem 3.21 implies that P PM (W 5 ) and P PM (C 4 ) are box-TDI.

Certainly, requiring the graph to be odd intercyclic is excessively restrictive as the perfect matching polytope of the graph illustrated in Figure 3.3 is box-TDI (for the proof we defer to Example 3.34). Proof. We prove by induction, over the number of bricks, that any PMP-matrix of P PM (G) is not equimodular, whenever there exists a near-brick of G that is not odd intercyclic. Consequently, P PM (G) is not box-TDI, by Theorems 3.1 and 1.34.

Similarly, we say that a walk (v 1 , e 1 , . . . , e k , v k+1 ) of a matching covered graph G is (F , Ω)weighted if there exists a maximal inclusion-wise family of laminar tight cuts with respect the odd cycle property F and a function ω from {e 1 , . . . , e k+1 } into Ω ⊆ Q such that ω(δ(v i )) = 0 for all i = 1, k + 1 and for all C ∈ F , ω({e 1 , . . . , e k+1 } ∩ C) = 1 if v 1 v k+1 ∈ C and 0 otherwise. Let v 1 v k+1 ∈ E(G) and suppose that k is odd, if ω is unique up to sign multiplication, we say that the v 1 , v k+1 -walk expresses the v 1 v k+1 .

Let G be a matching covered graph and F a maximal laminar family of tight cuts, and B be a base of a PMP-matrix of G. A base of G, denoted by G[B], is the subgraph of G whose edges corresponds to the columns of B whose structure is enriched with the tight cuts inherited from

F . That is, if δ(U ) ∈ F , then we consider the cut δ(U ∩ V (G[B])) of G[B].
Thus, as for the vertex-edge incidence matrix, since the only matrix to be considered for testing the box-TDIness of the perfect matching polytope is the PMP-matrix (Corollary 3.24), we have the following.

Second step towards box-TDIness: moonfish and very solid graphs

The moonfish graph In this section, we furnish an example that might provide a key lecture to solve the problem of characterizing the box-TDIness of the perfect matching polytope. Example 3.22 shows that the operation of "splitting" singletons into barriers might destroy the box-TDIness of the perfect matching polytope. However, this operation does not exclusively affect near-bricks and can be generalized to graphs having multiple bricks.

In Example 3.27, we demonstrate the case of a graph where any near-brick decomposition results in odd intercyclic near-bricks, yet its perfect matching polytope is not box-TDI.

Example 3.27. In Figure 3.4 a), we draw a graph that we call moonfish as it looks like the homonymous fish (see Figure 3.4 b)). Let G be the moonfish graph. One can check that G is matching covered. We first prove that the perfect matching polytope of G is not box-TDI. To do this, we show that its affine hull is not box-TDI, which suffices thanks to Theorem 1.34. Consider the system A G x = 1, x(C) = 1, x ≥ 0, where C = {e 1 , e 2 , e 3 , e 4 , e 5 , e 6 } is a tight cut having the odd cycle property. By Theorem 3.1, such a system is describing the affine hull of G, since as one can see in Figure 3.5 the two C-contractions are two near-bricks. Note that both C-contractions are odd intercyclic. Denote by A the PMP-matrix of this system and consider the spanning subgraphs of the moonfish graph of Figure 3.6. One can check that the matrices formed by the columns of A corresponding to the edges of the graph a) and those of the graph b) have determinant absolute value equals to 4 and 8 respectively. Since these two matrices are bases for A, A is not equimodular. Thus, P PM (G) is not box-TDI.

Another way to see that the perfect matching polytope of the moonfish graph is not box-TDI is that the graph in Figure 3.6 b) is not connected, that is, any edge of the moonfish graph having extremities in different connected components can be expressed only by using fractional weights. Thus, the PMP-matrix is not equimodular by Theorem 1.33. One can check that both possible near-bricks decomposition of the moonfish graph produce two odd intercyclic near-bricks. Thus, the converse of Theorem 3.23 does not hold. At this point, being box-TDI seems to be a property that is not due to the bricks of a matching covered graph neither to its near-bricks. Lastly, Theorem 1.10 implies that in order to establish the converse of Theorem 3.29, we require a theorem concerning barrier cuts that serves as the analogous counterpart to Theorem 3.29.

Conjecture 3.37. The perfect matching polytope of a matching covered graph G is box-TDI if and only if G is very solid.

Polyhedral variants and box-TDIness

In this section, we delve into various polyhedra associated with the perfect matching polytope and examine their box-TDIness. We start by introducing the concept of the matching polytope and summarizing the results of Ding et al. [28], which provide a characterization of the graphs for which the corresponding matching polytope is box-TDI. Subsequently, we shift our focus to the edge cover polytope, wherein we present several families of graphs. Within these families, we identify instances where the edge cover polytope exhibits box-TDIness and others where it does not. Notably, the perfect matching polytope is a face of both the matching and edge cover polytopes. However, it is important to note that neither the results obtained by Ding et al. [28] nor our results regarding the edge cover polytope offer sufficient conditions for the perfect matching polytope.

Lastly, we introduce the extendable matching polytope and we prove that this polytope is box-TDI if and only if the perfect matching polytope is.

Matching polytope

For the completeness of this compendium, we introduce the matching polytope along with two of its descriptions, one of which is minimal. For the minimal description we will also make reference to triangles, which denote cliques on three vertices, and factor-critical graphs, where a graph H factor-critical if H \ {v} has a perfect matching for each vertex v of H. Note that a graph G is factor-critical only if it has an odd number of vertices [START_REF] Lovász | Matching theory[END_REF].

Let G = (V, E) be a graph. The matching polytope of G, denoted by P M (G), is the convex hull of the incidence vectors of all matchings in G. The system

       x(E(U )) ≤ (|U | -1)/2, for each U ⊆ V with |U | ≥ 3 odd, A G x ≤ 1, x ≥ 0, (3.5)
describes P M (G) as proved in [START_REF] Edmonds | Maximum matching and a polyhedron with 0,1-vertices[END_REF] and is known as Edmonds system. Interestingly, Cunningham and Marsh proved in [START_REF] Cunningham | A primal algorithm for optimum matching[END_REF] that system (3.5) is TDI for any graph G.

Let I(G) = {v ∈ V : d(v) ≥ 3, or d(v) = 2
and v is contained in no triangle, or d(v) = 1 and the neighbor of v also have degree 1}, and

T (G) = {U ⊂ V : |U | ≥ 3, G[U ] is factor-critical and 2-connected}. The system        x(δ(u)) ≤ 1, for each u ∈ I(G), x(E(U )) ≤ (|U | -1)/2, for each U ⊆ T (G), x ≥ 0, (3.6)
is called the restricted Edmonds system for defining P M (G). In [START_REF] Pulleyblank | Facets of 1-Matching Polyhedra[END_REF] Pulleyblank and Edmonds show that all inequalities of the System (3.5) are nonnegative integer combinations of the ones of System (3.6). While Ding et al. [28] proved that for a given graph System (3.6) is box-TDI if and only if System (3.5) is.

Fully odd subdivision

For completeness and congruence with what follows, we show how the box-TDIness of the matching polytope behave with respect to the fully odd subdivision. The same result has been differently proved by Ding et al. [28]. However, our proof is based on geometric considerations.

Briefly, we show that the fully odd subdivision of a graph whose matching polytope is not box-TDI preserves it. To do this, we explicitly construct a face-defining matrix by adding the inequalities associated with the new vertices, and while doing this, we deduce a new family of good size of affinely independent points which complete the proof. Theorem 3.38. Let H be obtained from a graph G by replacing an edge with a path of length three. If P M (H) is box-TDI, then so is P M (G).

Proof. We equivalently prove that if P M (G) is not box-TDI, then neither is P M (H). Since P M (G) is not box-TDI, by Theorem 1.34, there exists a face-defining matrix M of P M (G) associated with the system (3.5) which is not equimodular. Let uv be the edge of G replaced by the path (uu

, u v , v v) in H. Let e∈E(U ) x e ≤ |U | -1 2 (3.7)
be an inequality of the subsystem M x ≤ d of System (3.5) for G. Then, the inequality

e∈E(U ) x e ≤ |U | -1 2 , (3.8)
where U is (U ∪ {u , v }) if {u, v} ⊆ U and U otherwise, belongs to System (3.5) for H. Let M x ≤ d be the subsystem of System (3.5) for H obtained from the one corresponding to M by considering the associated inequality (3.8) for each inequality (3.7), and the two inequalities associated with u and v . While, for the inequalities of the type x(δ(w)) ≤ 1 for any w ∈ V (G) we need to adjust the notation with respect to E(H) whenever u and v belong to N (w). Moreover, no change have to be made to the inequalities of the type 0 ≤ x e ≤ 1 whenever one of the sides is tight, but in the case e = uv, where we adjust the notation by replacing it with u v .

We prove that M is not equimodular. Since M is not equimodular there exist two nonsingular maximal submatrices of M with different determinants in absolute values, by complementing them with the 2 × 2 identity matrix corresponding to the rows of {u } and {v }, and the columns corresponding to uu and v v of M , we conclude that M is not equimodular.

We prove that M is a face-defining matrix of P M (H). Since M is face-defining for P M (G), there exists a set S of size |E| -rank(M ) + 1 of affinely independents points of the face for which M is face-defining. As shown before M has full row rank and rank(M ) = rank(M )+2, so it is sufficient to exhibit |E| -rank(M ) + 1 affinely independents points satisfying {x : M x = d } ∩ P M (H). Let S = {x ∈ R E+2 : x e = x e , for each e ∈ E \ {uv}, x uu = x v v = 1 -x u v = x uv , for all x ∈ S}. Thus, S is obtained by augmenting every mathing of G in S by adding either the elements uu and v v or u v depending on the presence of χ uv in S.

By construction, S is a family of incidence vectors of matchings of H such that M x = d for each x ∈ S and its element are affinely independent by construction. Thus, M is face-defining for P M (H).

To conclude, M is not equimodular and is a face-defining matrix for P M (H). Thus, P M (H) is not box-TDI by Theorem 1.34.

Proof. Since any Edmond's system is TDI, by Theorem 1.26, the restricted Edmonds system for H is box-TDI if and only if P M (H) is box-TDI. The proof follows by applying Theorem 3.38.

Note that the converse does not hold.

Adding an odd ear

From Observation 3.16 and by noting that adding edges preserves the nonbox-TDIness of the matching polytope as every face-defining matrix of the original graph can be complemented by setting the inequalities corresponding to the new edges to zero, we have the following.

Corollary 3.40. Let H be obtained from a graph G by adding an odd ear. If P M (H) is box-TDI, then so is P M (G).

The following example shows that the converse does not hold.

Edge cover polytope

We briefly describe the edge cover polytope and we immediate link it with the edge relaxation of the edge relaxation of its dominant introduced in Chapter 2.

The edge cover polytope of a graph G = (V, E), denoted by P EC (G), is the convex hull of the incidence vectors of all edge covers in G. The system

       x(δ(U ) ∪ E(U )) ≥ (|U | + 1)/2, for each U ⊆ V with |U | ≥ 3 odd, A G x ≥ 1 0 ≤ x ≤ 1, (3.9)
describes P EC (G) as proved in [START_REF] Edmonds | Matching: A well-solved class of integer linear programs[END_REF]. Theorem 3.43 (Ding et al. [START_REF] Ding | The complexity of recognizing linear systems with certain integrality properties[END_REF]). Let G be a graph. The polyhedron {x : A G x ≥ 1, x ≥ 0} is integer if and only if G is quasi-bipartite. (⇒) Let G be quasi-bipartite. P EC (G) ⊆ P follows by the definition of P EC (G). On the other hand, by Theorem 3.43, all vertices of {x : A G x ≥ 1, x ≥ 0} are binary points, hence, P is integer. Thus, P = P EC (G).

(⇐) Suppose that G is not quasi-bipartite. By Theorem 3.43, the polyhedron {x : A G x ≥ 1, x ≥ 0} has a fractional vertex, say x * . Note that x * ≤ 1 otherwise some line of the system A G x ≥ 1, x ≥ 0 are not tight. Then, x * belongs to P and it is a vertex of P . Hence, P is not integer which contradicts P EC (G) = P .

Fully odd subdivision

Theorem 3.45. Let H be a graph obtained from a graph G by replacing an edge with a path of length three. If P EC (H) is box-TDI, then so is P EC (G).

Proof. The proof is based on the one of Theorem 3.38 and we refer to the same notation applied to the inequalities of System (3.9).

We equivalently prove that if P EC (G) is not box-TDI, then neither is P EC (H). Similarly to the case of Theorem 3.38, we replace any row associated with any subset U of vertices such that {u, v} ∩ U = ∅, with U ∪ {u , v }. Moreover, we add the rows associated with {u } and {v }.

Note that the corresponding matrix, associated with the subsystem of System (3.9) for H, is not equimodular, since the entries corresponding to the rows {u } and {v }, and the columns corresponding to uu and v v forms a 2 × 2 identity matrix that can be used to complement the bases of M which is not equimodular by assumption.

To complete the proof, by the use of the same arguments, we can exhibit a good family of affinely independent points. Indeed, for each edge cover L of G we have an edge cover of H, when uv ∈ L, it contains the perfect matching {uu , vv }, otherwise the matching {u v } of the new path.

Adding an odd ear

Similarly to the case of the matching polytope, by Theorem 3.45 and Observation 3.16 we have the following. Corollary 3.46. Let H be a graph obtained from another graph G by adding an odd ear. If P EC (H) is box-TDI, then so is P EC (G).

Box-TDIness of the edge cover polytope

We start this section by proving that P EC (K 4 ) is not box-TDI. This result can be retrieved as follows: Observation 3.44, implies that the polyhedron obtained by adding the constraint x ≤ 1 to the edge cover dominant of K 4 is P EC (K 4 ). Thus, P EC (K 4 ) is not box-TDI by Theorems 1.31 and 2.35, since for quasi-bipartite graphs, the statement "edge relaxation" is irrelevant. However, for a sake of simplicity, we directly prove it by using the description of P EC (K 4 ).

Example 3.47. The P EC (K 4 ) is described by x(δ({u})) ≥ 1 for each u ∈ V (K 4 ), 0 ≤ x(e) ≤ 1 for each e ∈ E(K 4 ), by Observation 3.44. Let us order the rows and the columns A K4 as      1 1 1 0 0 0 1 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1

     .
The submatrix M of A K4 formed by the last three rows has full row rank but is not equimodular, since the first three columns form the identity matrix, while, the last three form the incidence matrix of K 3 which has determinant 2 in absolute value. Moreover, M is face-defining for P EC (K 4 ) because the corresponding vertices associated with the three perfect matchings of K 4 and the point χ {1,2,3} are affinely independent and |E(K We aim to find all graphs for which the edge cover polytope is box-TDI. To answer this question, it would be interesting to find a characterization based on forbidden structures such as minors, that is, subgraphs obtained by vertex or edge deletion, and edge contraction. Alternatively, by forbidding stronger structures such as induced subgraphs, or subgraphs, similarly to the work of Ding et al. [28] for the matching polytope.

The following example shows a graph whose edge cover polytope is box-TDI despite the fact it has an induced subgraph whose edge cover polytope is not box-TDI. inequalities and the trivial cuts that are tight with respect F ∩ (E \ E(B)). By construction, M has rank |V (B)| -1 + |E \ E(B)|, and has block structure (where the first block is the rectangular matrix M and the fourth block is the identity). Thus, M has full row rank but is not equimodular. By Observation 1.36, M is face-defining if and only if there exists |E(B)| -|V (B)| + 2 edge cover whose characteristic vectors are affinely independent. Lovász [START_REF] Lovász | Matching structure and the matching lattice[END_REF] proved that a brick with m edges and n vertices has precisely m -n + 1 perfect matchings whose characteristic vectors are affinely independent. Thus, for every perfect matching P of B there exists a unique edge cover P ∪ (F \ E(B)) of G. Furthermore, since every brick is 3-connected and bicritical, there exist two vertices, say u and u , in N (u) ∩ V (B) such that B \ {u , u } has a perfect matching, say P . Lastly, let G = W 5 \ {e}, where e is an edge of W 5 whose extremities are vertices of degree 3. By removing any triangle containing a vertex of degree 2 from G, one obtains a path of length 2, which means that G is not quasi-bipartite. Moreover, it contains no nonbipartite matching covered graphs. Indeed, one can see that the only nonbipartite matching covered graphs with 4 and 6 vertices are K 4 , C 6 , and W 5 .

Thus, G belongs to the class of graphs proposed in Conjecture 3.56 and does not satisfy the hypothesis of Theorem 3.48. However, we found a computational result stating that P EC (G) is box-TDI.

Extendable matching polytope

We conclude this section by introducing the extendable matching polytope of a graph. While this particular polytope is relatively less known, its connection with the box-TDIness of the perfect matching polytope makes it an interesting family of polytopes to delve into. Accordingly, we also provide a few more details about its description, since some readers may not be familiar with it.

Recall that a matching is extendable if there exists a perfect matching containing it. The extendable matching polytope of a graph G, denoted by P EM (G), is the convex hull of the characteristic vectors of the extendable matchings.

Interestingly, one can see that P EM (G) = (P PM (G) + R E ≤0 ) ∩ {x : x e ≥ 0}, that is P EM (G) is the submissive of P PM (G). Moreover, P EM (G) is the anti-blocking polyhedron of P PM (G) [START_REF] Cunningham | Dominants and submissives of matching polyhedra[END_REF].

The subsequent result is a special case of Theorem 1.23.

Compact description of the extendable matching polytope

We end this chapter by introducing a characterization problem that we found quite interesting.

Until recently, a compact description of the extendable matching polytope for graph classes other than bipartite ones [START_REF] Cunningham | Dominants and submissives of matching polyhedra[END_REF] had not been found. It is possible that, similarly to the perfect matching polytope, we can find a compact formulation for the extendable matching polytope of solid graphs. However, such conjecture looks hard to be proven. Even if we assume that a matching covered graph has a polynomial number of perfect matchings in relation to its number of vertices, since every subset of a perfect matching is extendable, the number of extendable matchings grows exponentially with the size of the graph (we will analize it precisely for the case of bicritical graphs). However, it is conceivable that the number of facets required to describe this growth could be polynomially related to the size of the graph. Consequently, we hope that considering an upper bound for the number of extendable matchings might hold a key to solving an easier version of this problem.

In this section, we introduce the concept of k-extendable matchings and their connection with matching covered graphs and edge connectivity. We also present a conjecture regarding solid bricks that are not 2-extendable, which aim to act as a first step toward a compact description of the extendable matching polytope for certains classes of graphs.

A graph is k-extendable if all matchings of size k are extendable to a perfect matching. Thus, matching covered graphs are nothing but 1-extendable graphs.

If G is a matching covered graph and C is a tight cut of G, it follows that every matching formed by a pair of edges from C is not extendable. In other words, any matching covered graph that is not a brick or a brace is not 2-extendable.

Conversely, Plummer proved that 2-extendable graphs with more than five vertices are either bicritical or elementary bipartite [START_REF] Plummer | On n-extendable graphs[END_REF]. Additionally, k-extendable graphs are also (k-1)-extendable and (k + 1)-edge-connected [START_REF] Plummer | On n-extendable graphs[END_REF]. As there are infinitely many k-extendable nonbipartite graphs, we can conclude that there are also infinitely many bricks that are k-extendable. Consequently, the extendable matching polytope of bricks features an extremely large number of vertices, despite the number of perfect matchings in a bicritical graph being polynomially bounded by the size of the graph [START_REF] Liu | The enumeration of near-perfect matchings of factor-critical graphs[END_REF].

Interestingly, every odd wheel and C 6 are not 2-extendable, while K 4 and the Möbius ladder of even order are 2-extendable. Notably, W 2n+1 contains precisely 2n + 1 perfect matchings [START_REF] Liu | The enumeration of near-perfect matchings of factor-critical graphs[END_REF]. Thus, the following conjecture represents a preliminary step towards characterizing the extendable matching polytope of solid bricks. Conjecture 3.63. A solid brick is not 2-extendable if and only if it is an odd wheel. Conjecture 3.64. There exists a compact formulation for the extendable matching polytope of solid bricks which are not 2-extendable.

We conclude this section by presenting another case that suggests that, at least for odd intercyclic near-bricks, the description of the extendable matching polytope proposed in [START_REF] Cunningham | Dominants and submissives of matching polyhedra[END_REF] may be simplified. Corollary 3.65. If G is an odd intercyclic near-brick, then P EM (G) is described by a 0, 1-matrix.

Proof. By Theorems 3.21 and 3.58, P EM (G) is box-TDI if and only if G is odd intercyclic. By Theorem 3.42, all nonzero entries of the matrix describing P EM (G) can be equal, up to the sign.

  .1 b) and d) are two bipartite graphs whose color classes are black and white. A connected graph is unicyclic if it has precisely one circuit (see Figure 1.1 b)). Graphs having the weaker property of having no two vertex-disjoint odd cycles are called odd intercyclic (see any graph of Figure 1.1).

Figure 1 . 1 :

 11 Figure 1.1: a) A tree; b) A bipartite graph; c) The complete graph K 5 ; d) The complete bipartite graph K 3,3 ; e) The odd wheel W 5 ; f) The Möbius ladder on 8 vertices.

Figure 1 . 2 :

 12 Figure 1.2: This figure refers to Example 1.2.

  A subset S of vertices of a graph G is a barrier if |O(G \ S)| = |S|, where for any graph O(•) denotes the family of connected components of odd cardinality. The cuts associated with the odd components of G \ S are called barrier cuts. Singletons are examples of barriers and we call them trivial barriers.

Figure 1 .SFigure 1 . 3 :

 113 Figure 1.3: A matching covered graph with a nontrivial barrier S.

Remark 1 . 7 .

 17 It is worth noting that if S is a barrier of a matching covered graph G, then, for every perfect matching M of G we have |M ∩ δ(S)| = |O(G \ S)|. Remark 1.7 gives a first hint on the importance of barriers and of barrier cuts.

Figure 1 . 4 :

 14 Figure 1.4: The brick decomposition of the graph G.

Figure 1 . 5 :

 15 Figure 1.5: The brick C 6 .

Figure 1 . 6 :

 16 Figure 1.6: (a) A barrier cut C with respect to the barrier B; (b) A 2-separation cut; (c) A tight cut which is not an ELP-cut. All the credits of this image are due to the authors of [26].

  e

Figure 1 . 7 :

 17 Figure 1.7: The union of K 4 and C 6 .

Figure 1 .

 1 Figure 1.8 shows that the converse of Observation 1.22 fails.

Figure 1 . 8 :

 18 Figure 1.8: A near-brick having two vertex-disjoint odd cycle and whose only brick is W 5 which is odd intercyclic.

Figure 1 . 9 :

 19 Figure 1.9: a) A polytope in R 2 ; b) The dominant of such polytope; c) The submissive of such polytope.

Figure 1 .Figure 1 .

 11 Figure1.10: a) An integer polytope in R 2 ; b) Shows that the intersection with an integer box preserves integrality; c) Shows that this polytope is also fully box-integer.

Figure 1 . 12 :

 112 Figure 1.12: Counterexample to the converse of Theorem 1.40.

Theorem 1 . 45 (

 145 Section 22.7,[START_REF] Schrijver | Theory of linear and integer programming[END_REF]). A system Ax ≤ b is TDI if and only if:

2

 2 be a totally equimodular matrix such that M 1 , M 2 , N 1 , and N 2 are nonsingular matrices of the same size. Then, if | det(M 1 )| = | det(N 1 )|, the matrix A is not totally equimodular.

The 2 -

 2 sum of two matrices A a and b B , with A and B matrices and a and b column and row vector respectively, is the matrix A ab 0 B .

Example 2 . 8 .

 28 The 2-sum of the matrices A a = 1 1 and b

  Thus, | det(N )| = | det(M )| and | det(M )| = | det(N )| by construction, and | det(M )| = | det(M )| by hypothesis.

When A has size 1

 1 then | det(A)| = 1. Suppose that A = α b c D has size n > 1 and, without loss of generality, that α = 1.

  have |V (F )| ≥ |F |, as otherwise M would have too many columns of zeros to have full row rank. If |V (F )| = |F |, then M has exactly one nonsingular k × k submatrix, hence M is equimodular. If |V (F )| > |F |, then H has a vertex u of degree one. Indeed, if every vertex of V (F ) had degree at least two we would have 2|F | = w∈V (F ) d H (w) ≥ 2|V (F )|, a contradiction.

  Since C 1 and C 2 are vertex-disjoint, there exists an edge e of T whose removal splits T into two trees T 1 and T 2 withC 1 \ {e 1 } ⊆ T 1 and C 2 \ {e 2 } ⊆ T 2 . By Theorem 2.21, | det(A Ti∪{ei} )| = | det(A T ∪{ei} )| = 2, for i = 1, 2. By construction, | det(A T ∪{e1,e2}\{e} )| = | det(A T1∪{e1} ) det(A T2∪{e2} )| = 4.The determinants of the maximal nonsingular square submatrices A T ∪{e1,e2}\{e} and A T ∪{e1} of A G differ in absolute value, thus A G is not equimodular.

Figure 2 . 1 :

 21 Figure 2.1: Graphs a) and b) both fulfill the criteria of being quasi-bipartite according to our definition. However, when considering the definition provided by Ding et al. [27], only graph a) conforms, while graph b) does not meet their criteria for quasi-bipartiteness.

Figure 2 . 2 :

 22 Figure 2.2: The graph G and the subgraph H (in blue) of the proof of Theorem 2.34.

Theorem 2 . 35 .

 235 The edge relaxation of the edge cover dominant of a connected graph G is box-TDI if and only if G is an odd hole or a quasi-bipartite graph different from K 4 .

  n) is a lower triangular matrix having determinant 1. On the other hand, the complement matrix of D(I, n) n n in D(I, n) is D(I , n -1) where I = I \ {n}. Indeed, D(I , n -1) is well defined since n -1 -|I | = n -|I|. Thus, det(D(I, n)) = (-1) n+1 + det(D(I , n -1)). The result holds by induction hypothesis. When n < m. By definition, D(I, n) is block structured has follows: D(I, n) = D(I, m) L 0 U , where D(I, m) is well defined since n and m have the same parity, L is a m × n -m matrix whose only nonzero entry is L 1 m = 1, and U is a (n -m) × (n -m) upper triangular matrix such that U i i = 1 for all i. Hence det(D(I, n)) = det(I, m) det(U ) = det(D(I, m)). The result holds by the induction hypothesis and the fact that n and m have the same parity. Theorem 2.48. Adding a star s to a hole of length congruent 2 mod 4 preserves the total equimodularity of the adjacency matrix if and only if s is the twin of a vertex. Proof. (⇐) Follows from Theorem 2.40 and Lemma 2.42.

Figure 2 .

 2 4 illustrates a counterexample to the converse of Corollary 2.52. Denote this graph as G.

Figure 2 . 4 :

 24 Figure 2.4: This graph refers to Example 2.54.

Theorem 3 . 1 and

 31 Remark 1.35 gives the following. Observation 3.2. Let G be a matching covered graph. A PMP-matrix of G is equimodular if and only if all PMP-matrices of G are equimodular.

  . Hence, again by Theorem 2.22, G[U ] has a base, say C, whose determinant absolute value equals 2 τ (G[U ]) . While, by construction, G[U ] correspond to one of the Ĝi with respect to F . Without loss of generality, we can suppose G[U ] = Ĝk Thus, by induction, there exists a base of A , say B, whose determinant absolute value is 2 k-1 i=1 τ ( Ĝi) , for appropriate Ĝi with respect to F . Finally, the matrix obtained by complementing B with C in A, is a base of A having block structure, and hence, having determinant 2 k i=1 τ ( Ĝi) , with Ĝk = G[U ].

. 1 .

 1 First we prove that P PM (G) is box-TDI. The tight cut decomposition of G with respect the tight cuts of the figure produce three times K 4 . Moreover, these two tight cuts are 2-separation cuts. Thus, by Theorem 3.30, P PM (G) is box-TDI. Finally, by Theorem 3.1 and Corollary 3.8, all absolute values of the nonzero maximal minors of any PMP-matrix of G equal 8.

Figure 3 . 1 :

 31 Figure 3.1: The graph G of Example 3.10.

  inclusion-wise family of laminar tight cuts. Since, by definition of PMP-matrix, A G is a submatrix of any PMP-matrix, Theorem 1.50 implies that d 1 = . . . = d |V |-1 = 1. We want to establish that d |V | = . . . = d |V |+k-1 = 2. To do this we refer to Theorem 3.7, which implies that d |V | ≤ 2, and that, if d |V | = 2, then all subsequent elementary divisors have to be 2.

Finally, as we

  have proved that d |V | = 2, and considering the fact that d |V | ≤ . . . ≤ d |V |+k-1 follows from the definition of the Smith normal form, coupled with d |V | • . . . • d |V |+k-1 ≤ 2 k as implied by Theorem 3.7, we can conclude that d |V | = . . . = d |V |+k-1 = 2.Theorem 3.12. The elementary divisors of a PMP-matrix of a matching covered graph G = (V, E) having k > 0 bricks ared 1 = . . . = d |V |-1 = 1, d |V | = . . . = d |V |+k-1 = 2.Theorems 3.7 and 3.12 imply the following.Corollary 3.13. The minimum among the absolute values of the maximal minors of every PMPmatrix of a matching covered graph with k bricks is 2 k .

Theorem 3 . 20 .

 320 For a matching covered graph G the following are equivalent: G is bipartite; there exists a totally equimodular PMP-matrix; there exists a totally unimodular PMP-matrix; all PMP-matrices of G are totally equimodular; all PMP-matrices of G are totally unimodular.

Figure 3 . 3 :

 33 Figure 3.3: A matching covered graph with two vertex-disjoint odd cycles and whose perfect matching polytope is box-TDI.

Theorem 3 . 26 .

 326 Let A be the PMP-matrix of a matching covered graph G with respect the maximal inclusion-wise family of laminar tight cuts F having the odd cycle property. Then, P PM (G) is box-TDI if and only if, for every base B of A and every edge uv ∈ G[B], there exists a (F , {0, ±1})weighted uv-walk in G[B] expressing uv.

Figure 3 . 4 :Figure 3 . 5 :

 3435 Figure 3.4: a) The moonfish graph; b) A moonfish (image taken from www.fr.wikipedia.org).

e 2 e 1 e 4 e 3 Figure 3 . 7 :

 14337 Figure 3.7: The graph G of Example 3.34.

Figure 3 . 8 ,Figure 3 . 8 :

 3838 Figure 3.8: The matching polytope of G is box-TDI, while the one of H is not by Theorem 3.42.

Example 3 . 41 .

 341 By Theorems 2.23 and 1.34, P M (C 4 ) is box-TDI, sinceP M (C 4 ) = {x : A C4 x ≤ 1, x ≥ 0}. While P M (C 6) is not by Theorem 3.42 since it contains F 1 as a subgraph, where C 6 is obtained from C 4 by adding three odd ears. That is the converse of Corollary 3.40 does not hold.Box-TDIness of the matching polytopeDing et al.[28] characterized the box-TDIness of the matching polytope by exhibiting four class of forbidden subgraphs obtained by full odd subdividing F 1 , F 2 , F 3 and F 4 of Figure3.9. Theorem 3.42 (Ding et al.[28]). The matching polytope of a graph G is box-TDI if and only if G does not include any fully odd subdivision of F 1 , F 2 , F 3 and F 4 as a subgraph.

Figure 3 . 9 :

 39 Figure 3.9: Forbidden subgraphs for the box-TDIness of the matching polytope. All the credits of this image are due to the authors of [28].

Observation 3 .

 3 [START_REF] Kawarabayashi | A simpler proof for the two disjoint odd cycles theorem[END_REF]. G is quasi-bipartite if and only ifP EC (G) = {x : A G x ≥ 1, x ≥ 0} ∩ {x : x ≤ 1}. Proof. Let P = {x : A G x ≥ 1, x ≥ 0} ∩ {x : x ≤ 1}.

  4 )| -rank(M ) + 1 = 4. By Theorem 2.35, Observation 3.44, and Example 3.47, we have the following. Theorem 3.48. The edge cover polytope of a quasi-bipartite graph different from K 4 is box-TDI.

  Thus, P ∪ (F \ E(B)) ∪ {uu , uu } is an edge cover of G. By construction, the aforementioned edge covers form a family of |E(B)| -|V (B)| + 2 affinely independent characteristic vectors. Hence, M is a face-defining matrix and P EC (G) is not box-TDI by Theorem 1.34. Finally, we introduce a conjecture which looks like a fair extension of Theorems 3.48, 3.51, 3.53, and 3.55. Conjecture 3.56. If G contains no nonbipartite matching covered subgraphs, then P EC (G) is box-TDI.

Theorem 3 . 57 (

 357 Cunningham and Green-Krotki[START_REF] Cunningham | Dominants and submissives of matching polyhedra[END_REF]). Let G = (V, E) be a matching covered graph and O be the family of subset of vertices of V whose associated cuts are nontrivial. Then P EM (G) is described by the nonnegative solutions of the system dx ≤ d 0 for every couple (d,d 0 ) ∈ R E ≥0 × R determined by    d uv = y u + y v + uv∈δ(U ) : U ∈O z U , for every uv ∈ E, d 0 = u∈V y u + U ∈O (U -1) 2 z U ,(3.10)

  Preliminaries on algorithms and complexity . . . . . . . . . . . . . . . . . . . . . . Equimodularity and total equimodularity of incidence matrices . . . . . . . . . . . 2.2.1 Edge-vertex incidence matrices . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Vertex-edge incidence matrices . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.3 Complexity consequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Equimodularity and total equimodularity of adjacency matrices . . . . . . . . . . . 2.3.1 Operations on graphs that preserve total equimodularity . . . . . . . . . . . 2.3.2 Adjacency matrices of bipartite graphs . . . . . . . . . . . . . . . . . . . . . 2.3.3 Adjacency matrices of nonbipartite graphs . . . . . . . . . . . . . . . . . . . Perfect matchings and box-total dual integrality . . . . . . . . . . . . . . . . . . . TDI system for the perfect matching polytope . . . . . . . . . . . . . . . 3.2.2 Fully odd subdivision and odd ears . . . . . . . . . . . . . . . . . . . . . . . 3.2.3 First step towards the box-TDIness: total equimodularity, odd intercylicity, and walk interpretation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.4 Second step towards box-TDIness: moonfish and very solid graphs . . . . . 3.3 Polyhedral variants and box-TDIness . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Matching polytope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 Edge cover polytope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.3 Extendable matching polytope . . . . . . . . . . . . . . . . . . . . . . . . .

	CONTENTS
	vii 3.2.1 A viii

xi 1 Preliminaries 1.1 Preliminaries on graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1 Definitions and notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.2 Matching covered graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Preliminaries on polyhedra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Polyhedra and integrality properties . . . . . . . . . . . . . . . . . . . . . . 1.2.2 Characterizations of box-total dual integrality . . . . . . . . . . . . . . . . . 1.3 Preliminaries on and complements to equimodularity . . . . . . . . . . . . . . . . . 1.3.1 Total unimodularity and graphs . . . . . . . . . . . . . . . . . . . . . . . . 1.3.2 Total dual integrality and dyadicness . . . . . . . . . . . . . . . . . . . . . . 1.3.3 Complements to unimodularity and equimodularity . . . . . . . . . . . . . 1.4 2 Equimodularity of graph matrices 2.1 Generalities on totally equimodular matrices . . . . . . . . . . . . . . . . . . . . . 2.1.1 Operations preserving and destroying (total) equimodularity . . . . . . . . 2.1.2 Determinants of totally equimodular matrices . . . . . . . . . . . . . . . . . 2.2 3 Polyhedral properties of perfect matchings 3.1 Affine Hull of Perfect Matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 The dimension of the affine hull of perfect matchings . . . . . . . . . . . . . 3.1.2 Perfect matching polytope . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2

  Example 3.19. Consider the graph G of Figure3.2. One can check that G is a brick. Moreover, any sequence for G steps into K 4 . Indeed, a simple counting argument on the number of vertices and edges shows that G contains no fully odd subdivision of C 6 as a subgraph, thus, the statement follows from Theorem 1.14. However, Theorem 3.21 (that we will prove later), implies that P PM (G) is not box-TDI, while the same theorem implies that P PM (K 4 ) is box-TDI.

	Figure 3.2: The graph G of example 3.19
	3.2.3 First step towards the box-TDIness: total equimodularity, odd
	intercylicity, and walk interpretation
	Total equimodularity for PMP-matrices

1

The idea behind this actually rise from Theorem 3.21.

In literature, twins or true twins typically denote two distinct vertices whose closed neighbors are equal, whereas false twins align with our specific definition. However, within the context of Chapter

[START_REF] Akbari | On unimodular graphs[END_REF], where frequent reference is made to twins, the situation differs. Unlike false twins, being classified as true twins would destroy the desired property of an adjacency matrix being equimodular.

Typically, literature excludes "triangles" from the definition of a "hole". However, in this context, delineating such a distinction is counterproductive as it undermines certain results

In the same paper the authors state that it is unknown if this problem is co-NP-complete.

In literature, it is more common to define the submissive as sub(P ) = -dom(-P ); however, we are more interested in its nonnegative points, so we refer to the definition presented in[START_REF] Cunningham | Dominants and submissives of matching polyhedra[END_REF].

Remerciements

Proof. Let v i be the twin of v i being added. Then, the adjacency matrix A H is equal to

Suppose that A G is totally equimodular (resp. totally unimodular). Then, Adding pendants to circuits Lemma 2.42. The adjacency matrix of C n is totally equimodular for every positive integer n. Moreover, there exists an order on the rows and columns for which A Cn = A Cn when n is odd, while A C2 = I 2 , B C4 = 1 1 1 1 , and

for n > 4 even.

Proof. Denote as v 1 , . . . , v n the vertices of C n clockwise ordered and let P and D be the increasing ordered lists of the even and odd numbers in {1, . . . , n}, respectively. Consider A Cn reordered as follows: the columns follow the order of D first, and P second and the rows follow the order of P first, and D, second. This order place two columns next to each other if and only if two vertices have a common neighbor. Suppose that n is odd. Then, A Cn is equal to the canonical form of A Cn by construction (to see it one can draw another circuit following the clockwise order whose edges connect two vertices only if they have a common neighbor; the edges and the vertices of this new circuit encoded give A Cn ). Hence, A Cn is totally equimodular by Theorem 2.25.

Suppose that n is even. When n = 2 and n = 4, A C2 = I 2 and B C4 = 1 1 1 1 follow from direct calculation. While, by construction, as for n odd, B Cn = A C n 2

for n > 4. Moreover, when n ≥ 4 is even, C n is bipartite. By Observation 1.3, A Cn is identified from B Cn . By Theorems 2.6 and 2.25, A Cn is totally equimodular for every positive integer n.

Theorem 2.43 (Akbari et al. [START_REF] Akbari | On unimodular graphs[END_REF]). Let G be a graph.

If G is a forest, then A G is totally unimodular; If G contains is unicyclic, then, A G is totally unimodular if and only if the length of the circuit is divisible by 4.

Theorem 2.44. The adjacency matrix of (V (C n ∪ {e}), C n ∪ {e}), where e is pendant, is totally equimodular if and only if n ≡ 4 0.

Proof. (⇐) Let n ≡ 4 0. Theorem 2.43 implies that A Cn∪{e} is totally unimodular, hence totally equimodular.

(⇒) Let e = uv, where u ∈ V (C n ) , and order C n clockwise starting from u and let v be indexed as last. By construction and by Lemma 2.42, one of the two matrices A Cn χ u and

Adjacency matrices of bipartite graphs

We subdivide this section into bipartite graphs having induced circuits of length congruent divisible by 4 or not. Indeed, Akbari et al. [START_REF] Akbari | On unimodular graphs[END_REF] showed necessary but not sufficient conditions for the total unimodularity of the adjacency matrix. Their statements are in terms of induced forbidden structures and, moreover, they exhibit an infinite family of bipartite graphs whose adjacency matrix is totally unimodular. Adding stars to odd circuits Theorem 2.59. Let G be a graph obtained from C n , with n odd, by adding a star s. Then A G is totally equimodular if and only if s is a twin of a vertex.

Proof. (⇒) Theorem 2.44 and Corollary 2.45 already solved the cases d(s) = 1, 2, since when s has such degrees both cases are equivalent to adding a pendant and an ear of length 2 respectively. There remains to prove the case when d(s) ≥ 3.

If n = 3, G corresponds to K 4 becase d(s) ≥ 3, and A G is not totally equimodular by Lemma 2.57. Consider n ≥ 5 and let us exhibit an induced subgraph corresponding to an odd hole with a pendant edge in each case. Let C be an odd hole of G containing s. Denote by u and v the two neighbors of s in C and by u and v the neighbors of u and v which are not in C. If u = v , then there exists a vertex w in V (C) \ {s} adjacent to u but not to s or u since C is a hole and n ≥ 5. Hence, the graph G induced by {u, u , s, w} is a triangle with a pendant edge. Suppose u = v . If s is not adjacent to u (or v ), the graph induced by V (C) ∪ {u } (or V (C) ∪ {v }) is an odd hole with a pendant edge. If s is adjacent to both u and v , then uv or u v is not an edge of G since n ≥ 5. Hence, sv or sv is a pendant edge of the triangle induced by {u, u , s}. In all cases, the adjacent matrix of the exhibit subgraph is not totally equimodular by Theorem2. [START_REF] Kawarabayashi | A simpler proof for the two disjoint odd cycles theorem[END_REF] Recall that removing a duplicated column or row is a polynomial solvable problem. Thus, we can remove all the twins of a given graph in polynomial-time. This consideration and Theorem 2.61 gives the following.

Corollary 2.62. For a given nonbipartite graph deciding whether the adjacency matrix is totally equimodular can be done in polynomial-time.

We want to prove that G/U and G/(V \ U ) are matching covered, that is, δ(U ) is separating, contradicting the hypothesis that G is solid.

Let u be the contraction of U in G/U . Suppose that G/U is not matching covered, then there exists a subset S of vertices such that |O(G/U \ S)| > |S| by Theorem 1.5, if G/U has no perfect matching, or |O(G/U \ S)| = |S| and one edge of G/U has both extremities in S by Theorem 1.6. Note that u ∈ S as otherwise, S would be a certificate that G has no perfect matching contradicting G matching covered. Moreover, since

Similarly, if G/U has no perfect matching, for every perfect matching M of G, the edges in M ∩ δ(U ) have to cover some vertices of some components of O(G/U \ S) or some vertices in S \ {u} by Theorem 1.5. If G/U has a perfect matching, but is not matching covered, by Theorem 1.6, there exists an edge e ∈ S, and since G is matching covered, there exists a perfect matching of G, say M e , including e. In both cases, a counting argument implies that

Since, by Theorem 1.18, a bipartite matching covered graph is solid as it contains no bricks, Theorem 3.5 along with Observation 1.4 allow to retrieve the following well-known result.

Corollary 3.6 (cited in [START_REF] De Carvalho | On a conjecture of lovász concerning bricks: I. the characteristic of a matching covered graph[END_REF]). The perfect matching polytope of a bipartite graph G is described by the system A G x = 1, x ≥ 0. About the maximal minors of a PMP-matrix Theorem 3.7. Let G be a matching covered graph having k > 0 bricks. Then, for every PMPmatrix there exists a maximal minor of absolute value equals 2 k .

Proof. We prove it by inducion over the number of bricks. When k = 1, G is a near-brick and, hence, every PMP-matrix reduce to A G , which has a maximal minor absolute value equal to 2.

Suppose that G has k > 1 bricks and that the statement is true for all matching covered graphs with at most k -1 bricks. Let U be a minimal inclusion-wise shore with respect a family of laminar tight cuts, say F , of G having the odd cycle property and being maximal inclusion-wise.

,

where A is the PMP-matrix of G/U associated with F \ δ(U ) and D an appropriate 0, 1-matrix. The base case is when G is a near-brick, which holds by Theorems 3.21 and 1.34. Let the statement be true for all matching covered graphs having k -1 > 0 bricks. Then, suppose that G has k bricks and that one of the corresponding near-bricks, say B , is not odd intercyclic. Let F be a maximal laminar family of tight cuts having the odd cycle property and A the corresponding PMP-matrix. Since F is laminar, there exist two minimal inclusion-wise shores, and one of them, say U , is such that B is a near-brick of G/U . Furthermore, note that G/U has k -1 bricks. Thus, by Observation 3.3, the matrix

, where D i is a binary matrix uniquely defined.

By construction, these two matrices have different determinant absolute value. Hence, A is not equimodular.

Theorems 3.5 and 3.23 imply the following.

Corollary 3.24. For a graph G, the following statements are equivalent:

2. the affine hull of P PM (G) is box-TDI;

3. there exists a PMP-matrix of G which is equimodular.

Since finding a PMP-matrix for a given graph and testing equimodularity of a given matrix are both achievable in polynomial-time by [START_REF] Edmonds | Brick decompositions and the matching rank of graphs[END_REF] and [START_REF] Chervet | Box-total dual integrality, box-integrality, and equimodular matrices[END_REF] respectively, Corollary 3.24 gives the following.

Corollary 3.25. For a given graph G deciding whether the perfect matching polytope is box-TDI can be done in polynomial-time.

This contrast with the fact that deciding whether a given polyhedron is box-TDI is co-NPcomplete, as we proved in Corollary 2.36.

Walk intepretation

We say that a walk (v 1 , e 1 , . . . , e k , v k+1 ) of a graph G is Ω-weighted if there exists a function ω

and suppose that k is odd, if ω is unique up to sign multiplication, we say that the v 1 , v k+1 -walk expresses the v 1 v k+1 .

Let G be a graph, B be a base of A G , and G[B] denote the subgraph of G whose edges corresponds to the columns of B. A well-known fact in combinatorial optimization which is based on linear algebra is the following: there exists a unique linear combination of the columns of B that express a column A i G and the corresponding coefficients are the entries of (B -1 A) i . These coefficients are precisely the weights to assign to the edges of G[B] to identify a weighted walk which expresses the edge of G associated with A i G . Moreover, by Theorem 1.33, B -1 A G is a 0, ±1matrix for every base B if and only if A G is equimodular. That is, when the graph is odd intercyclic (by Theorem 2.28), all walks expressing edges with respect to a base are {0, ±1}-weighted.

About 2-separation cuts

We discuss the other type of ELP-cuts and characterize its relation with the box-TDIness of the perfect matching polytope. The results presented here, along with the previous remarks on barriers, highlight a class of graphs that might be a good candidate for the graph characterization of the box-TDIness of the perfect matching polytope.

Lemma 3.28. Let G be a matching covered graph and C be a 2-separation cut of G with respect to two vertices u and v of G. Suppose that uv ∈ E(G). Then, G = (V (G), E(G) ∪ {uv}) is matching covered.

Proof. Let G 1 and G 2 be the two even connected components of G\{u, v} (both exist by definition of 2-separation cut). Suppose that G is not matching covered. Since G is matching covered, uv is the only edge of G not belonging to some perfect matchings. Thus, by abuse of notation (we use the same vertices labels for G and G ), there is no perfect matching in G 1 and G 2 . This contradict that G is matching covered, since

Thus, G is matching covered.

Though we will not use it, we mention that the converse of Lemma 3.28 holds. Proof. We first prove the result in the case when uv ∈ E. Let U u and U v be the shores of C containing u and v respectively. Then, up to edge multiplicity,

. By Theorem 3.26, for every edge not in the spanning subgraph associated with a base of G/U u (resp. G/U v ) there exists a (F , {0, ±1})-weighted walk that expresses it, where F is a maximal inclusion-wise family of laminar tight cut of G/U u (resp. G/U v ) including

) is a subgraph of G, the same edge can be expressed by the same walk for G.

Suppose that uv ∈ E(G), by Lemma 3.28 we can add the edge uv to G and preserve being matching covered. By definition, P PM (G) = P PM ((V (G), E(G) ∪ {uv})) ∩ {x : x uv = 0}, thus, P PM ((V (G), E(G) ∪ {uv})) box-TDI implies P PM (G) box-TDI. Another remark has to be done: the graph G of Figure 1.4 present a barrier cut, intersecting two vertex-disjoint odd circuits. However, differently from the moonfish graph, P PM (G) is box-TDI (as can be checked by using Corollary 3.24) and these two odd circuits belongs to separate bricks.

We summarize these ideas in the following deifnitions. Definition 3.32. Let G be a matching covered graph, F be a family of laminar tight cuts which is maximal inclusion-wise, and δ(U 0 ) be a barrier cut in F . Then, we say that δ(U 0 ) is simple if for every pair of vertex-disjoint odd cycles C 1 and C 2 intersecting δ(U 0 ), there exists no tight cut T in F \ δ(U 0 ) such that T intersects both C 1 and C 2 . Definition 3.33. Let G be a matching covered graph and F a family of laminar tight cuts which is maximal inclusion-wise. Then, G is very solid if all its near-bricks are odd intercyclic and all barrier cuts of F are simple.

The alignment of Definition 3.33 is congruent with the observation that barrier cuts (and not 2-separation cut) have the potential to generate bases consisting of multiple connected components which destroys the equimodularity of a PMP-matrix. Moreover, very solid graphs are solid, by Theorem 1.18 and Observation 1.22.

Furthermore, delving into the examination of the graph class whose 2-separation cuts do not intersect two vertex-disjoint odd cycles is excessively constraining, as the following example illustrates.

Example 3.34. In Figure 3.7, we observe a graph G which exhibits two vertex-disjoint odd cycles intersecting the tight cut C = {e 1 , e 2 , e 3 , e 4 }. However, P PM (G) is box-TDI. This is due to Theorem 3.30 because C is a 2-separation cut, and both C-contractions are K 4 . Thanks to Theorem 1.14 of Lovász, we prove that the edge cover polytope of any nonbipartite matching covered graph is not box-TDI. To do it, we complement the result of Example 3.47 by proving that P EC (C 6 ) is not box-TDI.

Example 3.50. We prove that P EC (C 6 ) is not box-TDI. Recall that P EC (C 6 ) is described by System (3.9). One can check that all the points of the type χ M , where M is a perfect matching of C 6 , form a family of four affinely independent points satisfying the system A C6 x = 1. Thus, A C6 is a face-defining matrix of P EC (C 6 ) by Observation 1.36. Moreover, A C6 is not equimodular by Theorem 2.28.

Theorem 3.51. The edge cover polytope of any nonbipartite matching covered graph is not box-TDI.

Proof. Let G be a nonbipartite matching covered graph. By Theorem 1.14, G is the last graph in a sequence of matching covered graphs obtained by adding one or two odd ears at each iteration. Furthermore, any of these sequences steps into K 4 or C 6 . By Examples 3.47 and 3.50, both P EC (K 4 ) and P EC (C 6 ) are nonbox-TDI. Finally, P EC (G) is not box-TDI by Corollary 3.46. By Theorem 3.48 and Theorem 3.51 we have the following. Corollary 3.52. If a nonbipartite graph is quasi-bipartite and matching covered, then is K 4 .

We will now present necessary conditions that are somewhat parallel to those expressed in Theorem 3.51.

Theorem 3.53. Let G = (V, E) and G be a subgraph of G. Suppose that the following statements hold:

1. G is nonbipartite and matching covered; 2. there exists a perfect matching F of G such that F ∩ δ(G ) = ∅.

Then, P EC (G) is not box-TDI.

Proof. We prove it by exhibiting a nonequimodular face-defining matrix for P EC (G) which suffices by Theorem 1.34.

By Theorem 3.51, P EC (G ) is not box-TDI. Thus, by Theorem 1.34 there exists a nonequimodular face-defining matrix, say M , of P EC (G ). Now, complement M in System (3.9) by Lemma 3.54. Let G = (V, E) be a brick. Then, for every u ∈ V the matrix associated with the system x(δ(v)) = 1 for all v ∈ V \ {u} is nonequimodular and face-defining for a face of P EC (G).

Proof. First, let us prove that for every vertex u of G there exists an odd circuit, say C u , which is adjacent to u, that is u ∈ N (V (C u )).

Let v be a neighbor of u. Since a brick is 3-connected, G \ {u} is 2-connected so there exists a circuit C of G \ {u} containing v. Hence, u is adjacent to a circuit. If C is odd, we are done. Otherwise, by Corollary 1.15, G \ {u} contains an odd circuit C . Since G \ {u} is 2-connected, there exist two paths P 1 and P 2 having different extremities and connecting C to C. Hence, P 1 ∪ P 2 ∪ C ∪ C contains and odd circuit containing v. Now, we exhibit a nonequimodular face-defining matrix of P EC (G) satisfying the lemma. Let C be an odd ciruit of G such that u ∈ N (V (C)). We prove that the matrix M whose rows are associated with V \ {u} has full row rank but is not equimodular. Let G be a unicyclic subgraph of G containing C and whose edges cover V \ {u}. By construction, A G is a maximal square submatrix of M and, by Theorem 2.21, its determinant absolute value is 2. On the other hand, the matrix M obtained from A G by replacing a column corresponding to an edge, say e, of C with one associated with some edge, say uw, in δ(C) ∩ δ(u) has determinant 1. This is because one can calculate the determinant starting from the rows whose corresponding to the vertices of G \ {e} of degree 1 until reducing the computation of | det(M )| to | det( A C\{e} χ v )|. Thus, M is not equimodular.

By Observation 1.36, M is face-defining if and only if there exists |E|-|V |+2 edge covers whose characteristic vectors are affinely independent. Since every brick is 3-connected and bicritical, there exist two vertices, say u and u , in N (u) ∩ V such that G \ {u , u } has a perfect matching, say P . Thus, P ∪ {uu , uu } is an edge cover of G. Furthermore, Lovász [START_REF] Lovász | Matching structure and the matching lattice[END_REF] proved that a brick with m edges and n vertices has precisely m -n + 1 perfect matchings whose characteristic vectors are affinely independent. By construction, the aforementioned edge covers form a family of |E| -|V | + 2 affinely independent characteristic vectors.

Hence, M is a face-defining matrix and P EC (G) is not box-TDI by Theorem 1.34.

Theorem 3.55. Let G = (V, E) and B be a subgraph of G. Suppose that the following statements hold:

1. B is a brick;

2. there exists a perfect matching

Then, P EC (G) is not box-TDI.

Proof. We prove it by exhibiting a nonequimodular face-defining matrix for P EC (G) which suffices by Theorem 1.34. Let u ∈ V (B) be such that uv ∈ F ∩ δ(V (B)), then, by Lemma 3.54, there exists a nonequimodular face-defining matrix of P EC (B), say M , whose rows correspond to all trivial cuts of V (B) \ {u}. Let us extend M to a matrix M by adding the rows corresponding to the trivial for some y ∈ R V and z ∈ R 0 + .

The description given in Theorem 3.57 for the extendable matching polytope can be challenging to understand.

In the same paper, the authors exhibit an infinite family of graphs in which bounding the degree of the inequalities of System (3.10) to a specific constant is impossible. More precisely, they demonstrate that for every odd n, there exists a graph with 2n + 4 vertices such that the corresponding extendable matching polytope has a facet described by an inequality of type (3.10) whose coefficient set is {0, 1, . . . , n}.

Box-TDIness of the extendable matching polytope

Here, we delve deeper into the discussions regarding the box-TDIness of the extendable matching polytope and extendable matchings. (⇐) Recall that every perfect matching is an extendable matching by definition. Thus, the perfect matching polytope is a face of the extendable matching polytope. Then, if P EM (G), also P PM (G) is box-TDI by definition of box-TDIness (or applying Remark 1.35).

From Theorems 3.58 and 3.21 we have the following. Corollary 3.59. Let G be an odd intercyclic near-brick. Then, P EM (G) is box-TDI.

Similarly, Theorems 3.58 and 3.30 implies the following. Corollary 3.60. Let G be a matching covered graph having an ELP-cut decomposition free of barrier cuts. Then, if H is a fully odd subdivision of G, P EM (H) is box-TDI.

Fully odd subdivision

By Theorem 3.58 and Theorem 3.15 we have the following. Corollary 3.61. Let H be a graph obtained from a graph G = (V, E) by replacing one edge with a path of length three. Then, P EM (H) is box-TDI if and only if P EM (G) is.

Adding an odd ear

By Theorem 3.58 and Corollary 3.17 we have the following. Corollary 3.62. Let H be a graph obtained from a graph G by adding an odd ear. Then, if P EM (H) is box-TDI, then P EM (G) is.