# Contraction lattice

## Recap

In the previous section Coverings, we introduced the idea of a **quiver covering**. Starting from a single quiver \(\quiver{Q}\) we considered the **contraction order** of \(\quiver{Q}\), whose elements are **contracted quivers** in which sets of vertices of \(\quiver{Q}\) are identified with one another. In this section we will develop this idea further, turning the contraction order into a **contraction lattice**, and study the structure of this lattice for some of the basic transitive quivers. We will also outline the connections of this lattice with group theory.

## Contraction sets and terms

Let's start with the quiver \(\bindCards{\subSize{\squareQuiver }{2}}{\rform{\card{r}},\bform{\card{b}}}\), shown below:

The contraction order for this quiver is shown below, where each contracted quiver is labeled with the corresponding **contraction set**, which we will define shortly:

A **contraction set** \(\sym{S}\) expresses a contraction of the original quiver in terms of a disjoint union of **contraction terms** \(\sym{T}_{\sym{i}}\):

Each term \(\sym{T}_{\sym{i}}\) represents a set of vertices that are contracted together. For example, the contracted quiver on the right is specified by the contraction set \(\contractionSum{\contractionProduct{\vert{E}\contractionProductSymbol \vert{S}}\contractionSumSymbol \contractionProduct{\vert{N}\contractionProductSymbol \vert{W}}}\), which consists of the disjoint contraction terms \(\contractionProduct{\vert{E}\contractionProductSymbol \vert{S}}\) and \(\contractionProduct{\vert{N}\contractionProductSymbol \vert{W}}\).

## Visualizing contractions

We'll introduce three ways to visualize the individual contracted quivers in the contraction lattice. To illustrate these visualizations, we'll use the same contractions of \(\bindCards{\subSize{\squareQuiver }{2}}{\rform{\card{r}},\bform{\card{b}}}\) that we introduced above:

The **clique visualization** depicts each contraction term as a clique of interconnected vertices. The **color visualization** draws vertices belonging to the same contraction term using distinct colors (note these colors have no connection to the colors of the cardinals), and uses white for vertices that are left uncontracted. The **graph visualization** shows the contracted graphs directly.

## Lattice structure

We defined the contraction order to be the partially ordered set of **contracted quivers** of some original quiver \(\quiver{Q}\). Next we will show how to to attach the structure of an **order-theoretic lattice** to this poset, which we'll call the **contraction lattice** of \(\quiver{Q}\), written \(\contractionLattice{\quiver{Q}}\).

#### Lattices

First we give a superficial summary of lattices, but we recommend reading additional material about lattices to make the most of this section.

A lattice is a poset with two additional binary operations, known as \(meet\) \(\latticeMeetSymbol\) and **join** \(\latticeJoinSymbol\). These operations distribute over each other, and play a role analogous to intersection and union of sets – in particular the subsets of a set \(\sym{X}\) form a lattice in which \(\latticeElement{A}\latticeMeetSymbol \latticeElement{B}\defEqualSymbol \latticeElement{A}\setIntersectionSymbol \latticeElement{B}\), \(\latticeElement{A}\latticeJoinSymbol \latticeElement{B}\defEqualSymbol \latticeElement{A}\setUnionSymbol \latticeElement{B}\), and \(\latticeElement{A} \le \latticeElement{B}\iff \latticeElement{A} \subseteq \latticeElement{B}\). A **bounded lattice** is a lattice with two distinguished elements called **top** \(\latticeTop\) and **bottom** \(\latticeBottom\), which are respectively greater than and less than all other elements, and serve as the identity for meet and join respectively.

#### Contractions as equivalence relations

Recall that \(\path{R}\) is a contraction quiver of \(\quiver{Q}\) if the vertices of \(\path{R}\) are contractions of vertices of \(\quiver{Q}\) that preserve the local uniqueness property. We can then see \(\path{R}\) as being uniquely specified by an equivalence relation on the vertices of \(\quiver{Q}\). We’ll write this relation as \(\isContractedIn{\vert{u}}{\vert{v}}{\quiver{R}}\), which is the statement that vertices \(\vert{u},\vert{v}\) of \(\quiver{Q}\) are considered contracted together in \(\quiver{R}\).

A little thought will reveal that a contraction \(\quiver{R}\) covers another contraction \(\quiver{S}\), written \(\quiver{R}\coversSymbol \quiver{S}\) (or in lattice terminology \(\quiver{R}\latticeGreaterEqualSymbol \quiver{S}\)) if and only if the relation for \(\quiver{R}\) is a **refinement** of the relation for \(\quiver{S}\):

