This article considers tools one can use to quickly test conjectures. I work in combinatorial optimization, and often there are cases where one can phrase a problem as a conjecture over a finite domain. Testing conjectures using brute force quickly becomes infeasible due to combinatorial explosion. Here, we walk through an actual example and learn a few techniques. We will use Sage and any fast linear program solver, such as Gurobi.

1 A conjecture on $k$-partitions of a submodular function

A collection of $k$ non-empty, pairwise disjoint sets whose union is $V$ is called a $k$-partition of $V$.

Let $f:2^V\to \mathbb{R}$ be a submodular function. A minimum $k$-partition is a $k$-partition $\mathcal{X}$ of $V$ such that ${\sum }_{X\in \mathcal{X}}f(X)$ is minimized; that is, the sum of the function values over the parts is minimized.

A $k$-partition $\mathcal{X}$ and a $j$-partition $\mathcal{Y}$ are noncrossing if there exist $X\in \mathcal{X}$ and $Y\in \mathcal{Y}$ such that $X\subseteq Y$. We denote this relation by $\mathcal{X}⊲\mathcal{Y}$.

One way to prove the conjecture is to start with a minimum $k$-partition that does not have the desired property, and then use it to construct a new minimum $k$-partition that does. This requires introducing a few additional notions.

For two partitions $\mathcal{X}$ and $\mathcal{Y}$, define $$\mathcal{X}\sqcap \mathcal{Y}=\left\{X\cap Y\mid X\in \mathcal{X},Y\in \mathcal{Y}\right\}.$$ That is, the new partition is obtained by intersecting every part of $\mathcal{X}$ with every part of $\mathcal{Y}$.

For two partitions $\mathcal{X}$ and $\mathcal{Y}$, write $\mathcal{X}\le \mathcal{Y}$ if for each $X\in \mathcal{X}$ there exists $Y\in \mathcal{Y}$ such that $X\subseteq Y$. If $\mathcal{X}\le \mathcal{Y}$, then every part of $\mathcal{Y}$ is the union of some parts of $\mathcal{X}$.

Now consider the following stronger conjecture, which implies the previous one.

We are interested in writing a program to test the stronger conjecture for small $k$.

One can first consider all possible ways $\mathcal{X}$ can intersect with $\mathcal{Y}$. A matrix encoding how $\mathcal{X}$ intersects with $\mathcal{Y}$ is called a configuration. For each configuration, we want to know: under that configuration, can we find the desired ${\mathcal{Y}}^{\prime }$?

2 Enumerate non-isomorphic configurations

Given $\mathcal{X}=\left\{X_1,\dots ,X_{k-1}\right\}$ and $\mathcal{Y}=\left\{Y_1,\dots ,Y_k\right\}$, let $$Z_{i,j}=X_i\cap Y_j,\mathcal{Z}=\{Z_{i,j}\}=\mathcal{X}\sqcap \mathcal{Y}.$$

We want to show that some minimum $k$-partition ${\mathcal{Y}}^{\prime }$ satisfies $\mathcal{Z}\le {\mathcal{Y}}^{\prime }$.

Observe that it does not matter whether $Z_{i,j}$ contains $100$ vertices or $1$ vertex – only whether it is empty. Hence, we can consider a matrix $M$ where $$M_{i,j}=\max (1,|Z_{i,j}|).$$ Such a matrix is called a configuration of $\mathcal{Z}$, and it encodes the information we care about. $\mathcal{X}$ and $\mathcal{Y}$ is called a realization of $M$. The goal is to prove the conjecture for each configuration. That is, all realizations of the configuration.

Two configurations are isomorphic if one can be obtained from the other by permuting rows and columns.

We are interested in enumerating possible configurations up to isomorphism.

This is the same as enumerating $\{0,1\}$-matrices modulo the action of a permutation group. This part can be done in Sage. There is a function that generates all integer vectors modulo a permutation group; the vectors have length $\ell$ with elements in $\left\{0,\dots ,n\right\}$. See the reference on Integer vectors modulo the action of a permutation group.

IntegerVectorsModPermutationGroup(P, max_part=1)

Once we have the output, we filter it to obtain valid configurations. For example, a configuration must have at least one $1$ in each row.

The Sage function requires the permutation group $P$ defining the desired equivalence.

One might think we can take $S_{k-1}\times S_k$ to obtain $P$, where $S_k$ is the symmetric group on $k$ letters. Unfortunately, this is not correct: it describes the action on rows and columns, but we need the induced action on the entries of the matrix.

The correct way is to use wreath products. We want $(S_{k-1}\wr S_k)\cap (S_k\wr S_{k-1})$. However, we must ensure that the element labeling is consistent. The following is Sage code where the elements are labeled $1$ to $k(k-1)$. We ensure the same labeling via the permutation pi.

a = SymmetricGroup(k-1)
b = SymmetricGroup(k)

matrix = [[k*x+y+1 for y in range(k-1)] for x in range(k)]
pi = list(itertools.chain.from_iterable(map(list, zip(*matrix))))

# we have to use SAGE to access GAP
GG = gap.WreathProduct(gap(a),gap(b))
HH = gap.WreathProduct(gap(b),gap(a))

G = PermutationGroup(gap_group = GG.AsPermGroup())
Hbad = PermutationGroup(gap_group = HH.AsPermGroup())
# make sure the elements are labelled correctly.
H = PermutationGroup([perm_replace(pi,g) for g in Hbad.gens()])

# The correct permutation group
P = H.intersection(G)

