# Box-total dual integrality, box-integrality, and equimodular matrices

Patrick Chervet, Roland Grappe, Louis-Hadrien Robert

► To cite this version:

Patrick Chervet, Roland Grappe, Louis-Hadrien Robert. Box-total dual integrality, box-integrality, and equimodular matrices. Mathematical Programming, 2020, 188 (1), pp.319-349. 10.1007/s10107-020-01514-0. hal-04155427

HAL Id: hal-04155427

https://uca.hal.science/hal-04155427

Submitted on 1 Feb 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Box-Total Dual Integrality, Box-Integrality, and
Equimodular Matrices

Patrick Chervet · Roland Grappe* ·
Louis-Hadrien Robert**

the date of receipt and acceptance should be inserted later

**Abstract** Box-TDI polyhedra are polyhedra described by systems which yield strong min-max relations. We characterize them in several ways, involving the notions of principal box-integer polyhedra and equimodular matrices.

A polyhedron is *box-integer* if its intersection with any integer box {$l \le x \le u$} is integer. We define *principally box-integer* polyhedra to be the polyhedra *P* such that *kP* is box-integer whenever *kP* is integer. A rational *r* × *n* matrix is *equimodular* if it has full row rank and its nonzero *r* × *r* determinants all have the same absolute value. A *face-defining* matrix is a full row rank matrix describing the affine hull of a face of the polyhedron. Our main result is that the following statements are equivalent.

• The polyhedron *P* is box-TDI.

• The polyhedron *P* is principally box-integer.

• Every face-defining matrix of *P* is equimodular.

• Every face of *P* has an equimodular face-defining matrix.

• Every face of *P* has a totally unimodular face-defining matrix.

<footnote>* Corresponding author</footnote>

<footnote>** Supported by the Luxembourg National Research Fund PRIDE17/1224660/GPS and by the NCCR SwissMAP, funded by the Swiss National Science Foundation.</footnote>

<footnote>Patrick Chervet
Lycée Olympe de Gouges, rue de Montreuil à Claye, 93130, Noisy le Sec, France
E-mail: patrick.chervet@ac-creteil.com</footnote>

<footnote>Roland Grappe
Université Sorbonne Paris Nord, LIPN, CNRS, UMR 7030, F-93430, Villetaneuse, France
E-mail: grappe@lipn.fr</footnote>

<footnote>Louis-Hadrien Robert
Université de Genève, rue du Lièvre 2-4, 1227, Genève, Switzerland
Université du Luxembourg, RMATH, Maison du Nombre, 6 avenue de la Fonte, L-4365
Esch-sur-Alzette, Luxembourg
E-mail: louis-hadrien.robert@unige.ch
E-mail: louis-hadrien.robert@uni.lu</footnote>
Box-Total Dual Integrality, Box-Integrality, and
Equimodular Matrices

Patrick Chervet · Roland Grappe* ·
Louis-Hadrien Robert**

the date of receipt and acceptance should be inserted later

**Abstract** Box-TDI polyhedra are polyhedra described by systems which yield strong min-max relations. We characterize them in several ways, involving the notions of principal box-integer polyhedra and equimodular matrices.

A polyhedron is *box-integer* if its intersection with any integer box {$l \le x \le u$} is integer. We define *principally box-integer* polyhedra to be the polyhedra *P* such that *kP* is box-integer whenever *kP* is integer. A rational *r* × *n* matrix is *equimodular* if it has full row rank and its nonzero *r* × *r* determinants all have the same absolute value. A *face-defining* matrix is a full row rank matrix describing the affine hull of a face of the polyhedron. Our main result is that the following statements are equivalent.

• The polyhedron *P* is box-TDI.

• The polyhedron *P* is principally box-integer.

• Every face-defining matrix of *P* is equimodular.

• Every face of *P* has an equimodular face-defining matrix.

• Every face of *P* has a totally unimodular face-defining matrix.

<footnote>* Corresponding author</footnote>

<footnote>** Supported by the Luxembourg National Research Fund PRIDE17/1224660/GPS and by the NCCR SwissMAP, funded by the Swiss National Science Foundation.</footnote>

<footnote>Patrick Chervet
Lycée Olympe de Gouges, rue de Montreuil à Claye, 93130, Noisy le Sec, France
E-mail: patrick.chervet@ac-creteil.com</footnote>

<footnote>Roland Grappe
Université Sorbonne Paris Nord, LIPN, CNRS, UMR 7030, F-93430, Villetaneuse, France
E-mail: grappe@lipn.fr</footnote>

<footnote>Louis-Hadrien Robert
Université de Genève, rue du Lièvre 2-4, 1227, Genève, Switzerland
Université du Luxembourg, RMATH, Maison du Nombre, 6 avenue de la Fonte, L-4365
Esch-sur-Alzette, Luxembourg
E-mail: louis-hadrien.robert@unige.ch
E-mail: louis-hadrien.robert@uni.lu</footnote>
• For every face $F$ of $P$, $\lin(F)$ has a totally unimodular basis.

Along our proof, we show that a polyhedral cone is box-TDI if and only if it is box-integer, and that these properties are carried over to its polar.

We illustrate these characterizations by reviewing well known results about box-TDI polyhedra. We also provide several applications. The first one is a new perspective on the equivalence between two results about binary clutters. Secondly, we refute a conjecture of Ding, Zang, and Zhao about box-perfect graphs. Thirdly, we discuss connections with an abstract class of polyhedra having the Integer Carathéodory Property. Finally, we characterize the box-TDIness of the cone of conservative functions of a graph and provide a corresponding box-TDI system.

**Keywords** Box-integer polyhedron · Polyhedral cone · Equimodular matrix · Box-TDI polyhedron · Box-perfect graph

**Mathematics Subject Classification (2000)** 90C27 · 52B12 · 90C05

# 1 Introduction

Box-totally dual integral systems are systems which yield strong min-max relations. These systems are useful to prove strong min-max combinatorial theorems and are known to be difficult to handle. A polyhedron that can be described by a box-totally dual integral system is called a *box-totally dual integral polyhedron* [14]. In this paper, we characterize box-totally dual integral polyhedra in several new ways. The key idea is to introduce and study the abstract class of principally box-integer polyhedra—see Definition 1 below. Indeed, the completely geometric nature of principally box-integer polyhedra makes them easier to be studied, and it turns out that this class coincides with that of box-totally dual integral polyhedra.

We characterize principally box-integer polyhedra in several ways. In this regard, some matrices play an important role. They generalize unimodular matrices and we call them *equimodular matrices*—see Definition 2 below. We show that the notion of principal box-integrality is strongly intertwined with that of equimodularity: equimodular matrices are characterized using principal box-integrality and, in turn, principally box-integer polyhedra are characterized by the equimodularity of a family of matrices. This sheds new lights on fundamental results in combinatorial optimization and integer programming. For instance, the classical characterization of unimodular matrices by Veinott and Dantzig [45] and that of totally unimodular matrices due to Hoffman and Kruskal [31] can be reformulated and extended using these notions.

More importantly, these notions bring a geometric and matricial perspective about box-totally dual integral polyhedra. Since the class of principally box-integer polyhedra coincides with that of box-totally integral polyhedra, our results provide several new characterizations of the latter. We believe that
• For every face $F$ of $P$, $\lin(F)$ has a totally unimodular basis.

Along our proof, we show that a polyhedral cone is box-TDI if and only if it is box-integer, and that these properties are carried over to its polar.

We illustrate these characterizations by reviewing well known results about box-TDI polyhedra. We also provide several applications. The first one is a new perspective on the equivalence between two results about binary clutters. Secondly, we refute a conjecture of Ding, Zang, and Zhao about box-perfect graphs. Thirdly, we discuss connections with an abstract class of polyhedra having the Integer Carathéodory Property. Finally, we characterize the box-TDIness of the cone of conservative functions of a graph and provide a corresponding box-TDI system.

**Keywords** Box-integer polyhedron · Polyhedral cone · Equimodular matrix · Box-TDI polyhedron · Box-perfect graph

**Mathematics Subject Classification (2000)** 90C27 · 52B12 · 90C05

# 1 Introduction

Box-totally dual integral systems are systems which yield strong min-max relations. These systems are useful to prove strong min-max combinatorial theorems and are known to be difficult to handle. A polyhedron that can be described by a box-totally dual integral system is called a *box-totally dual integral polyhedron* [14]. In this paper, we characterize box-totally dual integral polyhedra in several new ways. The key idea is to introduce and study the abstract class of principally box-integer polyhedra—see Definition 1 below. Indeed, the completely geometric nature of principally box-integer polyhedra makes them easier to be studied, and it turns out that this class coincides with that of box-totally dual integral polyhedra.

We characterize principally box-integer polyhedra in several ways. In this regard, some matrices play an important role. They generalize unimodular matrices and we call them equimodular matrices—see Definition 2 below. We show that the notion of principal box-integrality is strongly intertwined with that of equimodularity: equimodular matrices are characterized using principal box-integrality and, in turn, principally box-integer polyhedra are characterized by the equimodularity of a family of matrices. This sheds new lights on fundamental results in combinatorial optimization and integer programming. For instance, the classical characterization of unimodular matrices by Veinott and Dantzig [45] and that of totally unimodular matrices due to Hoffman and Kruskal [31] can be reformulated and extended using these notions.

More importantly, these notions bring a geometric and matricial perspective about box-totally dual integral polyhedra. Since the class of principally box-integer polyhedra coincides with that of box-totally integral polyhedra, our results provide several new characterizations of the latter. We believe that
these characterizations fill in “the lack of a proper tool for establishing box-total dual integrality”—to quote Ding, Tan, and Zang [17]—and we illustrate their use.

**Main definitions.** Before going deeper into the details of our contributions, let us give the main definitions relevant to this paper.

A polyhedron $P = \{x : Ax \le b\}$ of $\mathbb{R}^n$ is integer if each of its faces contains an integer point and box-integer if $P \cap \{\ell \le x \le u\}$ is integer for all $\ell, u \in \mathbb{Z}^n$. For $k \in \mathbb{Z}_{>0}$, the $k$th dilation of $P$ is $kP = \{kx : x \in P\} = \{x : Ax \le kb\}$.

**Definition 1** A polyhedron $P$ is principally box-integer if $kP$ is box-integer for all $k \in \mathbb{Z}_{>0}$ such that $kP$ is integer.

A full row rank $r \times n$ matrix is unimodular if it is integer and its nonzero $r \times r$ determinants have value 1 or $-1$ [38, Page 267]. There is a strong connection between principally box-integer polyhedra and the following generalization of unimodular matrices. Note that equimodular matrices are studied under the name of matrices with the Dantzig property in [29] or as unimodular sets of vectors in [28].

**Definition 2** A rational $r \times n$ matrix is equimodular if it has full row rank and its nonzero $r \times r$ determinants all have the same absolute value.

A linear system $Ax \le b$ is totally dual integral (TDI) if the minimum in the linear programming duality equation $\max\{w^\top x : Ax \le b\} = \min\{b^\top y : A^\top y = w, y \ge 0\}$ has an integer optimal solution for all integer vectors $w$ for which the optimum is finite. Every polyhedron can be described by a TDI system [38, Theorem 22.6]. Moreover, the right hand side of such a TDI system can be chosen integer if and only if the polyhedron is integer [22]. A linear system $Ax \le b$ is a box-TDI system if $Ax \le b$, $\ell \le x \le u$ is TDI for each pair of rational vectors $\ell$ and $u$. In other words, $Ax \le b$ is box-TDI if

$$ \min\{b^\top y + u^\top r - \ell^\top s : A^\top y + r - s = w, y \ge 0, r, s \ge 0\} \quad (1) $$

has an integer solution for all integer vectors $w$ and all rational vectors $\ell, u$ for which the optimum is finite. It is well-known that box-TDI systems are TDI [38, Theorem 22.7]. General properties of such systems can be found in [14], [39, Chap. 5.20] and [38, Chap. 22.4]. Though not every polyhedron can be described by a box-TDI system, the result of Cook [14] below proves that being box-TDI is a property of the polyhedron.

**Theorem 1 (Cook [14, Corollary 2.5])** If a system is box-TDI, then any TDI system describing the same polyhedron is also box-TDI.

This theorem justifies the following definition [14].

**Definition 3** A polyhedron that can be described by a box-TDI system is called a box-TDI polyhedron.

Let us now review results from the literature related to these notions.
these characterizations fill in “the lack of a proper tool for establishing box-total dual integrality”—to quote Ding, Tan, and Zang [17]—and we illustrate their use.

*Main definitions.* Before going deeper into the details of our contributions, let us give the main definitions relevant to this paper.

A polyhedron $P = \{x : Ax \le b\}$ of $\mathbb{R}^n$ is integer if each of its faces contains an integer point and box-integer if $P \cap \{\ell \le x \le u\}$ is integer for all $\ell, u \in \mathbb{Z}^n$. For $k \in \mathbb{Z}_{>0}$, the $k$th dilation of $P$ is $kP = \{kx : x \in P\} = \{x : Ax \le kb\}$.

**Definition 1** A polyhedron $P$ is *principally box-integer* if $kP$ is box-integer for all $k \in \mathbb{Z}_{>0}$ such that $kP$ is integer.

A full row rank $r \times n$ matrix is *unimodular* if it is integer and its nonzero $r \times r$ determinants have value 1 or $-1$ [38, Page 267]. There is a strong connection between principally box-integer polyhedra and the following generalization of unimodular matrices. Note that equimodular matrices are studied under the name of matrices with the Dantzig property in [29] or as unimodular sets of vectors in [28].

**Definition 2** A rational $r \times n$ matrix is *equimodular* if it has full row rank and its nonzero $r \times r$ determinants all have the same absolute value.

A linear system $Ax \le b$ is *totally dual integral (TDI)* if the minimum in the linear programming duality equation $\max\{w^\top x : Ax \le b\} = \min\{b^\top y : A^\top y = w, y \ge 0\}$ has an integer optimal solution for all integer vectors $w$ for which the optimum is finite. Every polyhedron can be described by a TDI system [38, Theorem 22.6]. Moreover, the right hand side of such a TDI system can be chosen integer if and only if the polyhedron is integer [22]. A linear system $Ax \le b$ is a *box-TDI system* if $Ax \le b$, $\ell \le x \le u$ is TDI for each pair of rational vectors $\ell$ and $u$. In other words, $Ax \le b$ is box-TDI if

$$ \min\{b^\top y + u^\top r - \ell^\top s : A^\top y + r - s = w, y \ge 0, r, s \ge 0\} \quad (1) $$

has an integer solution for all integer vectors $w$ and all rational vectors $\ell, u$ for which the optimum is finite. It is well-known that box-TDI systems are TDI [38, Theorem 22.7]. General properties of such systems can be found in [14], [39, Chap. 5.20] and [38, Chap. 22.4]. Though not every polyhedron can be described by a box-TDI system, the result of Cook [14] below proves that being box-TDI is a property of the polyhedron.

**Theorem 1 (Cook [14, Corollary 2.5])** If a system is box-TDI, then any TDI system describing the same polyhedron is also box-TDI.

This theorem justifies the following definition [14].

**Definition 3** A polyhedron that can be described by a box-TDI system is called a *box-TDI polyhedron*.

Let us now review results from the literature related to these notions.
**Unimodular matrices.** The notion of unimodularity dates back to Smith [43] and ensures that a linear system has an integral solution for each integer right-hand side. Hoffman and Kruskal [31] proved that integral solutions still exist under the weaker condition that (*) the gcd of the $r \times r$ determinants equals 1. Condition (*) and equimodularity are complementary generalizations of unimodularity, in the sense that if an integer matrix is equimodular and satisfies (*), then it is unimodular. Hoffman and Oppenheim [30] introduced variants of unimodularity, which were afterward studied by Truemper [44]. In [7,28], it is proved that equimodular matrices ensure that all basic solutions are integer, provided that one of them is—see also Barnett [5, Chap. 7].

The stronger notion of total unimodularity plays a central role in combinatorial optimization. A matrix is *totally unimodular* when all its subdeterminants have value in $\{0, \pm 1\}$. Examples of such matrices are network matrices and incidence matrices of bipartite graphs. Hoffman and Kruskal [31] characterized totally unimodular matrices to be the matrices for which the associated polyhedra are all box-integer. Several other characterizations were obtained since then—see e.g. [10] and [25]. Totally unimodular matrices are now well understood due to the decomposition theorem of Seymour [40]. For a survey of related results, we refer to [38, Chap. 4 and 19]. More recently, Appa [2] and Appa and Kotnyek [3] generalized total unimodularity to rational matrices, their goal being to ensure the integrality of the associated family of polyhedra for a specified set of right-hand sides, such as those with only even coordinates. In another direction, Lee [33] generalized totally unimodular matrices by considering the associated linear spaces. The connections between his results and the previous ones are discussed in Kotnyek's thesis [32, Chap. 11].

We will see how principal box-integrality fits within the characterization of unimodular matrices by Veinott and Dantzig [45] and that of totally unimodular matrices due to Hoffman and Kruskal [31]. Then, these results are naturally extended to characterize equimodular matrices. Also, a new generalization of totally unimodular matrices appears in Section 4.1, the notion of totally equimodular matrices, which still have nice polyhedral properties.

**Box-integrality.** In combinatorial optimization and integer programming, a desirable property for polyhedra is to be integer, as then the vertices can be seen as combinatorial objects. Henceforth, many results in those fields are devoted to the study of properties and descriptions of integer polyhedra. The stronger property of being box-integer is far less studied. Nevertheless, some important classes of polyhedra are known to be box-integer, such as polymatroids [21], and more generally box-totally dual integer polyhedra [38]. Box-integrality plays some role for polyhedra to have the Integer Carathéodory Property in [27]. Binary clutters being $\frac{1}{k}$-box-integer for all $k \in \mathbb{Z}_{>0}$ are characterized in [24].

Actually, all these examples of box-integer polyhedra are principally box-integer. Our characterizations then yield new insights towards their properties.
**Unimodular matrices.** The notion of unimodularity dates back to Smith [43] and ensures that a linear system has an integral solution for each integer right-hand side. Hoffman and Kruskal [31] proved that integral solutions still exist under the weaker condition that (*) the gcd of the $r \times r$ determinants equals 1. Condition (*) and equimodularity are complementary generalizations of unimodularity, in the sense that if an integer matrix is equimodular and satisfies (*), then it is unimodular. Hoffman and Oppenheim [30] introduced variants of unimodularity, which were afterward studied by Truemper [44]. In [7,28], it is proved that equimodular matrices ensure that all basic solutions are integer, provided that one of them is—see also Barnett [5, Chap. 7].

The stronger notion of total unimodularity plays a central role in combinatorial optimization. A matrix is *totally unimodular* when all its subdeterminants have value in $\{0, \pm 1\}$. Examples of such matrices are network matrices and incidence matrices of bipartite graphs. Hoffman and Kruskal [31] characterized totally unimodular matrices to be the matrices for which the associated polyhedra are all box-integer. Several other characterizations were obtained since then—see e.g. [10] and [25]. Totally unimodular matrices are now well understood due to the decomposition theorem of Seymour [40]. For a survey of related results, we refer to [38, Chap. 4 and 19]. More recently, Appa [2] and Appa and Kotnyek [3] generalized total unimodularity to rational matrices, their goal being to ensure the integrality of the associated family of polyhedra for a specified set of right-hand sides, such as those with only even coordinates. In another direction, Lee [33] generalized totally unimodular matrices by considering the associated linear spaces. The connections between his results and the previous ones are discussed in Kotnyek's thesis [32, Chap. 11].

We will see how principal box-integrality fits within the characterization of unimodular matrices by Veinott and Dantzig [45] and that of totally unimodular matrices due to Hoffman and Kruskal [31]. Then, these results are naturally extended to characterize equimodular matrices. Also, a new generalization of totally unimodular matrices appears in Section 4.1, the notion of totally equimodular matrices, which still have nice polyhedral properties.

**Box-integrality.** In combinatorial optimization and integer programming, a desirable property for polyhedra is to be integer, as then the vertices can be seen as combinatorial objects. Henceforth, many results in those fields are devoted to the study of properties and descriptions of integer polyhedra. The stronger property of being box-integer is far less studied. Nevertheless, some important classes of polyhedra are known to be box-integer, such as polymatroids [21], and more generally box-totally dual integer polyhedra [38]. Box-integrality plays some role for polyhedra to have the Integer Carathéodory Property in [27]. Binary clutters being $\frac{1}{k}$-box-integer for all $k \in \mathbb{Z}_{>0}$ are characterized in [24].

Actually, all these examples of box-integer polyhedra are principally box-integer. Our characterizations then yield new insights towards their properties.
**Box-total dual integrality.** Box-total dual integral (box-TDI) systems and polyhedra received a lot of attention from the combinatorial optimization community around the 80s. These systems yield strong combinatorial min-max relations with a geometric interpretation. A renewed interest appeared in the last decade and since then many deep results appeared involving such systems. The famous MaxFlow-MinCut theorem of Ford and Fulkerson [23] is a typical example of min-max relation implied by the box-TDIness of a system. Other examples of fundamental box-TDI systems appear for polymatroids and for systems with a totally unimodular matrix of constraints.

Originally, box-TDI systems were closely related to totally unimodular matrices. Indeed, any system with a totally unimodular matrix of constraint is box-TDI. Actually, until recently, the vast majority of known box-TDI systems were defined by a totally unimodular matrix, see [39] for examples. When the constraint matrix is not totally unimodular, proving that a given system is box-TDI can be quite a challenge: one has to prove its TDIness, and then to deal with the addition of box-contraints that perturb the combinatorial interpretation of the underlying min-max relation. Ding, Feng, and Zang prove in [16] that it is NP-hard to recognize box-TDI systems.

Based on an idea of Ding and Zang [18], Chen, Chen, and Zang provide in [11] a sufficient condition for some systems to be box-TDI, namely the ESP property. Due to its purely combinatorial nature, the ESP property is successfully used to characterize: box-Mengerian matroid ports in [11], the box-TDIness of the matching polytope in [17], subclasses of box-perfect graphs in [19]. Prior to the development of the ESP property, the main tool to prove box-TDIness was [38, Theorem 22.9] of Cook. Its pratical application turns out to be quite technical as one has to combine polyhedral and combinatorial considerations, such as in [13] where the box-TDIness of a system describing the 2-edge-connected spanning subgraph polytope on series-parallel graphs is proved. In [15], Cornaz, Grappe, and Lacroix prove that a number of standard systems are box-TDI if and only if the graph is series-parallel.

**Contributions.** Our results provide a framework within which the notions of equimodularity, principal box-integrality, and box-TDIness are all connected. The point of view obtained from principally box-integer polyhedra unveils new properties and simplifies the approach.

We now state our main result. A *face-defining matrix* for a polyhedron is a full row rank matrix describing the affine hull of a face of the polyhedron—see Section 4.2 for more details.

**Theorem 2** For a polyhedron P, the following statements are equivalent.

1. *The polyhedron P is box-TDI.*

1. The polyhedron *P* is box-TDI.

2. The polyhedron *P* is principally box-integer.

3. Every face-defining matrix of *P* is equimodular.

4. Every face of *P* has an equimodular face-defining matrix.

5. Every face of *P* has a totally unimodular face-defining matrix.

**Theorem 2** For a polyhedron *P*, the following statements are equivalent.
**Box-total dual integrality.** Box-total dual integral (box-TDI) systems and polyhedra received a lot of attention from the combinatorial optimization community around the 80s. These systems yield strong combinatorial min-max relations with a geometric interpretation. A renewed interest appeared in the last decade and since then many deep results appeared involving such systems. The famous MaxFlow-MinCut theorem of Ford and Fulkerson [23] is a typical example of min-max relation implied by the box-TDIness of a system. Other examples of fundamental box-TDI systems appear for polymatroids and for systems with a totally unimodular matrix of constraints.

Originally, box-TDI systems were closely related to totally unimodular matrices. Indeed, any system with a totally unimodular matrix of constraint is box-TDI. Actually, until recently, the vast majority of known box-TDI systems were defined by a totally unimodular matrix, see [39] for examples. When the constraint matrix is not totally unimodular, proving that a given system is box-TDI can be quite a challenge: one has to prove its TDIness, and then to deal with the addition of box-contraints that perturb the combinatorial interpretation of the underlying min-max relation. Ding, Feng, and Zang prove in [16] that it is NP-hard to recognize box-TDI systems.

Based on an idea of Ding and Zang [18], Chen, Chen, and Zang provide in [11] a sufficient condition for some systems to be box-TDI, namely the ESP property. Due to its purely combinatorial nature, the ESP property is successfully used to characterize: box-Mengerian matroid ports in [11], the box-TDIness of the matching polytope in [17], subclasses of box-perfect graphs in [19]. Prior to the development of the ESP property, the main tool to prove box-TDIness was [38, Theorem 22.9] of Cook. Its pratical application turns out to be quite technical as one has to combine polyhedral and combinatorial considerations, such as in [13] where the box-TDIness of a system describing the 2-edge-connected spanning subgraph polytope on series-parallel graphs is proved. In [15], Cornaz, Grappe, and Lacroix prove that a number of standard systems are box-TDI if and only if the graph is series-parallel.

**Contributions.** Our results provide a framework within which the notions of equimodularity, principal box-integrality, and box-TDIness are all connected. The point of view obtained from principally box-integer polyhedra unveils new properties and simplifies the approach.