(Note that we use the word "cover" here in the usual sense of a quiver covering, not in the lattice-theoretic sense of a cover, which has a different meaning.)

Ok, we've expressed the elements of the contraction order in terms of equivalence relations on sets, with the partial order induced by refinement of equivalence relations. The **finest** equivalence relation regards all vertices as distinct, corresponding to the **uncontraction** \(\quiver{Q}\), and the **coarsest** equivalence relation regards all vertices as contracted, corresponding to the **complete contraction**, given by a bouquet quiver with the same cardinals as \(\quiver{Q}\). These serve as the top and bottom of the contraction order: \(\latticeTop = \quiver{Q},\latticeBottom = \bouquetQuiver{\sym{k}}\).

#### Topped intersection structure

We now show that the set of vertex equivalence relations describing valid quiver contractions form a subset of the powerset of the vertices, closed under intersection. A set of this form is called a **topped intersection structure**, and automatically gives this set the structure of a **bounded lattice**. The meet and join are defined as you would expect: the meet of two relations corresponds to the finest relation that is still coarser than both, and the join of two relations gives the coarsest relation that still is finer than both.

First, we show that if we have two quiver contraction equivalence relations \(\contractedRelation{\quiver{R}},\contractedRelation{\quiver{S}}\), the set-theoretic intersection of these two relations (as subsets of the powerset) \(\contractedRelation{\quiver{R} \, \quiver{S}}\defEqualSymbol \contractedRelation{\quiver{R}}\setIntersectionSymbol \contractedRelation{\quiver{S}}\) is again an equivalence relation. This is straightforward:

\[ \begin{aligned} \paren{\isContractedIn{\vert{u}}{\vert{v}}{\quiver{R} \, \quiver{S}}}\andSymbol \paren{\isContractedIn{\vert{v}}{\vert{w}}{\quiver{R} \, \quiver{S}}} & \implies \paren{\isContractedIn{\vert{u}}{\vert{v}}{\quiver{R}}}\andSymbol \paren{\isContractedIn{\vert{u}}{\vert{v}}{\quiver{R}}}\andSymbol \paren{\isContractedIn{\vert{v}}{\vert{w}}{\quiver{S}}}\andSymbol \paren{\isContractedIn{\vert{v}}{\vert{w}}{\quiver{S}}}\\ & \implies \paren{\isContractedIn{\vert{u}}{\vert{w}}{\quiver{R}}}\andSymbol \paren{\isContractedIn{\vert{u}}{\vert{w}}{\quiver{S}}}\\ & \implies \isContractedIn{\vert{u}}{\vert{w}}{\quiver{R} \, \quiver{S}}\\ \end{aligned} \]It remains to be shown that this equivalence relation corresponds to a *quiver* contraction, meaning that it preserves LU. We use proof by contradiction: assume that we have a violation of LU witnessed by \(\tde{\vert{u}}{\vert{v}}{\card{c}},\tde{\vert{u}}{\vert{w}}{\card{c}},\isNotContractedIn{\vert{v}}{\vert{w}}{\quiver{R} \, \quiver{S}}\), where \(\vert{u},\vert{v},\vert{w}\) are arbitrary representatives of equivalence classes in the relation \(\contractedRelation{\quiver{R} \, \quiver{S}}\). Since \(\contractedRelation{\quiver{R}}\) and \(\contractedRelation{\quiver{S}}\) both **do** correspond to quiver contractions, we must have both \(\isContractedIn{\vert{v}}{\vert{w}}{\quiver{R}}\) and \(\isContractedIn{\vert{v}}{\vert{w}}{\quiver{S}}\) to *prevent* these being witnesses to violation of LU in \(\quiver{R}\) and \(\quiver{S}\) respectively. But this implies that \(\isContractedIn{\vert{v}}{\vert{w}}{\quiver{R} \, \quiver{S}}\) by definition, a contradiction.

#### Intuition

In terms of contractions, we can provide an intuitive summary of this situation as follows:

the meet \(\quiver{R}\latticeMeetSymbol \quiver{S}\) of two contracted quivers gives the contracted quiver that performs all the vertex contractions present in either, as well as the minimum number of additional contractions that is required to recover LU. In other words, the “minimal amount of contraction” that will unify both quivers.

the join \(\quiver{R}\latticeJoinSymbol \quiver{S}\) of two contracted quivers gives the contracted quiver that has undergone as

