Jun 13, 2016 (version 4).

### Every Clutter is a Tree of Blobs

Author: Gus Wiseman

Figures: http://imgur.com/a/B8WD4

- This article is plain text (markdown) but uses many special unicode characters. The reader should recognize and be familiar with the following: Greek letters (π σ τ μ δ ξ κ) and mathematical relations (∈ ⊆ ≤ →) and operators (∑ ∏ ∪).

- **Bold terms** indicate a defined meaning.

- f^(@)({a,b,...,z}) = {f(a),f(b),...,f(z)}

- A **set partition** π ⊢ S is any set of disjoint sets spanning S (i.e. ∪(π) = S).

- **iff** means *if and only if*.

## Introduction

If V is a finite vertex set and E ⊆ 2^(V) is a collection of finite subsets (called edges), none of which is a subset of another, we recursively define **Swell(E)** to be the collection of all sets which either:

- belong to E, or

- are the union of some pair of *overlapping* sets, both already belonging to Swell(E).

For example (see figure for a much larger clutter), if

* E = {{1,2},{1,3},{2,3,4}},

then

* Swell(E) = {{1,2},{1,3},{1,2,3},{2,3,4},{1,2,3,4}}.

If we also have ∪(E) ∈ Swell(E), then the set system E is called a **clutter**. This condition means that (except in the case |∪(E)| = 1) each edge contains at least two vertices, and that the hypergraph (∪(E),E) spanned by the edge set is *connected*.