We now state our main result. A *face-defining matrix* for a polyhedron is a full row rank matrix describing the affine hull of a face of the polyhedron—see Section 4.2 for more details.

**Theorem 2** For a polyhedron P, the following statements are equivalent.

1. *The polyhedron P is box-TDI.*

1. The polyhedron *P* is box-TDI.

2. The polyhedron *P* is principally box-integer.

3. Every face-defining matrix of *P* is equimodular.

4. Every face of *P* has an equimodular face-defining matrix.

5. Every face of *P* has a totally unimodular face-defining matrix.

**Theorem 2** For a polyhedron *P*, the following statements are equivalent.
Along our proof, we show that a polyhedral cone is box-TDI if and only if it is box-integer, and that these properties are carried over to its polar. We use this to derive a polar version of Theorem 2—see Corollary 6.

These new results allow us to prove the box-TDIness of systems by making full use of Theorem 1: find a TDI system describing the polyhedron on the one hand, and, on the other hand, apply one of the characterizations of principally box-integer polyhedra to prove the box-TDIness of the polyhedron. In particular, when a TDI system that describes the polyhedron is already known, our characterizations allow us to pick whichever system—TDI or not—describing the polyhedron, and to use algebraic tools to prove the “box” part. The drawback of our characterization is that it does not provide a box-TDI system describing the polyhedron. Nevertheless, one of our characterizations gives an easy way to disprove box-TDIness: it is enough to exhibit a face-defining matrix having two maximal nonzero determinants of different absolute values. In particular, this provides a simple co-NP certificate for the box-TDIness of a polyhedron.

We show how known results on box-TDI polyhedra are simple consequences of our characterizations—see Section 5.2. We also explain how our results are connected with Schrijver’s sufficient condition [39, Theorem 5.35] and Cook’s characterization [14], [38, Theorem 22.9].

We illustrate the use of our characterizations on several examples—see Section 6. First, we explain the equivalence between the main result of Gerards and Laurent [24] and that of Chen, Ding, and Zang [12] about binary clutters. As a second application, we disprove a conjecture of Ding, Zang, and Zhao [19] about box-perfect graphs. Then, we discuss Gijswijt and Regts [27]’s abstract class of polyhedra having the Integer Carathéodory Property and possible connections between principal box-integrality and the integer decomposition property. Finally, we prove that the cone of conservative functions of a graph is box-TDI if and only if the graph is series-parallel and we provide a box-TDI system describing it.

*Outline.* Section 2 contains standard definitions. In Section 3, we study general properties of principally box-integer polyhedra. Section 4 shows how equimodularity and principal box-integrality are intertwined: each notion is characterized using the other one. In Section 5, we first prove that a polyhedron is box-TDI if and only if it is principally box-integer, and then discuss the connections between our characterizations and existing results about box-TDI polyhedra. In Section 6, we illustrate the use of our characterizations on several examples.

## 2 Definitions

*Matrices.* Throughout the paper, all entries will be rational. The *i*th unit vector of $\mathbb{R}^n$ will be denoted by $\chi^i$. For $I \subseteq \{1, \dots, n\}$, let $\chi^I = \sum_{i \in I} \chi^i$. An
Along our proof, we show that a polyhedral cone is box-TDI if and only if it is box-integer, and that these properties are carried over to its polar. We use this to derive a polar version of Theorem 2—see Corollary 6.

These new results allow us to prove the box-TDIness of systems by making full use of Theorem 1: find a TDI system describing the polyhedron on the one hand, and, on the other hand, apply one of the characterizations of principally box-integer polyhedra to prove the box-TDIness of the polyhedron. In particular, when a TDI system that describes the polyhedron is already known, our characterizations allow us to pick whichever system—TDI or not—describing the polyhedron, and to use algebraic tools to prove the “box” part. The drawback of our characterization is that it does not provide a box-TDI system describing the polyhedron. Nevertheless, one of our characterizations gives an easy way to disprove box-TDIness: it is enough to exhibit a face-defining matrix having two maximal nonzero determinants of different absolute values. In particular, this provides a simple co-NP certificate for the box-TDIness of a polyhedron.

We show how known results on box-TDI polyhedra are simple consequences of our characterizations—see Section 5.2. We also explain how our results are connected with Schrijver’s sufficient condition [39, Theorem 5.35] and Cook’s characterization [14], [38, Theorem 22.9].

We illustrate the use of our characterizations on several examples—see Section 6. First, we explain the equivalence between the main result of Gerards and Laurent [24] and that of Chen, Ding, and Zang [12] about binary clutters. As a second application, we disprove a conjecture of Ding, Zang, and Zhao [19] about box-perfect graphs. Then, we discuss Gijswijt and Regts [27]’s abstract class of polyhedra having the Integer Carathéodory Property and possible connections between principal box-integrality and the integer decomposition property. Finally, we prove that the cone of conservative functions of a graph is box-TDI if and only if the graph is series-parallel and we provide a box-TDI system describing it.

*Outline.* Section 2 contains standard definitions. In Section 3, we study general properties of principally box-integer polyhedra. Section 4 shows how equimodularity and principal box-integrality are intertwined: each notion is characterized using the other one. In Section 5, we first prove that a polyhedron is box-TDI if and only if it is principally box-integer, and then discuss the connections between our characterizations and existing results about box-TDI polyhedra. In Section 6, we illustrate the use of our characterizations on several examples.

## 2 Definitions

*Matrices.* Throughout the paper, all entries will be rational. The *i*th unit vector of $\mathbb{R}^n$ will be denoted by $\chi^i$. For $I \subseteq \{1, \dots, n\}$, let $\chi^I = \sum_{i \in I} \chi^i$. An
element $A$ of $\mathbb{R}^{m \times n}$ will be thought of as a matrix with $m$ rows and $n$ columns, and an element $b$ of $\mathbb{R}^m$ as a column vector. When all their entries belong to $\mathbb{Z}$, we will call them *integer*. The row vectors of $A$ will be denoted by $a_i^\top$, the column vectors of $A$ by $A^i$. When rank($A$) = $m$, we say that $A$ has *full row rank*. A matrix is *totally unimodular*, or *TU*, if the determinants of its square submatrices are equal to -1, 0 or 1.

**Lattices.** The lattice generated by a set $V$ of vectors of $\mathbb{Q}^n$ is the set of integer combinations of these vectors, and is denoted by lattice($V$) = $\{\sum_{v \in V} \lambda_v v : \lambda_v \in \mathbb{Z}$ for all $v \in V\}$. The lattice generated by the column vectors of a matrix $A$ is denoted by lattice($A$).

**Polyhedra.** Given $A \in \mathbb{Q}^{m \times n}$ and $b \in \mathbb{Q}^m$, the set $P = \{x \in \mathbb{R}^n : Ax \leq b\} = \{x \in \mathbb{R}^n : a_i^\top x \leq b_i, i = 1, \dots, m\}$ is a *polyhedron*. We will often simply write $P = \{x : Ax \leq b\}$. The matrix $A$ is the *constraint matrix* of $P$. The *translation* of $P$ by $w \in \mathbb{R}^n$ is $P + w = \{x + w : x \in P\}$.

A face of $P$ is a nonempty<fnref n="1" /> set obtained by imposing equality on some inequalities in the description of $P$, that is, a nonempty set of the form $F = \{x : a_i^\top x = b_i, i \in I\} \cap P$ where $I \subseteq \{1, \dots, m\}$. A row $a_i^\top$ or an inequality $a_i^\top x \leq b_i$ with $F \subseteq \{x : a_i^\top x = b_i\}$ is *tight for F*, and $A_F x \leq b_F$ will denote the inequalities from $Ax \leq b$ that are tight for $F$. The set of points contained in $F$ and in no face $F' \subset F$ forms the *relative interior of F*. Let $\text{lin}(F) = \{x : A_F x = \mathbf{0}\}$ and $\text{aff}(F) = \{x : A_F x = b_F\}$. The dimension $\text{dim}(F)$ of a face $F$ is the dimension of its affine hull $\text{aff}(F)$. A *facet* is a face that is inclusionwise maximal among all faces distinct from $P$. A face is *minimal* if it contains no other face of $P$. Minimal faces are affine spaces. A minimal face of dimension 0 is called a *vertex*. Note that a polyhedron is integer if and if each of its minimal faces contains an integer point.

**Cones.** A *polyhedral cone* is a polyhedron of the form $C = \{x : Ax \leq \mathbf{0}\}$. Since all the cones involved in this paper are polyhedral, we simply write *cone*. A cone $C$ can also be described as the set of nonnegative combinations of a finite set of vectors $R \subseteq \mathbb{R}^n$, and we say that $C = \text{cone}(R)$ is *generated by R*. A *conic polyhedron* is a rational translation of a cone, that is, a set of the form $t + \{x : Ax \leq \mathbf{0}\}$ for some $t \in \mathbb{Q}^n$.

The *polar cone* of a cone $C = \{x : Ax \leq \mathbf{0}\}$ is the cone $C^* = \{x : z^\top x \leq 0 \text{ for all } z \in C\}$. Equivalently, $C^*$ is the cone generated by the columns of $A^\top$. Note that $C^{**} = C$.

Given a face $F$ of a polyhedron $P = \{x : Ax \leq b\}$, the *tangent cone associated to* $F$ is the conic polyhedron $C_F = \{x : A_F x \leq b_F\}$. When $F$ is a minimal face of $P$, its associated tangent cone is a *minimal tangent cone of P*. The cone of $\mathbb{R}^n$ generated by the columns of $A_F^\top$ is the *normal cone associated to* $F$. Note that the normal cone associated to $F$ is the polar of $\{x : A_F x \leq \mathbf{0}\}$.

For more details, we refer the reader to Schrijver's book [38].

<footnote n="1">¹ In the standard definition, the emptyset is a face. It is not the case in this paper in order to lighten the statements.</footnote>
element $A$ of $\mathbb{R}^{m \times n}$ will be thought of as a matrix with $m$ rows and $n$ columns, and an element $b$ of $\mathbb{R}^m$ as a column vector. When all their entries belong to $\mathbb{Z}$, we will call them *integer*. The row vectors of $A$ will be denoted by $a_i^\top$, the column vectors of $A$ by $A^i$. When rank($A$) = $m$, we say that $A$ has *full row rank*. A matrix is *totally unimodular*, or *TU*, if the determinants of its square submatrices are equal to -1, 0 or 1.

**Lattices.** The lattice generated by a set $V$ of vectors of $\mathbb{Q}^n$ is the set of integer combinations of these vectors, and is denoted by lattice($V$) = $\{\sum_{v \in V} \lambda_v v : \lambda_v \in \mathbb{Z}$ for all $v \in V\}$. The lattice generated by the column vectors of a matrix $A$ is denoted by lattice($A$).

**Polyhedra.** Given $A \in \mathbb{Q}^{m \times n}$ and $b \in \mathbb{Q}^m$, the set $P = \{x \in \mathbb{R}^n : Ax \leq b\} = \{x \in \mathbb{R}^n : a_i^\top x \leq b_i, i = 1, \dots, m\}$ is a *polyhedron*. We will often simply write $P = \{x : Ax \leq b\}$. The matrix $A$ is the *constraint matrix* of $P$. The *translation* of $P$ by $w \in \mathbb{R}^n$ is $P + w = \{x + w : x \in P\}$.

A face of $P$ is a nonempty<fnref n="1" /> set obtained by imposing equality on some inequalities in the description of $P$, that is, a nonempty set of the form $F = \{x : a_i^\top x = b_i, i \in I\} \cap P$ where $I \subseteq \{1, \dots, m\}$. A row $a_i^\top$ or an inequality $a_i^\top x \leq b_i$ with $F \subseteq \{x : a_i^\top x = b_i\}$ is *tight for F*, and $A_F x \leq b_F$ will denote the inequalities from $Ax \leq b$ that are tight for $F$. The set of points contained in $F$ and in no face $F' \subset F$ forms the *relative interior of F*. Let $\text{lin}(F) = \{x : A_F x = \mathbf{0}\}$ and $\text{aff}(F) = \{x : A_F x = b_F\}$. The dimension $\text{dim}(F)$ of a face $F$ is the dimension of its affine hull $\text{aff}(F)$. A *facet* is a face that is inclusionwise maximal among all faces distinct from $P$. A face is *minimal* if it contains no other face of $P$. Minimal faces are affine spaces. A minimal face of dimension 0 is called a *vertex*. Note that a polyhedron is integer if and if each of its minimal faces contains an integer point.

**Cones.** A *polyhedral cone* is a polyhedron of the form $C = \{x : Ax \leq \mathbf{0}\}$. Since all the cones involved in this paper are polyhedral, we simply write *cone*. A cone $C$ can also be described as the set of nonnegative combinations of a finite set of vectors $R \subseteq \mathbb{R}^n$, and we say that $C = \text{cone}(R)$ is *generated by R*. A *conic polyhedron* is a rational translation of a cone, that is, a set of the form $t + \{x : Ax \leq \mathbf{0}\}$ for some $t \in \mathbb{Q}^n$.

The *polar cone* of a cone $C = \{x : Ax \leq \mathbf{0}\}$ is the cone $C^* = \{x : z^\top x \leq 0 \text{ for all } z \in C\}$. Equivalently, $C^*$ is the cone generated by the columns of $A^\top$. Note that $C^{**} = C$.

Given a face $F$ of a polyhedron $P = \{x : Ax \leq b\}$, the *tangent cone associated to* $F$ is the conic polyhedron $C_F = \{x : A_F x \leq b_F\}$. When $F$ is a minimal face of $P$, its associated tangent cone is a *minimal tangent cone of P*. The cone of $\mathbb{R}^n$ generated by the columns of $A_F^\top$ is the *normal cone associated to* $F$. Note that the normal cone associated to $F$ is the polar of $\{x : A_F x \leq \mathbf{0}\}$.

For more details, we refer the reader to Schrijver's book [38].

<footnote n="1">¹ In the standard definition, the emptyset is a face. It is not the case in this paper in order to lighten the statements.</footnote>
**3 Generalities on Principally Box-Integer Polyhedra**

This section is devoted to the basic properties of box-integer and principally box-integer polyhedra. In particular, we study the behavior of these notions with respect to dilation and translation.

**3.1 Box-Integer Polyhedra**

Recall that a polyhedron $P$ is box-integer if $P \cap \{\ell \le x \le u\}$ is integer for all $\ell, u \in \mathbb{Z}^n$. Frequently, the following characterization will be more convenient to use than the definition.

**Lemma 1** A polyhedron $P$ is box-integer if and only if for each face $F$ of $P$, $I \subseteq \{1, \dots, n\}$, and $p \in \mathbb{Z}^I$ such that $\text{aff}(F) \cap \{x_i = p_i, i \in I\}$ is a singleton $v$, if $v$ belongs to $F$ then $v$ is integer.

*Proof.* Let $P = \{x \in \mathbb{R}^n : Ax \le b\}$. Suppose that $P$ is not box-integer. Then, $P \cap \{\ell \le x \le u\}$ has a noninteger vertex $v$ for some $\ell, u \in \mathbb{Z}^n$. In particular, $v$ belongs to $P \cap \{\ell \le x \le u\}$ and is the unique solution of a nonsingular system $a_jx = b_j, j \in J, x_i = p_i, i \in I$ where $p_i \in \{\ell_i, u_i\}$. Now, $F = \{x : a_jx = b_j, j \in J\} \cap P$ is a face of $P$, and $\{v\} = \text{aff}(F) \cap \{x_i = p_i, i \in I\}$ is not integer.

Conversely, suppose that $\{v\} = \text{aff}(F) \cap \{x_i = p_i, i \in I\}$ belongs to $F$ and is not integer, for some $p \in \mathbb{Z}^I$. Define $\ell$ and $u$ as follows: $\ell_i = u_i = p_i$ for $i \in I$, and $\ell_i = \lfloor v_i \rfloor$ and $u_i = \lceil v_i \rceil$ otherwise. Then, $v$ is a noninteger vertex of $P \cap \{\ell \le x \le u\}$ and $P$ is not box-integer.

□

Note that, if $I$ is such that the set $\text{aff}(F) \cap \{x_i = p_i, i \in I\}$ is a singleton for some $p \in \mathbb{R}^I$, then this set is either empty or a singleton for all $p \in \mathbb{R}^I$. If $I$ is moreover assumed inclusionwise minimal, then $\text{aff}(F) \cap \{x_i = p_i, i \in I\}$ is a singleton for all $p \in \mathbb{R}^I$.

The following two results seem to be known in the literature, we provide a proof for the sake of completeness.

**Corollary 1** If a polyhedron $P$ is box-integer, then $P$ is integer.

*Proof.* Let $F$ be a minimal face of $P$. There exists an inclusionwise minimal set $I$ as above, hence setting $\{x_i = p_i, i \in I\}$ for some $p \in \mathbb{Z}^I$ yields a singleton in $\text{aff}(F)$. Since $\text{aff}(F) = F$, this singleton is integer by Lemma 1, and thus $F$ contains an integer point. $\square$

**Corollary 2** Let $P$ be a polyhedron of $\mathbb{R}^n$. The following statements are equivalent.

1. $P$ is box-integer.

2. $P \cap \{x \ge \ell\}$ is integer for all $\ell \in \mathbb{Z}^n$.
**3 Generalities on Principally Box-Integer Polyhedra**

This section is devoted to the basic properties of box-integer and principally box-integer polyhedra. In particular, we study the behavior of these notions with respect to dilation and translation.

**3.1 Box-Integer Polyhedra**

Recall that a polyhedron $P$ is box-integer if $P \cap \{\ell \le x \le u\}$ is integer for all $\ell, u \in \mathbb{Z}^n$. Frequently, the following characterization will be more convenient to use than the definition.

**Lemma 1** *A polyhedron $P$ is box-integer if and only if for each face $F$ of $P$, $I \subseteq \{1, \dots, n\}$, and $p \in \mathbb{Z}^I$ such that $\text{aff}(F) \cap \{x_i = p_i, i \in I\}$ is a singleton $v$, if $v$ belongs to $F$ then $v$ is integer.*

*Proof.* Let $P = \{x \in \mathbb{R}^n : Ax \le b\}$. Suppose that $P$ is not box-integer. Then, $P \cap \{\ell \le x \le u\}$ has a noninteger vertex $v$ for some $\ell, u \in \mathbb{Z}^n$. In particular, $v$ belongs to $P \cap \{\ell \le x \le u\}$ and is the unique solution of a nonsingular system $a_jx = b_j, j \in J, x_i = p_i, i \in I$ where $p_i \in \{\ell_i, u_i\}$. Now, $F = \{x : a_jx = b_j, j \in J\} \cap P$ is a face of $P$, and $\{v\} = \text{aff}(F) \cap \{x_i = p_i, i \in I\}$ is not integer.

Conversely, suppose that $\{v\} = \text{aff}(F) \cap \{x_i = p_i, i \in I\}$ belongs to $F$ and is not integer, for some $p \in \mathbb{Z}^I$. Define $\ell$ and $u$ as follows: $\ell_i = u_i = p_i$ for $i \in I$, and $\ell_i = \lfloor v_i \rfloor$ and $u_i = \lceil v_i \rceil$ otherwise. Then, $v$ is a noninteger vertex of $P \cap \{\ell \le x \le u\}$ and $P$ is not box-integer.

□

Note that, if $I$ is such that the set $\text{aff}(F) \cap \{x_i = p_i, i \in I\}$ is a singleton for some $p \in \mathbb{R}^I$, then this set is either empty or a singleton for all $p \in \mathbb{R}^I$. If $I$ is moreover assumed inclusionwise minimal, then $\text{aff}(F) \cap \{x_i = p_i, i \in I\}$ is a singleton for all $p \in \mathbb{R}^I$.

The following two results seem to be known in the literature, we provide a proof for the sake of completeness.

**Corollary 1** *If a polyhedron $P$ is box-integer, then $P$ is integer.*

*Proof.* Let $F$ be a minimal face of $P$. There exists an inclusionwise minimal set $I$ as above, hence setting $\{x_i = p_i, i \in I\}$ for some $p \in \mathbb{Z}^I$ yields a singleton in $\text{aff}(F)$. Since $\text{aff}(F) = F$, this singleton is integer by Lemma 1, and thus $F$ contains an integer point. $\square$

**Corollary 2** *Let $P$ be a polyhedron of $\mathbb{R}^n$. The following statements are equivalent.*

1. $P$ is box-integer.

2. $P \cap \{x \ge \ell\}$ is integer for all $\ell \in \mathbb{Z}^n$.
3. $P \cap \{\ell \le x \le u\}$ is integer for all $\ell, u \in \mathbb{Z} \cup \{-\infty, +\infty\}^n$.

*Proof.* Statement 3 immediately implies statement 2. Statement 2 implies statement 1 by Lemma 1, as if $aff(F) \cap \{x_i = p_i, i \in I\}$ is a singleton $v \in F$, then $v$ is a vertex of $P \cap \{x \ge \lfloor v \rfloor\}$. Statement 1 implies statement 3 because if $P$ is box-integer, then for all $\ell, u \in \mathbb{Z} \cup \{-\infty, +\infty\}^n$, $P \cap \{\ell \le x \le u\}$ is box-integer—and hence integer by Corollary 1. $\square$

The following lemma shows two operations which preserve box-integrality.
The second one will be used in Section 5.

**Lemma 2** Let $P = \{x \in \mathbb{R}^n : Ax \le b\}$ be a polyhedron.

1. $P$ is box-integer if and only if $\tilde{P} = \{(y, z) \in \mathbb{R}^n \times \mathbb{R}^n : A(y+z) \le b\}$ is box-integer.

2. $P$ is box-integer if and only if $P_{\pm} = \{(y, z) \in \mathbb{R}^n \times \mathbb{R}^n : A(y-z) \le b, y, z \ge 0\}$ is box-integer.

*Proof.* To establish the “only if” part of statement 1, suppose that $\tilde{P}$ is box-integer. Then, so is $\tilde{P} \cap \{z = 0\}$. Since $P$ is obtained from $\tilde{P} \cap \{z = 0\}$ by deleting the $z$'s coordinates, $P$ is box-integer. To establish the “if” part of statement 1, we use Lemma 1. Let $F$ be a face of $\tilde{P}$, of affine space $aff(F) = \{(y, z) \in \mathbb{R}^n \times \mathbb{R}^n : a_j(y+z) = b_j, j \in J\}$, and let $p$ and $q$ be integer vectors such that $S = aff(F) \cap \{y_i = p_i, i \in I_y, z_i = q_i, i \in I_z\}$ is a singleton $(\bar{y}, \bar{z})$ which belongs to $F$. Let us show that $(\bar{y}, \bar{z})$ is integer. By Lemma 1, this implies that $\tilde{P}$ is box-integer.

We denote by $G$ the face of $P$ of affine space $\{x \in \mathbb{R}^n : a_j x = b_j, j \in J\}$. Then $aff(G) \cap \{x_i = p_i + q_i, i \in I_y \cap I_z\}$ is the singleton $\bar{x} = \bar{y} + \bar{z}$. Indeed, if it contained an other point $\bar{x}'$, we could set $\bar{y}'_i = p_i, i \in I_y, \bar{z}'_i = q_i, i \in I_z$ and then build $(\bar{y}', \bar{z}')$ in $S$ such that $\bar{y} + \bar{z}' = \bar{x}' \ne \bar{y} + \bar{z}$, a contradiction. $P$ is box-integer and $\bar{y} + \bar{z}$ belongs to $P$, thus $\bar{y} + \bar{z}$ is integer by Lemma 1. Since $S$ is a singleton, no $(\bar{y} + \chi_i, \bar{z} - \chi_i)$ belongs to $S$, and for all $i$, we have either $y_i = p_i$ or $z_i = q_i$. Since $p, q$, and $\bar{y} + \bar{z}$ are integer, $(\bar{y}, \bar{z})$ is integer.

To establish the “only if” part of statement 2, suppose that $P$ is box-integer. Then, so is $P_{\pm}$ by statement 1 and because $P_{\pm}$ is obtained from $\tilde{P} \cap \{y \ge 0, z \ge 0\}$ by replacing $z$ by $-z$. To establish the “if” part of statement 2, suppose now that $P_{\pm}$ is box-integer. For $t \in \mathbb{R}^n$, define $t_+ = \max\{0, t\}$ and $t_- = \max\{0, -t\}$. For $\ell, u \in \mathbb{Z}^n$, we have $u = u_+ - u_-$, $\ell = \ell_+ - \ell-$, and $u_+, u_-, \ell_+, \ell_- \ge 0$, hence $P \cap \{\ell \le x \le u\}$ is the projection onto $x = y-z$ of $P_{\pm} \cap \{\ell_+ \le y \le u_+, -\ell_- \le -z \le -u_\-\}$. Since the latter is integer, this implies the integrality of $P \cap \{\ell \le x \le u\}$. $\square$

## 3.2 Dilations of Box-Integer Polyhedra

In this section we investigate how the box-integrality of a polyhedron behaves with respect to dilation. As a preliminary, the following observation describes the behaviour of integrality with respect to dilation.
3. $P \cap \{\ell \le x \le u\}$ is integer for all $\ell, u \in \mathbb{Z} \cup \{-\infty, +\infty\}^n$.