*much*contraction as possible that is consistent with either of them: any additional contractions would contract pairs of vertices that are*not*contracted in one or the other.

## Minimal contraction sets

We now describe a simple algorithm to find the **minimal contraction sets** of a quiver \(\quiver{Q}\). These are “minimal” in the sense that they are *forced* by a contraction of only two vertices. We'll write this set as \(\minimalContractionSets(\quiver{Q})\), and the corresponding contracted quivers as \(\minimalContractions(\quiver{Q})\).

The algorithm starts by enumerating the set of all possible contaction terms containing two distinct vertices. Each 2-term serves as a "seed" for calculating a minimal contraction set that preserves local uniqueness (abbreviated LU). We first contract the vertices of the original quiver using the seed 2-term, and then test if this produces any duplicate incoming or outgoing cardinals, as these indicate a violation of LU for one or more cardinals. If there are no duplicates, we are done, and have a new minimal contraction set containing just that single 2-term, and we can move on to the next candidate term.

If not, we "chase" all duplicate incoming or outgoing cardinals, and so obtain one or more additional 2-terms that must be contracted to re-establish the LU. This chasing process might have to repeat several times, since these additional contraction terms will eliminate the original violations of LU but could introduce new violations for the new terms. When we finally obtain a new set of contraction terms that does not introduce any new LU violations, we are done, and we have a minimal contraction set, and can proceed to the next candidate pair.

#### Example

We'll use \(\bindSize{\squareQuiver }{2,3}\) to illustrate this process:

Here we show a seed term \(\contractionProduct{1\contractionProductSymbol 2}\) and the successive steps of the "growing" of the seed, each time chasing outgoing \(\rform{\card{r}}\)-duplicates:

Here we show the sequence for a different seed term \(\contractionProduct{1\contractionProductSymbol 3}\):

The sequence for \(\contractionProduct{2\contractionProductSymbol 3}\):

Notice that if we start at the seed \(\contractionProduct{4\contractionProductSymbol 5}\), we obtain the same final contraction:

With a little thought it becomes clear that we will grow the same contraction set when starting from *any* of its terms. This implies that our enumeration algorithm can avoid this redundancy by skipping any candidate 2-terms that have already appeared as a 2-term of any previously generated contraction set.

## Some simple minimal contractions

To gain intuition, we'll explore the minimal contraction sets \(\minimalContractionSets(\quiver{Q})\) for the line, cycle, square, and square tori quivers. These will turn out to be straightforward to understand, and in fact will give us a good initial understanding of the nature of the contraction lattices for these particular quivers.

### Cycle quiver

Here we show \(\minimalContractionSets(\subSize{\cycleQuiver }{12})\), using color visualization, and below each, the corresponding minimal contracted quivers \(\minimalContractions(\subSize{\cycleQuiver }{12})\):

We've also labeled each of the contracted quivers with its "closed form", that is, a named quiver that is isomoprhic to the contracted quiver. These are the cycle quivers whose size consists of prime power divisors of 12, plus the "degenerate prime" \(\subSize{\cycleQuiver }{1}\). This turns out to be true for the minimal contraction sets of \(\subSize{\cycleQuiver }{\sym{n}}\) for arbitrary \(\sym{n}\), yielding the theorem:

\[ \minimalContractions(\subSize{\cycleQuiver }{\sym{n}}) = \setConstructor{\subSize{\cycleQuiver }{\power{\sym{p}}{\sym{m}}}}{\elemOf{\sym{m}}{\mathbb{N}^+},\elemOf{\sym{p}}{\mathbb{P}},\power{\sym{p}}{\sym{m}}\dividesSymbol \sym{n}}\setUnionSymbol \list{\subSize{\cycleQuiver }{1}} \]Here \(\mathbb{P}\) stands for the domain of the prime numbers.

### Line quiver

Here we show \(\minimalContractionSets(\subSize{\lineQuiver }{7})\):

The minimal contractions here the ways to glue the two ends of the line together with more or less overlap, yielding cycle quivers. Again, the pattern generalizes, yielding the following theorem:

\[ \minimalContractions(\subSize{\lineQuiver }{\sym{n}}) = \setConstructor{\subSize{\cycleQuiver }{\sym{i}}}{1 \le \sym{i}<\sym{n}} \]### Square quiver

We'll start with \(\bindSize{\squareQuiver }{3,2}\), the example we worked through earlier:

Here is \(\minimalContractionSets(\bindSize{\squareQuiver }{3,2})\):

