Good partitions of forests

In the BPHZ convergence proofs in Euclidean signature position space in my article arXiv:hep-th/0601168, the configuration space of the vertices of a Feynman diagram is divided into regions associated with the different "good partitions" of the set of all the Zimmermann forests of the diagram. A "good partition" of the forests is a partition of the set of all the forests into disjoint "good sets of forests", where a "good set of forests" is defined by a maximal member Q and a minimal member P such that P ⊆ Q, and consists of all the forests F such that P ⊆ F ⊆ Q.

This page provides the C++ source code for a program that enumerates the good partitions of a set of forests with specified subset relations. On a Linux system with gcc, the program can be built for example with the command:

g++ -o GoodPartitionsOfForests GoodPartitionsOfForests.cpp -Wall

The program expects to be given as input the number of forests, followed by a square table giving the subset relations among the forests, with a 1 at position (A,B) if forest number A is a subset of forest number B, and 0 otherwise. The program output lists the good partitions of the forests, assuming that the forests are numbered 0, 1, 2, ... .

For example, if the file FData contains the data:

4

1 1 1 1
0 1 0 1
0 0 1 1
0 0 0 1

then the command:

./GoodPartitionsOfForests < FData

will cause the program to output:

1 1 1 1 
0 1 0 1 
0 0 1 1 
0 0 0 1 

{(0,3)}
{(1,3), (0,2)}
{(1,3), (2,2), (0,0)}
{(2,3), (0,1)}
{(2,3), (1,1), (0,0)}
{(3,3), (0,1), (2,2)}
{(3,3), (1,1), (0,2)}
{(3,3), (1,1), (2,2), (0,0)}
No more good partitions
8 good partitions of the 4 forests found

GoodPartitionsOfForests.cpp is copyright (c) Chris Austin 2013 and is licensed for use under the Free Software Foundation GNU General Public License. This documentation page is copyright (c) Chris Austin 2013 and is licensed for use under the Free Software Foundation GNU Free Documentation License.

Page last updated 29 July 2013.