* [swell_example.png](http://imgur.com/wbxTFA2)

> IMPORTANT NOTE

> Some of our definitions are slightly non-standard, but this may be justified by a brief critique of the literature. For many authors, "clutter" is a word entailing essentially the same mathematical structure as "hypergraph". And indeed much has been written about such "clutters", both pure and applied. We propose to make the following relevant but unrecognized distinction, between two different notions of connectedness.

> - On the edge set of a *hypergraph*, a *set partition* π ⊆ Swell(E) is *connected* if ∪(π) ∈ Swell(E).

> - On the edge set of a *clutter*, a *set system* F ⊆ Swell(E) is *connected* if ∪(F) ∈ Swell(F). ☐

The number of clutters |C(n)| spanning n = 1,2,...,8 vertices is given by [A048143](http://oeis.org/A048143),

- 1, 1, 5, 84, 6348, 7743728, 2414572893530, 56130437190053299918162.

This sequence varies as 2^(2^n), so the number of digits required roughly doubles with each consecutive term. Our main example shown in the figures is just one of some 56-sextillion members of C(8). The following is a list of non-isomorphic representatives for all clutters with up to four vertices.

- ((1))

- ((12))

- ((123))

- ((12)(13))

- ((12)(13)(23))

- ((1234))

- ((12)(134))

- ((123)(124))

- ((12)(13)(14))

- ((12)(13)(24))

- ((12)(13)(234))

- ((12)(134)(234))

- ((123)(124)(134))

- ((12)(13)(14)(23))

- ((12)(13)(14)(234))

- ((12)(13)(24)(34))

- ((123)(124)(134)(234))

- ((12)(13)(14)(23)(24))

- ((12)(13)(14)(23)(24)(34))

## Kernels and Caps in Clutters

A **kernel** of E is a clutter E|w (the restriction of E to edges that are subsets of w) for some w ∈ Swell(E). Suppose π ⊢ E is a set partition of E such that each block T ∈ π is a kernel of E (i.e. ∪(T) ∈ Swell(E) and T = E|∪(T)). Since S ⊆ T would imply E|S ⊆ E|T, it follows that the set of unions F = ∪^(@)(π) is itself a clutter, which we call a **cap** of E. Equivalently, a cap F of E is a clutter satisfying:

- F ⊆ Swell(E), and

- every edge of E is a subset of exactly one edge of F.

To see that this does *not* establish a partial order of clutters with a vertex set, observe that

* {{1,2},{1,3},{2,3},{3,4}}

* {{1,2},{1,3},{2,3,4}}

* {{1,2,3},{2,3,4}}

is a non-transitive chain of caps. The following two figures depict the caps and corresponding set partitions of the clutter introduced in the preceding figure.

* [caps_example.png](http://imgur.com/xVmA9er)

* [clutptns_example.png](http://imgur.com/EpOHGKY)

## Trees and Blobs

The **density** of a clutter E is

- κ(E) = ∑(|e|-1) - |∪(E)|,

where the sum is over all edges e ∈ E.

A clutter E with two or more edges is a **tree** iff κ(E) = -1. This is equivalent to the usual definition of a spanning hypertree.

A clutter E is a **blob** iff no cap of E is a tree. The trees and blobs among the caps depicted above are:

* [trees_example.png](http://imgur.com/DKdbAeC)

* [blobs_example.png](http://imgur.com/PM3b0NG)

Suppose a clutter E decomposes into a cap F and corresponding set of kernels ξ ⊢ E. Then

- κ(E) - κ(F) = ∑(κ(H)+1),

where the sum is over all H ∈ ξ. In particular, κ(F) ≤ κ(E), and κ(E) = κ(F) iff every H ∈ ξ is a tree. Using this simple identity, one easily proves the following.

> LEMMA

> - *Every kernel (with two or more edges) of a tree is a tree.*

> - *Every cap (with two or more edges) of a tree is a tree.*

> - *The union of a set of trees whose set of unions is a tree, is a tree.* ☐

The following is also straight-forward.

> PROPOSITION

> - *A clutter E is a tree iff no kernel of E is a blob.* ☐

We now come to the main result. For our two running examples, this corresponds to the following decompositions (into trees of blobs):

* τ = {{{1,2},{1,3},{2,3}},{{3,4}}}

* τ = [tree_of_blobs_example.png](http://imgur.com/4cM97bw)

> THEOREM

> - *Assume E is not a blob. Let τ = τ(E) be the subset-maximal kernels of E which are blobs. Then τ is a set partition of E whose set of unions ∪^(@)(τ) is a tree.*

> **Proof.**

> First we show that any blob (kernel) is contained within a single branch of any tree (cap). Suppose that B = E|w is a kernel of E which is a blob, and that T is a cap of E which is a tree. Let T' be the subtree of T contributing to the set partition π ⊢ B of *non-empty* intersections B ∩ E|t for each branch t ∈ T'. The set of unions H = ∪^(@)(π) form a clutter that is obtained from T' by deleting in turn all vertices not in w, a process which weakly decreases density. Let σ ⊢ B be the set partition comprised of maximal kernels (i.e. connected components) contained in blocks of π. Then F = ∪^(@)(σ) is a cap of B, and κ(H) - κ(F) = |σ| - |π|. Since F is a connected clutter, we have -1 ≤ κ(F) ≤ κ(H) ≤ κ(T') ≤ -1, and therefore F = H. But since B is a blob, F cannot be a tree, hence must be a maximal cap (viz. F = {w}, π = {B}).

> Next we show that τ(E) ⊢ E. If any two blobs overlap, both blobs must be contained entirely in whatever branch (of any given tree) contains their intersection. This implies that there is another blob containing their union; and hence that the maximal blobs τ(E) are disjoint. Since every singleton is also a blob, we conclude that ∪^(@)(τ) is a cap of E.

> Finally, if any kernel of ∪^(@)(τ) were a blob, so would be the restriction of E to its union, contradicting maximality of τ. This proves that the set of unions of τ is a tree. ☐

## Connected Sets of Kernels

Let ker(E) be the set of all kernels of E. If K ⊆ ker(E) is itself a (connected) clutter with vertex set E = ∪(K), then there exists a unique subset-minimal upper bound ⋁(K) = E|∪(∪^(@)(K)) satisfying

- ⋁(K) ∈ ker(E), and

- k ⊆ ⋁(K) for all k ∈ K.

In general, we can only define ⋁(K) uniquely for K a *connected* set of kernels, so ⋁ is not strictly a join-operation for the lattice of subsets ker(E) ⊆ 2^(E). But if K is not connected as a clutter, then letting π ⊢ K be its (maximal) connected components, we say that K is a **connected set of kernels** iff ⋁^(@)(π) is also connected (as a set of kernels); in which case the join is given by

- ⋁(K) = ⋁(⋁^(@)(π)).

In practice, the verification of connectedness, and the computation of ⋁, may require several iterations constructing joins of connected components. For example, the connected set of kernels

K = {(12)(13),(12)(14),(15)(16)(56),(34)(35),(36)},

has the following sequence of partitions into connected components:

- {(12)(13)} {(12)(14)} {(15)(16)(56)} {(34)(35)} {(36)},

- {(12)(13),(12)(14)} {(15)(16)(56)} {(34)(35)} {(36)},

- {(12)(13)(14)(34),(34)(35)} {(15)(16)(56)} {(36)},

- {(12)(13)(14)(15)(34)(35),(15)(16)(56)} {(36)},

- {(12)(13)(14)(15)(16)(34)(35)(36)(56)}.

> OPEN PROBLEM

> If K is a connected set of kernels, we define its **compression** cmp(K) to be the number of iterations in the computation of ⋁(K) by constructing consecutive joins of connected components. For the above example we have cmp(K) = 5. Although it seems unlikely that cmp is a bounded invariant, we do not know how to construct an example with compression greater than 5.

> - *For which positive numbers n ≥ 1 does there exist a connected set of kernels K such that cmp(K)=n?*

> - *Does there exist an infinite chain K^(1) ⊆ K^(2) ⊆ K^(3) ⊆ ... of connected sets of kernels such that cmp(K^(i)) < cmp(K^(i+1)) for all i ≥ 1?* ☐

Define an invariant μ : ker(E) → ℤ by

- ∑ μ(ξ1)\*μ(ξ2)\*...\*μ(ξn) = δ^(|H|=1)

for all H ∈ ker(E), where the sum is over all clutter partitions ker(E) ⊇ ξ ⊢ H. Here δ^(P) denotes the indicator function for a proposition P, equal to 1 or 0 depending on whether P is true or false respectively.

> THEOREM

> *For any H ∈ ker(E) we have*

> - μ(H) = ∑(-1)^(|K|),

> *where the sum is over all connected sets of kernels spanning H.*

> **Proof.**

> Let cptn(E) be the set of all clutter partitions ker(E) ⊇ π ⊢ E. What we have essentially shown above is that cptn(E) ⊆ ∪^(-1)(E) is a sub-lattice of set partitions ordered by refinement. We have the simple enumerative identity

> δ^(E=∪^@ [π]) = ∏(1 - δ^(H≤π))

> where the product is over all non-singleton kernels H, here regarded as elements of cptn(E) whose only non-singleton block is {H}. Expanding the right-hand side gives

> ∑(-1)^(|S|) δ^(⋁[S]≤π)

> where the sum is over all sets of non-singleton kernels S ⊆ ker(E), again regarded as lattice elements. Here ⋁(S) ∈ cptn(E) is algorithmically the same operation as the connected-join operation on ker(E). Expanding and factoring accordingly, this becomes

> ∑ ∑(-1)^(|S|) δ^(σ=⋁[S]) = ∑ ∏ ∑(-1)^(|K|),

> where the outer sum is over all σ ≤ π, the product is over all H ∈ σ, and the inner sum is over all connected sets of kernels K ⊆ ker(E) spanning H. For any kernel F ∈ ker(E), define

> d(F) = ∑ ∏ ∑(-1)^(|K|),

> where the outer sum is over all clutter partitions σ ∈ cptn(F), and where the product and inner sum are as before. Letting π be the set partition of E whose only non-singleton block is {F}, we have shown that

> d(F) = δ^(E=∪^@ [π]) = δ^(|F|=1).

> Hence our theorized expansion does indeed satisfy the defining identity of μ. ☐

Note that it is sufficient in the preceding theorem and proof, to consider only connected sets of *subset-minimal* non-singleton kernels; and it is often practical to do so. The hypergraph (E,minker(E)) whose edges are minimal non-singleton kernels, is also of some interest. The well-known Mobius function of a hypergraph is defined on the lattice of connected set partitions, and in this context an element of Swell(minker(E)) may be called a *pseudo-kernel*. In comparison however, our invariant μ, which is defined on essentially all clutters, seems to be vastly more interesting; we do not know if it has been studied before.

## Additional Considerations

A **semi-clutter** is any anti-chain of subsets E ⊆ 2^(V). For each finite set S, let K(S) be the set of semi-clutters spanning S. A **species** [2] is an endo-functor on the category of finite sets and bijections; so here we have defined a species of semi-clutters. The compound semi-clutter of a decomposition R(R1,...,Rk), as defined by Billera [1], is obtained as a disjoint "sum" of cartesian "products". Interpreted in the language of species-theory, this is a certain natural transformation

- com : K ⊙ K → K,

where ⊙ denotes the composition operation on species, a generalization of composition of exponential formal power series. Let C(S) be the set of (connected) clutters spanning S; let T(S) be the set {{S}} containing only the maximal clutter on S; and let P(S) be the set of clutters having no expression as a compound of a proper decomposition (i.e. P is the species of "prime" clutters). Billera's main Theorem attributed to Shapley, establishing a unique reduced compound representation, is itself a species of decompositions,

- com(T ⊙ P + P ⊙ K) = C.

From this it is evident that K = 1 ⊙ C can ultimately be reduced to a (nested) compound expression using only trivial and prime clutters. Hence the problem of enumerating semi-clutters on a vertex set is only as interesting as the problem of constructing, for any (connected) clutter, its "maximal proper committees". Which is the non-trivial solution of [1], for the enumeration of prime clutters considered. This is a particularly interesting application of formal species.

## References

\[1\] [Louis J. Billera](http://www.math.cornell.edu/~billera/), *On the Composition and Decomposition of Clutters.* J. Combinatorial Theory 11, 234-245 (1971).

\[2\] André Joyal. *Une théorie combinatoire des séries formelles.* Advances in Mathematics 42, 1-82 (1981).