Example: Piping geng

by Derrick Stolee

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.

Advertisements