Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces

Introduction

The Isolation Lemma by Mulmuley, Vazirani, and Vazirani states that for any given family of subsets of a ground set $E$, if we assign random weights (bounded in magnitude by poly($\lvert E\rvert$)) to the elements of $E$ then, with high probability, the minimum weight set in the family is unique. Such a weight assignment is called an isolating weight assignment. The lemma was introduced in the context of randomized parallel algorithms for the matching problem. Since then it has found numerous other applications, in both algorithms and complexity: e.g., a reduction from CLIQUE to UNIQUE-CLIQUE , NL/poly $\subseteq\oplus$L/poly , NL/poly $=$ UL/poly , an RNC-algorithm for linear matroid intersection , and an RP-algorithm for disjoint paths . In all of these results, the Isolation Lemma is the only place where they need randomness. Thus, if the Isolation Lemma can be derandomized, i.e., if a polynomially bounded isolating weight assignment can be deterministically constructed, then the aforementioned results that rely on it can also be derandomized. In particular, it will give a deterministic parallel algorithm for matching.

A simple counting argument shows that a single weight assignment with polynomially bounded weights cannot be isolating for all possible families of subsets of $E$. We can relax the question and ask if we can construct a poly-size list of poly-bounded weight assignments such that for each family $\mathcal{B}\subseteq 2^{E}$, one of the weight assignments in the list is isolating. Unfortunately, even this can be shown to be impossible via arguments involving the polynomial identity testing (PIT) problem. The PIT problem asks if an implicitly given multivariate polynomial is identically zero. Derandomization of PIT is another important consequence of derandomizing the Isolation Lemma. Here, the Isolation Lemma is applied to the family of monomials present in the polynomial. In essence, if we have a small list of weight assignments that works for all families, then we will have a small hitting-set for all small degree polynomials, which is impossible (see ). Once we know that a deterministic isolation is not possible for all families, a natural question is to solve the isolation question for families $\mathcal{B}$, that have a succinct representation, for example, the family of perfect matchings of a graph.

For the general setting of families with succinct representations, no deterministic isolation is known, other than the trivial construction with exponentially large weights. In fact, derandomizing the isolation lemma in this setting will imply circuit lower bounds . Efficient deterministic isolation is known only for very special kinds of families, for example, perfect matchings in some special classes of graphs , $s$-$t$ paths in directed graphs . Recently, there has been significant progress on deterministic isolation for perfect matchings in bipartite graphs and subsequently, in general graphs , and matroid intersection , which implied quasi-NC algorithms for these problems.

A large variety of polytopes satisfy this property and, as a consequence, have been extensively studied in combinatorial optimization. The simplest such class is when the polytope $P(\mathcal{B})$ has a description $Ax\leq b$ with $A$ being a TU matrix. Thus, a simple consequence of our main result is a resolution to the problem of derandomizing the isolation lemma for polytopes with TU constraints, as raised in a recent work . This generalizes the isolation result for perfect matchings in a bipartite graph , since the perfect matching polytope of a bipartite graph can be described by the incidence matrix of the graph, which is TU. Other examples of families whose polytopes are defined by TU constraints are vertex covers of a bipartite graph, independent sets of a bipartite graph, and, edge covers of a bipartite graph. Note that these three problems are computationally equivalent to bipartite matching and thus, already have quasi-NC algorithms due to . However, the isolation results for these families are not directly implied by isolation for bipartite matchings.

Our work also generalizes the isolation result for the family of common bases of two matroids . In the matroid intersection problem, the constraints of the common base polytope are a rank bound on every subset of the ground set. These constraints, in general, do not form a TUM. However, for every face of the polytope there exist two laminar families of subsets that form a basis for the tight constraints of the face. The incidence matrix for the union of two laminar families is TU (see [22, Theorem 41.11]).

Since our condition on the polytope $P(\mathcal{B})$ does not require the constraint matrix defining the polytope itself (or any of its faces) to be TU, it is quite weak and is also well studied. Schrijver [21, Theorem 5.35] shows that this condition is sufficient to prove that the polytope is box-totally dual integral. The second volume of Schrijver’s book gives an excellent overview of polytopes that satisfy the condition required in theorem 2.3 such as

$R-S$ bibranching polytope [22, Section 54.6]

directed cut cover polytope [22, Section 55.2]

submodular flow polyhedron [22, Theorem 60.1]

submodular base polytope [22, Section 44.3]

many other polytopes defined via submodular and supermodular set functions [22, Sections 46.1, 48.1, 48.23, 46.13, 46.28, 46.29, 49.3, 49.12, 49.33, 49.39, 49.53].

We would like to point out that it is not clear if our isolation results in the above settings lead to any new derandomization of algorithms. Finding such algorithmic applications of our isolation result would be quite interesting.

The above lattice result is in contrast to general lattices where the number of such near-shortest vectors could be exponential in the dimension.

Our result on lattices can be reformulated using the language of matroid theory: the number of near-shortest circuits in a regular matroid is polynomially bounded; see theorem 2.6. In fact, we show how theorem 2.5 can be deduced from theorem 2.6. One crucial ingredient in the proof of theorem 2.6 is Seymour’s remarkable decomposition theorem for regular matroids . theorem 2.6 answers a question raised by Subramanian and is a generalization of (and builds on) known results in the case of graphic and cographic matroids, that is, the number of near-minimum length cycles in a graph is polynomially bounded (see ) and the result of Karger that states that the number of near-mincuts in a graph is polynomially bounded.

Thus, not only do our results make progress in derandomizing the isolation lemma for combinatorial polytopes, they make interesting connections between lattices (that are geometric objects) and combinatorial polytopes. Our structural results about the number of near-shortest vectors in lattices and near-shortest circuits in matroids should be of independent interest and raise the question: to what extent are they generalizable?