Notice that the first 5 contractions have intuitive interpretations. The \(1^{\textrm{st}}\), \(2^{\textrm{nd}}\) and \(5^{\textrm{th}}\) have "rolled up" the square quiver to form toroidal lattices in either the \(\rform{\card{r}}\) or \(\bform{\card{b}}\) axis. The \(3^{\textrm{rd}}\) and \(4^{\textrm{th}}\) have "projected" the 2D square lattice into a 1D lattice with the two possibily "parities". To explain the final two contractions, we will consider the larger example of \(\bindSize{\squareQuiver }{3,3}:\)

The twelve generating contraction sets are shown below using color visualization:

As before, we obtain several torodial contractions and two linear contractions. A little thought will see that we can compose the remaining, mysterious contractions with each other to obtain sheared toroidal contractions with shear factors of \(1\) and \(-1\) along either the \(\rform{\card{r}}\) or \(\bform{\card{b}}\) axes.

### Square tori

Earlier, we saw that a line quiver contracted to cycle quivers, which themselves contracted to other cycle quivers according to their prime power factors. Similarly, the square quiver contracted to line quivers and (possibly sheared) square tori, which are the 2D analogues of the cycle quivers. So do the square tori contract to other square tori?

To answer this question, we compute the minimal contractions for some small square tori:

The answer here is a provisional yes. Eliding cardinal assingments for brevity, we have the following closed forms, given in the same order as the above diagrams:

\[ \begin{aligned} \minimalContractions(\bindSize{\toroidalModifier{\squareQuiver }}{3,3}) &= \list{\bindSize{\lineQuiver }{3},\bindSize{\lineQuiver }{3},\bindSize{\toroidalModifier{\squareQuiver }}{3,1},\bindSize{\toroidalModifier{\squareQuiver }}{1,3}}\\ \minimalContractions(\bindSize{\toroidalModifier{\squareQuiver }}{3,4}) &= \list{\bindSize{\cycleQuiver }{1},\bindSize{\toroidalModifier{\squareQuiver }}{1,2},\bindSize{\toroidalModifier{\squareQuiver }}{3,1},\bindSize{\toroidalModifier{\squareQuiver }}{2,4},\bindSize{\toroidalModifier{\squareQuiver }}{3,2}}\\ \minimalContractions(\bindSize{\toroidalModifier{\squareQuiver }}{4,4}) &= \list{\bindSize{\cycleQuiver }{4},\bindSize{\toroidalModifier{\squareQuiver }}{2_1,2},\bindSize{\toroidalModifier{\squareQuiver }}{2,2_1},\bindSize{\toroidalModifier{\squareQuiver }}{4,1},\bindSize{\toroidalModifier{\squareQuiver }}{1,4},\bindSize{\toroidalModifier{\squareQuiver }}{4,2},\bindSize{\toroidalModifier{\squareQuiver }}{2,4},\bindSize{\toroidalModifier{\squareQuiver }}{2_2,2}}\\ \end{aligned} \]## Obtaining the contraction lattice

Having obtained the set of minimal contraction sets for a quiver, how do we go about generating the entire contraction lattice?

To gain intuition for this problem, let's look at the lattice for the quiver \(\bindSize{\squareQuiver }{2,3}\) we looked at initially. Here we highlight the vertices that correspond to the minimal contraction sets:

The minimal contractions here seem to be precisely the elements that are covered by a *single* other element. Lattice elements with this property are known as **meet-irreducible** in order theory. Meet-irreducible elements have the further property that for complete lattices, *every* element can be expressed as the meet of meet-irreducible elements (although not necessarily in a unique way).

The non-uniqueness of this decomposition can be seen in the example above. The rightmost element on the third row can be formed by taking the meet of any 2 of its 3 parents (or all three). The situation can be even more complicated: the left element on the penultimate row has 4 meet-irreducible parents. There are 5 ways of taking the meet of 2 of these parents to form it, but there is *also* 1 way of taking the meet of 2 of its parents (the left 2) that does *not* form it. Taking the meet of any 3 of its parents is sufficient to form it, however.

Nevertheless, this connection with meet-irreducibility suggests a plain if inelegant way generate all other contraction sets: we can form all possible sums of the meet irreducible contraction sets. This corresponds to forming a valid contraction \(\quiver{R}\coveredBySymbol \quiver{Q}\) as the meet of every minimal contraction generated by all pairs of contracted vertices in \(\quiver{R}\).