The Combinatorial Object Server

Input graph | ||

Predefined inputs | ||

Output format | ||

Output
numbering
graphics

An elimination tree of a connected graph $G$ is a rooted tree whose root is a vertex $v$ of $G$, and the subtrees of $v$ are obtained by recursing on the connected components of the graph obtained by removing $v$ from $G$.
The children of a vertex in an elimination tree are unordered.
An elimination forest of a graph $G$ (not necessarily connected) is the disjoint union of elimination trees, one for each connected component of $G$.

The figure below shows a graph $G$ on vertices $a,b,c,d,e,f$ (left) and one of its elimination trees $T$ (right), obtained by removing the vertices in the order $d,a,c,b,e,f$. There may be several elimination orders corresponding to the same elimination tree. For example, removing the vertices in the order $d,f,a,c,e,b$ yields the same elimination tree. Formally, the set of elimination orders corresponding to an elimination tree is the set of linear extensions of the poset whose Hasse diagram is the tree.

By choosing suitable families of graphs $G$, elimination forests encode many different combinatorial objects, and tree rotations in the elimination trees correspond to natural minimum change operations on those objects:

- If $G$ is a path labeled $1,\ldots,n$ between its two end vertices, then its elimination trees correspond to binary trees. The distinction between left and right child of a vertex in an elimination tree is given by the smaller and larger labels. Elimination tree rotations correspond to classical rotations in binary trees.
- If $G$ is a complete graph on $n$ vertices, then its elimination trees are paths, which can be interpreted as permutations, by reading off the vertices of the elimination tree from the root to the leaf of the path. Elimination tree rotations correspond to adjacent transpositions in the permutations.
- If $G$ is a star with center $c$ and leaves $1,\ldots,n$, then its elimination trees are brooms, and reading off the vertices of the broom starting at the root and ending at the parent of $c$ yields partial permutations, i.e., linear orderings of all subsets of $\{1,\ldots,n\}$. Moreover, elimination tree rotations correspond to adjacent transpositions or deletions and insertions of a trailing element in a partial permutation.
- If $G$ is a disjoint union of $n$ edges $\{i,n+i\}$, then its elimination forests correspond to bitstrings of length $n$, where the value of the $i$th bit is 0 if in the elimination forest the edge $\{i,n+i\}$ is rooted at $i$ and the bit is 1 if the edge is rooted at $n+i$. Elimination tree rotations correspond to flipping a single bit in the bitstrings.
- If $G$ is a disjoint union of $n$ edges and a complete graph on $n$ vertices, then its elimination forest can be interpreted as signed permutations: The elimination tree of the complete graph determines the permutation, and the elimination trees for the edges determine the signs. Elimination tree rotations correspond to adjacent transpositions in the permutations (without changing the signs), or to sign reversals of a single entry in the permutation.

It was shown in [MP15] that if $G$ has at least two edges, then all its elimination forests can be ordered cyclically so that any two consecutive elimination forests differ in a single tree rotation. These orderings of elimination forests correspond to Hamilton cycles on the skeleta of polytopes known as graph associahedra [CD06], [Pos09]. In the paper [CMM21] we propose an efficient algorithm for computing such an ordering for the case when $G$ is chordal (albeit the ordering is not necessarily cyclic). The algorithm running on this website implements this algorithm, and it first outputs the perfect elimination ordering that is used for labeling the vertices of the input graph. In the graphical output, the elimination trees are rotated to save space, with the root on the left and growing to the right. In the textual output, each elimination tree is traversed in DFS order, printing each vertex label followed by a sequence of dots corresponding to the number of children of that vertex in the elimination tree. For example, the elimination tree shown above with the perfect elimination ordering $a,d,f,b,c,e$ would be printed as 2.. 1. 5. 4 6 3

The OEIS sequences listed below count the five combinatorial classes mentioned in the examples before.

- binary trees: OEIS A000108 (Catalan numbers)
- permutations: OEIS A000142 (factorials)
- partial permutations: OEIS A000522
- bitstrings: OEIS A000079 (powers of 2)
- signed permutations: OEIS A000165 (double factorials)

- [CD06] M. P. Carr and S. L. Devadoss. Coxeter complexes and graph-associahedra. Topology Appl., 153(12):2155–2168, 2006.
- [CMM21] J. Cardinal, A. Merino, and T. Mütze. Combinatorial generation via permutation languages. IV. Elimination trees. arXiv:2106.16204, June 2021.
- [MP15] T. Manneville and V. Pilaud. Graph properties of graph associahedra. Sém. Lothar. Combin., 73:Art. B73d, 31, 2015.
- [Pos09] A. Postnikov. Permutohedra, associahedra, and beyond. Int. Math. Res. Not. IMRN, (6):1026–1106, 2009.