A natural conjecture would be that for any $(0,1)$-matrix, the lattice formed by its integral null vectors has a small number of near-shortest vectors. In turn, this would give us the isolation result for any polytope which is defined by a $(0,1)$-constraint matrix. Many combinatorial polytopes have this property. One such interesting example is the perfect matchings polytope for general graphs. The recent result of , which showed a quasi-NC algorithm for perfect matchings, does not actually go via a bound on the number of near-shortest vectors in the associated lattice. Obtaining a polynomial bound on this number would give a proof for their quasi-NC result in our unified framework and with improved parameters. Another possible generalization is for $(0,1)$-polytopes that have this property that the integers occurring in the description of each supporting hyperplane are bounded by a polynomial in the dimension of the polytope. Such polytopes generalize almost all combinatorial polytopes and yet seem to have enough structure – they have been recently studied in the context of optimization .

Our Results

Let $E$ be a set, $\lvert E\rvert=m$, and let $w\colon E\to\{1,2,\dots,2m\}$ be a random weight function, where for each $e\in E$, the weight $w(e)$ is chosen uniformly and independently at random. Then for any family $\mathcal{B}\subseteq 2^{E}$, $w$ is isolating with probability at least $\nicefrac{{1}}{{2}}$.

The task of derandomizing the Isolation Lemma requires the deterministic construction of an isolating weight function with weights polynomially bounded in $m=\lvert E\rvert$. Here, we view the isolation question for $\mathcal{B}$ as an isolation over a corresponding polytope $P(\mathcal{B})$, as follows. For a set $S\subseteq E$, its indicator vector $x^{S}:=(x^{S}_{e})_{e\in E}$ is defined as

Note that $P(\mathcal{B})$ is contained in the $m$-dimensional unit hypercube.

Our main theorem gives an efficient quasi-polynomial isolation for a family $\mathcal{B}$ when each face of the polytope $P(\mathcal{B})$ lies in the affine space defined by a TU matrix.

2 Short vectors in lattices associated to polytopes

Our starting point towards proving theorem 2.3 is a reformulation of the isolation approach for bipartite perfect matching and matroid intersection . For a set $E$ and a family $\mathcal{B}\subseteq 2^{E}$, we define a lattice corresponding to each face of the polytope $P(\mathcal{B})$. The isolation approach works when this lattice has a small number of near-shortest vectors. For any face $F$ of $P(\mathcal{B})$, consider the lattice of all integral vectors parallel to $F$,

The length of the shortest nonzero vector of a lattice $L$ is denoted by

Let $E$ be a set with $|E|=m$ and let $\mathcal{B}\subseteq 2^{E}$ be a family such that there exists a constant $c>1$, such that for any face $F$ of polytope $P(\mathcal{B})$, we have

Then one can construct a set of $m^{O(\log m)}$ weight functions with weights bounded by $m^{O(\log m)}$ such that at least one of them is isolating for $\mathcal{B}$.

The main ingredient of the proof of theorem 2.3 is to show that the hypothesis of theorem 2.4 is true when the lattice $L_{F}$ is the set of all integral vectors in the nullspace of a TU matrix. For any $n\times m$ matrix $A$ we define a lattice:

For an $n\times m$ TU matrix $A$, let $\lambda:=\lambda(L(A))$. Then

Let $F$ be a face of the polytope $P(\mathcal{B})$ and let $A_{F}$ be the TU matrix associated with $F$. Thus $A_{F}x=b_{F}$ defines the affine span of $F$. In other words, the set of vectors parallel to $F$ is precisely the solution set of $A_{F}x=0$ and the lattice $L_{F}$ is given by $L(A_{F})$. theorem 2.5 implies the hypothesis of theorem 2.4 for any $L_{F}=L(A_{F})$, when the matrix $A_{F}$ is TU. ∎

3 Near-shortest circuits in regular matroids

The proof of theorem 2.5 is combinatorial and uses the language and results from matroid theory. We refer the reader to Section 6 for preliminaries on matroids; here we just recall a few basic definitions. A matroid is said to be represented by a matrix $A$, if its ground set is the column set of $A$ and its independent sets are the sets of linearly independent columns of $A$. A matroid represented by a TU matrix is said to be a regular matroid. A circuit of a matroid is a minimal dependent set. The following is one of our main results which gives a bound on the number of near-shortest circuits in a regular matroid, which, in turn, implies theorem 2.5. Instead of the circuit size, we consider the weight of a circuit and present a more general result.

An extension of this result would be to give a polynomial bound on the number of circuits of weight at most $\alpha r$ for any constant $\alpha$. Our current proof technique does not extend to this setting.

Isolation via the Polytope Lattices: Proof of theorem 2.4

The following claim asserts that if we modify the current weight function on a small scale, then the new minimizing face will be a subset of the current minimizing face. In the following, we will denote the size of the set $E$ by $m$.

Consider any vertex $x\in F^{\prime}$. We show that $x\in F$. By definition of $F^{\prime}$, for any vertex $y\in P(\mathcal{B})$ we have

Since $x$ and $y$ are vertices of $\mathcal{P}(\mathcal{B})$, we have $x,y\in\{0,1\}^{m}$. Thus, $\lvert\langle w^{\prime},x-y\rangle\rvert<mN.$ On the other hand, if $\lvert\langle mN\,w,x-y\rangle\rvert$ is nonzero then it is at least $mN$ and thus dominates $\lvert\langle w^{\prime},x-y\rangle\rvert$. Hence, for (1) to hold, it must be that

It follows that $\langle w,x\rangle\leq\langle w,y\rangle$, and therefore $x\in F$. ∎

Let $F$ be the face of $P(\mathcal{B})$ minimizing $\langle w,x\rangle$ and let $v\in L_{F}$. Then $\langle w,v\rangle=0$.