At this point, we obtain all matrices, some of which correspond to configurations. In particular, for $k=3,4,5,6$, the numbers of configurations are $13,87,1053,28576$.

If we restrict to matrices with at least one $1$ in each row and at least one $1$ in each column, this reduces the counts to $5,42,633,20755$. These are valid configurations.

We can further observe that for some configurations, we already have $\mathcal{X}⊲\mathcal{Y}$, so we do not have to check them. Let us call the remaining configurations good. The numbers of good configurations for $k=3,4,5,6$ are $3,23,353,12828$.

3 Test if there exists a noncrossing ${\mathcal{Y}}^{\prime }$ for a configuration $M$

Fix a configuration $M$. We now construct a linear program to decide whether there always exists a minimum $k$-partition ${\mathcal{Y}}^{\prime }$ that is noncrossing with the minimum $(k-1)$-partition $\mathcal{X}$. For a given $M$, one can recover (a minimal) $\mathcal{X}$ and $\mathcal{Y}$ that realize $M$. It is easy to see that if our argument works for these particular $\mathcal{X}$ and $\mathcal{Y}$, it works for all $\mathcal{X}$ and $\mathcal{Y}$ realizing $M$.

Let $V$ be the vertex set, with $|V|$ equal to the number of $1$’s in $M$. Let $P_k(V)$ be the set of $k$-partitions of $V$. For each $U\subseteq V$, create a variable $x_U$ representing the value $f(U)$, and also create a variable $z$.

For a partition $\mathcal{S}$, write $x_{\mathcal{S}}={\sum }_{S\in \mathcal{S}}{x}_S$.

Consider the following linear program: $$\begin{array}{rlrlrl}& \max & & z& & \\ & \text{s.t.}& & x_{S\cup \{a\}}+x_{S\cup \{b\}}\ge x_{S\cup \{a,b\}}+x_S& & \forall S\subseteq V,a,b\in V\setminus S\\ & & & x_{\mathcal{X}}\le x_{{\mathcal{X}}^{\prime }}& & \forall {\mathcal{X}}^{\prime }\in P_{k-1}(V)\\ & & & x_{\mathcal{Y}}\le x_{{\mathcal{Y}}^{\prime }}& & \forall {\mathcal{Y}}^{\prime }\in P_k(V)\\ & & & x_{\mathcal{Y}}=1& & \\ & & & z\le x_{{\mathcal{Y}}^{\prime }}& & \forall {\mathcal{Y}}^{\prime }\in P_k(V)\text{with}\mathcal{X}⊲{\mathcal{Y}}^{\prime }.\end{array}$$

The first set of constraints are the submodular inequalities, which enforce that $x_S=f(S)$ for some submodular function $f$. The next constraints enforce that $\mathcal{X}$ is a minimum $(k-1)$-partition and $\mathcal{Y}$ is a minimum $k$-partition. We normalize the optimal $k$-partition value to be $1$. Finally, among all $k$-partitions that are noncrossing with $\mathcal{X}$, the variable $z$ is a lower bound on their objective values.

If the optimal value is $z=1$, then there exists at least one $k$-partition ${\mathcal{Y}}^{\prime }$ that is noncrossing with $\mathcal{X}$ and has the same value as the minimum $k$-partition. Therefore, the conjecture holds if and only if for every configuration $M$, the above linear program has optimum $1$.

4 Redundant constraints

One can easily prove the conjecture for $k=3,4$ by directly solving the above linear program over all good configurations. However, it becomes difficult for $k=5$ because the linear program is far too large. The number of $k$-partitions of an $n$-element set is the Stirling number of the second kind $\left\{\genfrac{}{}{0ex}{}{n}{k}\right\}$: $$\left\{\genfrac{}{}{0ex}{}{20}{5}\right\}=749206090500,\left\{\genfrac{}{}{0ex}{}{20}{4}\right\}=45232115901.$$ It seems many constraints are redundant due to symmetry, and it would be interesting to see if we can reduce the formulation to a manageable size. If so, the conjecture for $k=5$, or even $k=6$, might become solvable.

To do this, consider the following definition. For a vector $s=(s_1,\dots ,s_k)$, say that a family of $k$-partitions $\mathfrak{F}$ is $s$-complete if $$f(\mathcal{P})\ge f(\mathcal{Y})\forall \mathcal{P}\in \mathfrak{F}⟹f(\mathcal{P})\ge f(\mathcal{Y})\forall \mathcal{P}\in P_k(V),$$ where $\mathcal{Y}=\{Y_1,\dots ,Y_k\}$ is a $k$-partition with $|Y_i|=s_i$. By the previous discussion, we only need to consider the case ${\sum }_i{s}_i\le k(k-1)$.

Let $\lambda (s)$ be the minimum size of an $s$-complete family. Instead of including constraints for all $k$-partitions, it suffices to include constraints for an $s$-complete family (for the relevant $s$). If $\lambda (s)$ is small for all relevant $s$, there is hope to solve the problem quickly.

As an example, we show a simple bound on $\lambda (a,b)$.

Currently, I do not know much about $\lambda (s)$ in general, so let us look at a special case. Define $${\lambda }_k(d)=\lambda ((d,\dots ,d)),$$ where $d$ is repeated $k$ times. It would be very interesting to understand how large ${\lambda }_k(d)$ is, especially ${\lambda }_5(4)$. If ${\lambda }_5(4)$ is small, then there is hope of solving the conjecture for $k=5$.

In particular, because we see ${\lambda }_2(d)\le 2^{d+1}$, I would conjecture ${\lambda }_k(d)=O(k^d)$.