# Subspace codes and graph genus: combinatorial open MIPLIB instances

A few open MIPLIB 2017 instances encode crisp mathematical questions rather than industrial plans. `cdc7-4-3-2` asks for the largest set of 3-dimensional subspaces of $\mathbb{F}_2^7$ that pairwise meet in at most a one-dimensional subspace, a question tied to the hypothetical binary q-analogue of the Fano plane; five `genus` instances ask for the minimum genus of specific graphs.

## Problem

**Subspace code.** Find a largest family $\mathcal{C}$ of 3-dimensional subspaces of $\mathbb{F}_2^7$ such that $\dim(U \cap W) \le 1$ for all distinct $U, W \in \mathcal{C}$. Its size is $A_2(7,4;3)$, the largest binary constant-dimension code of length 7, dimension 3 and subspace distance 4. The instance has 11,811 binary variables, as many as there are 3-dimensional subspaces of $\mathbb{F}_2^7$, and maximises the size of the code, written as minimising its negative.

**Graph genus.** For a graph $G = (V, E)$, choose a rotation system (a cyclic order of the edges around each vertex) so that face tracing yields as many faces $f$ as possible; the orientable genus of that embedding is $\gamma = (2 - |V| + |E| - f)/2$. The instances use the integer programming model of Beyer, Chimani, Hedtke and Kotrbčík (2016), which maximises $f$; MIPLIB stores the objective as $-f$.

| Instance | Graph or code | Variables | Best known |
|---|---|---|---|
| `cdc7-4-3-2` | $A_2(7,4;3)$ | 11,811 | 333 subspaces |
| `genus-g31-8` | AT&T graph g.31.8 | 3,484 | 23 faces |
| `genus-sym-g31-8` | same, with symmetry breaking | 3,484 | 23 faces |
| `genus-g61-25` | AT&T graph g.61.25 | 14,380 | 40 faces |
| `genus-sym-g62-2` | AT&T graph g.62.2, symmetry breaking | 12,912 | 38 faces |
| `genus-sym-grafo5708-48` | Rome graph grafo5708.48, symmetry breaking | 3,379 | 21 faces |

## Background

MIPLIB files `cdc7-4-3-2` under codes for network coding; it was submitted by Sascha Kurz. A code of size 381 would be a binary q-analogue of the Fano plane, an object that nobody has found or ruled out; Kiermaier, Kurz and Wassermann (2018) showed that its automorphism group would have order at most two. Computing the minimum genus of a graph is NP-hard; the first practical exact methods, based on integer programming and SAT, date from 2016 (Beyer et al.) and were strengthened by Chimani and Wiedera (2019). The AT&T and Rome graphs come from graph-drawing benchmark collections.

## What is known

- MIPLIB lists the best values above (solution file version 37, 24 September 2026); it records no dual bounds.
- For `cdc7-4-3-2` the instance page gives $333 \le A_2(7,4;3) \le 381$. The value 333 is the code of Heinlein, Kiermaier, Kurz and Wassermann (2019), entered in MIPLIB in August 2026. The best solver run submitted before that reached 307 (Yuji Shinano and Stefan Vigerske, October 2025).
- The smaller case $A_2(6,4;3) = 77$ is settled (Honold, Kiermaier and Kurz, as cited by MIPLIB).
- The genus records date from 2019 to 2024; the latest, for `genus-g61-25` and `genus-sym-g62-2`, came from the local-search solver Local-MIP (Peng Lin, Mengchuan Zou and Shaowei Cai, January 2024), which also matched the 23 that Mars Davletshin had found for `genus-sym-g31-8` with Huawei OptVerse in November 2023.

## What would count as progress

- A solution file in MIPLIB's SOL format with a better objective, checked by MIPLIB's exact-arithmetic solution checker in seconds. For `cdc7-4-3-2` this means a code of at least 334 subspaces, which can also be checked directly by testing all pairwise intersections; for a genus instance it means an embedding with more faces, which face tracing confirms.
- A proof that a listed value is optimal. For `cdc7-4-3-2` any upper bound below 381 would also rule out the binary q-analogue of the Fano plane, a much harder kind of progress.

## References

1. A. Gleixner et al. (2021). MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library. *Mathematical Programming Computation* 13, 443–490. https://doi.org/10.1007/s12532-020-00194-3
2. D. Heinlein, M. Kiermaier, S. Kurz and A. Wassermann (2019). A subspace code of size 333 in the setting of a binary q-analog of the Fano plane. *Advances in Mathematics of Communications* 13, 457–475. https://doi.org/10.3934/amc.2019029
3. M. Kiermaier, S. Kurz and A. Wassermann (2018). The order of the automorphism group of a binary q-analog of the Fano plane is at most two. *Designs, Codes and Cryptography* 86, 239–250. https://doi.org/10.1007/s10623-017-0360-6
4. S. Beyer, M. Chimani, I. Hedtke and M. Kotrbčík (2016). A practical method for the minimum genus of a graph: models and experiments. *SEA 2016*, LNCS 9685, 75–88. https://doi.org/10.1007/978-3-319-38851-9_6
5. M. Chimani and T. Wiedera (2019). Stronger ILPs for the graph genus problem. *ESA 2019*, LIPIcs 144, 30:1–30:15. https://doi.org/10.4230/LIPIcs.ESA.2019.30

## Source

Imported from [MIPLIB 2017, Open tag](https://miplib.zib.de/tag_open.html), curated by Zuse Institute Berlin. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.