Now, let $F_{0}$ be the face that minimizes the current weight function $w_{0}$. Let $v$ be in $L_{F_{0}}$. Choose a new weight function $w^{\prime}\in\{0,1,\dots,N-1\}^{E}$ such that $\langle w^{\prime},v\rangle\neq 0.$ Let $w_{1}:=mN\,w_{0}+w^{\prime}$ and let $F_{1}$ be the face that minimizes $w_{1}$. Clearly, $\langle w_{1},v\rangle\neq 0$ and thus, by 3.2, $v\not\in L_{F_{1}}$. This implies that $F_{1}$ is strictly contained in $F_{0}$. To ensure that $F_{1}$ is significantly smaller than $F_{0}$, we choose many vectors in $L_{F_{0}}$, say $v_{1},v_{2},\dots,v_{k}$, and construct a weight vector $w^{\prime}$ such that for all $i\in[k]$, we have $\langle w^{\prime},v_{i}\rangle\neq 0$. The following well-known lemma actually constructs a list of weight vectors such that one of them has the desired property (see [9, Lemma 2]).

First define $w:=(1,t,t^{2},\dots,t^{m-1})$. Clearly, $\langle w,v_{i}\rangle\neq 0$ for each $i$, because each coordinate of $v_{i}$ is less than $t$ in absolute value. To get a weight vector with small coordinates, we go modulo small numbers. We consider the following weight vectors $w_{j}$ for $1\leq j\leq q$:

We claim that this set of weight vectors has the desired property. We know that

Note that the product $W$ is bounded by $t^{mk}$. On the other hand, it is known that $\lcm(2,3,\dots,q)>2^{q}=t^{mk}$ for all $q\geq 7$ . Thus, there must exist a $2\leq j\leq q$ such that $j$ does not divide $W$. In other words, for all $i\in[k]$

There are two things to note about this lemma: (i) It is black-box in the sense that we do not need to know the set of vectors $\{v_{1},v_{2},\dots,v_{k}\}$. (ii) We do not know a priori which function will work in the given set of functions. So, one has to try all possibilities.

The lemma tells us that we can ensure that $\langle w^{\prime},v\rangle\neq 0$ for polynomially many vectors $v$ whose coordinates are polynomially bounded. Below, we formally present the weight construction.

the face of $P(\mathcal{B})$ minimizing $w_{i-1}$

a weight vector in $\{0,1,\dots,N-1\}^{E}$ such that $\langle w^{\prime}_{i},v\rangle\neq 0$ for all nonzero $v\in L_{F_{i-1}}$ with $\left\lVert v\right\rVert<c^{i+1}$.

Observe that $F_{i}\subseteq F_{i-1}$, for each $i$ by 3.1. Hence, also for the associated lattices we have $L_{F_{i}}\subseteq L_{F_{i-1}}$. As we show in the next claim, the choice of $w^{\prime}_{i}$ together with 3.2 ensures that there are no vectors in $L_{F_{i}}$ with norm less than $c^{i+1}$.

For $i=0,1,2,\dots,p$, we have $\lambda(L_{F_{i}})\geq c^{i+1}$.

Consider a nonzero vector $v\in L_{F_{i}}$. By 3.2, we have

Since $v$ is in $L_{F_{i}}$, it is also in $L_{F_{i-1}}$ and again by 3.2, we have $\langle w_{i-1},v\rangle=0$. Together with (2) we conclude that $\langle w^{\prime}_{i},v\rangle=0.$ By the definition of $w^{\prime}_{i}$, this implies that $\left\lVert v\right\rVert\geq c^{i+1}$. ∎

Finally we argue that $w_{p}$ is isolating.

Let $y_{1},y_{2}\in F_{p}$ be vertices and thus belong to $\{0,1\}^{m}$. Then $y_{1}-y_{2}\in L_{F_{p}}$ and $\left\lVert y_{1}-y_{2}\right\rVert\leq m<c^{p+1}$. By 3.4, we have that $y_{1}-y_{2}$ must be zero, i.e., $y_{1}=y_{2}$. ∎

The following claim, which gives bounds on the number of weight vectors we need to try and the weights involved, finishes the proof of theorem 2.4.

The number of possible choices for $w_{p}$ such that one of them is isolating for $\mathcal{B}$ is $m^{O(\log m)}$. The weights in each such weight vector are bounded by $m^{O(\log m)}$.

To bound the weights of $w_{p}$, we bound $w^{\prime}_{i}$ for each $i$. By 3.4, we have $\lambda(L_{F_{i-1}})\geq c^{i}$, for each $1\leq i\leq p$. The hypothesis of theorem 2.4 implies

Recall that we have to ensure $\langle w^{\prime}_{i},v\rangle\neq 0$ for all nonzero vectors $v$ in the above set. We apply lemma 3.3 with $k=m^{O(1)}$. For parameter $t$, note that as $\left\lVert v\right\rVert<c^{i+1}\leq c^{p+1}\leq c(m+1)$, each coordinate of $v$ is less than $c(m+1)$ and therefore $t\leq c(m+1)$. Thus, we get $w^{\prime}_{i}$ with weights bounded by $m^{O(1)}$. Therefore the weights in $w_{p}$ are bounded by $m^{O(p)}=m^{O(\log m)}$.

Recall that lemma 3.3 actually gives a set of $m^{O(1)}$ weight vectors for possible choices of $w^{\prime}_{i}$ and one of them has the desired property. Thus, we try all possible combinations for each $w^{\prime}_{i}$. This gives us a set of $m^{O(\log m)}$ possible choices for $w_{p}$ such that one of them is isolating for $\mathcal{B}$. ∎

Number of Short Vectors in Lattices: Proof of theorem 2.5

In this section, we show that theorem 2.5 follows from theorem 2.6. We define a circuit of a matrix and show that to prove theorem 2.5, it is sufficient to upper bound the number of near-shortest circuits of a TU matrix. We argue that this, in turn, is implied by a bound on the number of near-shortest circuits of a regular matroid. Just as a circuit of a matroid is a minimal dependent set, a circuit of matrix is a minimal linear dependency among its columns. Recall that for an $n\times m$ matrix $A$, the lattice $L(A)$ is defined as the set of integer vectors in its kernel,

For an $n\times m$ matrix $A$, a vector $u\in L(A)$ is a circuit of $A$ if