*Proof.* Statement 3 immediately implies statement 2. Statement 2 implies statement 1 by Lemma 1, as if $aff(F) \cap \{x_i = p_i, i \in I\}$ is a singleton $v \in F$, then $v$ is a vertex of $P \cap \{x \ge \lfloor v \rfloor\}$. Statement 1 implies statement 3 because if $P$ is box-integer, then for all $\ell, u \in \mathbb{Z} \cup \{-\infty, +\infty\}^n$, $P \cap \{\ell \le x \le u\}$ is box-integer—and hence integer by Corollary 1. $\square$

The following lemma shows two operations which preserve box-integrality.
The second one will be used in Section 5.

**Lemma 2** Let $P = \{x \in \mathbb{R}^n : Ax \le b\}$ be a polyhedron.

1. $P$ is box-integer if and only if $\tilde{P} = \{(y, z) \in \mathbb{R}^n \times \mathbb{R}^n : A(y+z) \le b\}$ is box-integer.

2. $P$ is box-integer if and only if $P_{\pm} = \{(y, z) \in \mathbb{R}^n \times \mathbb{R}^n : A(y-z) \le b, y, z \ge 0\}$ is box-integer.

*Proof.* To establish the “only if” part of statement 1, suppose that $\tilde{P}$ is box-integer. Then, so is $\tilde{P} \cap \{z = 0\}$. Since $P$ is obtained from $\tilde{P} \cap \{z = 0\}$ by deleting the $z$'s coordinates, $P$ is box-integer. To establish the “if” part of statement 1, we use Lemma 1. Let $F$ be a face of $\tilde{P}$, of affine space $aff(F) = \{(y, z) \in \mathbb{R}^n \times \mathbb{R}^n : a_j(y+z) = b_j, j \in J\}$, and let $p$ and $q$ be integer vectors such that $S = aff(F) \cap \{y_i = p_i, i \in I_y, z_i = q_i, i \in I_z\}$ is a singleton $(\bar{y}, \bar{z})$ which belongs to $F$. Let us show that $(\bar{y}, \bar{z})$ is integer. By Lemma 1, this implies that $\tilde{P}$ is box-integer.

We denote by $G$ the face of $P$ of affine space $\{x \in \mathbb{R}^n : a_j x = b_j, j \in J\}$. Then $aff(G) \cap \{x_i = p_i + q_i, i \in I_y \cap I_z\}$ is the singleton $\bar{x} = \bar{y} + \bar{z}$. Indeed, if it contained an other point $\bar{x}'$, we could set $\bar{y}'_i = p_i, i \in I_y, \bar{z}'_i = q_i, i \in I_z$ and then build $(\bar{y}', \bar{z}')$ in $S$ such that $\bar{y} + \bar{z}' = \bar{x}' \ne \bar{y} + \bar{z}$, a contradiction. $P$ is box-integer and $\bar{y} + \bar{z}$ belongs to $P$, thus $\bar{y} + \bar{z}$ is integer by Lemma 1. Since $S$ is a singleton, no $(\bar{y} + \chi_i, \bar{z} - \chi_i)$ belongs to $S$, and for all $i$, we have either $y_i = p_i$ or $z_i = q_i$. Since $p, q$, and $\bar{y} + \bar{z}$ are integer, $(\bar{y}, \bar{z})$ is integer.

To establish the “only if” part of statement 2, suppose that $P$ is box-integer. Then, so is $P_{\pm}$ by statement 1 and because $P_{\pm}$ is obtained from $\tilde{P} \cap \{y \ge 0, z \ge 0\}$ by replacing $z$ by $-z$. To establish the “if” part of statement 2, suppose now that $P_{\pm}$ is box-integer. For $t \in \mathbb{R}^n$, define $t_+ = \max\{0, t\}$ and $t_- = \max\{0, -t\}$. For $\ell, u \in \mathbb{Z}^n$, we have $u = u_+ - u_-$, $\ell = \ell_+ - \ell-$, and $u_+, u_-, \ell_+, \ell_- \ge 0$, hence $P \cap \{\ell \le x \le u\}$ is the projection onto $x = y-z$ of $P_{\pm} \cap \{\ell_+ \le y \le u_+, -\ell_- \le -z \le -u_\-\}$. Since the latter is integer, this implies the integrality of $P \cap \{\ell \le x \le u\}$. $\square$

## 3.2 Dilations of Box-Integer Polyhedra

In this section we investigate how the box-integrality of a polyhedron behaves with respect to dilation. As a preliminary, the following observation describes the behaviour of integrality with respect to dilation.
**Proposition 1** Let $P$ be a polyhedron. There exists $d \in \mathbb{Z}_{>0}$ such that $\{k \in \mathbb{Z}_{>0} : kP \text{ is integer}\} = d\mathbb{Z}_{>0}$.

*Proof.* When $P$ has vertices, it is enough to choose $d$ as the smallest positive integer $d$ such $dv$ is integer for every vertex $v$ of $P$. To treat the general case, we prove that if $kP$ and $k'P$ are integer polyhedra, then $\gcd(k, k')P$ is an integer polyhedron too. Then, the smallest positive integer $k$ such that $kP$ is integer divides all the others, and as any dilation of an integer polyhedron is an integer polyhedron too, this proves the observation.

Let $P = \{x : Ax \leq b\}$, $i = \gcd(k, k')$, $\bar{k} = k/i$, $\bar{k}' = k'/i$, and $F$ be a minimal face of $iP$. Since $F$ is a minimal face, $F$ is the affine space $F = \{x : A_F x = ib_F\}$. Note that $\bar{k}F$ and $\bar{k}'F$ are minimal faces, respectively of $kP$ and $k'P$, thus contain an integer point, respectively $x_k$ and $x_{k'}$. By Bézout's lemma, there exist $\lambda$ and $\mu$ in $\mathbb{Z}$ such that $\lambda k + \mu k' = i$. Then $A_F(\lambda x_k + \mu x_{k'}) = ib_F$, hence $F$ contains an integer point. Therefore, $\gcd(k, k')P$ is an integer polyhedron.
$\square$

One of the arguments in the previous proof is the fact that the dilations of an integer polyhedron are also integer polyhedra. This does not hold for box-integrality, intuitively because any 0/1 polytope is box-integer, though its dilations have no reasons to be. Actually, an example of box-integer polyhedron having non box-integer dilations will be provided at the end of this section. For now we prove the following lemma in order to determine, given a polyhedron $P$, the structure of the set of positive integers $k$ such that $kP$ is box-integer.

**Lemma 3** Let $P$ be a polyhedron and $k \in \mathbb{Z}_{>0}$ such that $kP$ is integer but not box-integer. Then, no dilation $k'P$ with $k' \ge k$ is box-integer.

*Proof.* Let $k' \ge k$. Assume $k'P$ integer, as otherwise $k'P$ would not be box-integer. By Lemma 1, there exist a face $F$ of $kP$ and an integer vector $p$ such that $\text{aff}(F) \cap \{x_i = p_i, i \in I\}$ is a noninteger singleton $v \in F$. By Proposition 1, $kP$ and $k'P$ are both dilations of an integer polyhedron $dP$. In particular, there exists an integer point $z$ in $F$ such that $z' = \frac{k'}{k}z$ is an integer point contained in the face $F' = \frac{k'}{k}F$ of $k'P$. Since $k' \ge k$, we have $F - z \subseteq F' - z'$, thus in particular $v - z$ is in $F' - z'$, which implies that $v' = (z' - z) + v$ is in $F'$. Moreover, $\text{aff}(F') \cap \{x_i = (z'_i - z_i) + p_i, i \in I\}$ is the singleton $v'$ of $F'$, which is not integer, hence $k'P$ is not box-integer by Lemma 1.
$\square$

A polyhedron $P$ is fully box-integer if $kP$ is box-integer for all $k \in \mathbb{Z}_{>0}$. In other words, $P$ is fully box-integer if and only if $P$ is principally box-integer and integer.

**Proposition 2** For a polyhedron $P$, the following statements are equivalent.

1. $P$ is principally box-integer.

2. There exists $d \in \mathbb{Z}_{>0}$ such that $\{k \in \mathbb{Z}_{>0} : kP \text{ is box-integer}\} = d\mathbb{Z}_{>0}$.

3. $P$ has a fully box-integer dilation.
**Proposition 1** Let $P$ be a polyhedron. There exists $d \in \mathbb{Z}_{>0}$ such that $\{k \in \mathbb{Z}_{>0} : kP \text{ is integer}\} = d\mathbb{Z}_{>0}$.

*Proof.* When $P$ has vertices, it is enough to choose $d$ as the smallest positive integer $d$ such $dv$ is integer for every vertex $v$ of $P$. To treat the general case, we prove that if $kP$ and $k'P$ are integer polyhedra, then $\gcd(k, k')P$ is an integer polyhedron too. Then, the smallest positive integer $k$ such that $kP$ is integer divides all the others, and as any dilation of an integer polyhedron is an integer polyhedron too, this proves the observation.

Let $P = \{x : Ax \leq b\}$, $i = \gcd(k, k')$, $\bar{k} = k/i$, $\bar{k}' = k'/i$, and $F$ be a minimal face of $iP$. Since $F$ is a minimal face, $F$ is the affine space $F = \{x : A_F x = ib_F\}$. Note that $\bar{k}F$ and $\bar{k}'F$ are minimal faces, respectively of $kP$ and $k'P$, thus contain an integer point, respectively $x_k$ and $x_{k'}$. By Bézout's lemma, there exist $\lambda$ and $\mu$ in $\mathbb{Z}$ such that $\lambda k + \mu k' = i$. Then $A_F(\lambda x_k + \mu x_{k'}) = ib_F$, hence $F$ contains an integer point. Therefore, $\gcd(k, k')P$ is an integer polyhedron. $\square$

One of the arguments in the previous proof is the fact that the dilations of an integer polyhedron are also integer polyhedra. This does not hold for box-integrality, intuitively because any 0/1 polytope is box-integer, though its dilations have no reasons to be. Actually, an example of box-integer polyhedron having non box-integer dilations will be provided at the end of this section. For now we prove the following lemma in order to determine, given a polyhedron $P$, the structure of the set of positive integers $k$ such that $kP$ is box-integer.

**Lemma 3** Let $P$ be a polyhedron and $k \in \mathbb{Z}_{>0}$ such that $kP$ is integer but not box-integer. Then, no dilation $k'P$ with $k' \ge k$ is box-integer.

*Proof.* Let $k' \ge k$. Assume $k'P$ integer, as otherwise $k'P$ would not be box-integer. By Lemma 1, there exist a face $F$ of $kP$ and an integer vector $p$ such that $\text{aff}(F) \cap \{x_i = p_i, i \in I\}$ is a noninteger singleton $v \in F$. By Proposition 1, $kP$ and $k'P$ are both dilations of an integer polyhedron $dP$. In particular, there exists an integer point $z$ in $F$ such that $z' = \frac{k'}{k}z$ is an integer point contained in the face $F' = \frac{k'}{k}F$ of $k'P$. Since $k' \ge k$, we have $F - z \subseteq F' - z'$, thus in particular $v - z$ is in $F' - z'$, which implies that $v' = (z' - z) + v$ is in $F'$. Moreover, $\text{aff}(F') \cap \{x_i = (z'_i - z_i) + p_i, i \in I\}$ is the singleton $v'$ of $F'$, which is not integer, hence $k'P$ is not box-integer by Lemma 1. $\square$

A polyhedron $P$ is fully box-integer if $kP$ is box-integer for all $k \in \mathbb{Z}_{>0}$. In other words, $P$ is fully box-integer if and only if $P$ is principally box-integer and integer.

**Proposition 2** For a polyhedron $P$, the following statements are equivalent.

1. $P$ is principally box-integer.

2. There exists $d \in \mathbb{Z}_{>0}$ such that $\{k \in \mathbb{Z}_{>0} : kP \text{ is box-integer}\} = d\mathbb{Z}_{>0}$.

3. $P$ has a fully box-integer dilation.
*Proof.* The definition of principal box-integrality and Proposition 1 give (1)⇒(2). To get (2)⇒(3), just note that $dP$ is a fully box-integer polyhedron. To prove (3)⇒(1), suppose that $P$ is not principally box-integer, that is, there exists a positive integer $k$ such that $kP$ is integer but not box-integer. By Lemma 3, this is not compatible with the existence of a fully box-integer dilation of $P$.

□

We mention that relaxing $k \in \mathbb{Z}_{>0}$ to $k \in \mathbb{Z}$ in Definition 1 yields an equivalent definition. Then, the set arising in statement 2 of Proposition 2 is $d\mathbb{Z}$, which is a principal ideal of $\mathbb{Z}$. This explains why we called these polyhedra principally box-integer. The next proposition shows what can happen when a polyhedron is not principally box-integer.

**Proposition 3** For a polyhedron $P$, exactly one of the following situations holds.

1. $P$ is principally box-integer.

2. No dilation of $P$ is a box-integer polyhedron.

3. There exist $d, q \in \mathbb{Z}_{>0}$ such that $kP$ is box-integer if and only if $k \in \{d, 2d, \dots, qd\}$.

*Proof.* If $P$ has a box-integer dilation but is not principally box-integer, then there is a smallest $q$ in $\mathbb{Z}_{>0}$ such that $(q+1)P$ is a polyhedron which is integer but not box-integer. By Lemma 3, no $kP$ with $k > q$ is box-integer. Now, if $d$ is chosen as in Proposition 1, the minimality of $q$ gives $\{k \in \mathbb{Z}_{>0} : kP \text{ is box-integer}\} = \{d, 2d, \dots, qd\}$. □

Note that the following property, which holds for integrality, also holds for box-integrality: if $kP$ and $k'P$ are box-integer polyhedra, then so is $gcd(k, k')P$.

*Remark 1* Though we only considered dilations with positive integer coefficients, all these results can readily be adapted to dilations with rational coefficients.

We conclude this section with an example of polyhedron whose box-integrality is not preserved by dilation.

As $P = \text{conv}(\mathbf{0}, (1, 1, 0, 0, 0), (1, 0, 1, 0, 0), (1, 0, 0, 1, 0), (1, 1, 1, 1, 1))$ is a $0/1$ polytope, it is box-integer. However, it can be checked that $(2, 1, 1, 1, 1/2)$ is a fractional vertex of $2P \cap \{x_2 = x_3 = x_4 = 1\}$. In particular, $P$ illustrates statement 3 of Proposition 3.

### 3.3 Translations of Principally Box-Integer Polyhedra

Box-integrality is clearly preserved under integer translation. So are principal and full box-integrality.

**Observation 1** Box-integrality, principal box-integrality and full box-integrality are all preserved by integer translation.
*Proof.* The definition of principal box-integrality and Proposition 1 give $(1)\Rightarrow(2)$. To get (2)$\Rightarrow$(3), just note that $dP$ is a fully box-integer polyhedron. To prove (3)$\Rightarrow$(1), suppose that $P$ is not principally box-integer, that is, there exists a positive integer $k$ such that $kP$ is integer but not box-integer. By Lemma 3, this is not compatible with the existence of a fully box-integer dilation of $P$.

□

We mention that relaxing $k \in \mathbb{Z}_{>0}$ to $k \in \mathbb{Z}$ in Definition 1 yields an equivalent definition. Then, the set arising in statement 2 of Proposition 2 is $d\mathbb{Z}$, which is a principal ideal of $\mathbb{Z}$. This explains why we called these polyhedra principally box-integer. The next proposition shows what can happen when a polyhedron is not principally box-integer.

**Proposition 3** For a polyhedron $P$, exactly one of the following situations holds.

1. $P$ is principally box-integer.

2. No dilation of $P$ is a box-integer polyhedron.

3. There exist $d, q \in \mathbb{Z}_{>0}$ such that $kP$ is box-integer if and only if $k \in \{d, 2d, \dots, qd\}$.

*Proof.* If $P$ has a box-integer dilation but is not principally box-integer, then there is a smallest $q$ in $\mathbb{Z}_{>0}$ such that $(q + 1)P$ is a polyhedron which is integer but not box-integer. By Lemma 3, no $kP$ with $k > q$ is box-integer. Now, if $d$ is chosen as in Proposition 1, the minimality of $q$ gives $\{k \in \mathbb{Z}_{>0} : kP$ is box-integer$\} = \{d, 2d, \dots, qd\}$. $\square$

Note that the following property, which holds for integrality, also holds for box-integrality: if $kP$ and $k'P$ are box-integer polyhedra, then so is $gcd(k, k')P$.

*Remark 1* Though we only considered dilations with positive integer coefficients, all these results can readily be adapted to dilations with rational coefficients.

We conclude this section with an example of polyhedron whose box-integrality is not preserved by dilation.

As $P = \text{conv}(\mathbf{0}, (1, 1, 0, 0, 0), (1, 0, 1, 0, 0), (1, 0, 0, 1, 0), (1, 1, 1, 1, 1))$ is a $0/1$ polytope, it is box-integer. However, it can be checked that $(2, 1, 1, 1, 1/2)$ is a fractional vertex of $2P \cap \{x_2 = x_3 = x_4 = 1\}$. In particular, $P$ illustrates statement 3 of Proposition 3.

### 3.3 Translations of Principally Box-Integer Polyhedra

Box-integrality is clearly preserved under integer translation. So are principal and full box-integrality.

**Observation 1** Box-integrality, principal box-integrality and full box-integrality are all preserved by integer translation.
**Proof.** The translation $Q = t + P$ of a box-integer polyhedron $P$ by $t$ in $\mathbb{Z}^n$ is also box-integer because $Q \cap \{\ell \le x \le u\} = t + (P \cap \{\ell - t \le x \le u - t\})$ for all $\ell, u \in \mathbb{Z}^n$. Moreover, since $kQ = kt + kP$ and $kt \in \mathbb{Z}^n$ for all $k \in \mathbb{Z}_{>0}$, principal box-integrality and full box-integrality are also preserved by integer translation. $\square$

Conic polyhedra play an important role in the next sections. One of the reasons is that, up to translation, every dilation of a conic polyhedron is the conic polyhedron itself. Since box-integrality is preserved by integer translation, this has the following consequences.

**Observation 2** Let $D = t + C$ be a conic polyhedron for some cone $C$ of $\mathbb{R}^n$ and some $t \in \mathbb{Q}^n$.

1. For $C$, the three properties of being box-integer, fully box-integer, or principally box-integer are equivalent.

2. $D$ is fully box-integer if and only if it is box-integer.

3. $D$ is principally box-integer if and only if $C$ is box-integer.

**Proof.** The fact that $kC = C$ for all $k \in \mathbb{Z}_{>0}$ proves statement 1. When $D$ is box-integer, its minimal face contains an integer point, hence $t$ can be chosen to be an integer. Since $kD = (k-1)t + D$ for all $k \in \mathbb{Z}_{>0}$, and since integer translation preserves box-integrality, statement 2 follows. When $t \in \mathbb{Q}^n$, take $k$ large enough such that $kt$ is integer. Now, $kD = kt + C$ is a fully box-integer dilation of $D$ if and only if $C$ is box-integer, which proves statement 3. $\square$

# 4 Principally Box-Integer Polyhedra and Equimodular Matrices

In this section, we show how equimodularity and principal box-integrality are intertwined. First, we characterize equimodular matrices using principal box-integrality. Then, principally box-integer polyhedra are characterized by the equimodularity of a family of matrices.

## 4.1 Characterizations of Equimodular Matrices

In this section, we extend to equimodular matrices two classical results about unimodular matrices. We first state the results of Heller [28] about unimodular sets in terms of equimodular matrices—see also [38, Theorem 19.5].

**Theorem 3 (Heller [28])** For a full row rank $r \times n$ matrix $A$, the following statements are equivalent.

1. *A is equimodular.*

2. For each nonsingular $r \times r$ submatrix $D$ of $A$, lattice$(D) = \text{lattice}(A)$.

3. For each nonsingular $r \times r$ submatrix $D$ of $A$, $D^{-1}A$ is integer.

4. For each nonsingular $r \times r$ submatrix $D$ of $A$, $D^{-1}A$ is in $\{0, \pm 1\}^{r \times n}$.
**Proof.** The translation $Q = t + P$ of a box-integer polyhedron $P$ by $t$ in $\mathbb{Z}^n$ is also box-integer because $Q \cap \{\ell \le x \le u\} = t + (P \cap \{\ell - t \le x \le u - t\})$ for all $\ell, u \in \mathbb{Z}^n$. Moreover, since $kQ = kt + kP$ and $kt \in \mathbb{Z}^n$ for all $k \in \mathbb{Z}_{>0}$, principal box-integrality and full box-integrality are also preserved by integer translation. $\square$

Conic polyhedra play an important role in the next sections. One of the reasons is that, up to translation, every dilation of a conic polyhedron is the conic polyhedron itself. Since box-integrality is preserved by integer translation, this has the following consequences.

**Observation 2** Let $D = t + C$ be a conic polyhedron for some cone $C$ of $\mathbb{R}^n$ and some $t \in \mathbb{Q}^n$.

1. For $C$, the three properties of being box-integer, fully box-integer, or principally box-integer are equivalent.

2. $D$ is fully box-integer if and only if it is box-integer.

3. $D$ is principally box-integer if and only if $C$ is box-integer.

**Proof.** The fact that $kC = C$ for all $k \in \mathbb{Z}_{>0}$ proves statement 1. When $D$ is box-integer, its minimal face contains an integer point, hence $t$ can be chosen to be an integer. Since $kD = (k-1)t + D$ for all $k \in \mathbb{Z}_{>0}$, and since integer translation preserves box-integrality, statement 2 follows. When $t \in \mathbb{Q}^n$, take $k$ large enough such that $kt$ is integer. Now, $kD = kt + C$ is a fully box-integer dilation of $D$ if and only if $C$ is box-integer, which proves statement 3. $\square$

# 4 Principally Box-Integer Polyhedra and Equimodular Matrices

In this section, we show how equimodularity and principal box-integrality are intertwined. First, we characterize equimodular matrices using principal box-integrality. Then, principally box-integer polyhedra are characterized by the equimodularity of a family of matrices.

## 4.1 Characterizations of Equimodular Matrices

In this section, we extend to equimodular matrices two classical results about unimodular matrices. We first state the results of Heller [28] about unimodular sets in terms of equimodular matrices—see also [38, Theorem 19.5].

**Theorem 3 (Heller [28])** For a full row rank $r \times n$ matrix $A$, the following statements are equivalent.

1. *A is equimodular.*

2. For each nonsingular $r \times r$ submatrix $D$ of $A$, lattice$(D) = \text{lattice}(A)$.

3. For each nonsingular $r \times r$ submatrix $D$ of $A$, $D^{-1}A$ is integer.

4. For each nonsingular $r \times r$ submatrix $D$ of $A$, $D^{-1}A$ is in $\{0, \pm 1\}^{r \times n}$.
5. For each nonsingular $r \times r$ submatrix $D$ of $A$, $D^{-1}A$ is totally unimodular.

6. There exists a nonsingular $r \times r$ submatrix $D$ of $A$ such that $D^{-1}A$ is totally unimodular.

