### Example: Piping geng

I realized shortly after writing yesterday’s post about using gtools that I did not properly explain the piping procedure for geng. To remedy that deficiency, I will provide a concrete example of how I used this method in actual research.

In this example, we will exactly characterize the infinite class of $p$-extremal graphs for $p \leq 10$. We’ll start by talking about the mathematics, and at the very end we will go into the concrete piping example. Theoretically, you could skip straight to the code, but you’ll miss out on the fact that the computer is simultaneously discovering and proving a structure theorem for an infinite class of graphs!

### The Theory

A perfect matching is a set of edges which covers every vertex exactly once. Dudek and Schmitt defined the function $f(n,p)$ to be the maximum number of edges in a graph on $n$ vertices with exactly $p$ perfect matchings. An unpublished theorem of Hetyei states $f(n,1) = \frac{n^2}{4}$ and there is a unique graph attaining this bound for all even $n$. Dudek and Schmitt proved

Theorem (Dudek, Schmitt, 2012). For all $p \geq 1$, there are constants $n_p$ and $c_p$ such that $f(n,p) = \frac{n^2}{4} + c_p = f(n,1) + c_p$.

This implies that no matter how many perfect matchings we want to cram into our graph, we can only change the maximum number of edges by some constant. We call the difference $c(G) = |E(G)| - \frac{|V(G)|^2}{4}$ the excess of a graph $G$. Thus, we are attempting to maximize the excess over graphs with $p$ perfect matchings.

A graph is $p$-extremal if it has $n$ vertices, $p$ perfect matchings, and $\frac{n^2}{4}+c_p$ edges. Dudek and Schmitt were able to determine $c_p$ for $2 \leq p \leq 6$ and characterized the $p$-extremal graphs for $p \in \{2,3\}$.

With Hartke, West, and Yancey, we developed a structural characterization of the infinite class of $p$-extremal graphs for every fixed $p$. There was just one missing component: we described a way to build every $p$-extremal graph if you know a finite list of building blocks.

Here is a brief description of these blocks and how to glue them together. An edge is extendable if it is contained in a perfect matching; otherwise it is free. A graph is a chamber if the subgraph of extendable edges is connected. In a chamber, the subgraph of free edges is a set of disjoint cliques.

Given a non-chamber graph, its vertex set is partitioned into chambers by the connected components of the extendable subgraph. An important property of any graph $G$ is that the number of perfect matchings is the product of the number of perfect matchings in each chamber.

One way to build a graph with $p$ perfect matchings is to start with a list $H_1, \dots, H_k$ of chambers where $H_i$ has $p_i$ perfect matchings and $p = \prod_{i=1}^k p_i$. The disjoint union of these chambers has $p$ perfect matchings, but is very sparse. We can add free edges between the chambers by taking a clique $X_i$ of free edges in some $H_i$ and adding edges between all vertex in $X_i$ and vertices in $H_j$ for all $j > i$. This construction is called a spire, a very specific instance of a cathedral, as in Lovász’s Cathedral Theorem (see Lovász and Plummer, Chapter 5). To maximize the excess of the spire, we must select the largest clique $X_i$ of free edges in $H_i$ and satisfy the inequality $\frac{|X_i|}{|V(H_i)|} \geq \frac{|X_j|}{|V(H_j)|}$. Given such a spire $G$, the excess is bounded as $c(G) \leq \sum_{i=1}^k c(H_j)$ with equality if and only if $\frac{|X_i|}{|V(H_i)|} = \frac{1}{2}$ for all $1 \leq i < k$.

So, to finish the structural characterization, we must find the chambers with maximum excess and find out which have large cliques of free edges. It is not hard to observe that the only chamber with a unique perfect matching is $K_2$, the graph of exactly one edge. So, given any $p$-extremal graph $G$ on $n$ vertices, we can always extend $G$ to a $p$-extremal graph on $n + 2$ vertices by creating a new spire with an extra copy of $K_2$ as the first chamber.

An important fact that I have not yet discussed is that a chamber with $p$ perfect matchings and excess at least $c$ has at most $3 + \sqrt{16p - 8c - 23}$ vertices (a non-trivial fact!). Now this is a finite computation!

### The Computation

Download the C file permcount.c and place it in the nauty directory along with geng. To compile the program, type

gcc nausparse.o gtools.o nautil.o permcount.c -o permcount.exe -I./

This will create the executable permcount.exe. It has three parameters: $p_{\min}, p_{\max}, c_{\min}$ which provide the minimum number of perfect matchings, the maximum number of perfect matchings, and the minimum excess value. If you run