Note that if $u$ is a circuit of $A$, then so is $-u$. The following property of the circuits of a TU matrix is well known (see [17, Lemma 3.18]).

Let $A$ be a TU matrix. Then every circuit of $A$ has its coordinates in $\{-1,0,1\}$.

Now, we define a notion of conformality among two vectors.

For vectors $u$ and $v$ with $u\sqsubseteq v$, we have $\left\lVert v-u\right\rVert=\left\lVert v\right\rVert-\left\lVert u\right\rVert$.

The following lemma follows from [17, Lemma 3.19].

Let $A$ be a TU matrix. Then for any nonzero vector $v\in L(A)$, there is a circuit $u$ of $A$ that is conformal to $v$.

We use the lemma to argue that any small enough vector in $L(A)$ must be a circuit.

Let $A$ be a TU matrix and let $\lambda:=\lambda(L(A))$. Then any nonzero vector $v\in L(A)$ with $\left\lVert v\right\rVert<2\lambda$ is a circuit of $A$.

Suppose $v\in L(A)$ is not a circuit of $A$. We show that $\left\lVert v\right\rVert\geq 2\lambda$. By lemma 4.5, there is a circuit $u$ of $A$ with $u\sqsubseteq v$. Since $v$ is not a circuit, $v-u\neq 0$. Since both $u$ and $v-u$ are nonzero vectors in $L(A)$, we have $\left\lVert u\right\rVert,\left\lVert v-u\right\rVert\geq\lambda$. By 4.4, we have $\left\lVert v\right\rVert=\left\lVert v-u\right\rVert+\left\lVert u\right\rVert$ and thus, we get that $\left\lVert v\right\rVert\geq 2\lambda$. ∎

Recall that a matroid represented by a TU matrix is a regular matroid (see theorem 6.3). The following lemma shows that the two definitions of circuits, 1) for TU matrices and 2) for regular matroids, coincide.

Let $M=(E,\mathcal{I})$ be a regular matroid, represented by a TU matrix $A$. Then there is a one to one correspondence between the circuits of $M$ and the circuits of $A$ (up to change of sign).

In the other direction, a circuit $C\subseteq E$ of matroid $M$ is a minimal dependent set. Thus, the set of columns of $A$ corresponding to $C$ is minimally linear dependent. Hence, there are precisely two circuits $u,-u\in L(A)$ with their support being $C$. ∎

Proof Overview of theorem 2.6

theorem 2.6 states that for a regular matroid, the number of near-shortest circuits – circuits whose size is at most 3/2 of the shortest circuit size – is polynomially bounded. The starting point of the proof of this theorem is a remarkable result of Seymour which showed that every regular matroid can be decomposed into a set of much simpler matroids. Each of these building blocks for regular matroids either belongs to the classes of graphic and cographic matroids – the simplest and well-known examples of regular matroids, or is a special 10-element matroid $R_{10}$ (see Section 6 for the definitions). One important consequence of Seymour’s result is a polynomial time algorithm, the only one known, for testing the total unimodularity of a matrix; see (recall that a TU matrix represents a regular matroid). Our strategy is to leverage Seymour’s decomposition theorem in order to bound the number of circuits in a regular matroid.

Seymour’s decomposition involves a sequence of binary operations on matroids, each of which is either a $1$-sum, a $2$-sum or a $3$-sum. Formally, it states that for every regular matroid $M$, we can build a decomposition tree – which is a binary rooted tree – in which the root node is the matroid $M$, every node is a $k$-sum of its two children for $k=1,2$, or $3$, and at the bottom we have graphic, cographic and the $R_{10}$ matroids as the leaf nodes. Note that the tree, in general, is not necessarily balanced and can have large depth (linear in the ground set size).

This suggests that to bound the number of near-shortest circuits in a regular matroid, perhaps one can use the tree structure of its decomposition, starting from the leaf nodes and arguing, inductively, all the way up to the root. It is known that the number of near-shortest circuits in graphic and cographic matroids is polynomially bounded. This follows from the polynomial bounds on the number of near-shortest cycles of a graph and on the number of near min-cuts in a graph (theorem 6.8). The challenge is to show how to combine the information at an internal node.

The $k$-sum $M$ of two matroids $M_{1}$ and $M_{2}$ is defined in a way such that each circuit of $M$ can be built from a combination of two circuits, one from $M_{1}$ and another from $M_{2}$. Thus, if we have upper bounds for the number of circuits in $M_{1}$ and $M_{2}$, their product will give a naive upper bound for number of circuits in $M$. Since there can be many $k$-sum operations involved, the naive product bound can quickly explode. Hence, to keep a polynomial bound we need to take a closer look at the $k$-sum operations.

kk-sum operations

A $1$-sum $M$ of two matroids $M_{1}$ and $M_{2}$ is simply their direct sum. That is, the ground set of $M$ is the disjoint union of the ground sets of $M_{1}$ and $M_{2}$, and any circuit of $M$ is either a circuit of $M_{1}$ or a circuit of $M_{2}$.

The $2$-sum and $3$-sum are a bit more intricate. It is known that the set of circuits of a matroid completely characterizes the matroid. The $2$-sum and $3$-sum operations are defined by describing the set of circuits of the matroid obtained by the sum. To get an intuition for the $2$-sum operation, we first describe it on two graphic matroids. A graphic matroid is defined with respect to a graph, where a circuit is a simple cycle in the graph.