Veinott and Dantzig [45] proved that an integer $r \times n$ matrix $A$ of full row rank is unimodular if and only if the polyhedron $\{x : Ax = b, x \ge 0\}$ is integer for all $b \in \mathbb{Z}^r$. Observe that statement 2 of Corollary 2 allows us to reformulate their result as follows, since $\{x : Ax = kb\} \cap \{x \ge \ell\} = \ell + \{x : Ax = b', x \ge 0\}$, where $b' = kb + kA\ell \in \mathbb{Z}^r$.

**Theorem 4 (Veinott and Dantzig [45])** Let $A$ be a full row rank matrix of $\mathbb{Z}^{r \times n}$. Then, $A$ is unimodular if and only if $\{x : Ax = b\}$ is fully box-integer for all $b \in \mathbb{Z}^r$.

It turns out that this result can be extended to characterize equimodular matrices.

**Theorem 5** Let $A$ be a full row rank matrix of $\mathbb{Q}^{r \times n}$. Then, $A$ is equimodular if and only if $\{x : Ax = b\}$ is principally box-integer for all $b \in \mathbb{Q}^r$.

*Proof.* Suppose that $A$ is equimodular and let $b \in \mathbb{Q}^r$, $k \in \mathbb{Z}_{>0}$ be such that $H = \{x : Ax = kb\}$ is integer. Then $b' = kb$ belongs to lattice($A$). Let $D$ be a nonsingular $r \times r$ submatrix $D$ of $A$. By statement 2 of Theorem 3, we have lattice($D$) = lattice($A$), hence $D^{-1}b'$ is in $\mathbb{Z}^r$. Since $A$ has full row rank, by statement 5 of Theorem 3, $D^{-1}A$ is unimodular. By Theorem 4, we get that $\{x : D^{-1}Ax = D^{-1}b'\}$ is fully box-integer. In particular, $H$ is box-integer.

Conversely, suppose that $A$ is not equimodular. Then, possibly reordering the columns, we may assume that the first $r$ columns of $A$ are linearly independent, and, by statement 3 of Theorem 3, that the $(r+1)$th column $A^{r+1}$ of $A$ is a noninteger combination of those. Let $H = \{x : Ax = A^{r+1}\}$. Then, $\{x : Ax = A^{r+1}\} \cap \{x_j = 0, j \ge r+1\}$ has no integer solution, hence $H$ is not box-integer. However, $H$ is integer as it contains $\chi^{r+1}$ as an integer point. Therefore, $H$ is not principally box-integer. $\square$

Veinott and Dantzig [45] devised Theorem 4 in order to get a simpler proof of a characterization of totally unimodular matrices due to Hoffman and Kruskal [31]. This characterization states that an integer matrix $A$ is totally unimodular if and only if $\{x : Ax \le b\}$ is box-integer for all $b \in \mathbb{Z}^m$. In our context, this can be reformulated as follows.

**Theorem 6 (Hoffman and Kruskal [31])** A matrix $A$ of $\mathbb{Z}^{m \times n}$ is totally unimodular if and only if $\{x : Ax \le b\}$ is fully box-integer for all $b \in \mathbb{Z}^m$.

An equivalent definition of total unimodularity is to ask for every set of linearly independent rows to be unimodular. In this light, it is natural to define totally equimodular matrices as those for which all sets of linearly independent rows form an equimodular matrix. Theorem 6 then extends to totally equimodular matrices as follows.
5. For each nonsingular $r \times r$ submatrix $D$ of $A$, $D^{-1}A$ is totally unimodular.

6. There exists a nonsingular $r \times r$ submatrix $D$ of $A$ such that $D^{-1}A$ is totally unimodular.

Veinott and Dantzig [45] proved that an integer $r \times n$ matrix $A$ of full row rank is unimodular if and only if the polyhedron $\{x : Ax = b, x \ge 0\}$ is integer for all $b \in \mathbb{Z}^r$. Observe that statement 2 of Corollary 2 allows us to reformulate their result as follows, since $\{x : Ax = kb\} \cap \{x \ge \ell\} = \ell + \{x : Ax = b', x \ge 0\}$, where $b' = kb + kA\ell \in \mathbb{Z}^r$.

**Theorem 4 (Veinott and Dantzig [45])** Let $A$ be a full row rank matrix of $\mathbb{Z}^{r \times n}$. Then, $A$ is unimodular if and only if $\{x : Ax = b\}$ is fully box-integer for all $b \in \mathbb{Z}^r$.

It turns out that this result can be extended to characterize equimodular matrices.

**Theorem 5** Let $A$ be a full row rank matrix of $\mathbb{Q}^{r \times n}$. Then, $A$ is equimodular if and only if $\{x : Ax = b\}$ is principally box-integer for all $b \in \mathbb{Q}^r$.

*Proof.* Suppose that $A$ is equimodular and let $b \in \mathbb{Q}^r$, $k \in \mathbb{Z}_{>0}$ be such that $H = \{x : Ax = kb\}$ is integer. Then $b' = kb$ belongs to lattice($A$). Let $D$ be a nonsingular $r \times r$ submatrix $D$ of $A$. By statement 2 of Theorem 3, we have lattice($D$) = lattice($A$), hence $D^{-1}b'$ is in $\mathbb{Z}^r$. Since $A$ has full row rank, by statement 5 of Theorem 3, $D^{-1}A$ is unimodular. By Theorem 4, we get that $\{x : D^{-1}Ax = D^{-1}b'\}$ is fully box-integer. In particular, $H$ is box-integer.

Conversely, suppose that $A$ is not equimodular. Then, possibly reordering the columns, we may assume that the first $r$ columns of $A$ are linearly independent, and, by statement 3 of Theorem 3, that the $(r+1)$th column $A^{r+1}$ of $A$ is a noninteger combination of those. Let $H = \{x : Ax = A^{r+1}\}$. Then, $\{x : Ax = A^{r+1}\} \cap \{x_j = 0, j \ge r+1\}$ has no integer solution, hence $H$ is not box-integer. However, $H$ is integer as it contains $\chi^{r+1}$ as an integer point. Therefore, $H$ is not principally box-integer. □

Veinott and Dantzig [45] devised Theorem 4 in order to get a simpler proof of a characterization of totally unimodular matrices due to Hoffman and Kruskal [31]. This characterization states that an integer matrix $A$ is totally unimodular if and only if $\{x : Ax \le b\}$ is box-integer for all $b \in \mathbb{Z}^m$. In our context, this can be reformulated as follows.

**Theorem 6 (Hoffman and Kruskal [31])** A matrix $A$ of $\mathbb{Z}^{m \times n}$ is totally unimodular if and only if $\{x : Ax \le b\}$ is fully box-integer for all $b \in \mathbb{Z}^m$.

An equivalent definition of total unimodularity is to ask for every set of linearly independent rows to be unimodular. In this light, it is natural to define totally equimodular matrices as those for which all sets of linearly independent rows form an equimodular matrix. Theorem 6 then extends to totally equimodular matrices as follows.
**Theorem 7** A matrix $A$ of $Q^{m \times n}$ is totally equimodular if and only if $\{x : Ax \leq b\}$ is principally box-integer for all $b \in Q^m$.

*Proof.* Suppose $A$ totally equimodular and $b \in Q^m$, and let us prove that $P = \{x : Ax \leq b\}$ is principally box-integer. Let $k \in \mathbb{Z}_{>0}$ be such that $kP$ is an integer polyhedron, and let us prove that $kP$ is box-integer. Let $F$ be a face of $kP$ and $p$ be an integer vector such that $\text{aff}(F) \cap \{x_i = p_i, i \in I\}$ is a singleton $\bar{x}$ in $F$. By Lemma 1, it remains to show that $\bar{x}$ is integer. There exists a full row rank subset $L$ of rows of $A$ such that $\text{aff}(F) = \{x : A_L x = kb_L\}$. Since $A$ is totally equimodular, $A_L$ is equimodular. By Theorem 5, $\text{aff}(F)$ is principally box-integer. Now, since $kP$ is integer, so is $\text{aff}(F)$. Hence, $\text{aff}(F)$ is box-integer and $\bar{x}$ is integer.

Suppose now that $A$ is not equimodular, that is, there exists a full row rank submatrix $A_L$ of size $r \times n$ of $A$ which is not equimodular. Then, we may assume that the first $r$ columns of $A_L$ are linearly independent, and that the $(r+1)$th column of $A_L$ is a noninteger combination of those. Let $\bar{x}$ be the unique solution of $A_L x = 0$, $x_{r+1} = -1$, $x_j = 0, j > r+1$. Then, $\bar{x} \notin \mathbb{Z}^n$. Define $b_L = 0$ and $b_j = 1$ if $j \notin L$, and let us show that $P = \{x : Ax \leq b\}$ is not principally box-integer. There exists $k \in \mathbb{Z}_{>0}$ large enough such that $\bar{x} \in kP$, and such that $kP$ is integer. Then, $kP \cap \{x_{r+1} = -1, x_j = 0, j > r+1\}$ contains $\bar{x}$ as a vertex because $\bar{x}$ satisfies to equality $n$ linearly independent inequalities. Therefore, $kP$ is not box-integer. $\square$

Since deciding whether a given matrix is totally unimodular can be done in polynomial time, see e.g. [38, Chapter 20], statement 5 of Theorem 3 implies that deciding whether a given matrix is equimodular can be done in polynomial time. However, for totally equimodular matrices, the recognition problem remains open.

**Open Problem 1** Can totally equimodular matrices be recognized in polynomial time?

As we shall see later, totally equimodular matrices are precisely the matrices whose associated polyhedra are all box-TDI—see Corollary 8. Interestingly, it is enough to study totally equimodular matrices with 0, ±1 coefficients. Indeed, in a totally equimodular matrix, the nonzero coefficients of a given row all have the same absolute value. Thus, such a matrix can be scaled row by row into a 0, ±1 matrix. This scaling preserves total equimodularity and do not change the family of associated polyhedra.

*Remark 2* The full row rank hypothesis made throughout this section is convenient, but not really necessary, provided the notions of unimodularity and equimodularity are correctly extended. Hoffman and Kruskal [31] extend the notion of unimodularity to not necessarily full row rank matrices, and Theorem 4 still holds for those matrices [38, Page 301]. The correct extension of equimodularity to general matrices is to require, for a matrix $A$ of rank $r$, that each set of $r$ linearly independent rows of $A$ forms an equimodular matrix. Properties of such matrices are studied in [28]. We mention that none of the
**Theorem 7** A matrix $A$ of $Q^{m \times n}$ is totally equimodular if and only if $\{x : Ax \leq b\}$ is principally box-integer for all $b \in Q^m$.

*Proof.* Suppose $A$ totally equimodular and $b \in Q^m$, and let us prove that $P = \{x : Ax \leq b\}$ is principally box-integer. Let $k \in \mathbb{Z}_{>0}$ be such that $kP$ is an integer polyhedron, and let us prove that $kP$ is box-integer. Let $F$ be a face of $kP$ and $p$ be an integer vector such that $\text{aff}(F) \cap \{x_i = p_i, i \in I\}$ is a singleton $\bar{x}$ in $F$. By Lemma 1, it remains to show that $\bar{x}$ is integer. There exists a full row rank subset $L$ of rows of $A$ such that $\text{aff}(F) = \{x : A_L x = kb_L\}$. Since $A$ is totally equimodular, $A_L$ is equimodular. By Theorem 5, $\text{aff}(F)$ is principally box-integer. Now, since $kP$ is integer, so is $\text{aff}(F)$. Hence, $\text{aff}(F)$ is box-integer and $\bar{x}$ is integer.

Suppose now that $A$ is not equimodular, that is, there exists a full row rank submatrix $A_L$ of size $r \times n$ of $A$ which is not equimodular. Then, we may assume that the first $r$ columns of $A_L$ are linearly independent, and that the $(r+1)$th column of $A_L$ is a noninteger combination of those. Let $\bar{x}$ be the unique solution of $A_L x = 0$, $x_{r+1} = -1$, $x_j = 0, j > r+1$. Then, $\bar{x} \notin \mathbb{Z}^n$. Define $b_L = 0$ and $b_j = 1$ if $j \notin L$, and let us show that $P = \{x : Ax \leq b\}$ is not principally box-integer. There exists $k \in \mathbb{Z}_{>0}$ large enough such that $\bar{x} \in kP$, and such that $kP$ is integer. Then, $kP \cap \{x_{r+1} = -1, x_j = 0, j > r+1\}$ contains $\bar{x}$ as a vertex because $\bar{x}$ satisfies to equality $n$ linearly independent inequalities. Therefore, $kP$ is not box-integer. $\square$

Since deciding whether a given matrix is totally unimodular can be done in polynomial time, see e.g. [38, Chapter 20], statement 5 of Theorem 3 implies that deciding whether a given matrix is equimodular can be done in polynomial time. However, for totally equimodular matrices, the recognition problem remains open.

**Open Problem 1** Can totally equimodular matrices be recognized in polynomial time?

As we shall see later, totally equimodular matrices are precisely the matrices whose associated polyhedra are all box-TDI—see Corollary 8. Interestingly, it is enough to study totally equimodular matrices with 0, ±1 coefficients. Indeed, in a totally equimodular matrix, the nonzero coefficients of a given row all have the same absolute value. Thus, such a matrix can be scaled row by row into a 0, ±1 matrix. This scaling preserves total equimodularity and do not change the family of associated polyhedra.

*Remark 2* The full row rank hypothesis made throughout this section is convenient, but not really necessary, provided the notions of unimodularity and equimodularity are correctly extended. Hoffman and Kruskal [31] extend the notion of unimodularity to not necessarily full row rank matrices, and Theorem 4 still holds for those matrices [38, Page 301]. The correct extension of equimodularity to general matrices is to require, for a matrix $A$ of rank $r$, that each set of $r$ linearly independent rows of $A$ forms an equimodular matrix. Properties of such matrices are studied in [28]. We mention that none of the
definitions and results of this paper are affected if these extended definitions
are adopted and the full row rank hypothesis removed.

## 4.2 Affine Spaces and Face-Defining Matrices

Affine spaces being special cases of conic polyhedra, by statement 3 Observation 2, {$x : Ax = b$} is principally box-integer for all $b$ if and only if {$x : Ax = 0$} is fully box-integer. In particular, one can drop the quantification over all $b \in \mathbb{Q}^n$ from Theorem 5 as follows.

**Corollary 3** Let $A$ be a full row rank matrix of $\mathbb{Q}^{r \times n}$ and $b \in \mathbb{Q}^n$. Then, $A$ is equimodular if and only if the affine space {$x : Ax = b$} is principally box-integer.

An affine space {$x : Ax = b$} being integer if and only if $b$ belongs to lattice$(A)$, the previous result has the following immediate consequence.

**Corollary 4** Let $A$ be a full row rank matrix of $\mathbb{Q}^{r \times n}$ and $b \in \mathbb{Q}^n$. The affine space {$x : Ax = b$} is fully box-integer if and only if $A$ is equimodular and $b \in \text{lattice}(A)$.

Corollary 3 yields a correspondence between equimodular matrices and principally box-integer affine spaces. We shall see in the next section that this correspondence, when applied to the faces of a polyhedron, provides a characterization of principally box-integer polyhedra. This motivates the following definition.

*Face-defining matrices.* Let $P = \{x : Ax \leq b\}$ be a polyhedron of $\mathbb{R}^n$ and $F$ be a face of $P$. A full row rank matrix $M$ such that $\text{aff}(F)$ can be written {$x : Mx = d$} for some $d$ is *face-defining for F*. Such matrices are called *face-defining matrices of P*<fnref n="1" />. Note that face-defining matrices need not correspond to valid inequalities for the polyhedron. A face-defining matrix for a facet of $P$ is called *facet-defining*.

Affine spaces are polyhedra whose only face is themselves. The following observation characterizes their principal box-integrality in terms of face-defining matrices.

**Observation 3** For an affine space $H$, the following statements are equivalent.

1. $H$ is principally box-integer.

2. $H$ has an equimodular face-defining matrix.

3. Every face-defining matrix of $H$ is equimodular.

<footnote n="1">¹ When we write that a face *F* has a face-defining matrix *M*, we mean that *M* is face-defining for the face *F*, which is more restrictive than being a face-defining matrix of the polyhedron *F*.</footnote>
definitions and results of this paper are affected if these extended definitions
are adopted and the full row rank hypothesis removed.

## 4.2 Affine Spaces and Face-Defining Matrices

Affine spaces being special cases of conic polyhedra, by statement 3 Observation 2, {$x : Ax = b$} is principally box-integer for all $b$ if and only if {$x : Ax = 0$} is fully box-integer. In particular, one can drop the quantification over all $b \in \mathbb{Q}^n$ from Theorem 5 as follows.

**Corollary 3** Let $A$ be a full row rank matrix of $\mathbb{Q}^{r \times n}$ and $b \in \mathbb{Q}^n$. Then, $A$ is equimodular if and only if the affine space {$x : Ax = b$} is principally box-integer.

An affine space {$x : Ax = b$} being integer if and only if $b$ belongs to lattice$(A)$, the previous result has the following immediate consequence.

**Corollary 4** Let $A$ be a full row rank matrix of $\mathbb{Q}^{r \times n}$ and $b \in \mathbb{Q}^n$. The affine space {$x : Ax = b$} is fully box-integer if and only if $A$ is equimodular and $b \in \text{lattice}(A)$.

Corollary 3 yields a correspondence between equimodular matrices and principally box-integer affine spaces. We shall see in the next section that this correspondence, when applied to the faces of a polyhedron, provides a characterization of principally box-integer polyhedra. This motivates the following definition.

*Face-defining matrices.* Let $P = \{x : Ax \leq b\}$ be a polyhedron of $\mathbb{R}^n$ and $F$ be a face of $P$. A full row rank matrix $M$ such that $\text{aff}(F)$ can be written {$x : Mx = d$} for some $d$ is *face-defining for F*. Such matrices are called *face-defining matrices of P*<fnref n="1" />. Note that face-defining matrices need not correspond to valid inequalities for the polyhedron. A face-defining matrix for a facet of $P$ is called *facet-defining*.

Affine spaces are polyhedra whose only face is themselves. The following observation characterizes their principal box-integrality in terms of face-defining matrices.

**Observation 3** For an affine space $H$, the following statements are equivalent.

1. *H is principally box-integer.*

2. *H has an equimodular face-defining matrix.*

3. *Every face-defining matrix of H is equimodular.*

<footnote n="1">¹ When we write that a face *F* has a face-defining matrix *M*, we mean that *M* is face-defining for the face *F*, which is more restrictive than being a face-defining matrix of the polyhedron *F*.</footnote>
4. *H has a totally unimodular face-defining matrix.*

*Proof.* The equivalence among statements 1, 2, and 3 follows from Corollary 3. The equivalence between statements 2 and 4 follows from statement 5 of Theorem 3, because if $A \in \mathbb{Q}^{r \times n}$ is face-defining for $H$, then so is $D^{-1}A$ for each nonsingular $r \times r$ submatrix $D$ of $A$. $\square$

Note that, when $P$ is full-dimensional, facet-defining matrices are composed of a single row and are uniquely determined, up to multiplying by a scalar. In general, the number of rows of a face-defining matrix for a face $F$ is $n-\dim(F)$. More precisely, the following immediate observation characterizes face-defining matrices.

**Observation 4** *A full row rank matrix $M \in \mathbb{Q}^{k \times n}$ is face-defining for a face $F$ of a polyhedron $P \subseteq \mathbb{R}^n$ if and only if there exist a vector $d \in \mathbb{Q}^k$ and a family $\mathcal{H} \subseteq F \cap \{x: Mx = d\}$ of $\dim(F)+1$ affinely independent points such that $|\mathcal{H}| + k = n + 1$.*

## 4.3 Characterizations of Principally Box-Integer Polyhedra

In this section, we provide several characterizations of principally box-integer polyhedra, the starting point being the following lemma.

**Lemma 4** *A polyhedron $P$ is principally box-integer if and only if $\text{aff}(F)$ is principally box-integer for each face $F$ of $P$.*

*Proof.* Let $P$ be a polyhedron such that the affine spaces generated by its faces are all principally box-integer. Then, when $k \in \mathbb{Z}_{>0}$ is such that $kP$ is integer, all the affine spaces generated by the faces of $kP$ are box-integer. Therefore, by Lemma 1, if $F$ is a face of such a $kP$ and $p$ is an integer vector such that $\text{aff}(F) \cap \{x_i = p_i, i \in I\}$ is a singleton in $F$, then this singleton is integer. Then, by the other direction of Lemma 1, $kP$ is box-integer, thus $P$ is principally box-integer.

Conversely, let $P$ be a principally box-integer polyhedron and $F$ be a face of $P$. If $F$ is a singleton, then $\text{aff}(F) = F$ is a singleton, thus obviously principally box-integer. Otherwise, let $t$ be a rational point in the relative interior of $F$, let $G = F - t$ and $Q = P - t$. By statement 3 of Observation 2, it suffices to show that $\text{aff}(G)$ is box-integer. Let $p$ be an integer vector such that $\text{aff}(G) \cap \{x_i = p_i, i \in I\}$ is a singleton $\bar{x}$ in $\text{aff}(G)$. Since $t$ was chosen in the relative interior of $F$, there exists $k \in \mathbb{Z}_{>0}$ such that $\bar{x} \in kQ$. Moreover, such a $k$ can be chosen so that $kt$ is integer and $kP$ is an integer polyhedron. Since $P$ is principally box-integer, $kP$ is box-integer and so is $kQ = kP - kt$ by Observation 1. Applying Lemma 1 to the face $kG$ of $kQ$ yields $\bar{x}$ integer. By applying the other direction of Lemma 1 to the unique face $\text{aff}(G)$ of $\text{aff}(G)$, we obtain that $\text{aff}(G)$ is box-integer. $\square$

**Theorem 8** For a polyhedron $P$, the following statements are equivalent.
4. *H has a totally unimodular face-defining matrix.*

*Proof.* The equivalence among statements 1, 2, and 3 follows from Corollary 3. The equivalence between statements 2 and 4 follows from statement 5 of Theorem 3, because if $A \in \mathbb{Q}^{r \times n}$ is face-defining for $H$, then so is $D^{-1}A$ for each nonsingular $r \times r$ submatrix $D$ of $A$. $\square$

Note that, when $P$ is full-dimensional, facet-defining matrices are composed of a single row and are uniquely determined, up to multiplying by a scalar. In general, the number of rows of a face-defining matrix for a face $F$ is $n-\dim(F)$. More precisely, the following immediate observation characterizes face-defining matrices.

**Observation 4** *A full row rank matrix $M \in \mathbb{Q}^{k \times n}$ is face-defining for a face $F$ of a polyhedron $P \subseteq \mathbb{R}^n$ if and only if there exist a vector $d \in \mathbb{Q}^k$ and a family $\mathcal{H} \subseteq F \cap \{x: Mx=d\}$ of $\dim(F)+1$ affinely independent points such that $|\mathcal{H}|+k=n+1$.*

## 4.3 Characterizations of Principally Box-Integer Polyhedra

In this section, we provide several characterizations of principally box-integer polyhedra, the starting point being the following lemma.

**Lemma 4** *A polyhedron $P$ is principally box-integer if and only if $\text{aff}(F)$ is principally box-integer for each face $F$ of $P$.*

*Proof.* Let $P$ be a polyhedron such that the affine spaces generated by its faces are all principally box-integer. Then, when $k \in \mathbb{Z}_{>0}$ is such that $kP$ is integer, all the affine spaces generated by the faces of $kP$ are box-integer. Therefore, by Lemma 1, if $F$ is a face of such a $kP$ and $p$ is an integer vector such that $\text{aff}(F) \cap \{x_i = p_i, i \in I\}$ is a singleton in $F$, then this singleton is integer. Then, by the other direction of Lemma 1, $kP$ is box-integer, thus $P$ is principally box-integer.

Conversely, let $P$ be a principally box-integer polyhedron and $F$ be a face of $P$. If $F$ is a singleton, then $\text{aff}(F) = F$ is a singleton, thus obviously principally box-integer. Otherwise, let $t$ be a rational point in the relative interior of $F$, let $G = F - t$ and $Q = P - t$. By statement 3 of Observation 2, it suffices to show that $\text{aff}(G)$ is box-integer. Let $p$ be an integer vector such that $\text{aff}(G) \cap \{x_i = p_i, i \in I\}$ is a singleton $\bar{x}$ in $\text{aff}(G)$. Since $t$ was chosen in the relative interior of $F$, there exists $k \in \mathbb{Z}_{>0}$ such that $\bar{x} \in kQ$. Moreover, such a $k$ can be chosen so that $kt$ is integer and $kP$ is an integer polyhedron. Since $P$ is principally box-integer, $kP$ is box-integer and so is $kQ = kP - kt$ by Observation 1. Applying Lemma 1 to the face $kG$ of $kQ$ yields $\bar{x}$ integer. By applying the other direction of Lemma 1 to the unique face $\text{aff}(G)$ of $\text{aff}(G)$, we obtain that $\text{aff}(G)$ is box-integer. $\square$

**Theorem 8** For a polyhedron $P$, the following statements are equivalent.
1. The polyhedron $P$ is principally box-integer.

2. Every minimal tangent cone of $P$ is principally box-integer.

3. Every face of $P$ has an equimodular face-defining matrix.

*Proof.* Each face of $P$ is contained in a face of some minimal tangent cone of $P$ having the same affine hull. Conversely, each face of a minimal tangent cone of $P$ contains some face of $P$ having the same affine hull. Therefore, Lemma 4 gives the equivalence between statement 1 and statement 2. The equivalence between statement 1 and statement 3 is immediate by Corollary 3 and Lemma 4.
$\square$

The minimal faces of a polyhedron being affine spaces, Lemma 4 has a fully box-integer counterpart. Moreover, by statement 2 of Observation 2, so does the equivalence between statement 1 and statement 3 of Theorem 8. This gives the following corollary.

**Corollary 5** For a polyhedron $P$, the following statements are equivalent.

1. The polyhedron $P$ is fully box-integer.

2. Every minimal tangent cone of $P$ is box-integer.

3. For each face $F$ of $P$, $\text{aff}(F)$ is fully box-integer.

# 5 Box-Totally Dual Integral Polyhedra

## 5.1 New Characterizations of Box-TDI Polyhedra

The main result of this section is that the notions of principal box-integrality and box-TDIness coincide—see Theorem 9 below. Combined with Theorem 8, this provides several new characterizations of box-TDI polyhedra.

**Theorem 9** A polyhedron is box-TDI if and only if it is principally box-integer.

*Proof.* The proof relies on Lemmas 5 and 6, which are proven below.

Lemma 5 states that a polyhedron is box-TDI if and only if all its minimal tangent cones are box-TDI. By Theorem 8, a polyhedron is principally box-integer if and only if all its minimal tangent cones are principally box-integer. Hence it is enough to prove Theorem 9 for conic polyhedra.

Lemma 6 states that a cone is box-TDI if and only if it is box-integer. Then, by statement 3 of Observation 2, and since box-TDIness is preserved under rational translation, a conic polyhedron is box-TDI if and only if it is principally box-integer.
$\square$

The following lemma seems somewhat implicitly known in the literature, but is not stated explicitly to the best of our knowledge. For the sake of completeness, we provide a proof which relies only on the definitions. It can also be shown using known characterizations of box-TDI polyhedra, such as the one by Cook [38, Theorem 22.9].
1. The polyhedron $P$ is principally box-integer.

2. Every minimal tangent cone of $P$ is principally box-integer.

3. Every face of $P$ has an equimodular face-defining matrix.

*Proof.* Each face of $P$ is contained in a face of some minimal tangent cone of $P$ having the same affine hull. Conversely, each face of a minimal tangent cone of $P$ contains some face of $P$ having the same affine hull. Therefore, Lemma 4 gives the equivalence between statement 1 and statement 2. The equivalence between statement 1 and statement 3 is immediate by Corollary 3 and Lemma 4.
$\square$

The minimal faces of a polyhedron being affine spaces, Lemma 4 has a fully box-integer counterpart. Moreover, by statement 2 of Observation 2, so does the equivalence between statement 1 and statement 3 of Theorem 8. This gives the following corollary.

**Corollary 5** For a polyhedron $P$, the following statements are equivalent.

1. The polyhedron $P$ is fully box-integer.

2. Every minimal tangent cone of $P$ is box-integer.

3. For each face $F$ of $P$, $\text{aff}(F)$ is fully box-integer.

# 5 Box-Totally Dual Integral Polyhedra

## 5.1 New Characterizations of Box-TDI Polyhedra

The main result of this section is that the notions of principal box-integrality and box-TDIness coincide—see Theorem 9 below. Combined with Theorem 8, this provides several new characterizations of box-TDI polyhedra.

**Theorem 9** A polyhedron is box-TDI if and only if it is principally box-integer.

*Proof.* The proof relies on Lemmas 5 and 6, which are proven below.

Lemma 5 states that a polyhedron is box-TDI if and only if all its minimal tangent cones are box-TDI. By Theorem 8, a polyhedron is principally box-integer if and only if all its minimal tangent cones are principally box-integer. Hence it is enough to prove Theorem 9 for conic polyhedra.

Lemma 6 states that a cone is box-TDI if and only if it is box-integer. Then, by statement 3 of Observation 2, and since box-TDIness is preserved under rational translation, a conic polyhedron is box-TDI if and only if it is principally box-integer.
$\square$

The following lemma seems somewhat implicitly known in the literature, but is not stated explicitly to the best of our knowledge. For the sake of completeness, we provide a proof which relies only on the definitions. It can also be shown using known characterizations of box-TDI polyhedra, such as the one by Cook [38, Theorem 22.9].
**Lemma 5** A polyhedron is box-TDI if and only if all its minimal tangent cones are.

*Proof.* Let $P = \{x : Ax \le b\}$ be a polyhedron of $\mathbb{R}^n$ and $w \in \mathbb{Z}^n$. We will denote $(P_{\ell,u}) = \max\{wx : Ax \le b, \ell \le x \le u\}$ and $(P_{\ell,u}^F) = \max\{wx : A_I x \le b_I, \ell \le x \le u\}$ for a minimal face $F$ of $P$ where $I$ is the index set of the tight rows for $F$.

To establish the “only if” part of the statement, suppose that the system $Ax \le b$ is box-TDI. Let $F$ be a minimal face of $P$, $v \in F$ and let $x^*$ be an optimal solution of $(P_{\ell,u}^F)$. Since $a_i v < b_i$ for all $i \notin I$, there exists $\lambda > 0$ such that $y^* = v + \lambda(x^* - v)$ belongs to $P$ and $a_i y^* < b_i$ for all $i \notin I$. Let $\ell' = v + \lambda(\ell - v)$ and $u' = v + \lambda(u - v)$. Then, $y^*$ is an optimal solution of $(P_{\ell',u'})$, as otherwise $x^*$ would not be an optimal solution of $(P_{\ell,u}^F)$. Let $(z^*, r^*, s^*)$ be an integer optimal solution of the dual of $(P_{\ell',u'})$. By complementary slackness, denoting by $z_I^*$ the vector obtained from $z^*$ by deleting the coordinates not in $I$, without loss of generality we have $z^* = (z_I^*, 0)$. Now, since $w^\top y^* = b^\top z^* + u'^\top r^* - \ell'^\top s^*$, one can check that $w^\top x^* = b_I^\top z_I^* + u^\top r^* - \ell^\top s^*$, by applying the definition of $y^*, u'$ and $\ell', b^\top z^* = b_I^\top z_I^*$, $w = A^\top z^* + r^* - s^*$, $A^\top z^* = A_I^\top z_I^*$, and $A_I v = b_I$. Therefore, $(z_I^*, r^*, s^*)$ is an integer optimal solution of the dual $\min\{b_I^\top z + u^\top r - \ell^\top s : A_I^\top z_I + r - s = w, z_I, r, s \ge 0\}$ of $(P_{\ell,u}^F)$.

To establish the “if” part of the statement, let $H$ be the face of $P$ composed of all the optimal solutions of $(P_{\ell,u}) = \max\{wx : Ax \le b, \ell \le x \le u\}$ and let $F$ be a minimal face of $P$ contained in $H$ whose tight rows are indexed by $I$. Let $(z_I^*, r^*, s^*)$ be an integer optimal solution of the dual of $(P_{\ell,u}^F)$. Then, one can check that extending $z_I^*$ to a vector $z^* = (z_I^*, 0)$ of $\mathbb{R}^m$ yields an integer optimal solution $(z^*, r^*, s^*)$ of the dual of $(P_{\ell,u})$. $\square$

The following result reveals that cones behave nicely with respect to box-TDIness. It is already known that a box-TDI cone is box-integer [39, Equation (5.82)]. Suprisingly, the converse holds and these properties are carried oved to the polar.

**Lemma 6** For a cone $C$, the following statements are equivalent.

1. $C$ is box-TDI,

2. $C$ is box-integer,

3. $C^*$ is box-TDI,

4. $C^*$ is box-integer.

*Proof.* Let $C = \{x : Ax \le 0\}$ be a cone of $\mathbb{R}^n$. By [38, Theorem 22.6(i)], the system $Ax \le 0$ can be chosen to be TDI.

Suppose that $C$ is box-TDI. By Theorem 1, the system $Ax \le 0$ is box-TDI. Hence, for all $\ell, u \in \mathbb{Z}^n$, the system $Ax \le 0, \ell \le x \le u$ is TDI. As $\ell$ and $u$ are integer, this system defines an integer polyhedron by [38, Corollary 22.1c]. Therefore, $C$ is box-integer, and we get (1)⇒(2). This also gives (3)⇒(4).

All that remains to prove is (4)⇒(1). Indeed, applying this implication to the cone $C^*$ and using that $C^{**} = C$ yields (2)⇒(3).
**Lemma 5** A polyhedron is box-TDI if and only if all its minimal tangent cones are.

*Proof.* Let $P = \{x : Ax \leq b\}$ be a polyhedron of $\mathbb{R}^n$ and $w \in \mathbb{Z}^n$. We will denote $(P_{\ell,u}) = \max\{wx : Ax \leq b, \ell \leq x \leq u\}$ and $(P_{\ell,u}^F) = \max\{wx : A_I x \leq b_I, \ell \leq x \leq u\}$ for a minimal face $F$ of $P$ where $I$ is the index set of the tight rows for $F$.

To establish the “only if” part of the statement, suppose that the system $Ax \leq b$ is box-TDI. Let $F$ be a minimal face of $P$, $v \in F$ and let $x^*$ be an optimal solution of $(P_{\ell,u}^F)$. Since $a_iv < b_i$ for all $i \notin I$, there exists $\lambda > 0$ such that $y^* = v + \lambda(x^* - v)$ belongs to $P$ and $a_iy^* < b_i$ for all $i \notin I$. Let $\ell' = v + \lambda(\ell - v)$ and $u' = v + \lambda(u - v)$. Then, $y^*$ is an optimal solution of $(P_{\ell',u'})$, as otherwise $x^*$ would not be an optimal solution of $(P_{\ell,u}^F)$. Let $(z^*, r^*, s^*)$ be an integer optimal solution of the dual of $(P_{\ell',u'})$. By complementary slackness, denoting by $z_I^*$ the vector obtained from $z^*$ by deleting the coordinates not in $I$, without loss of generality we have $z^* = (z_I^*, 0)$. Now, since $w^\top y^* = b^\top z^* + u'^\top r^* - \ell'^\top s^*$, one can check that $w^\top x^* = b_I^\top z_I^* + u^\top r^* - \ell^\top s^*$, by applying the definition of $y^*, u'$ and $\ell', b^\top z^* = b_I^\top z_I^*$, $w = A^\top z^* + r^* - s^*$, $A^\top z^* = A_I^\top z_I^*$, and $A_I v = b_I$. Therefore, $(z_I^*, r^*, s^*)$ is an integer optimal solution of the dual $\min\{b_I^\top z + u^\top r - \ell^\top s : A_I^\top z_I + r - s = w, z_I, r, s \geq 0\}$ of $(P_{\ell,u}^F)$.

To establish the “if” part of the statement, let $H$ be the face of $P$ composed of all the optimal solutions of $(P_{\ell,u}) = \max\{wx : Ax \leq b, \ell \leq x \leq u\}$ and let $F$ be a minimal face of $P$ contained in $H$ whose tight rows are indexed by $I$. Let $(z_I^*, r^*, s^*)$ be an integer optimal solution of the dual of $(P_{\ell,u}^F)$. Then, one can check that extending $z_I^*$ to a vector $z^* = (z_I^*, 0)$ of $\mathbb{R}^m$ yields an integer optimal solution $(z^*, r^*, s^*)$ of the dual of $(P_{\ell,u})$. $\square$

The following result reveals that cones behave nicely with respect to box-TDIness. It is already known that a box-TDI cone is box-integer [39, Equation (5.82)]. Suprisingly, the converse holds and these properties are carried oved to the polar.

**Lemma 6** For a cone $C$, the following statements are equivalent.

1. $C$ is box-TDI,

2. $C$ is box-integer,

3. $C^*$ is box-TDI,

4. $C^*$ is box-integer.

*Proof.* Let $C = \{x : Ax \leq 0\}$ be a cone of $\mathbb{R}^n$. By [38, Theorem 22.6(i)], the system $Ax \leq 0$ can be chosen to be TDI.

Suppose that $C$ is box-TDI. By Theorem 1, the system $Ax \leq 0$ is box-TDI. Hence, for all $\ell, u \in \mathbb{Z}^n$, the system $Ax \leq 0, \ell \leq x \leq u$ is TDI. As $\ell$ and $u$ are integer, this system defines an integer polyhedron by [38, Corollary 22.1c]. Therefore, $C$ is box-integer, and we get (1)⇒(2). This also gives (3)⇒(4).

All that remains to prove is (4)⇒(1). Indeed, applying this implication to the cone $C^*$ and using that $C^{**} = C$ yields (2)⇒(3).
Suppose that $C^*$ is box-integer and let us prove that the dual $(D)$ of the
linear program $(P)$ below has an integer solution for all $w \in \mathbb{Z}^n$ and $\ell, u \in \mathbb{Q}^n$
such that the optimum is finite.

$$
\begin{array}{ll}
\max & w^\top x \\
(P) \quad \quad \quad \quad \quad \begin{array}{l} Ax \le \mathbf{0} \\ x \le u \\ -x \le -\ell \end{array} \\
\min & u^\top r - \ell^\top s \\
(D) \quad \quad \quad \quad \quad \begin{array}{l} A^\top z + r - s = w \\ z, r, s \ge \mathbf{0} \end{array}
\end{array}
$$

The projection of the set of points $(z, r, s)$ satisfying the constraints of $(D)$ onto the variables $r$ and $s$ is the polyhedron $Q = \{r, s \ge \mathbf{0} : v^\top(s - r + w) \le 0\}$, for all $v \in K$, where $K$ is the projection cone $K = \{v \in \mathbb{R}^n : v^\top A^\top \le \mathbf{0}\}$. That is $K = C$ and therefore $Q = (C^* - w)_\pm$.

Since integer translations of box-integer polyhedra are box-integer, $C^* - w$ is box-integer. Thus, by statement 2 of Lemma 2, $Q$ is box-integer. In particular, $Q$ is integer.

Since the optimum of (D) is finite, so is $\min\{u^\top r - \ell^\top s : (r, s) \in Q\}$. Since
$Q$ is an integer polyhedron, this minimum is achieved by an integer $(\bar{r}, \bar{s}) \in Q$.
Let $\bar{w} = w - \bar{r} + \bar{s}$. As $(\bar{r}, \bar{s})$ belongs to $Q$, there exists a feasible solution $\bar{z}$ of
the dual of $\max\{\bar{w}^\top x : Ax \le 0\}$. Recall that $Ax \le 0$ has been chosen to be
TDI. Hence, since $\bar{w}$ is integer, such a $\bar{z}$ can be chosen to be an integer. Then,
$(\bar{z}, \bar{r}, \bar{s})$ is an integer optimal solution of (D). $\square$

We are now ready to prove our main result, Theorem 2.

*Proof.* (of Theorem 2) Statements 2 and 1 are equivalent by Theorem 9. Statements 2 and 4 are equivalent by the equivalence between statements 1 and 3 of Theorem 8. Finally, the equivalence among statements 3, 4, and 5 comes from Observation 3. $\square$

We now apply polarity to derive additional characterizations of box-TDI
polyhedra.

**Corollary 6** For a polyhedron *P*, the following statements are equivalent.

1. The polyhedron *P* is box-TDI.

2. For every face F of P, every basis of lin(F) is the transpose of an equimod-ular matrix.

3. For every face F of P, some basis of lin(F) is the transpose of an equimod-ular matrix.

4. For every face F of P, some basis of lin(F) is a totally unimodular matrix.

*Proof.* Let *F* be a face of *P*. By Corollary 3, *F* has an equimodular face-
defining matrix if and only if aff(*F*) is principally box-integer. Equivalently,
by Observation 2, lin(*F*) is box-integer. By Lemma 6, lin(*F*) is box-integer
if and only lin(*F*)* is. By Corollary 3, lin(*F*)* is box-integer if and only if
lin(*F*)* has an equimodular face-defining matrix *M*. Note that the columns
of *M*† form a basis of lin(*F*), therefore *F* has an equimodular face-defining
matrix if and only if some basis of lin(*F*) is the transpose of an equimodular
matrix.
Suppose that $C^*$ is box-integer and let us prove that the dual (D) of the linear program (P) below has an integer solution for all $w \in \mathbb{Z}^n$ and $\ell, u \in \mathbb{Q}^n$ such that the optimum is finite.

$$ \begin{array}{ll} \max & w^\top x \\ (P) \quad \quad \quad \quad \quad \begin{array}{l} Ax \le \mathbf{0} \\ x \le u \\ -x \le -\ell \end{array} \\ & \min \quad \begin{array}{l} u^\top r - \ell^\top s \\ A^\top z + r - s = w \\ z, r, s \ge \mathbf{0} \end{array} \\ (D) \quad \quad \quad \quad \quad \begin{array}{l} Ax \le \mathbf{0} \\ -x \le -\ell \end{array} \end{array} $$

The projection of the set of points $(z, r, s)$ satisfying the constraints of (D) onto the variables $r$ and $s$ is the polyhedron $Q = \{r, s \ge \mathbf{0} : v^\top(s - r + w) \le 0, \text{ for all } v \in K\}$, where $K$ is the projection cone $K = \{v \in \mathbb{R}^n : v^\top A^\top \le \mathbf{0}\}$. That is $K = C$ and therefore $Q = (C^* - w)_\pm$.

Since integer translations of box-integer polyhedra are box-integer, $C^* - w$ is box-integer. Thus, by statement 2 of Lemma 2, $Q$ is box-integer. In particular, $Q$ is integer.

Since the optimum of (D) is finite, so is $\min\{u^\top r - \ell^\top s : (r, s) \in Q\}$. Since $Q$ is an integer polyhedron, this minimum is achieved by an integer $(\bar{r}, \bar{s}) \in Q$. Let $\bar{w} = w - \bar{r} + \bar{s}$. As $(\bar{r}, \bar{s})$ belongs to $Q$, there exists a feasible solution $\bar{z}$ of the dual of $\max\{\bar{w}^\top x : Ax \le \mathbf{0}\}$. Recall that $Ax \le \mathbf{0}$ has been chosen to be TDI. Hence, since $\bar{w}$ is integer, such a $\bar{z}$ can be chosen to be an integer. Then, $(\bar{z}, \bar{r}, \bar{s})$ is an integer optimal solution of (D). $\square$

We are now ready to prove our main result, Theorem 2.

*Proof.* (of Theorem 2) Statements 2 and 1 are equivalent by Theorem 9. Statements 2 and 4 are equivalent by the equivalence between statements 1 and 3 of Theorem 8. Finally, the equivalence among statements 3, 4, and 5 comes from Observation 3. $\square$

We now apply polarity to derive additional characterizations of box-TDI polyhedra.

**Corollary 6** For a polyhedron $P$, the following statements are equivalent.

1. The polyhedron $P$ is box-TDI.

2. For every face $F$ of $P$, every basis of $\operatorname{lin}(F)$ is the transpose of an equimodular matrix.

3. For every face $F$ of $P$, some basis of $\operatorname{lin}(F)$ is the transpose of an equimodular matrix.

4. For every face $F$ of $P$, some basis of $\operatorname{lin}(F)$ is a totally unimodular matrix.

*Proof.* Let $F$ be a face of $P$. By Corollary 3, $F$ has an equimodular face-defining matrix if and only if $\operatorname{aff}(F)$ is principally box-integer. Equivalently, by Observation 2, $\operatorname{lin}(F)$ is box-integer. By Lemma 6, $\operatorname{lin}(F)$ is box-integer if and only $\operatorname{lin}(F)^*$ is. By Corollary 3, $\operatorname{lin}(F)^*$ is box-integer if and only if $\operatorname{lin}(F)^*$ has an equimodular face-defining matrix $M$. Note that the columns of $M^\top$ form a basis of $\operatorname{lin}(F)$, therefore $F$ has an equimodular face-defining matrix if and only if some basis of $\operatorname{lin}(F)$ is the transpose of an equimodular matrix.
Since, by Theorem 2, the polyhedron $P$ is box-TDI if and only if each of its faces $F$ has an equimodular face-defining matrix, this proves the equivalence between statements 1 and 3. The equivalence with the two others statements follows from Observation 3. □

Recall that a cone $C = \{x : Ax \le 0\}$ can also be defined as $C = \text{cone}(R)$ for some set $R$ of generators. Moreover, by Lemma 6, a cone is box-TDI if and only if it is box-integer. Corollary 6 then allows us to check whether cones are box-integer by looking at their generators.

**Corollary 7** A cone $C = \text{cone}(R)$ is box-integer if and only if $S^\top$ is equimodular for each linearly independent subset $S$ of $R$ generating a face of $C$.

Consequently, the recognition of box-integer cones might have a different complexity status than the following related problems, which are all co-NP-complete: deciding whether a given polytope is integer [37], deciding whether a given system is TDI or box-TDI [16], deciding whether a given conic system is TDI [36].

**Open Problem 2** What is the complexity of deciding whether a given cone is box-integer?

We mention that polarity preserves box-integrality only for cones, and does not extend to polyhedra. For instance, the polyhedron $\text{conv}((2, -1), (-2, -1), (0, 1))$ is fully box-integer, and its polar conv $((1, 1), (-1, 1), (0, -1))$ is integer but not box-integer.

## 5.2 Connections with Existing Results

In this section, we investigate the connections of our results with those from the literature about box-TDI polyhedra. We first derive known results about box-TDI polyhedra from our characterizations. Then, we show how Cook's characterization [38, Theorem 22.9] is connected to ours. Finally, we discuss Schrijver's sufficient condition [39, Theorem 5.35].

### 5.2.1 Consequences

Here, we review several known results about box-TDI polyhedra which can be derived from our results. The dominant of a polyhedron $P$ of $\mathbb{R}^n$ is $\text{dom}(P) = P + \mathbb{R}_+^n$.

**Consequence 1** ([14, Theorem 3.6] or [38, Theorem 22.11]) The dominant of a box-TDI polyhedron is box-TDI.

*Proof.* A face of $\text{dom}(P)$ is the sum of a face of $P$ and a cone generated by unit vectors. By statement 4 of Corollary 6, and since adding unit vectors preserves total unimodularity, the dominant of a box-TDI polyhedron is box-TDI. □
Since, by Theorem 2, the polyhedron $P$ is box-TDI if and only if each of its faces $F$ has an equimodular face-defining matrix, this proves the equivalence between statements 1 and 3. The equivalence with the two others statements follows from Observation 3. □

Recall that a cone $C = \{x : Ax \le 0\}$ can also be defined as $C = \text{cone}(R)$ for some set $R$ of generators. Moreover, by Lemma 6, a cone is box-TDI if and only if it is box-integer. Corollary 6 then allows us to check whether cones are box-integer by looking at their generators.

**Corollary 7** A cone $C = \text{cone}(R)$ is box-integer if and only if $S^\top$ is equimodular for each linearly independent subset $S$ of $R$ generating a face of $C$.

Consequently, the recognition of box-integer cones might have a different complexity status than the following related problems, which are all co-NP-complete: deciding whether a given polytope is integer [37], deciding whether a given system is TDI or box-TDI [16], deciding whether a given conic system is TDI [36].

**Open Problem 2** What is the complexity of deciding whether a given cone is box-integer?

We mention that polarity preserves box-integrality only for cones, and does not extend to polyhedra. For instance, the polyhedron $\text{conv}((2, -1), (-2, -1), (0, 1))$ is fully box-integer, and its polar conv $((1, 1), (-1, 1), (0, -1))$ is integer but not box-integer.

## 5.2 Connections with Existing Results

In this section, we investigate the connections of our results with those from the literature about box-TDI polyhedra. We first derive known results about box-TDI polyhedra from our characterizations. Then, we show how Cook's characterization [38, Theorem 22.9] is connected to ours. Finally, we discuss Schrijver's sufficient condition [39, Theorem 5.35].

### 5.2.1 Consequences

Here, we review several known results about box-TDI polyhedra which can be derived from our results. The dominant of a polyhedron $P$ of $\mathbb{R}^n$ is $\text{dom}(P) = P + \mathbb{R}_+^n$.

**Consequence 1** ([14, Theorem 3.6] or [38, Theorem 22.11]) The dominant of a box-TDI polyhedron is box-TDI.

*Proof.* A face of $\text{dom}(P)$ is the sum of a face of $P$ and a cone generated by unit vectors. By statement 4 of Corollary 6, and since adding unit vectors preserves total unimodularity, the dominant of a box-TDI polyhedron is box-TDI. □
**Consequence 2 ([38, Remark 2.21])** If $P$ is a box-TDI polyhedron, then $\mathrm{aff}(P) = \{x : Cx = d\}$ for some totally unimodular matrix $C$.

*Proof.* If $P$ is a box-TDI polyhedron, then by statement 5 of Theorem 2, since $P$ is a face of $P$, its affine hull can be described using a totally unimodular matrix. $\square$

**Consequence 3 ([38, Remark 2.22])** Each edge and each extremal ray of a pointed box-TDI polyhedron is in the direction of a $\{0, \pm 1\}$-vector.

*Proof.* This is statement 4 of Corollary 6 applied to the faces of dimension one of the polyhedron. $\square$

By polarity, the above proof shows that every full-dimensional box-TDI polyhedron can be described using a $\{0, \pm 1\}$-matrix. Edmonds and Giles prove in [22] that it is still true without the full-dimensional hypothesis.

**Consequence 4 ([22, Theorem 2.16])** If $P$ is a box-TDI polyhedron, then $P = \{x : Ax \le b\}$ for some $\{0, \pm 1\}$-matrix $A$ and some vector $b$.

*Proof.* Let $P$ be a box-TDI polyhedron. By Consequence 2, we have $\mathrm{aff}(P) = \{x : Cx = d\}$ for some full row rank totally unimodular matrix $C$. By statement 5 of Theorem 2, for each facet $F$ of $P$, there exists a totally unimodular matrix $D_F$ such that $\mathrm{aff}(F) = \{x : D_F x = d_F\}$. Then, one of the rows $a_F x = b_F$ of $D_F x = d_F$ does not contain $\mathrm{aff}(P)$. Possibly multiplying by $-1$, we may assume that $a_F x \le b_F$ is valid for $P$ because $F$ is a facet of $P$. Then, the matrix $A$ whose rows are those of $C$ and every $a_F$ yields a description of $P$ as desired. $\square$

### 5.2.2 Cook's Characterization [14], [38, Theorem 22.9]

In order to get a geometric characterization of box-TDI polyhedra, Cook [14] introduced the so-called box property. Schrijver [38, Theorem 22.9] states Cook's characterization with the following equivalent form of the box property: a cone $C$ of $\mathbb{R}^n$ has the *box property* if for all $c \in C$ there exists $\tilde{c} \in C \cap \mathbb{Z}^n$ such that $\lfloor c \rfloor \le \tilde{c} \le \lfloor c \rfloor$. To highlight the connections with our results, we reformulate Schrijver's version as follows.

* A polyhedron is box-TDI if and only if the normal cones of its faces all have the box property (Cook [38, Theorem 22.9]).

The parallel with our work is clear with the following reformulation of one of our characterizations.

* A polyhedron $P$ is box-TDI if and only if every minimal tangent cone of $P$ is box-integer, up to translation (Observation 2 and Theorems 8 and 9).
**Consequence 2 ([38, Remark 2.21])** If $P$ is a box-TDI polyhedron, then $\mathrm{aff}(P) = \{x : Cx = d\}$ for some totally unimodular matrix $C$.

*Proof.* If $P$ is a box-TDI polyhedron, then by statement 5 of Theorem 2, since $P$ is a face of $P$, its affine hull can be described using a totally unimodular matrix. $\square$

**Consequence 3 ([38, Remark 2.22])** Each edge and each extremal ray of a pointed box-TDI polyhedron is in the direction of a $\{0, \pm 1\}$-vector.

*Proof.* This is statement 4 of Corollary 6 applied to the faces of dimension one of the polyhedron. $\square$

By polarity, the above proof shows that every full-dimensional box-TDI polyhedron can be described using a $\{0, \pm 1\}$-matrix. Edmonds and Giles prove in [22] that it is still true without the full-dimensional hypothesis.

**Consequence 4 ([22, Theorem 2.16])** If $P$ is a box-TDI polyhedron, then $P = \{x : Ax \le b\}$ for some $\{0, \pm 1\}$-matrix $A$ and some vector $b$.

*Proof.* Let $P$ be a box-TDI polyhedron. By Consequence 2, we have $\mathrm{aff}(P) = \{x : Cx = d\}$ for some full row rank totally unimodular matrix $C$. By statement 5 of Theorem 2, for each facet $F$ of $P$, there exists a totally unimodular matrix $D_F$ such that $\mathrm{aff}(F) = \{x : D_F x = d_F\}$. Then, one of the rows $a_F x = b_F$ of $D_F x = d_F$ does not contain $\mathrm{aff}(P)$. Possibly multiplying by $-1$, we may assume that $a_F x \le b_F$ is valid for $P$ because $F$ is a facet of $P$. Then, the matrix $A$ whose rows are those of $C$ and every $a_F$ yields a description of $P$ as desired. $\square$

### 5.2.2 Cook's Characterization [14], [38, Theorem 22.9]

In order to get a geometric characterization of box-TDI polyhedra, Cook [14] introduced the so-called box property. Schrijver [38, Theorem 22.9] states Cook's characterization with the following equivalent form of the box property: a cone $C$ of $\mathbb{R}^n$ has the *box property* if for all $c \in C$ there exists $\tilde{c} \in C \cap \mathbb{Z}^n$ such that $\lfloor c \rfloor \le \tilde{c} \le \lceil c \rceil$. To highlight the connections with our results, we reformulate Schrijver's version as follows.

* A polyhedron is box-TDI if and only if the normal cones of its faces all have the box property (Cook [38, Theorem 22.9]).

The parallel with our work is clear with the following reformulation of one of our characterizations.

* A polyhedron $P$ is box-TDI if and only if every minimal tangent cone of $P$ is box-integer, up to translation (Observation 2 and Theorems 8 and 9).
The first difference between these two results is that the first one involves the normal cones, whereas the second one involves the tangent cones. Recall that the tangent cones are the polars of the normal cones, up to translation. This polarity connection between the two statements is not surprising in light of the polarity result of Lemma 6. The second difference is that the first result involves the box property, whereas the second involves the notion of box-integrality. It is easy to see that box-integer cones have the box property. The converse does not hold. In fact, the lemma below shows that the box property is a local property when the box-integrality is a global one. The third difference is a consequence of this local/global aspect: the first result involves *all* the normal cones, whereas the second involves only the *minimal* tangent cones.

To sum up, the first result is a polar local characterization of box-TDI polyhedra, and the second is a primal global characterization.

**Proposition 4** *A cone is box-integer if and only if all its faces have the box property.*

The following lemma proves the proposition, since a cone $C$ is box-integer if and only if $\text{aff}(F)$ is box-integer for all faces $F$ of $C$.

**Lemma 7** Let $C = \{x : Ax \le 0\}$ and let $F = \{x : A_F x \le 0\}$ be a face of $C$.

* If $C$ is box-integer, then $F$ has the box property.

* If $F$ has the box property, then $\text{aff}(F)$ is box-integer.

*Proof.* Suppose that $C$ is box-integer and let $c \in F$. Since $c$ belongs to $P = F \cap \{\lfloor c \rfloor \le x \le \lfloor c \rfloor\}$, the latter is nonempty. Since $C$ is box-integer, so is $F$, hence $P$ has only integer vertices, and any of them forms a suitable $\tilde{c}$ which shows that $F$ has the box property.

Suppose now that $F$ has the box property. Let $p \in \mathbb{Z}^I$ be such that $\text{aff}(F) \cap \{x_i = p_i, i \in I\}$ is a singleton $c$ in $\text{aff}(F)$. There exists $t \in \mathbb{Z}^n$ be such that $c' = c + t \in F$. By the box property of $F$, there exists $\tilde{c} \in F \cap \mathbb{Z}^n$ such that $t + \lfloor c \rfloor = \lfloor c' \rfloor \le \tilde{c} \le \lfloor c' \rfloor = \lfloor c \rfloor + t$. Now, $\tilde{c} - t$ belongs to $\text{aff}(F) \cap \{x_i = p_i, i \in I\}$, hence $c = \tilde{c} - t$ is integer. By Lemma 1, $\text{aff}(F)$ is box-integer. $\square$

In a way, the above lemma shows that the box property of a cone is sandwiched between the box-integrality of the cone and that of its underlying affine space—an even more local property. This, up to polarity again, further compares Cook's characterization and ours, as the latter property appears in Lemma 4.

The following picture illustrates some differences between the three properties.

The notion of box-integrality of cones and affine spaces sheds a better light on box-TDI polyhedra by providing insights of how their local, global, and polar properties are connected. Both are preserved by polarity, the global notion yields a global geometric characterization of box-TDI polyhedra, and the most local one allows us to derive matricial counterparts.
The first difference between these two results is that the first one involves the normal cones, whereas the second one involves the tangent cones. Recall that the tangent cones are the polars of the normal cones, up to translation. This polarity connection between the two statements is not surprising in light of the polarity result of Lemma 6. The second difference is that the first result involves the box property, whereas the second involves the notion of box-integrality. It is easy to see that box-integer cones have the box property. The converse does not hold. In fact, the lemma below shows that the box property is a local property when the box-integrality is a global one. The third difference is a consequence of this local/global aspect: the first result involves *all* the normal cones, whereas the second involves only the *minimal* tangent cones.

To sum up, the first result is a polar local characterization of box-TDI polyhedra, and the second is a primal global characterization.

**Proposition 4** *A cone is box-integer if and only if all its faces have the box property.*

The following lemma proves the proposition, since a cone $C$ is box-integer if and only if $\text{aff}(F)$ is box-integer for all faces $F$ of $C$.

**Lemma 7** Let $C = \{x : Ax \le 0\}$ and let $F = \{x : A_F x \le 0\}$ be a face of $C$.

* If $C$ is box-integer, then $F$ has the box property.

* If $F$ has the box property, then $\text{aff}(F)$ is box-integer.

*Proof.* Suppose that $C$ is box-integer and let $c \in F$. Since $c$ belongs to $P = F \cap \{\lfloor c \rfloor \le x \le \lfloor c \rfloor\}$, the latter is nonempty. Since $C$ is box-integer, so is $F$, hence $P$ has only integer vertices, and any of them forms a suitable $\tilde{c}$ which shows that $F$ has the box property.

Suppose now that $F$ has the box property. Let $p \in \mathbb{Z}^I$ be such that $\text{aff}(F) \cap \{x_i = p_i, i \in I\}$ is a singleton $c$ in $\text{aff}(F)$. There exists $t \in \mathbb{Z}^n$ be such that $c' = c + t \in F$. By the box property of $F$, there exists $\tilde{c} \in F \cap \mathbb{Z}^n$ such that $t + \lfloor c \rfloor = \lfloor c' \rfloor \le \tilde{c} \le \lfloor c' \rfloor = \lfloor c \rfloor + t$. Now, $\tilde{c} - t$ belongs to $\text{aff}(F) \cap \{x_i = p_i, i \in I\}$, hence $c = \tilde{c} - t$ is integer. By Lemma 1, $\text{aff}(F)$ is box-integer. $\square$

In a way, the above lemma shows that the box property of a cone is sandwiched between the box-integrality of the cone and that of its underlying affine space—an even more local property. This, up to polarity again, further compares Cook's characterization and ours, as the latter property appears in Lemma 4.

The following picture illustrates some differences between the three properties.

The notion of box-integrality of cones and affine spaces sheds a better light on box-TDI polyhedra by providing insights of how their local, global, and polar properties are connected. Both are preserved by polarity, the global notion yields a global geometric characterization of box-TDI polyhedra, and the most local one allows us to derive matricial counterparts.
<figure><img src="image_1.png" /><figcaption>**Fig. 1** The cone $C = \text{cone}\{(2,1), (1,0)\}$ has the box property but is not box-integer. The cone $C' = \text{cone}\{(2,1), (3,1)\}$ does not have the box property, yet $\text{aff}(C') = \mathbb{R}^2$ is box-integer. The cone $C'' = \text{cone}\{(2,1)\}$ does not have the box property, yet its polar does.</figcaption></figure>

### 5.2.3 Schrijver's Sufficient Condition [39, Theorem 5.35]

In this section, we compare our results on box-TDI polyhedra with known results on box-TDI systems. It appears that our results in some sense allow us to split the “box-” from the “-TDI”: to prove that a given system is box-TDI, prove that it is TDI on the one hand, and prove that the polyhedron is box-TDI with Theorem 2 on the other hand.

As noticed by Schrijver [38, Page 318], Hoffman and Kruskal's result [31] implies that a matrix $A$ is totally unimodular if and only if the system $Ax \le b$ is box-TDI for each vector $b$. Then, by Theorem 7 and Theorem 9, the parallel with totally equimodular matrices can be thought as relaxing the box-TDIness of those systems to that of the associated polyhedra.

**Corollary 8** A matrix $A$ of $Q^{m \times n}$ is totally equimodular if and only if the polyhedron $\{x : Ax \le b\}$ is box-TDI for all $b \in Q^m$.

Totally unimodular matrices being totally equimodular, the following well-known result is a special case of the above corollary.

**Consequence 5** A polyhedron whose constraint matrix is totally unimodular is box-TDI.

We mention that there exist box-TDI systems which are not defined by a totally unimodular matrix. By Corollary 8 and Theorem 1, any TDI system defined with a totally equimodular matrix is box-TDI. Therefore, to find a box-TDI system for a polyhedron described by a totally equimodular matrix, there only remains to find a TDI system describing this polyhedron.

Another interesting parallel can be observed with Schrijver's Sufficient Condition. Schrijver proves in [39, Theorem 5.35] that the following weakening of $A$ being totally unimodular already suffices to obtain the box-TDIness of the system $Ax \le b$.

**Theorem 10 ([39, Theorem 5.35])** Let $Ax \le b$ be a system of linear inequalities, with $A$ an $m \times n$ matrix. Suppose that $(\star)$ for each $c \in \mathbb{R}^n$, $\max\{c^\top x : Ax \le b\}$ has (if finite) an optimum dual solution $y \in \mathbb{R}_+^m$ such
<figure><img src="image_2.png" /><figcaption>**Fig. 1** The cone $C = \text{cone}\{(2,1), (1,0)\}$ has the box property but is not box-integer. The cone $C' = \text{cone}\{(2,1), (3,1)\}$ does not have the box property, yet $\text{aff}(C') = \mathbb{R}^2$ is box-integer. The cone $C'' = \text{cone}\{(2,1)\}$ does not have the box property, yet its polar does.</figcaption></figure>

### 5.2.3 Schrijver's Sufficient Condition [39, Theorem 5.35]

In this section, we compare our results on box-TDI polyhedra with known results on box-TDI systems. It appears that our results in some sense allow us to split the “box-” from the “-TDI”: to prove that a given system is box-TDI, prove that it is TDI on the one hand, and prove that the polyhedron is box-TDI with Theorem 2 on the other hand.

As noticed by Schrijver [38, Page 318], Hoffman and Kruskal's result [31] implies that a matrix $A$ is totally unimodular if and only if the system $Ax \le b$ is box-TDI for each vector $b$. Then, by Theorem 7 and Theorem 9, the parallel with totally equimodular matrices can be thought as relaxing the box-TDIness of those systems to that of the associated polyhedra.

**Corollary 8** A matrix $A$ of $Q^{m \times n}$ is totally equimodular if and only if the polyhedron $\{x : Ax \le b\}$ is box-TDI for all $b \in Q^m$.

Totally unimodular matrices being totally equimodular, the following well-known result is a special case of the above corollary.

**Consequence 5** A polyhedron whose constraint matrix is totally unimodular is box-TDI.

We mention that there exist box-TDI systems which are not defined by a totally unimodular matrix. By Corollary 8 and Theorem 1, any TDI system defined with a totally equimodular matrix is box-TDI. Therefore, to find a box-TDI system for a polyhedron described by a totally equimodular matrix, there only remains to find a TDI system describing this polyhedron.

Another interesting parallel can be observed with Schrijver's Sufficient Condition. Schrijver proves in [39, Theorem 5.35] that the following weakening of $A$ being totally unimodular already suffices to obtain the box-TDIness of the system $Ax \le b$.

**Theorem 10 ([39, Theorem 5.35])** Let $Ax \le b$ be a system of linear inequalities, with $A$ an $m \times n$ matrix. Suppose that $(\star)$ for each $c \in \mathbb{R}^n$, $\max\{c^\top x : Ax \le b\}$ has (if finite) an optimum dual solution $y \in \mathbb{R}_+^m$ such
that the rows of A corresponding to positive components of y form a totally unimodular submatrix of A. Then $Ax \leq b$ is box-TDI.

Note that the property $(\star)$ is equivalent to the condition that for every face $F$ of $\{x: Ax \leq b\}$, the system $Ax \leq b$ contains a totally unimodular face-defining matrix for $F$. Theorem 2 contains a polyhedral version: a polyhedron is box-TDI if and only if each of its faces has a totally unimodular face-defining matrix. This latter condition is weaker than $(\star)$, hence does not ensure the box-TDIness of the system. Nevertheless, when satisfied, all that remains to do is to find a TDI system describing the same polyhedron.

In light of our characterizations, one could wonder whether Theorem 10 can be turned into an equivalence, that is: can every box-TDI polyhedron be described by a box-TDI system satisfying $(\star)$? Unfortunately, the answer to this question is negative. Indeed, systems satisfying $(\star)$ can be assumed $\{0, \pm 1\}$, and there exist box-TDI polyhedra for which no TDI description is $\{0, \pm 1\}$—see [38, Page 325].

# 6 Illustrations

In this section, we provide illustrations of our results. The first one is a new perspective on the equivalence between two results about binary clutters. Secondly, we refute a conjecture of Ding, Zang, and Zhao [19] about box-perfect graphs. Thirdly, we discuss connections with an abstract class of polyhedra introduced in [27]. Finally, we characterize the box-TDIness of the cone of conservative functions of a graph.

## 6.1 Box-Mengerian Clutters

We briefly introduce the definitions we need about clutters. A collection $\mathcal{C}$ of subsets of a set $E$ is a *clutter* if none of its sets contains another one. We denote by $A_C$ the $\mathcal{C} \times E$ incidence matrix of $\mathcal{C}$ and by $P_C = \{x \in \mathbb{R}^E : A_C x \ge 1, x \ge 0\}$ the associated covering polyhedron. A clutter $\mathcal{C}$ is *binary* if the symmetric difference of any three elements of $\mathcal{C}$ contains an element of $\mathcal{C}$. A clutter $\mathcal{C}$ is *box-$\frac{1}{d}$-integral* if for all $\ell, u \in \frac{1}{d}\mathbb{Z}^E$, each vertex of $P_C \cap \{\ell \le x \le u\}$ belongs to $\frac{1}{d}\mathbb{Z}^E$. A matrix $A \in \{0,1\}^{m \times n}$ is called (*box-*)Mengerian if the system $Ax \ge 1, x \ge 0$ is (*box-*)TDI. A clutter $\mathcal{C}$ is (*box-*)Mengerian if $A_C$ is (*box-*)Mengerian. Deleting an element $e \in E$ means replacing $\mathcal{C}$ by $\mathcal{C} \setminus e = \{X \in \mathcal{C} : e \notin X\}$ and contracting an element $e \in E$ means replacing $\mathcal{C}$ by $\mathcal{C}/e$ which is composed of the inclusionwise minimal members of $\{X \setminus \{e\} : X \in \mathcal{C}\}$. The minors of a clutter are the clutters obtained by repeatedly deleting and contracting elements of $E$. The clutter $Q_6$ is defined on the set $E_4$ of the edges of the complete graph $K_4$, and its elements are the triangles of $K_4$—see Figure 2. The clutter $Q_7$ is defined on $E_4 \cup e$ where $e \notin E_4$, and its elements are $X \cup \{e\}$ for each triangle or perfect matching $X$ of $K_4$.
that the rows of A corresponding to positive components of y form a totally unimodular submatrix of A. Then $Ax \le b$ is box-TDI.

Note that the property $(\star)$ is equivalent to the condition that for every face $F$ of $\{x: Ax \le b\}$, the system $Ax \le b$ contains a totally unimodular face-defining matrix for $F$. Theorem 2 contains a polyhedral version: a polyhedron is box-TDI if and only if each of its faces has a totally unimodular face-defining matrix. This latter condition is weaker than $(\star)$, hence does not ensure the box-TDIness of the system. Nevertheless, when satisfied, all that remains to do is to find a TDI system describing the same polyhedron.

In light of our characterizations, one could wonder whether Theorem 10 can be turned into an equivalence, that is: can every box-TDI polyhedron be described by a box-TDI system satisfying $(\star)$? Unfortunately, the answer to this question is negative. Indeed, systems satisfying $(\star)$ can be assumed $\{0, \pm 1\}$, and there exist box-TDI polyhedra for which no TDI description is $\{0, \pm 1\}$—see [38, Page 325].

# 6 Illustrations

In this section, we provide illustrations of our results. The first one is a new perspective on the equivalence between two results about binary clutters. Secondly, we refute a conjecture of Ding, Zang, and Zhao [19] about box-perfect graphs. Thirdly, we discuss connections with an abstract class of polyhedra introduced in [27]. Finally, we characterize the box-TDIness of the cone of conservative functions of a graph.

## 6.1 Box-Mengerian Clutters

We briefly introduce the definitions we need about clutters. A collection $\mathcal{C}$ of subsets of a set $E$ is a *clutter* if none of its sets contains another one. We denote by $A_C$ the $\mathcal{C} \times E$ incidence matrix of $\mathcal{C}$ and by $P_C = \{x \in \mathbb{R}^E : A_C x \ge 1, x \ge 0\}$ the associated covering polyhedron. A clutter $\mathcal{C}$ is *binary* if the symmetric difference of any three elements of $\mathcal{C}$ contains an element of $\mathcal{C}$. A clutter $\mathcal{C}$ is *box-$\frac{1}{d}$-integral* if for all $\ell, u \in \frac{1}{d}\mathbb{Z}^E$, each vertex of $P_C \cap \{\ell \le x \le u\}$ belongs to $\frac{1}{d}\mathbb{Z}^E$. A matrix $A \in \{0,1\}^{m \times n}$ is called (*box-*)Mengerian if the system $Ax \ge 1, x \ge 0$ is (*box-*)TDI. A clutter $\mathcal{C}$ is (*box-*)Mengerian if $A_C$ is (*box-*)Mengerian. Deleting an element $e \in E$ means replacing $\mathcal{C}$ by $\mathcal{C} \setminus e = \{X \in \mathcal{C} : e \notin X\}$ and contracting an element $e \in E$ means replacing $\mathcal{C}$ by $\mathcal{C}/e$ which is composed of the inclusionwise minimal members of $\{X \setminus \{e\} : X \in \mathcal{C}\}$. The minors of a clutter are the clutters obtained by repeatedly deleting and contracting elements of $E$. The clutter $Q_6$ is defined on the set $E_4$ of the edges of the complete graph $K_4$, and its elements are the triangles of $K_4$—see Figure 2. The clutter $Q_7$ is defined on $E_4 \cup e$ where $e \notin E_4$, and its elements are $X \cup \{e\}$ for each triangle or perfect matching $X$ of $K_4$.
In 1995, Gerards and Laurent [24] characterized the binary clutters that are box-$\frac{1}{d}$-integral for all $d \in \mathbb{Z}_{>0}$ by forbidding minors.

**Theorem 11 ([24, Theorem 1.2])** A binary clutter is box-$\frac{1}{d}$-integral for all $d \in \mathbb{Z}_{>0}$ if and only if neither $Q_6$ nor $Q_7$ is its minor.

In 2008, Chen, Ding, and Zang [12] characterized box-Mengerian binary clutters by forbidding minors. In [11], Chen, Chen, and Zang provide a simpler proof of this characterization, based on the so called ESP property. We mention that none of the proofs of Theorem 12 rely on Theorem 11.

**Theorem 12 ([12, Corollary 1.2])** A binary clutter is box-Mengerian if and only if neither $Q_6$ nor $Q_7$ is its minor.

The combination of Theorems 11 and 12 implies that a binary clutter is box-Mengerian if and only if it is box-$\frac{1}{d}$-integral for all $d \in \mathbb{Z}_{>0}$. We show in the following how this equivalence is actually a special case of Theorem 9.

By definition, a clutter $\mathcal{C}$ is box-$\frac{1}{d}$-integral if and only if $dP_{\mathcal{C}}$ is box-integer, which implies the following reformulation of the class of polyhedra characterized in Theorem 11.

A clutter $\mathcal{C}$ is box-$\frac{1}{d}$-integral for all $d \in \mathbb{Z}_{>0}$ if and only if $P_{\mathcal{C}}$ is fully box-integer.

Recall that a system is box-TDI if and only if it is TDI and defines a box-TDI polyhedron. Then, by Theorem 9, a clutter is box-Mengerian if and only if it is Mengerian and $P_C$ is principally box-integer. Since $\mathcal{C}$ being Mengerian implies the integrality of $P_C$, we get the following reformulation for the systems involved in Theorem 12.

A clutter $\mathcal{C}$ is box-Mengerian if and only if it is Mengerian and $P_C$ is fully box-integer.

Therefore, to prove the announced equivalence it is enough to show the following statement.

If $\mathcal{C}$ is binary and $P_C$ is fully box-integer, then $\mathcal{C}$ is Mengerian.

We apply Seymour's characterization [41]: a binary clutter is Mengerian if and only if it has no $Q_6$ minor. The property of $P_C$ being fully box-integer is closed under taking minors since $P_{C/e}$ and $P_{C\setminus e}$ are respectively obtained from $P_C \cap \{x_e = 0\}$ and $P_C \cap \{x_e = 1\}$ by deleting $e$'s coordinate. Furthermore, $P_{Q_6}$ is not fully box-integer by statement 3 of Theorem 8. Indeed, the first three rows of the matrix $A_{Q_6}$ of Figure 2 form a nonequimodular matrix $M$, as the determinant of the three first columns equals 2 and that of the three last columns equals 1. Moreover, $M$ is face-defining for $P_{Q_6}$, by Observation 4 and because $\chi^1 + \chi^6, \chi^2 + \chi^5, \chi^3 + \chi^4$, and $\chi^4 + \chi^5 + \chi^6$ are affinely independent, belong to $P_{Q_6}$, and satisfy $Mx = 1$. Therefore, if $\mathcal{C}$ is binary and $P_C$ is fully box-integer, then $\mathcal{C}$ has no $Q_6$ minor.
In 1995, Gerards and Laurent [24] characterized the binary clutters that are box-$\frac{1}{d}$-integral for all $d \in \mathbb{Z}_{>0}$ by forbidding minors.

**Theorem 11 ([24, Theorem 1.2])** A binary clutter is box-$\frac{1}{d}$-integral for all $d \in \mathbb{Z}_{>0}$ if and only if neither $Q_6$ nor $Q_7$ is its minor.

In 2008, Chen, Ding, and Zang [12] characterized box-Mengerian binary clutters by forbidding minors. In [11], Chen, Chen, and Zang provide a simpler proof of this characterization, based on the so called ESP property. We mention that none of the proofs of Theorem 12 rely on Theorem 11.

**Theorem 12 ([12, Corollary 1.2])** A binary clutter is box-Mengerian if and only if neither $Q_6$ nor $Q_7$ is its minor.

The combination of Theorems 11 and 12 implies that a binary clutter is box-Mengerian if and only if it is box-$\frac{1}{d}$-integral for all $d \in \mathbb{Z}_{>0}$. We show in the following how this equivalence is actually a special case of Theorem 9.

By definition, a clutter $\mathcal{C}$ is box-$\frac{1}{d}$-integral if and only if $dP_{\mathcal{C}}$ is box-integer, which implies the following reformulation of the class of polyhedra characterized in Theorem 11.

A clutter $\mathcal{C}$ is box-$\frac{1}{d}$-integral for all $d \in \mathbb{Z}_{>0}$ if and only if $P_{\mathcal{C}}$ is fully box-integer.

Recall that a system is box-TDI if and only if it is TDI and defines a box-TDI polyhedron. Then, by Theorem 9, a clutter is box-Mengerian if and only if it is Mengerian and $P_C$ is principally box-integer. Since $\mathcal{C}$ being Mengerian implies the integrality of $P_C$, we get the following reformulation for the systems involved in Theorem 12.

A clutter $\mathcal{C}$ is box-Mengerian if and only if it is Mengerian and $P_C$ is fully box-integer.

Therefore, to prove the announced equivalence it is enough to show the following statement.

If $\mathcal{C}$ is binary and $P_C$ is fully box-integer, then $\mathcal{C}$ is Mengerian.

We apply Seymour's characterization [41]: a binary clutter is Mengerian if and only if it has no $Q_6$ minor. The property of $P_C$ being fully box-integer is closed under taking minors since $P_{C/e}$ and $P_{C\setminus e}$ are respectively obtained from $P_C \cap \{x_e = 0\}$ and $P_C \cap \{x_e = 1\}$ by deleting $e$'s coordinate. Furthermore, $P_{Q_6}$ is not fully box-integer by statement 3 of Theorem 8. Indeed, the first three rows of the matrix $A_{Q_6}$ of Figure 2 form a nonequimodular matrix $M$, as the determinant of the three first columns equals 2 and that of the three last columns equals 1. Moreover, $M$ is face-defining for $P_{Q_6}$, by Observation 4 and because $\chi^1 + \chi^6, \chi^2 + \chi^5, \chi^3 + \chi^4$, and $\chi^4 + \chi^5 + \chi^6$ are affinely independent, belong to $P_{Q_6}$, and satisfy $Mx = 1$. Therefore, if $\mathcal{C}$ is binary and $P_C$ is fully box-integer, then $\mathcal{C}$ has no $Q_6$ minor.
$$A_{Q_6} = \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 \end{bmatrix}$$

<caption>Fig. 2 The matrix representation of the clutter $Q_6$.</caption>

## 6.2 On Box-Perfect Graphs

In this section, we provide a construction which preserves non box-perfection, and use it to refute a conjecture of Ding, Zang, and Zhao [19].

In a graph, a *clique* is a set of pairwise adjacent vertices, and a *stable set* is the complement of a clique. The *stable set polytope* of a graph is the convex hull of the incidence vectors of its stable sets. *Perfect graphs* are known to be those whose stable set polytope is described by the system composed of the clique inequalities and the nonnegativity constraints:

$$ \begin{array}{l} x(C) \le 1 \quad \text{for all cliques } C, \\ x \ge 0. \end{array} $$

A *box-perfect graph* is a graph for which this system is box-TDI. Since this system is known to be TDI if and only if the graph is perfect [34], a graph is box-perfect if and only if it is perfect and its stable set polytope is box-TDI. The characterization of box-perfect graphs is a long standing open question raised by Cameron and Edmonds in 1982 [8]. Recent progress has been made on this topic by Ding, Zang, and Zhao [19]. They exhibit several new subclasses of perfect graphs, and in particular prove the conjecture of Cameron and Edmonds [8] that parity graphs are box-perfect. They also propose a conjecture for the characterization of box-perfect graphs.

To state their conjecture, they introduce the class of graphs $\mathcal{R}$, built as follows. Let $G = (U, V, E)$ be a bipartite graph whose biadjacency matrix is minimally non-TU. Add a set of edges $F$ between vertices of $V$ such that the neighborhood $N_{G'}(u)$ of $u$ in $G' = (U \cup V, E \cup F)$ is a clique for all $u \in U$. If there exists $u \in U$ such that $N_{G'}(u) = V$, then $G' \setminus \{u\}$ is in $\mathcal{R}$, otherwise $G'$ is in $\mathcal{R}$.

*Conjecture 1 (Ding, Zang, and Zhao [19])* A perfect graph is box-perfect if and only if it contains no graph from $\mathcal{R}$ as an induced subgraph.

We introduce the operation of *unfolding* a vertex $v \in V$ in $G = (V, E)$. Take a vertex $v \in V$ and two sets of vertices $X$ and $Y$ such that $X \cup Y = N_G(v)$ and no edge connects $X \setminus Y$ and $Y \setminus X$. Delete $v$ and add two new vertices $x$ and $y$ such that the neighborhoods of $x$ and $y$ are respectively $X$ and $Y$. Finally, add another vertex $z$ adjacent only to $x$ and $y$.

We mention that unfolding a vertex might not preserved perfection. Nevertheless, if the starting graph is perfect but not box-perfect, then the graph obtained by unfolding is not box-perfect.
$$A_{Q_6} = \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 \end{bmatrix}$$

<caption>Fig. 2 The matrix representation of the clutter $Q_6$.</caption>

## 6.2 On Box-Perfect Graphs

In this section, we provide a construction which preserves non box-perfection, and use it to refute a conjecture of Ding, Zang, and Zhao [19].

In a graph, a *clique* is a set of pairwise adjacent vertices, and a *stable set* is the complement of a clique. The *stable set polytope* of a graph is the convex hull of the incidence vectors of its stable sets. *Perfect graphs* are known to be those whose stable set polytope is described by the system composed of the clique inequalities and the nonnegativity constraints:

$$ \begin{array}{l} x(C) \le 1 \quad \text{for all cliques } C, \\ x \ge 0. \end{array} $$

A *box-perfect graph* is a graph for which this system is box-TDI. Since this system is known to be TDI if and only if the graph is perfect [34], a graph is box-perfect if and only if it is perfect and its stable set polytope is box-TDI. The characterization of box-perfect graphs is a long standing open question raised by Cameron and Edmonds in 1982 [8]. Recent progress has been made on this topic by Ding, Zang, and Zhao [19]. They exhibit several new subclasses of perfect graphs, and in particular prove the conjecture of Cameron and Edmonds [8] that parity graphs are box-perfect. They also propose a conjecture for the characterization of box-perfect graphs.

To state their conjecture, they introduce the class of graphs $\mathcal{R}$, built as follows. Let $G = (U, V, E)$ be a bipartite graph whose biadjacency matrix is minimally non-TU. Add a set of edges $F$ between vertices of $V$ such that the neighborhood $N_{G'}(u)$ of $u$ in $G' = (U \cup V, E \cup F)$ is a clique for all $u \in U$. If there exists $u \in U$ such that $N_{G'}(u) = V$, then $G' \setminus \{u\}$ is in $\mathcal{R}$, otherwise $G'$ is in $\mathcal{R}$.

**Conjecture 1 (Ding, Zang, and Zhao [19])** A perfect graph is box-perfect if and only if it contains no graph from $\mathcal{R}$ as an induced subgraph.

We introduce the operation of *unfolding* a vertex $v \in V$ in $G = (V, E)$. Take a vertex $v \in V$ and two sets of vertices $X$ and $Y$ such that $X \cup Y = N_G(v)$ and no edge connects $X \setminus Y$ and $Y \setminus X$. Delete $v$ and add two new vertices $x$ and $y$ such that the neighborhoods of $x$ and $y$ are respectively $X$ and $Y$. Finally, add another vertex $z$ adjacent only to $x$ and $y$.

We mention that unfolding a vertex might not preserved perfection. Nevertheless, if the starting graph is perfect but not box-perfect, then the graph obtained by unfolding is not box-perfect.
<figure><img src="image_2.png" /><figcaption>Fig. 3 A non box-perfect graph obtained by unfolding the vertex v in S$_{3}$ , with X = { b, c, e } and Y = { b, c, d } .</figcaption></figure>

It is well known that the graph S$_{3}$ in Figure 3 is not box-perfect [9]. It can also be seen because the nonequimodular matrix M below is face-defining for the stable set polytope of S$_{3}$ .

$$
M = \begin{bmatrix}
1 & 1 & 0 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 1 & 0 \\
0 & 1 & 1 & 0 & 0 & 1
\end{bmatrix}
$$

Indeed, up to reordering the vertices, the rows of M correspond to the three ex- ternal triangles, and the four affinely independent stable sets { a, v } , { b, e } , { c, d } , { a, d, e } belong to the corresponding face. By Observation 4 and Theorem 2, S$_{3}$ is not box-perfect.

**Proposition 5** The graph G of Figure 3 is perfect but not box-perfect and none of its induced subgraphs belongs to R .

Proof. Note that the graphs G and G^v are perfect. By Lemma 8, G^v is not box-perfect. The graph G^v \ {z} is box-perfect, as one can check that the constraint matrix of its stable set polytope is totally unimodular. Hence, if G^v contains an induced subgraph H ∈ R , then z ∈ V (H). As no graph in R has a vertex of degree one, this contradicts the claim below.

If H ∈ R has a vertex z with only two neighbors x and y , then xy is an edge of H .

Recall that vertices of H are partitioned into sets U and V such that the neighborhood of every vertex of U is a clique of V , and the biadjacency matrix M of the edges between U and V is either minimally non-TU or obtained from such a matrix by removing a row. In particular, every column of M contains at least a one, and every row of M contains at least two ones.

If z ∈ U , then xy is an edge of H . Suppose now z ∈ V . The z -column of M contains a one, so a neighbor of z , say x , belongs to U . The x -row of M contains two ones, so x has an other neighbor in V , which is connected to z . Therefore, this neighbor is y , and xy is an edge of H . □

Note that choosing X = { c, e } and Y = { b, c, d } when unfolding v in Figure 3 yields another perfect but not box-perfect graph with no graph from R as an induced subgraph.
<figure><img src="image_3.png" /><figcaption>**Fig. 3** A non box-perfect graph obtained by unfolding the vertex v in $S_3$, with $X = \{b, c, e\}$ and $Y = \{b, c, d\}$.</figcaption></figure>

It is well known that the graph $S_3$ in Figure 3 is not box-perfect [9]. It can also be seen because the nonequimodular matrix $M$ below is face-defining for the stable set polytope of $S_3$.

$$M = \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 \end{bmatrix}$$

Indeed, up to reordering the vertices, the rows of $M$ correspond to the three external triangles, and the four affinely independent stable sets $\{a, v\}, \{b, e\}, \{c, d\}, \{a, d, e\}$ belong to the corresponding face. By Observation 4 and Theorem 2, $S_3$ is not box-perfect.

**Proposition 5** The graph $G$ of Figure 3 is perfect but not box-perfect and none of its induced subgraphs belongs to $\mathcal{R}$.

*Proof.* Note that the graphs $G$ and $G^v$ are perfect. By Lemma 8, $G^v$ is not box-perfect. The graph $G^v \setminus \{z\}$ is box-perfect, as one can check that the constraint matrix of its stable set polytope is totally unimodular. Hence, if $G^v$ contains an induced subgraph $H \in \mathcal{R}$, then $z \in V(H)$. As no graph in $\mathcal{R}$ has a vertex of degree one, this contradicts the claim below.

If $H \in \mathcal{R}$ has a vertex $z$ with only two neighbors $x$ and $y$, then $xy$ is an edge of $H$.

Recall that vertices of $H$ are partitioned into sets $U$ and $V$ such that the neighborhood of every vertex of $U$ is a clique of $V$, and the biadjacency matrix $M$ of the edges between $U$ and $V$ is either minimally non-TU or obtained from such a matrix by removing a row. In particular, every column of $M$ contains at least a one, and every row of $M$ contains at least two ones.

If $z \in U$, then $xy$ is an edge of $H$. Suppose now $z \in V$. The $z$-column of $M$ contains a one, so a neighbor of $z$, say $x$, belongs to $U$. The $x$-row of $M$ contains two ones, so $x$ has an other neighbor in $V$, which is connected to $z$. Therefore, this neighbor is $y$, and $xy$ is an edge of $H$. □

Note that choosing $X = \{c, e\}$ and $Y = \{b, c, d\}$ when unfolding $v$ in Figure 3 yields another perfect but not box-perfect graph with no graph from $\mathcal{R}$ as an induced subgraph.
## 6.3 Integer Decomposition Property

In this section, we discuss possible connections between full box-integrality and the integer decomposition property. This property arises in various fields such as integer programming, algebraic geometry, combinatorial commutative algebra. Several classes of polyhedra are known to have the integer decomposition property, as for instance: projections of polyhedra defined by totally unimodular matrices [40], polyhedra defined by nearly totally unimodular matrices [26], certain polyhedra defined by $k$-balanced matrices [46], the stable set polytope of claw-free $t$-perfect graphs and $h$-perfect line-graphs [6].

A polyhedron $P$ has the *integer decomposition property*, if for any natural number $k$ and any integer vector $x \in kP$, there exist $k$ integer vectors $x_1, \dots, x_k \in P$ with $x_1 + \dots + x_k = x$. A stronger property is when the polyhedron $P$ has the *Integer Carathéodory Property*, that is, if for every positive integer $k$ and every integer vector $x \in kP$, there exist $n_1, \dots, n_t \in \mathbb{Z}_{\ge 0}$ and affinely independent $x_1, \dots, x_t \in P \cap \mathbb{Z}^n$ such that $n_1 + \dots + n_t = k$ and $x = \sum_i n_i x_i$.

In [27], Gijswijt and Regts introduce a class $\mathcal{P}$ of polyhedra and show that they have the Integer Carathéodory Property. They define $\mathcal{P}$ to be the set of polyhedra $P$ such that for any $k \in \mathbb{Z}_{\ge 0}$, $r \in \{0, \dots, k\}$, and $w \in \mathbb{Z}^n$ the intersection $rP \cap (w - (k-r)P)$ is box-integer. They also show [27, Proposition 4] that every $P \in \mathcal{P}$ is box-integer. Given the definition of $\mathcal{P}$, note that if a polyhedron is in $\mathcal{P}$, then so are all its dilations. Therefore, every $P$ in $\mathcal{P}$ is fully box-integer. By Theorem 9, this has the following consequence.

**Corollary 9** Every $P \in \mathcal{P}$ is box-TDI.

The converse of Corollary 9 does not hold. We show below that polyhedra in $\mathcal{P}$ satisfy the stronger property that not only the affine hulls of their faces are principally box-integer, but also the intersection of the affine hulls of any two faces. In terms of matrices, this is phrased as follows.

**Proposition 6** If $P \in \mathcal{P}$, then $\text{aff}(F) \cap \text{aff}(G)$ has an equimodular face-defining matrix for all faces $F$ and $G$ of $P$.

*Proof.* Let $F$ and $G$ be faces of $P$, and let $x_F$ and $x_G$ be rational points in their respective relative interior. There exists $k \in \mathbb{Z}_{\ge 0}$ such that both $kx_F$ and $kx_G$ are integers. Let $w = k(x_F + x_G)$, and $Q = kP \cap (w - kP) = k(P \cap (x_F + x_G - P))$. Since $P \in \mathcal{P}$, note that $rQ$ is box-integer for all $r \in \mathbb{Z}_{\ge 0}$, that is, $Q$ is fully box-integer. By the choice of $x_F$ and $x_G$, the minimal face $H$ of $Q$ containing $kx_F$ satisfies $\text{aff}(H) = k(\text{aff}(F) \cap -(x_F + x_G + \text{aff}(G)))$. Thus, the latter is a translation of $\text{aff}(F) \cap -\text{aff}(G)$. Since $Q$ is fully box-integer, $\text{aff}(H)$ has an equimodular face-defining matrix by Theorem 8, hence so has $\text{aff}(F) \cap -\text{aff}(G)$ by translation. Since $\text{aff}(F) \cap \text{aff}(G)$ can be described using the matrix of constraints of $\text{aff}(F) \cap \text{aff}(G)$ and multiplying by $-1$ the right-hand sides corresponding to $\text{aff}(G)$, we get an equimodular face-defining matrix for $\text{aff}(F) \cap \text{aff}(G)$. $\square$
## 6.3 Integer Decomposition Property

In this section, we discuss possible connections between full box-integrality and the integer decomposition property. This property arises in various fields such as integer programming, algebraic geometry, combinatorial commutative algebra. Several classes of polyhedra are known to have the integer decomposition property, as for instance: projections of polyhedra defined by totally unimodular matrices [40], polyhedra defined by nearly totally unimodular matrices [26], certain polyhedra defined by $k$-balanced matrices [46], the stable set polytope of claw-free $t$-perfect graphs and $h$-perfect line-graphs [6].

A polyhedron $P$ has the *integer decomposition property*, if for any natural number $k$ and any integer vector $x \in kP$, there exist $k$ integer vectors $x_1, \dots, x_k \in P$ with $x_1 + \dots + x_k = x$. A stronger property is when the polyhedron $P$ has the *Integer Carathéodory Property*, that is, if for every positive integer $k$ and every integer vector $x \in kP$, there exist $n_1, \dots, n_t \in \mathbb{Z}_{\ge 0}$ and affinely independent $x_1, \dots, x_t \in P \cap \mathbb{Z}^n$ such that $n_1 + \dots + n_t = k$ and $x = \sum_i n_i x_i$.

In [27], Gijswijt and Regts introduce a class $\mathcal{P}$ of polyhedra and show that they have the Integer Carathéodory Property. They define $\mathcal{P}$ to be the set of polyhedra $P$ such that for any $k \in \mathbb{Z}_{\ge 0}$, $r \in \{0, \dots, k\}$, and $w \in \mathbb{Z}^n$ the intersection $rP \cap (w - (k-r)P)$ is box-integer. They also show [27, Proposition 4] that every $P \in \mathcal{P}$ is box-integer. Given the definition of $\mathcal{P}$, note that if a polyhedron is in $\mathcal{P}$, then so are all its dilations. Therefore, every $P$ in $\mathcal{P}$ is fully box-integer. By Theorem 9, this has the following consequence.

**Corollary 9** Every $P \in \mathcal{P}$ is box-TDI.

The converse of Corollary 9 does not hold. We show below that polyhedra in $\mathcal{P}$ satisfy the stronger property that not only the affine hulls of their faces are principally box-integer, but also the intersection of the affine hulls of any two faces. In terms of matrices, this is phrased as follows.

**Proposition 6** If $P \in \mathcal{P}$, then $\text{aff}(F) \cap \text{aff}(G)$ has an equimodular face-defining matrix for all faces $F$ and $G$ of $P$.

*Proof.* Let $F$ and $G$ be faces of $P$, and let $x_F$ and $x_G$ be rational points in their respective relative interior. There exists $k \in \mathbb{Z}_{\ge 0}$ such that both $kx_F$ and $kx_G$ are integers. Let $w = k(x_F + x_G)$, and $Q = kP \cap (w - kP) = k(P \cap (x_F + x_G - P))$. Since $P \in \mathcal{P}$, note that $rQ$ is box-integer for all $r \in \mathbb{Z}_{\ge 0}$, that is, $Q$ is fully box-integer. By the choice of $x_F$ and $x_G$, the minimal face $H$ of $Q$ containing $kx_F$ satisfies $\text{aff}(H) = k(\text{aff}(F) \cap -(x_F + x_G + \text{aff}(G)))$. Thus, the latter is a translation of $\text{aff}(F) \cap -\text{aff}(G)$. Since $Q$ is fully box-integer, $\text{aff}(H)$ has an equimodular face-defining matrix by Theorem 8, hence so has $\text{aff}(F) \cap -\text{aff}(G)$ by translation. Since $\text{aff}(F) \cap \text{aff}(G)$ can be described using the matrix of constraints of $\text{aff}(F) \cap \text{aff}(G)$ and multiplying by $-1$ the right-hand sides corresponding to $\text{aff}(G)$, we get an equimodular face-defining matrix for $\text{aff}(F) \cap \text{aff}(G)$. $\square$
Fully box-integer polyhedra do not inherit the Integer Carathéodory Property. Actually, they do not even inherit the integer decomposition property, as the classical example of polytope without the integer decomposition property $P = \text{conv}((0, 0, 0), (1, 1, 0), (1, 0, 1), (0, 1, 1))$ is fully box-integer. To see that $P$ is fully box-integer, note that in the minimal linear description of $P$ given below, the matrix of constraints is totally equimodular. Since $P$ is also integer, this implies that $P$ is fully box-integer by Theorem 7. The point $(1, 1, 1)$ is in $2P$ and cannot be written as an integer combination of the integer points of $P$, hence $P$ does not have the integer decomposition property.

$$P = \left\{ x \in \mathbb{R}^3 : \begin{bmatrix} 1 & -1 & -1 \\ -1 & 1 & -1 \\ -1 & -1 & 1 \\ 1 & 1 & 1 \end{bmatrix} x \le \begin{bmatrix} 0 \\ 0 \\ 0 \\ 2 \end{bmatrix} \right\}$$

Nevertheless, given the strong integrality properties of fully box-integer polyhedra and as the above large subclass $\mathcal{P}$ has the Integer Carathéodory Property, it might be that many of them have the integer decomposition property. In this area, a long standing open question is known as Oda's question [35]: is it true that every smooth polytope has the integer decomposition property? A full-dimensional polytope of $\mathbb{R}^n$ is simple if every vertex has $n$ neighbors. A simple integer polytope is smooth if for every vertex $v$ the generators of the associated minimal tangent cone form a basis of the lattice $\mathbb{Z}^n$.

The polyhedron of the example above is not smooth, and the following special case of Oda's question is a reasonable first step to determine which fully box-integer polyhedra have the integer decomposition property.

**Open Problem 3** Do smooth fully box-integer polyhedra have the integer decomposition property?

## 6.4 Box-TDIness for Conservative Functions

In [15], the authors prove that the standard system describing the circuit cone is box-TDI if and only if the graph is series-parallel. We illustrate that polarity preserves the box-TDIness of cones by providing a box-TDI system for the cone of conservative function—polar of the circuit cone.

Let $G = (V, E)$ be an undirected graph. The set of edges connecting a given set of vertices and its complement is called a *cut*. A cut containing no other nonempty cut is called a *bond*. A set of edges is called a *circuit* if it induces a connected subgraph where every vertex has degree two. The *minors* of a graph are the graphs obtained by repeatedly contracting edges and deleting edges and isolated vertices. Given $e \in E$, the graphs obtained from $G$ by respectively deleting and contracting $e$ are denoted by $G \setminus e$ and $G/e$. A graph is *series-parallel* if and only if it contains no $K_4$ minor [20].

The *circuit cone* $C_{\text{circuit}}(G) = \text{cone}\{\chi^C \text{ for all circuits } C \text{ of } G\}$ is the cone generated by the incidence vectors of the circuits of $G$. Seymour [42] proved
Fully box-integer polyhedra do not inherit the Integer Carathéodory Property. Actually, they do not even inherit the integer decomposition property, as the classical example of polytope without the integer decomposition property $P = \text{conv}((0, 0, 0), (1, 1, 0), (1, 0, 1), (0, 1, 1))$ is fully box-integer. To see that $P$ is fully box-integer, note that in the minimal linear description of $P$ given below, the matrix of constraints is totally equimodular. Since $P$ is also integer, this implies that $P$ is fully box-integer by Theorem 7. The point $(1, 1, 1)$ is in $2P$ and cannot be written as an integer combination of the integer points of $P$, hence $P$ does not have the integer decomposition property.

$$P = \left\{ x \in \mathbb{R}^3 : \begin{bmatrix} 1 & -1 & -1 \\ -1 & 1 & -1 \\ -1 & -1 & 1 \\ 1 & 1 & 1 \end{bmatrix} x \le \begin{bmatrix} 0 \\ 0 \\ 0 \\ 2 \end{bmatrix} \right\}$$

Nevertheless, given the strong integrality properties of fully box-integer polyhedra and as the above large subclass $\mathcal{P}$ has the Integer Carathéodory Property, it might be that many of them have the integer decomposition property. In this area, a long standing open question is known as Oda's question [35]: is it true that every smooth polytope has the integer decomposition property? A full-dimensional polytope of $\mathbb{R}^n$ is simple if every vertex has $n$ neighbors. A simple integer polytope is smooth if for every vertex $v$ the generators of the associated minimal tangent cone form a basis of the lattice $\mathbb{Z}^n$.

The polyhedron of the example above is not smooth, and the following special case of Oda's question is a reasonable first step to determine which fully box-integer polyhedra have the integer decomposition property.

**Open Problem 3** Do smooth fully box-integer polyhedra have the integer decomposition property?

## 6.4 Box-TDIness for Conservative Functions

In [15], the authors prove that the standard system describing the circuit cone is box-TDI if and only if the graph is series-parallel. We illustrate that polarity preserves the box-TDIness of cones by providing a box-TDI system for the cone of conservative function—polar of the circuit cone.

Let $G = (V, E)$ be an undirected graph. The set of edges connecting a given set of vertices and its complement is called a *cut*. A cut containing no other nonempty cut is called a *bond*. A set of edges is called a *circuit* if it induces a connected subgraph where every vertex has degree two. The *minors* of a graph are the graphs obtained by repeatedly contracting edges and deleting edges and isolated vertices. Given $e \in E$, the graphs obtained from $G$ by respectively deleting and contracting $e$ are denoted by $G \setminus e$ and $G/e$. A graph is *series-parallel* if and only if it contains no $K_4$ minor [20].

The *circuit cone* $C_{\text{circuit}}(G) = \text{cone}\{\chi^C \text{ for all circuits } C \text{ of } G\}$ is the cone generated by the incidence vectors of the circuits of $G$. Seymour [42] proved
that $C_{\text{circuit}}(G) = \{x \in \mathbb{R}^E : x \ge \mathbf{0}, x(D \setminus e) \ge x_e \text{ for all cuts } D \text{ of } G \text{ and } e \in D\}$.
A function $f : E \to \mathbb{R}$ is *conservative* if $f(C) \ge 0$ for each circuit $C$ of $G$.
These functions form the *cone of conservative functions* $C_{\text{cons}}(G) = \{x \in \mathbb{R}^E : x(C) \ge 0 \text{ for all circuits } C \text{ of } G\}$. By polarity [39, Corollary 29.2h], we have
$C_{\text{cons}}(G) = -C_{\text{circuit}}(G)^* = \text{cone}\{\chi^e \text{ for all } e \in E, \chi^{D\setminus e} - \chi^e \text{ for all cuts } D \text{ of } G \text{ and } e \in D\}$.

We show that box-TDI systems describing $C_{\text{cons}}(G)$ only exist when $G$ is
series-parallel. In this case, we provide such a system in the following propo-
sition.

**Proposition 7** For a graph $G = (V, E)$, the following statements are equiva-
lent.

1. The graph *G* is series-parallel.

2. The cone of conservative functions of G is box-TDI.

3. The system $\frac{1}{2}x(C) \ge 0$ for all circuits $C$ of $G$ is box-TDI.

*Proof.* Since the cone of conservative functions of $G$ is decribed by $\frac{1}{2}x(C) \ge 0$ for all circuits $C$ of $G$, statement 3 implies statement 2.

To prove that statement 1 implies statement 3, suppose that $G$ is series-parallel. Then, [15, Theorem 1] asserts that the system $x \ge \mathbf{0}$, $x(D \setminus e) \ge x(e)$ for all cuts $D$ of $G$ and $e \in C$ is box-TDI. Hence the circuit cone of $G$ is a box-TDI cone. By Lemma 6, $C_{\text{cons}}(G) = -C_{\text{circuit}}(G)^*$ is box-TDI. By Theorem 1, it remains to show that the system $\frac{1}{2}x(C) \ge 0$ for all circuits $C$ of $G$ is TDI. [38, Corollary 22.5a] states that a system $Ax \le 0$ is TDI if and only if the rows of $A$ form a Hilbert basis. In other words, it remains to show that any integer vector $z$ in the circuit cone of $G$ is a nonnegative integer combination of vectors of $\mathcal{H} = \{\frac{1}{2}\chi^C : C \text{ is a circuit of } G\}$. [1, Theorem 1] asserts that, in graphs with no Petersen minors, if $p$ is an integer vector of the circuit cone such that $p(C)$ is even for all cuts $C$ of $G$, then $p$ is a sum of circuits. Since the Petersen graph contains a $K_4$ minor, [1, Theorem 1] applies to $G$. Since $2z$ satisfies the conditions, $2z = \sum_{C \in \mathcal{C}} \chi^C$ for some family $\mathcal{C}$ of circuits of $G$. Therefore, $z = \sum_{C \in \mathcal{C}} \frac{1}{2}\chi^C$.

To prove that statement 2 implies statement 1, we show that if the graph $G$
is not series-parallel, then its cone of conservative functions is not box-TDI. For
$e \in E$, one can see that $C_{\text{cons}}(G \setminus e)$ and $C_{\text{cons}}(G/e)$ are respectively obtained
by deleting $e$'s coordinate in $C_{\text{cons}}(G) \cap \{x_e = +\infty\}$ and $C_{\text{cons}}(G) \cap \{x_e = 0\}$.
Hence, taking minors preserves the box-TDIness of the cone of conservative
functions. It remains to prove that $C_{\text{cons}}(K_4)$ is not box-TDI. Let us apply
Theorem 2.

The nonequimodular matrix $M$ of Figure 4 is the constraint matrix ob-
tained by considering the inequalities associated with the three circuits formed
by the three internal triangles of $K_4$. By Observation 4, $M$ is face-defining
for $C_{\text{cons}}(K_4)$ because $\mathbf{0}$ and the three conservative functions $\chi^4 + \chi^5 - \chi^1$,
$\chi^4 + \chi^6 - \chi^2$ and $\chi^5 + \chi^6 - \chi^3$ are affinely independent, belong to $C_{\text{cons}}(K_4)$ and
satisfy $Mx = \mathbf{0}$. Therefore, by statement 3 of Theorem 2, the cone $C_{\text{cons}}(K_4)$
is not box-TDI.

$\square$
that $C_{\text{circuit}}(G) = \{x \in \mathbb{R}^E : x \ge \mathbf{0}, x(D \setminus e) \ge x_e \text{ for all cuts } D \text{ of } G \text{ and } e \in D\}$.
A function $f : E \to \mathbb{R}$ is *conservative* if $f(C) \ge 0$ for each circuit $C$ of $G$.
These functions form the *cone of conservative functions* $C_{\text{cons}}(G) = \{x \in \mathbb{R}^E : x(C) \ge 0 \text{ for all circuits } C \text{ of } G\}$. By polarity [39, Corollary 29.2h], we have
$C_{\text{cons}}(G) = -C_{\text{circuit}}(G)^* = \text{cone}\{\chi^e \text{ for all } e \in E, \chi^{D\setminus e} - \chi^e \text{ for all cuts } D \text{ of } G \text{ and } e \in D\}$.

We show that box-TDI systems describing $C_{\text{cons}}(G)$ only exist when $G$ is
series-parallel. In this case, we provide such a system in the following propo-
sition.

**Proposition 7** For a graph $G = (V, E)$, the following statements are equiva-
lent.

1. The graph *G* is series-parallel.

2. The cone of conservative functions of G is box-TDI.

3. The system $\frac{1}{2}x(C) \ge 0$ for all circuits $C$ of $G$ is box-TDI.

*Proof.* Since the cone of conservative functions of $G$ is decribed by $\frac{1}{2}x(C) \ge 0$ for all circuits $C$ of $G$, statement 3 implies statement 2.

To prove that statement 1 implies statement 3, suppose that $G$ is series-parallel. Then, [15, Theorem 1] asserts that the system $x \ge \mathbf{0}$, $x(D \setminus e) \ge x(e)$ for all cuts $D$ of $G$ and $e \in C$ is box-TDI. Hence the circuit cone of $G$ is a box-TDI cone. By Lemma 6, $C_{\text{cons}}(G) = -C_{\text{circuit}}(G)^*$ is box-TDI. By Theorem 1, it remains to show that the system $\frac{1}{2}x(C) \ge 0$ for all circuits $C$ of $G$ is TDI. [38, Corollary 22.5a] states that a system $Ax \le 0$ is TDI if and only if the rows of $A$ form a Hilbert basis. In other words, it remains to show that any integer vector $z$ in the circuit cone of $G$ is a nonnegative integer combination of vectors of $\mathcal{H} = \{\frac{1}{2}\chi^C : C \text{ is a circuit of } G\}$. [1, Theorem 1] asserts that, in graphs with no Petersen minors, if $p$ is an integer vector of the circuit cone such that $p(C)$ is even for all cuts $C$ of $G$, then $p$ is a sum of circuits. Since the Petersen graph contains a $K_4$ minor, [1, Theorem 1] applies to $G$. Since $2z$ satisfies the conditions, $2z = \sum_{C \in \mathcal{C}} \chi^C$ for some family $\mathcal{C}$ of circuits of $G$. Therefore, $z = \sum_{C \in \mathcal{C}} \frac{1}{2}\chi^C$.

To prove that statement 2 implies statement 1, we show that if the graph $G$
is not series-parallel, then its cone of conservative functions is not box-TDI. For
$e \in E$, one can see that $C_{\text{cons}}(G \setminus e)$ and $C_{\text{cons}}(G/e)$ are respectively obtained
by deleting $e$'s coordinate in $C_{\text{cons}}(G) \cap \{x_e = +\infty\}$ and $C_{\text{cons}}(G) \cap \{x_e = 0\}$.
Hence, taking minors preserves the box-TDIness of the cone of conservative
functions. It remains to prove that $C_{\text{cons}}(K_4)$ is not box-TDI. Let us apply
Theorem 2.

The nonequimodular matrix $M$ of Figure 4 is the constraint matrix ob-
tained by considering the inequalities associated with the three circuits formed
by the three internal triangles of $K_4$. By Observation 4, $M$ is face-defining
for $C_{\text{cons}}(K_4)$ because $\mathbf{0}$ and the three conservative functions $\chi^4 + \chi^5 - \chi^1$,
$\chi^4 + \chi^6 - \chi^2$ and $\chi^5 + \chi^6 - \chi^3$ are affinely independent, belong to $C_{\text{cons}}(K_4)$ and
satisfy $Mx = \mathbf{0}$. Therefore, by statement 3 of Theorem 2, the cone $C_{\text{cons}}(K_4)$
is not box-TDI.

$\square$
<figure><img src="image_3.png" /><figcaption>Fig. 4 The graph $K_4$ and a face-defining matrix $M$ of $C_{\text{cons}}(K_4)$.</figcaption></figure>

Note that the coefficients of the system in Proposition 7 are half-integral. We leave open the question<fnref n="1" /> of finding a box-TDI system with integer coefficients, which exists by [38, Theorem 22.6(i)] and Theorem 1.

By planar duality, there is a correspondance between the circuits of a planar graph and the bonds of its planar dual. This is used in [15] to obtain the box-TDIness of the standard system describing the cut cone of a series-parallel graph. Applying planar duality to Proposition 7 provides the following: if the graph is series-parallel, then $\frac{1}{2}x(B) \ge 0$ for all bonds $B$ is a box-TDI system describing the polar of the cut cone. This is in fact an equivalence as one can check that the box-TDIness of the corresponding cone is preserved under taking minors and that the matrix of Figure 4 is face-defining when $G = K_4$.

**Acknowledgements** We are grateful to András Sebő for his invaluable comments and suggestions. We also thank the referees for their very careful reading and useful suggestions.

## References

1. B. Alspach, M. Goddyn, and C.-Q. Zhang. Graphs with the circuit cover property. *Transactions of the American Mathematical Society*, 344:131–154, 1994.

2. G. Appa. k-integrality, an extension of total unimodularity. *Operations Research Letters*, 13:159–163, 1993.

3. G. Appa and B. Kotnyek. Rational and integral k-regular matrices. *Discrete Mathematics*, 275(1):1–15, 2004.

4. M. Barbato, R. Grappe, M. Lacroix, E. Lancini, and R. W. Calvo. The schrijver system of the flow cone in series-parallel graphs. *to appear in Discrete Applied Mathematics*.

5. S. Barnett. *Matrices in Control Theory*. R.E. Krieger, 1984.

6. Y. Benchetrit. Integer round-up property for the chromatic number of some h-perfect graphs. *Mathematical Programming*, 164(1):245–262, 2017.

7. J. H. Bevis and F. J. Hall. Some classes of integral matrices. *Linear Algebra and its Applications*, 48:473–483, 1982.

8. K. Cameron. Polyhedral and algorithmic ramifications of antichains. *Ph.D. Thesis*, *University of Waterloo*, 1982.

9. K. Cameron. A min-max relation for the partial q-colourings of a graph. part ii: Box perfection. *Discrete Mathematics*, 74(1):15–27, 1989.

10. P. Camion. Characterization of totally unimodular matrices. *Proceedings of the American Mathematical Society*, 16(5):1068–1073, 1965.

11. X. Chen, Z. Chen, and W. Zang. A unified approach to box-Mengerian hypergraphs. *Mathematics of Operations Research*, 35(3):655–668, 2010.

<footnote n="1">¹ Between the submission and the publication of this paper, the question was answered in [4].</footnote>
<figure><img src="image_4.png" /><figcaption>Fig. 4 The graph $K_4$ and a face-defining matrix $M$ of $C_{\text{cons}}(K_4)$.</figcaption></figure>

Note that the coefficients of the system in Proposition 7 are half-integral. We leave open the question<fnref n="1" /> of finding a box-TDI system with integer coefficients, which exists by [38, Theorem 22.6(i)] and Theorem 1.

By planar duality, there is a correspondance between the circuits of a planar graph and the bonds of its planar dual. This is used in [15] to obtain the box-TDIness of the standard system describing the cut cone of a series-parallel graph. Applying planar duality to Proposition 7 provides the following: if the graph is series-parallel, then $\frac{1}{2}x(B) \ge 0$ for all bonds $B$ is a box-TDI system describing the polar of the cut cone. This is in fact an equivalence as one can check that the box-TDIness of the corresponding cone is preserved under taking minors and that the matrix of Figure 4 is face-defining when $G = K_4$.

**Acknowledgements** We are grateful to András Sebő for his invaluable comments and suggestions. We also thank the referees for their very careful reading and useful suggestions.

## References

1. B. Alspach, M. Goddyn, and C.-Q. Zhang. Graphs with the circuit cover property. *Transactions of the American Mathematical Society*, 344:131–154, 1994.

2. G. Appa. k-integrality, an extension of total unimodularity. *Operations Research Letters*, 13:159–163, 1993.

3. G. Appa and B. Kotnyek. Rational and integral k-regular matrices. *Discrete Mathematics*, 275(1):1–15, 2004.

4. M. Barbato, R. Grappe, M. Lacroix, E. Lancini, and R. W. Calvo. The schrijver system of the flow cone in series-parallel graphs. *to appear in Discrete Applied Mathematics*.

5. S. Barnett. *Matrices in Control Theory*. R.E. Krieger, 1984.

6. Y. Benchetrit. Integer round-up property for the chromatic number of some h-perfect graphs. *Mathematical Programming*, 164(1):245–262, 2017.

7. J. H. Bevis and F. J. Hall. Some classes of integral matrices. *Linear Algebra and its Applications*, 48:473–483, 1982.

8. K. Cameron. Polyhedral and algorithmic ramifications of antichains. *Ph.D. Thesis*, *University of Waterloo*, 1982.

9. K. Cameron. A min-max relation for the partial q-colourings of a graph. part ii: Box perfection. *Discrete Mathematics*, 74(1):15–27, 1989.

10. P. Camion. Characterization of totally unimodular matrices. *Proceedings of the American Mathematical Society*, 16(5):1068–1073, 1965.

11. X. Chen, Z. Chen, and W. Zang. A unified approach to box-Mengerian hypergraphs. *Mathematics of Operations Research*, 35(3):655–668, 2010.

<footnote n="1">¹ Between the submission and the publication of this paper, the question was answered in [4].</footnote>
12. X. Chen, G. Ding, and W. Zang. A characterization of box-Mengerian matroid ports. *Mathematics of Operations Research*, 33(2):497–512, 2008.

13. X. Chen, G. Ding, and W. Zang. The box-TDI system associated with 2-edge connected spanning subgraphs. *Discrete Applied Mathematics*, 157(1):118–125, 2009.

14. W. Cook. On box totally dual integral polyhedra. *Mathematical Programming*, 34(1):48–61, 1986.

15. D. Cornaz, R. Grappe, and M. Lacroix. Trader multiflow and box-TDI systems in series-parallel graphs. *Discrete Optimization*, 31:103–114, 2019.

16. G. Ding, L. Feng, and W. Zang. The complexity of recognizing linear systems with certain integrality properties. *Mathematical Programming*, 114(2):321–334, 2008.

17. G. Ding, L. Tan, and W. Zang. When is the matching polytope box-totally dual integral? *Mathematics of Operations Research*, 43(1):64–99, 2018.

18. G. Ding and W. Zang. Packing cycles in graphs. *Journal of Combinatorial Theory, Series B*, 86(2):381–407, 2002.

19. G. Ding, W. Zang, and Q. Zhao. On box-perfect graphs. *Journal of Combinatorial Theory, Series B*, 128:17–46, 2018.

20. R. Duffin. Topology of series-parallel networks. *Journal of Mathematical Analysis and Applications*, 10(2):303–318, 1965.

21. J. Edmonds. *Submodular Functions, Matroids, and Certain Polyhedra*, pages 11–26. Springer Berlin Heidelberg, Berlin, Heidelberg, 2003.

22. J. Edmonds and R. Giles. Total dual integrality of linear inequality systems. *Progress in combinatorial optimization (Jubilee Conference, University of Waterloo, Waterloo, Ontario, 1982, W. R. Pulleyblank, ed.)*, pages 117–129, 1984.

23. L. R. Ford and D. R. Fulkerson. Maximal flow through a network. *Canadian Journal of Mathematics*, 8:399–404, 1956.

24. A. Gerards and M. Laurent. A characterization of box $\frac{1}{d}$-integral binary clutters. *Journal of Combinatorial Theory, Series B*, 65(2):186–207, 1995.

25. A. Ghouila-Houri. Caractérisation des matrices totalement unimodulaires. *Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences (Paris)*, 254:1192–1194, 1962.

26. D. Gijswijt. Integer decomposition for polyhedra defined by nearly totally unimodular matrices. *SIAM Journal on Discrete Mathematics*, 19(3):798–806, 2005.

27. D. Gijswijt and G. Regts. Polyhedra with the integer Carathéodory property. *Journal of Combinatorial Theory, Series B*, 102(1):62–70, 2012.

28. I. Heller. On linear systems with integral valued solutions. *Pacific Journal of Mathematics*, 7(3):1351–1364, 1957.

29. I. Heller and C. B. Tompkins. An extension of a theorem of dantzig's. In *Linear Inequalities and Related Systems. (AM-38)*, pages 247–254. Princeton University Press, 1956.

30. A. Hoffman and R. Oppenheim. Local unimodularity in the matching polytope. In B. Alspach, P. Hell, and D. Miller, editors, *Algorithmic Aspects of Combinatorics*, volume 2 of *Annals of Discrete Mathematics*, pages 201–209. Elsevier, 1978.

31. A. J. Hoffman and J. B. Kruskal. Integral boundary points of convex polyhedra. In *Linear Inequalities and Related Systems. (AM-38)*, pages 223–246. Princeton University Press, 1956.

32. B. Kotnyek. A generalization of totally unimodular and network matrices. *Ph.D. Thesis*, *London School of Economics*, 2002.

33. J. Lee. Subspaces with well-scaled frames. *Linear Algebra and its Applications*, 114:21–56, 1989.

34. L. Lovász. Normal hypergraphs and the perfect graph conjecture. *Discrete Mathematics*, 306(10-11):867–875, 2006.

35. T. Oda. Problems on Minkowski sums of convex lattice polytopes. *arXiv:0812.1418*, 2008.

36. J. Pap. Recognizing conic TDI systems is hard. *Mathematical Programming*, 128(1-2):43–48, 2011.

37. C. H. Papadimitriou and M. Yannakakis. On recognizing integer polyhedra. *Combinatorica*, 10(1):107–109, 1990.

38. A. Schrijver. *Theory of Linear and Integer Programming*. Wiley-Interscience series in discrete mathematics and optimization. Wiley, 1999.
12. X. Chen, G. Ding, and W. Zang. A characterization of box-Mengerian matroid ports. *Mathematics of Operations Research*, 33(2):497–512, 2008.

13. X. Chen, G. Ding, and W. Zang. The box-TDI system associated with 2-edge connected spanning subgraphs. *Discrete Applied Mathematics*, 157(1):118–125, 2009.

14. W. Cook. On box totally dual integral polyhedra. *Mathematical Programming*, 34(1):48–61, 1986.

15. D. Cornaz, R. Grappe, and M. Lacroix. Trader multiflow and box-TDI systems in series-parallel graphs. *Discrete Optimization*, 31:103–114, 2019.

16. G. Ding, L. Feng, and W. Zang. The complexity of recognizing linear systems with certain integrality properties. *Mathematical Programming*, 114(2):321–334, 2008.

17. G. Ding, L. Tan, and W. Zang. When is the matching polytope box-totally dual integral? *Mathematics of Operations Research*, 43(1):64–99, 2018.

18. G. Ding and W. Zang. Packing cycles in graphs. *Journal of Combinatorial Theory, Series B*, 86(2):381–407, 2002.

19. G. Ding, W. Zang, and Q. Zhao. On box-perfect graphs. *Journal of Combinatorial Theory, Series B*, 128:17–46, 2018.

20. R. Duffin. Topology of series-parallel networks. *Journal of Mathematical Analysis and Applications*, 10(2):303–318, 1965.

21. J. Edmonds. *Submodular Functions, Matroids, and Certain Polyhedra*, pages 11–26. Springer Berlin Heidelberg, Berlin, Heidelberg, 2003.

22. J. Edmonds and R. Giles. Total dual integrality of linear inequality systems. *Progress in combinatorial optimization (Jubilee Conference, University of Waterloo, Waterloo, Ontario, 1982, W. R. Pulleyblank, ed.)*, pages 117–129, 1984.

23. L. R. Ford and D. R. Fulkerson. Maximal flow through a network. *Canadian Journal of Mathematics*, 8:399–404, 1956.

24. A. Gerards and M. Laurent. A characterization of box $\frac{1}{d}$-integral binary clutters. *Journal of Combinatorial Theory, Series B*, 65(2):186–207, 1995.

25. A. Ghouila-Houri. Caractérisation des matrices totalement unimodulaires. *Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences (Paris)*, 254:1192–1194, 1962.

26. D. Gijswijt. Integer decomposition for polyhedra defined by nearly totally unimodular matrices. *SIAM Journal on Discrete Mathematics*, 19(3):798–806, 2005.

27. D. Gijswijt and G. Regts. Polyhedra with the integer Carathéodory property. *Journal of Combinatorial Theory, Series B*, 102(1):62–70, 2012.

28. I. Heller. On linear systems with integral valued solutions. *Pacific Journal of Mathematics*, 7(3):1351–1364, 1957.

29. I. Heller and C. B. Tompkins. An extension of a theorem of dantzig's. In *Linear Inequalities and Related Systems. (AM-38)*, pages 247–254. Princeton University Press, 1956.

30. A. Hoffman and R. Oppenheim. Local unimodularity in the matching polytope. In B. Alspach, P. Hell, and D. Miller, editors, *Algorithmic Aspects of Combinatorics*, volume 2 of *Annals of Discrete Mathematics*, pages 201–209. Elsevier, 1978.

31. A. J. Hoffman and J. B. Kruskal. Integral boundary points of convex polyhedra. In *Linear Inequalities and Related Systems. (AM-38)*, pages 223–246. Princeton University Press, 1956.

32. B. Kotnyek. A generalization of totally unimodular and network matrices. *Ph.D. Thesis*, *London School of Economics*, 2002.

33. J. Lee. Subspaces with well-scaled frames. *Linear Algebra and its Applications*, 114:21–56, 1989.

34. L. Lovász. Normal hypergraphs and the perfect graph conjecture. *Discrete Mathematics*, 306(10-11):867–875, 2006.

35. T. Oda. Problems on Minkowski sums of convex lattice polytopes. *arXiv:0812.1418*, 2008.

36. J. Pap. Recognizing conic TDI systems is hard. *Mathematical Programming*, 128(1-2):43–48, 2011.

37. C. H. Papadimitriou and M. Yannakakis. On recognizing integer polyhedra. *Combinatorica*, 10(1):107–109, 1990.

38. A. Schrijver. *Theory of Linear and Integer Programming*. Wiley-Interscience series in discrete mathematics and optimization. Wiley, 1999.
39. A. Schrijver. *Combinatorial Optimization: Polyhedra and Efficiency*. Algorithms and combinatorics. Springer-Verlag, Berlin, Heidelberg, New York, N.Y., et al., 2003.

40. A. Sebő. Path partitions, cycle covers and integer decomposition. In M. Lipshteyn, V. E. Levit, and R. M. McConnell, editors, *Graph Theory, Computational Intelligence and Thought: Essays Dedicated to Martin Charles Golumbic on the Occasion of His 60th Birthday*, pages 183–199. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009.

41. P. Seymour. The matroids with the max-flow min-cut property. *Journal of Combinatorial Theory, Series B*, 23(2):189–222, 1977.

42. P. Seymour. Sums of circuits. *Graph Theory and Related Topics (Proceedings Conference, Waterloo, Ontario, 1977; J.A. Bondy, U.S.R. Murty)*, 1:341–355, 1979.

43. H. J. S. Smith. On systems of linear indeterminate equations and congruences. *Philosophical Transactions of the Royal Society of London*, 151:293–326, 1861.

44. K. Truemper and R. Chandrasekaran. Local unimodularity of matrix-vector pairs. *Linear Algebra and its Applications*, 22:65–78, 1978.

45. A. F. J. Veinott and G. B. Dantzig. Integral extreme points. *SIAM Review*, 10(3):371–372, 1968.

46. G. Zambelli. Colorings of k-balanced matrices and integer decomposition property of related polyhedra. *Operations Research Letters*, 35(3):353–356, 2007.
39. A. Schrijver. *Combinatorial Optimization: Polyhedra and Efficiency*. Algorithms and combinatorics. Springer-Verlag, Berlin, Heidelberg, New York, N.Y., et al., 2003.

40. A. Sebő. Path partitions, cycle covers and integer decomposition. In M. Lipshteyn, V. E. Levit, and R. M. McConnell, editors, *Graph Theory, Computational Intelligence and Thought: Essays Dedicated to Martin Charles Golumbic on the Occasion of His 60th Birthday*, pages 183–199. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009.

41. P. Seymour. The matroids with the max-flow min-cut property. *Journal of Combinatorial Theory, Series B*, 23(2):189–222, 1977.

42. P. Seymour. Sums of circuits. *Graph Theory and Related Topics (Proceedings Conference, Waterloo, Ontario, 1977; J.A. Bondy, U.S.R. Murty)*, 1:341–355, 1979.

43. H. J. S. Smith. On systems of linear indeterminate equations and congruences. *Philosophical Transactions of the Royal Society of London*, 151:293–326, 1861.

44. K. Truemper and R. Chandrasekaran. Local unimodularity of matrix-vector pairs. *Linear Algebra and its Applications*, 22:65–78, 1978.

45. A. F. J. Veinott and G. B. Dantzig. Integral extreme points. *SIAM Review*, 10(3):371–372, 1968.

46. G. Zambelli. Colorings of k-balanced matrices and integer decomposition property of related polyhedra. *Operations Research Letters*, 35(3):353–356, 2007.