./geng 8 | ./permcount.exe 1 1 0

You will get the output

>A ./geng -d0D7 n=8 e=0-28 1 0 G?bN^{ >Z 12346 graphs generated in 0.01 sec

This means that geng generated all 12,346 graphs of order 8 but exactly one had a unique perfect matching and non-negative excess. So, we have just verified Hetyei’s theorem for this order!

Now, let’s find the maximum excess for a graph with $p$ perfect matchings. We proved that chambers with between one and seven perfect matchings have at most 10 vertices. So, we can find the maximum excess for these graphs by running

geng 10 | ./permcount.exe 1 7 0

Running with these parameters will output 471 graphs! However, some of these are unnecessary, as they are all graphs with one to seven perfect matchings and non-negative excess. But looking through the list, we find the following values for $c_p$:

 $p$ 1 2 3 4 5 6 7 $c_p$ 0 1 2 2 2 3 3

Hence, to find the list of $p$-extremal graphs for $1 \leq p \leq 7$, we can instead run the following commands (given with output):

./geng 8 | ./permcount.exe 1 1 0 >A ./geng -d0D7 n=8 e=0-28 1 0 G?bN^{ >Z 12346 graphs generated in 0.01 sec

./geng 8 | ./permcount.exe 2 2 1
>A ./geng -d0D7 n=8 e=0-28
2 1 G?bN~{
2 1 G?bn^{
2 1 G?rN^{
>Z 12346 graphs generated in 0.01 sec

./geng 8 | ./permcount.exe 3 5 2
>A ./geng -d0D7 n=8 e=0-28
4 2 G?bn~{
4 2 G?rN~{
4 2 G?rn^{
5 2 GCR]~{
5 2 GCrM~{
3 2 GCe]~{
>Z 12346 graphs generated in 0.01 sec

./geng 8 | ./permcount.exe 6 7 3
>A ./geng -d0D7 n=8 e=0-28
6 3 G?b~~{
6 3 G?zn^{
7 3 GCr]~{
6 3 GCe^~{
6 3 GCf]~{
>Z 12346 graphs generated in 0.01 sec

We can extend this just a little bit farther. When $p \leq 10$ we proved that $p$-extremal chambers have at most 12 vertices. Generating all graphs of order 12 and counting the number of perfect matchings on each one will take too long. Instead, we will limit the graphs we generate by specifying the number of edges. A graph on 12 vertices with excess $c$ has $36+c$ edges. By checking all graphs of order 10, we can quickly determine that there exist graphs with 8 perfect matchings and excess 3, and graphs with 9 or 10 perfect matchings and excess 4. The following lemma from Dudek and Schmitt is helpful in this case:

Lemma (Dudek, Schmitt, 2012). If $c_p \leq C$ for all $p < q$, then $c_q \leq C+1$.

That is, the excess can increase by at most one over all previous excess values. Therefore, by our previous determinations of $c_p$ we now know that $c_8 \in \{3, 4\}$ and once we determine $c_8 = 3$, we will know $c_9 \in \{4, 5\}$. Again, once we determine $c_9 = 4$ we will know $c_{10} \in \{4,5\}$. Thus, we can run the following two commands:

./geng 12 39:40 | ./permcount.exe 8 8 3 ./geng 12 40:41 | ./permcount.exe 9 10 4

Now, by looking at the output graphs, we can extract the list of chambers. From those chambers we can determine the structure theorems for $p$-extremal graphs for all $p \leq 10$. Here is a picture that demonstrates the spire structures that determine all $p$-extremal graphs:

Figure 1. The $p$-extremal spires for $p\leq 10$.

Unfortunately, our bound on the order of 11-extremal chambers is at most 14 vertices. Generating all graphs of order 14 (even restricting to the number of edges) is intractable, even for a supercomputer. To find the $p$-extremal chambers for larger values of $p$, we must do something drastically different. That will be the subject of a later blog post, which will first require a description of canonical deletion (the algorithm behind geng).

#### References

A. Dudek, J. Schmitt, On the size and structure of graphs with a constant number of 1-factors. Discrete Math. 312 (2012) 1807-1811.

S. G. Hartke, D. Stolee, D. B. West, M. Yancey, Extremal graphs with a given number of perfect matchings. To appear in Journal of Graph Theory.

L. Lovász, M. Plummber, Matching Theory. (AMS Chelsea Publishing; Providence, RI, 2009), xxxiii+547 pp.