For two graphs $G_{1}$ and $G_{2}$, their $2$-sum $G=G_{1}\oplus_{2}G_{2}$ is any graph obtained by identifying an edge $(u_{1},v_{1})$ in $G_{1}$ with an edge $(u_{2},v_{2})$ in $G_{2}$, that is, identifying $u_{1}$ with $u_{2}$ and $v_{1}$ with $v_{2}$ and then, deleting the edge $(u_{1},v_{1})=(u_{2},v_{2})$. It would be instructive to see how a cycle in $G$, i.e., a circuit of the associated graphic matroid, looks like. A cycle in $G$ is either a cycle in $G_{1}$ or in $G_{2}$ that avoids the edge $(u_{1},v_{1})=(u_{2},v_{2})$, or it is a union of a path $u_{1}\rightsquigarrow v_{1}$ in $G_{1}$ and a path $v_{2}\rightsquigarrow u_{2}$ in $G_{2}$. This last possibility is equivalent to taking a symmetric difference $C_{1}\triangle C_{2}$ of two cycles $C_{1}$ in $G_{1}$ and $C_{2}$ in $G_{2}$ such that $C_{1}$ passes through $(u_{1},v_{1})$ and $C_{2}$ passes through $(u_{2},v_{2})$.

The $2$-sum $M_{1}\oplus_{2}M_{2}$ of two matroids $M_{1}$ and $M_{2}$ is defined analogously. The grounds sets of $M_{1}$ and $M_{2}$, say $E_{1}$ and $E_{2}$ respectively, have an element in common, say $e$ (this can be achieved by identifying an element from $E_{1}$ with an element from $E_{2}$). The sum $M_{1}\oplus_{2}M_{2}$ is defined on the ground set $E=E_{1}\Delta E_{2}$, the symmetric difference of the two given ground sets. Any circuit of the sum $M_{1}\oplus_{2}M_{2}$ is either a circuit in $M_{1}$ or in $M_{2}$ that avoids the common element $e$, or it is the symmetric difference $C_{1}\triangle C_{2}$ of two circuits $C_{1}$ and $C_{2}$ of $M_{1}$ and $M_{2}$, respectively, such that both $C_{1}$ and $C_{2}$ contain the common element $e$.

A $3$-sum is defined similarly. A matroid $M$ is a $3$-sum of two matroids $M_{1}$ and $M_{2}$ if their ground sets $E_{1}$ and $E_{2}$ have a set $S$ of three elements in common such that $S$ is a circuit in both the matroids and the ground set of $M$ is the symmetric difference $E_{1}\triangle E_{2}$. Moreover, a circuit of $M$ is either a circuit in $M_{1}$ or in $M_{2}$ that avoids the common elements $S$, or it is the symmetric difference $C_{1}\triangle C_{2}$ of two circuits $C_{1}$ and $C_{2}$ of $M_{1}$ and $M_{2}$, respectively, such that both $C_{1}$ and $C_{2}$ contain a common element $e$ from $S$ and no other element from $S$.

The inductive bound on the number of circuits

Our proof is by a strong induction on the ground set size.

For a graphic or cographic matroid with a ground set of size $m$, if its shortest circuit has size $r$ then the number of its circuits of size less than $\alpha r$ is at most $m^{4\alpha}$. For the $R_{10}$ matroid, we present a constant upper bound on the number of circuits.

For any regular matroid with a ground set of size $m<m_{0}$, if its shortest circuit has size $r$, then the number of its circuits of size less than $\alpha r$ is bounded by ${m}^{c\alpha}$ for some sufficiently large constant $c$.

We prove the induction hypothesis for a regular matroid $M$ with a ground set of size $m_{0}$. Let the minimum size of a circuit in $M$ be $r$. We want to show a bound of $m_{0}^{c\alpha}$ on the number of circuits in $M$ of size less than $\alpha r$. The main strategy here is as follows: by Seymour’s Theorem, we can write $M$ as a $k$-sum of two smaller regular matroids $M_{1}$ and $M_{2}$, with ground sets of size $m_{1}<m_{0}$ and $m_{2}<m_{0}$ respectively. As the circuits of $M$ can be written as a symmetric differences of circuits of $M_{1}$ and $M_{2}$, we derive an upper bound on the number circuits of $M$ from the corresponding bounds for $M_{1}$ and $M_{2}$, which we get from the induction hypothesis.

The $1$-sum case. In this case, any circuit of $M$ is either a circuit of $M_{1}$ or a circuit of $M_{2}$. Hence, the number of circuits in $M$ of size less than $\alpha r$ is simply the sum of the number of circuits in $M_{1}$ and $M_{2}$ of size less than $\alpha r$. Using the induction hypothesis, this sum is bounded by $m_{1}^{c\alpha}+m_{2}^{c\alpha}$, which is less than $m_{0}^{c\alpha}$ since $m_{0}=m_{1}+m_{2}$.

The $2$-sum and $3$-sum cases. Let the set of common elements in the ground sets of $M_{1}$ and $M_{2}$ be $S$. Note that $m_{0}=m_{1}+m_{2}-\lvert S\rvert$. Recall from the definition of a $k$-sum that any circuit $C$ of $M$ is of the form $C_{1}\triangle C_{2}$, where $C_{1}$ and $C_{2}$ are circuits in $M_{1}$ and $M_{2}$ respectively, such that either (i) one of them, say $C_{1}$, has no element from $S$ and the other one $C_{2}$ is empty or (ii) they both contain exactly one common element from $S$. We will refer to $C_{1}$ and $C_{2}$ as projections of $C$. Note that $\lvert C_{1}\rvert,\lvert C_{2}\rvert\leq\lvert C\rvert$. In particular, if circuit $C$ is of size less than $\alpha r$, then so are its projections $C_{1}$ and $C_{2}$.

An obstacle. The first step would be to bound the number of circuits $C_{1}$ of $M_{1}$ and $C_{2}$ of $M_{2}$ using the induction hypothesis. However, we do not have a lower bound on the minimum size of a circuit in $M_{1}$ or $M_{2}$, which is required to use the induction hypothesis. What we do know is that any circuit in $M_{1}$ or $M_{2}$ that does not involve elements from $S$ is also a circuit of $M$, and thus, must have size at least $r$. However, a circuit that involves elements from $S$ could be arbitrarily small. We give different solutions for this obstacle in case (i) and case (ii) mentioned above.

