Contraction lattices #
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.
Note: this section is largely incomplete. See here for more information.
Contraction sets and terms #
Let's start with the quiver \( \bindCards{\subSize{\squareQuiver }{2}}{\reFo{\card{r}},\blFo{\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}} \):
\[ \sym{S} = \CoSuFo{\sym{T}_1 \coSuFo \sym{T}_2 \coSuFo \elSy \coSuFo \sym{T}_{\sym{n}}} \]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 \( \CoSuFo{\CoPrFo{\vert{E} \coPrFo \vert{S}} \coSuFo \CoPrFo{\vert{N} \coPrFo \vert{W}}} \), which consists of the disjoint contraction terms \( \CoPrFo{\vert{E} \coPrFo \vert{S}} \) and \( \CoPrFo{\vert{N} \coPrFo \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}}{\reFo{\card{r}},\blFo{\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 \( \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 \( \mathbf{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 \( \latticeElementSymbol{A}\latticeMeetSymbol \latticeElementSymbol{B}\defEqualSymbol \latticeElementSymbol{A}\setIntersectionSymbol \latticeElementSymbol{B} \), \( \latticeElementSymbol{A}\latticeJoinSymbol \latticeElementSymbol{B}\defEqualSymbol \latticeElementSymbol{A}\setUnionSymbol \latticeElementSymbol{B} \), and \( \latticeElementSymbol{A} \le \latticeElementSymbol{B}\iff \latticeElementSymbol{A} \subseteq \latticeElementSymbol{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 \( \IsCoFoⅡ{\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 \( \CoFo{\quiver{R}}{\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} \):
\[ \CoFo{\quiver{R}}{\quiver{S}}\iff \paren{\IsCoFoⅡ{\vert{u}}{\vert{v}}{\quiver{S}}\implies \IsCoFoⅡ{\vert{u}}{\vert{v}}{\quiver{R}}} \](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 \( \CoReFo{\quiver{R}},\CoReFo{\quiver{S}} \), the set-theoretic intersection of these two relations (as subsets of the powerset) \( \CoReFo{\quiver{R} \, \quiver{S}}\defEqualSymbol \CoReFo{\quiver{R}}\setIntersectionSymbol \CoReFo{\quiver{S}} \) is again an equivalence relation. This is straightforward:
\[ \begin{aligned} \paren{\IsCoFoⅡ{\vert{u}}{\vert{v}}{\quiver{R} \, \quiver{S}}}\andSymbol \paren{\IsCoFoⅡ{\vert{v}}{\vert{w}}{\quiver{R} \, \quiver{S}}}& \implies \paren{\IsCoFoⅡ{\vert{u}}{\vert{v}}{\quiver{R}}}\andSymbol \paren{\IsCoFoⅡ{\vert{u}}{\vert{v}}{\quiver{R}}}\andSymbol \paren{\IsCoFoⅡ{\vert{v}}{\vert{w}}{\quiver{S}}}\andSymbol \paren{\IsCoFoⅡ{\vert{v}}{\vert{w}}{\quiver{S}}}\\ & \implies \paren{\IsCoFoⅡ{\vert{u}}{\vert{w}}{\quiver{R}}}\andSymbol \paren{\IsCoFoⅡ{\vert{u}}{\vert{w}}{\quiver{S}}}\\ & \implies \IsCoFoⅡ{\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}},\IsNoCoFoⅡ{\vert{v}}{\vert{w}}{\quiver{R} \, \quiver{S}} \), where \( \vert{u},\vert{v},\vert{w} \) are arbitrary representatives of equivalence classes in the relation \( \CoReFo{\quiver{R} \, \quiver{S}} \). Since \( \CoReFo{\quiver{R}} \) and \( \CoReFo{\quiver{S}} \) both do correspond to quiver contractions, we must have both \( \IsCoFoⅡ{\vert{v}}{\vert{w}}{\quiver{R}} \) and \( \IsCoFoⅡ{\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 \( \IsCoFoⅡ{\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 \( \CoPrFo{1 \coPrFo 2} \) and the successive steps of the "growing" of the seed, each time chasing outgoing \( \reFo{\card{r}} \)-duplicates:
Here we show the sequence for a different seed term \( \CoPrFo{1 \coPrFo 3} \):
The sequence for \( \CoPrFo{2 \coPrFo 3} \):
Notice that if we start at the seed \( \CoPrFo{4 \coPrFo 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}}{\poNa},\elemOf{\sym{p}}{\pr},\power{\sym{p}}{\sym{m}}\dividesSymbol \sym{n}}\setUnionSymbol \list{\subSize{\cycleQuiver }{1}} \]Here \( \pr \) 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 \( \reFo{\card{r}} \) or \( \blFo{\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 \( \reFo{\card{r}} \) or \( \blFo{\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 \( \CoByFo{\quiver{R}}{\quiver{Q}} \) as the meet of every minimal contraction generated by all pairs of contracted vertices in \( \quiver{R} \).
Cycle quiver #
The first lattice we'll examine in the most detail is the case of the cycle quiver \( \subSize{\cycleQuiver }{\sym{n}} \).
\( \subSize{\cycleQuiver }{\sym{n}} \) is the Cayley quiver of the cyclic group \( \cyclicGroup{\sym{n}} \), and we can observe a fairly straightforward connection between the contraction lattice and some elementary ideas in group theory. Specifically, we can use the fact that for Cayley quivers, quiver contractions correspond to group homomorphisms, and so the lattice of quivers we see below is in fact the lattice of subgroups of the original group.
Here we show the generating contraction sets of each \( \subSize{\cycleQuiver }{\sym{n}} \) for \( 3 \le \sym{n} \le 12 \):
Here we show the contraction lattices of each \( \subSize{\cycleQuiver }{\sym{n}} \) for \( 3 \le \sym{n} \le 12 \):
First note that the contraction lattices for prime \( \sym{n} \) are trivial, consisting only of the original lattice and the total contraction that contracts every vertex together -- reflecting the fact that cyclic groups of prime order are simple (they have no non-trivial subgroups).
For composite \( \sym{n} \), the vertices of the contraction lattice correspond to the factors of \( \sym{n} \), where the number of vertices in each contraction term gives the one factor, and the number of contraction terms gives the other factor. Consider the lattice for \( \subSize{\cycleQuiver }{12} \):
The vertices of the lattice correspond to the factorizations \( \list{\gFo{12}\times 1,\gFo{4}\times 3,\gFo{6}\times 2,\gFo{2}\times 6,\gFo{3}\times 4,\gFo{1}\times 12} \), where the gray number is the number of terms and the black number the size of each term. Chains through the lattice correspond to ordered prime factorizations, where we interpret the simultaneous contraction of disjoint sets of \( \sym{k} \) terms to correspond to the factor \( \sym{k} \). Then, for example, the leftmost chain gives the ordered factorization \( 3\times 2\times 2 \), the rightmost chain \( 2\times 2\times 3 \).
Square quiver #