Case (i): deleting elements in $S$. Let us first consider the circuits $C_{1}$ of $M_{1}$ that do not involve elements from $S$. These circuits can be viewed as circuits of a new regular matroid $M_{1}\setminus S$ obtained by deleting the elements in $S$ from $M_{1}$. Since we know that the minimum size of a circuit in $M_{1}\setminus S$ is $r$, we can apply the induction hypothesis to get a bound of $(m_{1}-\lvert S\rvert)^{c\alpha}$ for the number of circuits $C_{1}$ of $M_{1}\setminus S$ of size less than $\alpha r$. Summing this with a corresponding bound for $M_{2}\setminus S$ gives us a bound less than $m_{0}^{c\alpha}$ for the number of circuits of $M$ in case (i).

Case (ii): stronger induction hypothesis. The case when circuits $C_{1}$ and $C_{2}$ contain an element from $S$ turns out to be much harder. For this case, we actually need to strengthen our induction hypothesis. Let us assume that for a regular matroid of ground set size $m<m_{0}$, if the minimum size of a circuit that avoids a given element $\widetilde{e}$ is $r$, then the number of circuits containing $\widetilde{e}$ and of size less than $\alpha r$ is bounded by $m^{c\alpha}$. This statement will also be proved by induction, but we will come to its proof later.

Since we know that any circuit in $M_{1}$ (or $M_{2}$) that avoids elements from $S$ has size at least $r$, we can use the above stronger inductive hypothesis to get a bound of $m_{1}^{c\alpha}$ on the number of circuits $C_{1}$ in $M_{1}$ containing a given element from $S$ and of size less than $\alpha r$. Similarly, we get an analogous bound of $m_{2}^{c\alpha}$ for circuits $C_{2}$ of $M_{2}$. Since $C$ can be a symmetric difference of any $C_{1}$ and $C_{2}$, the product of these two bounds, that is, $(m_{1}m_{2})^{c\alpha}$ bounds the number of circuits $C$ of $M$ of size less than $\alpha r$. Unfortunately, this product can be much larger than $m_{0}^{c\alpha}$. Note that this product bound on the number of circuits $C$ is not really tight since $C_{1}$ and $C_{2}$ both cannot have their sizes close to $\alpha r$ simultaneously. This is because $C=C_{1}\triangle C_{2}$ and thus, $\lvert C\rvert=\lvert C_{1}\rvert+\lvert C_{2}\rvert-1$. Hence, a better approach is to consider different cases based on the sizes of $C_{1}$ and $C_{2}$.

Number of circuits $C$ when one of its projections is small. We first consider the case when the size of $C_{1}$ is very small, i.e., close to zero. In this case, the size of $C_{2}$ will be close to $\alpha r$ and we have to take the bound of $m_{2}^{c\alpha}$ on the number of such circuits $C_{2}$. Now, if number of circuits $C_{1}$ with small size is $N$ then we get a bound of $Nm_{2}^{c\alpha}$ on the number of circuits $C$ of $M$ of this case. Note that $Nm_{2}^{c\alpha}$ is dominated by $m_{0}^{c\alpha}$ only when $N\leq 1$, as $m_{2}$ can be comparable to $m$. While $N\leq 1$ does not always hold, we show something weaker which is true.

Uniqueness of $C_{1}$. We can show that for any element $s$ in the set of common elements $S$, there is at most one circuit $C_{1}$ of size less than $r/2$ that contains $s$ and no other element from $S$. To see this, assume that there are two such circuits $C_{1}$ and $C^{\prime}_{1}$. It is known that the symmetric difference of two circuits of a matroid is a disjoint union of some circuits of the matroid. Thus, $C_{1}\triangle C^{\prime}_{1}$ will be a disjoint union of circuits of $M_{1}$. Since $C_{1}\triangle C^{\prime}_{1}$ does not contain any element from $S$, it is also a disjoint union of circuits of $M$. This would lead us to a contradiction because the size of $C_{1}\triangle C^{\prime}_{1}$ is less than $r$ and $M$ does not have circuits of size less than $r$. This proves the uniqueness of $C_{1}$. Our problem is still not solved since the set $S$ can have three elements in case of a $3$-sum, and thus, there can be three possibilities for $C_{1}$ (i.e., N=3).

Assigning weights to the elements. To get around this problem, we use a new idea of considering matroids elements with weights. For each element $s$ in $S$, consider the unique circuit $C_{1}$ of size at most $r/2$ that contains $s$. In the matroid $M_{2}$, we assign a weight of $\lvert C_{1}\rvert-1$ to the element $s$. The elements outside $S$ get weight $1$. The weight of element $s\in S$ signifies that if a circuit $C_{2}$ of $M_{2}$ contains $s$ then it has to be summed up with the unique circuit $C_{1}$ containing $s$, which adds a weight of $\lvert C_{1}\rvert-1$. Essentially, the circuits of the weighted matroid $M_{2}$ that have weight $\gamma$ will have a one-to-one correspondence with circuits $C=C_{1}\triangle C_{2}$ of $M$ that have size $\gamma$ and have $\lvert C_{1}\rvert<r/2$. Hence, we can assume there are no circuits in the weighted matroid $M_{2}$ of weight less than $r$. Thus, we can apply the induction hypothesis on $M_{2}$, but we need to further strengthen the hypothesis to a weighted version. By this new induction hypothesis, we will get a bound of $m_{2}^{c\alpha}$ on the number of circuits of $M_{2}$ with weight less that $\alpha r$. As mentioned above, this will bound the number of circuits $C=C_{1}\triangle C_{2}$ of $M$ with size less than $\alpha r$ and $\lvert C_{1}\rvert<r/2$. Note that the bound $m_{2}^{c\alpha}$ is smaller than the desired bound $m_{0}^{c\alpha}$.

Number of circuits $C$ when none of its projections is small. It is relatively easier to handle the other case when $C_{1}$ has size at least $r/2$ (and less than $\alpha r$). In this case, $C_{2}$ has size less than $(\alpha-\nicefrac{{1}}{{2}})r$. The bounds we get by the induction hypothesis for the number of circuits $C_{1}$ and $C_{2}$ are $m_{1}^{c\alpha}$ and $m_{2}^{c(\alpha-\nicefrac{{1}}{{2}})}$ respectively. Their product $m_{1}^{c\alpha}m_{2}^{c(\alpha-\nicefrac{{1}}{{2}})}$ bounds the number of circuits $C$ in this case. However, this product is not bounded by $m_{0}^{c\alpha}$.

Stronger version of Seymour’s Theorem. To get a better bound we need another key idea. Instead of Seymour’s Theorem, we work with a stronger variant given by Truemper . It states that any regular matroid can be written as a $k$-sum of two smaller regular matroids $M_{1}$ and $M_{2}$ for $k=1,2$ or $3$ such that one of them, say $M_{1}$, is a graphic, cographic or $R_{10}$ matroid. The advantage of this stronger statement is that we can take a relatively smaller bound on the number of circuits of $M_{1}$, which gives us more room for the inductive argument. Formally, we know from above that when $M_{1}$ is a graphic or cographic matroid, the number of its circuits of size less than $\alpha r$ is at most $m_{1}^{4\alpha}$. One can choose the constant $c$ in our induction hypothesis to be sufficiently large so that the product $m_{1}^{4\alpha}m_{2}^{c(\alpha-\nicefrac{{1}}{{2}})}$ is bounded by $m_{0}^{c\alpha}$.

A stronger induction hypothesis

To summarize, we work with an inductive hypothesis as follows: If a regular matroid (with weights) has no circuits of weight less than $r$ that avoid a given set $R$ of elements then the number of circuits of weight less than $\alpha r$ that contain the set $R$ is bounded by $m^{c\alpha}$. As the base case, lemma 7.1 shows this statement for the graphic and cographic case.

When we rerun the whole inductive argument with weights and with a fixed set $R$, we run into another issue. It turns out that in the case when the size of $C_{1}$ is very small, our arguments above do not go through if $C_{1}$ has some elements from $R$. To avoid such a situation we use yet another strengthened version of Seymour’s Theorem. It says that any regular matroid with a given element $\widetilde{e}$ can be written as a $k$-sum of two smaller regular matroids $M_{1}$ and $M_{2}$, such that $M_{1}$ is a graphic, cographic or $R_{10}$ matroid and $M_{2}$ is a regular matroid containing $\widetilde{e}$ (theorem 6.19). When our $R$ is a single element set, say $\{\widetilde{e}\}$, we use this theorem to ensure that $M_{1}$, and thus $C_{1}$, has no elements from $R$. This rectifies the problem when $R$ has size $1$. However, as we go deeper inside the induction, the set $R$ can grow in size. Essentially, whenever $\alpha$ decreases by $\nicefrac{{1}}{{2}}$ in the induction, the size of $R$ grows by $1$. Thus, we take $\alpha$ to be $\nicefrac{{3}}{{2}}$, which means that to reach $\alpha=1$ we need only one step of decrement, and thus, the size of $R$ at most becomes $1$. This is the reason our main theorem only deals with circuits of size less than $\nicefrac{{3}}{{2}}$ times the smallest size.

In order to generalize this result for an arbitrary constant $\alpha$, a different method is required. This will be the subject of a follow-up work.

The remainder of the paper is dedicated to the formal proof of theorem 2.6. We first give some matroid preliminaries and Seymour’s decomposition theorem for regular matroids in Section 6. Finally, in Section 7, we prove theorem 2.6.

Matroids

In Section 6.1, we recall some basic definitions and well-known facts about matroids (see, for example, ). In Section 6.2, we describe Seymour’s decomposition theorem for regular matroids.

A pair $M=(E,\mathcal{I})$ is a matroid if $E$ is a finite set and $\mathcal{I}$ is a nonempty collection of subsets of $E$ satisfying

if $I\in\mathcal{I}$ and $J\subseteq I$, then $J\in\mathcal{I}$,

if $I,J\in\mathcal{I}$ and $|I|<|J|$, then $I\cup\{z\}\in\mathcal{I}$, for some $z\in J\setminus I$.

A subset $I$ of $E$ is said to be independent, if $I$ belongs to $\mathcal{I}$ and dependent otherwise. An inclusionwise maximal independent subset of $E$ is a base of $M$. An inclusionwise minimal dependent set is a circuit of $M$.

We define some special classes of matroids.

A matroid $M$ is binary, if $M$ is representable over $\rm{GF}(2)$. A matroid $M$ is regular, if $M$ is representable over every field.

It is well known that regular matroids can be characterized in terms of TU matrices.

Two special classes of regular matroids are graphic matroids and their duals, cographic matroids.

A matroid $M=(E,\mathcal{I})$ is said to be a graphic, if there is an undirected graph $G=(V,E)$ whose edges correspond to the ground set $E$ of $M$, such that $I\in\mathcal{I}$ if and only if $I$ forms a forest in $G$. By $M(G)$ we denote the graphic matroid corresponding to $G$.

The dual of $M$ is the matroid $M^{*}=(E,\mathcal{I}^{*})$ over the same ground set such that a set $I\subseteq E$ is independent in $M^{*}$ if and only if $E\setminus I$ contains a base set of $M$. A cographic matroid is the dual of a graphic matroid.

For $G=(V,E)$, we can represent $M(G)$ by the vertex-edge incidence matrix $A_{G}\in\{0,1\}^{V\times E}$ (over $GF(2)$),

For a graph $G=(V,E)$, a cut is a partition $(V_{1},V_{2})$ of $V$ into two disjoint subsets. Any cut $(V_{1},V_{2})$ uniquely determines a cut-set, the set of edges that have one endpoint in $V_{1}$ and the other in $V_{2}$. The size of a cut is the number of edges in the corresponding cut-set. A minimum cut is one of minimum size.

The circuits of the graphic matroid $M(G)$ are exactly the simple cycles of $G$.

The circuits of the cographic matroid $M^{*}(G)$ are exactly the inclusionwise minimal cut-sets of $G$.

The symmetric difference of two cycles in a graph is a disjoint union of cycles. The analogous statement is true for binary matroids.

Let $M$ be binary. If $C_{1}$ and $C_{2}$ are circuits of $M$, then the symmetric difference $C_{1}\triangle C_{2}$ is a disjoint union of circuits.

To prove theorem 2.6, we have to bound the number of short circuits in regular matroids. In lemma 7.1, we start by providing such a bound for graphic and cographic matroids. The lemma is a variant of the following theorem that bounds the number of near-shortest cycles and the number of near-minimum cuts in a graph.

Let $G=(V,E)$ be a graph with $m\geq 1$ edges and $\alpha\geq 2$.

If $G$ has no cycles of length at most $r$, then the number of cycles in $G$ of length at most $\alpha r/2$ is bounded by $(2m)^{\alpha}$ .

If $G$ has no cuts of size at most $r$, then the number of cuts in $G$ of size at most $\alpha r/2$ is bounded by $m^{\alpha}$ .

Let $M=(E,\mathcal{I})$ be a matroid and $e\in E$. The matroid obtained from $M$ by deleting $e$ is denoted by $M\setminus e$. Its independent sets are given by the collection $\left\{\,I\in\mathcal{I}\mid e\not\in I\,\right\}$.

The matroid obtained by contracting $e$ is denoted by $M/e$. Its independent sets are given by the collection $\left\{\,I\subseteq E\setminus\{e\}\mid I\cup\{e\}\in\mathcal{I}\,\right\}$.

A matroid obtained after a series of deletion and contraction operations on $M$ is called a minor of $M$.

Let $M=(E,\mathcal{I})$ be a matroid and $e\in E$.

The circuits of $M\setminus e$ are those circuits of $M$ that do not contain $e$.

The classes of regular matroids, graphic matroids, and cographic matroids are minor closed.

For a characterization of regular matroids, we will need a specific matroid $R_{10}$, first introduced by . It is a matroid, with 10 elements in the ground set, represented over $GF(2)$ by the following matrix.

Any matroid obtained by deleting some elements from $R_{10}$ is a graphic matroid.

2 Seymour’s Theorem and its variants

The main ingredient for the proof of theorem 2.6 is a theorem of Seymour [23, Theorem 14.3] that shows that every regular matroid can be constructed from piecing together three kinds of matroids – graphic matroids, cographic matroids, and the matroid $R_{10}$. This piecing together is done via matroid operations called $1$-sum, $2$-sum and $3$-sum. These operations are defined for binary matroids.

Let $M_{1}=(E_{1},\mathcal{I}_{1})$ and $M_{2}=(E_{2},\mathcal{I}_{2})$ be two binary matroids, and let $S=E_{1}\cap E_{2}$. The sum of $M_{1}$ and $M_{2}$ is a matroid denoted by $M_{1}\triangle M_{2}$. It is defined over the ground set $E_{1}\triangle E_{2}$ such that the circuits of $M_{1}\triangle M_{2}$ are minimal non-empty subsets of $E_{1}\triangle E_{2}$ that are of the form $C_{1}\triangle C_{2}$, where $C_{i}$ is a (possibly empty) disjoint union of circuits of $M_{i}$, for $i=1,2$.

From the characterization of the circuits of a matroid [18, Theorem 1.1.4], it can be verified that the sum $M_{1}\triangle M_{2}$ is indeed a matroid.

We are only interested in three special sums:

Let $M_{1}=(E_{1},\mathcal{I}_{1})$ and $M_{2}=(E_{2},\mathcal{I}_{2})$ be two binary matroids and $E_{1}\cap E_{2}=S$. Let $m_{1}=\lvert E_{1}\rvert$, $m_{2}=\lvert E_{2}\rvert$, and $s=\lvert S\rvert$. Let furthermore $m_{1},m_{2}<|E_{1}\triangle E_{2}|=m_{1}+m_{2}-2s$. The sum $M_{1}\triangle M_{2}$ is called a

$2$-sum, if $s=1$ and $S$ is not a circuit of $M_{1},M_{2},M^{*}_{1}$ or $M^{*}_{2}$,

$3$-sum, if $s=3$ and $S$ is a circuit of $M_{1}$ and $M_{2}$ that does not contain a circuit of $M^{*}_{1}$ or $M^{*}_{2}$.

Note that the condition $m_{1},m_{2}<m_{1}+m_{2}-2s$ implies that

From the definition of $M_{1}\triangle M_{2}$ the following fact follows easily.

Let $C_{i}$ be a disjoint union of circuits of $M_{i}$, for $i=1,2$. If $C_{1}\triangle C_{2}$ is a subset of $E_{1}\triangle E_{2}$ then it is a disjoint union of circuits of $M_{1}\triangle M_{2}$.

In particular, it follows that for $i=1,2$, any circuit $C_{i}$ of $M_{i}$ with $C_{i}\subseteq E_{i}\setminus S$ is a circuit of $M_{1}\triangle M_{2}$. Further, for $1$-sums, circuits are easy to characterize.

If $M$ is a $1$-sum of $M_{1}$ and $M_{2}$ then any circuit of $M$ is either a circuit of $M_{1}$ or a circuit of $M_{2}$.

Thus, if one is interested in the number of circuits, one can assume that the given matroid is not a $1$-sum of two smaller matroids.

A matroid $M$ is connected if it cannot be written as a $1$-sum of two smaller matroids.

A characterization of circuits in a 2-sum or 3-sum is not as easy. Seymour [23, Lemma 2.7] provides a unique representation of the circuits for these cases.

Let $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ be the sets of circuits of $M_{1}$ and $M_{2}$, respectively. Let $M$ be a $2$- or $3$-sum of $M_{1}$ and $M_{2}$. For $S=E_{1}\cap E_{2}$, we have $\lvert S\rvert=1$ or $\lvert S\rvert=3$, respectively. Then for any circuit $C$ of $M$, one of the following holds: