Measures on Cameron's treelike classes and applications to tensor categories

This paper completes the classification of measures on Cameron's elementary treelike Fraïssé classes by establishing a bijection for $n$-colored rooted binary trees that yields infinite families of novel semisimple tensor categories with superexponential growth, while simultaneously proving the nonexistence of such measures on $n$-colored and labeled tree classes for $n \geq 2$.

The Gist

Imagine you are an architect trying to build a new type of universe. In mathematics, these "universes" are called Tensor Categories. They are complex systems where you can combine objects (like Lego bricks) in specific ways, following strict rules of symmetry and logic.

For a long time, mathematicians knew how to build these universes using "standard" Lego sets (like the symmetric groups, which are just ways of shuffling items). But they wanted to build new, exotic universes that couldn't be made from standard sets. These new universes grow so fast they are called "superexponential."

This paper is the blueprint for building a massive new family of these exotic universes. Here is how the authors did it, explained simply.

1. The Building Blocks: Trees and Colors

The authors start with a very specific type of Lego set: Rooted Binary Trees.

• Imagine a family tree where every person (node) has exactly two children.
• Now, paint the "parents" (the nodes) with different colors (say, Red, Blue, Green, etc.).
• The "children" (the leaves at the bottom) are uncolored.

They call this collection of trees $\partial T_3(n)$. The goal is to find a way to assign a "weight" or a "measure" to every possible tree in this collection.

2. The "Measure": A Magical Rulebook

Think of a Measure not as a physical weight, but as a rulebook for a game.

• The Game: You take two trees and try to glue them together (amalgamate them) at a common branch.
• The Rule: The rulebook tells you exactly how much "value" or "probability" to assign to every possible way you can glue them.
• The Catch: The rules are incredibly strict. If you glue Tree A and Tree B together, the total value of the result must equal the sum of the values of all the different ways you could have glued them.

The authors discovered that for some tree classes (like trees with colored leaves), the rules are so contradictory that no valid rulebook exists. It's like trying to write a rulebook for a game where "1 + 1 = 3" is required; the game collapses. They proved this for several types of trees.

3. The Breakthrough: The "Directed Tree" Key

However, for the node-colored trees (where only the parents are colored), they found a solution!

They discovered a magical key to unlock the correct rulebook. This key is a Directed Rooted Tree with a special "Distinguished" vertex.

• Imagine you have a map of cities (nodes) connected by one-way streets (edges).
• Each street is labeled with a color (1 to $n$).
• You pick one city to be the "Star City" (the distinguished vertex).

The Magic Connection:
Every single possible valid rulebook (measure) for their tree universe corresponds one-to-one with one of these directed street maps.

• If you have $n$ colors, there are exactly $(2n + 2)^n$ different rulebooks.
• For example, if you have 2 colors, there are $(2\times2 + 2)^2 = 36$ different rulebooks.

This is a massive discovery because it turns a difficult math problem into a simple counting problem of maps.

4. Building the New Universes (Tensor Categories)

Once they have a valid rulebook (a measure), they can build a Tensor Category.

• Think of the rulebook as the "physics engine" of a new universe.
• The "objects" in this universe are the trees.
• The "gluing" (tensor product) is how these objects interact.

The authors showed that for every one of those 36 (or more) rulebooks, they can build a Semisimple Tensor Category.

• "Semisimple" means the universe is stable and well-behaved; it doesn't have "ghosts" or broken pieces.
• "Superexponential Growth" means this universe is incredibly vast. If you start with a small object and keep combining it with itself, the number of new things you can create explodes faster than you can count.

5. Why This Matters

Before this paper, we only knew a few ways to build these exotic universes. This paper says: "Look, there are actually thousands (or millions) of them, and here is exactly how to build them all."

They also proved that these new universes are truly new. You cannot build them by just stretching or interpolating the old, standard universes. They are unique, wild, and mathematically rich.

Summary Analogy

Imagine you are a chef trying to create new flavors of ice cream.

• Old Ice Cream: You only knew how to mix vanilla and chocolate (standard categories).
• The Problem: You wanted to make ice cream with flavors that didn't exist in nature (superexponential categories).
• The Failure: You tried mixing "Red Leaves" and "Blue Leaves," but the flavors canceled each other out, and you got nothing (vanishing measure rings).
• The Success: You tried mixing "Colored Parents" on a tree. You realized that for every specific road map you could draw with colored arrows, there is a unique, delicious, and stable new ice cream flavor.
• The Result: You now have a recipe book with $(2n+2)^n$ recipes, allowing you to bake an infinite variety of new, stable, and mind-bogglingly complex ice cream universes.

This paper is that recipe book.

Technical Summary

Here is a detailed technical summary of the paper "Measures on Cameron's Treelike Classes and Applications to Tensor Categories" by Thanh Can and Thomas Rüd.

1. Problem Statement and Motivation

The primary objective of this paper is to address the scarcity of concrete examples of tensor categories with superexponential growth that cannot be constructed via Deligne's interpolation of representation categories.

• Context: Deligne's theorem characterizes tensor categories with subexponential growth as representation categories of affine supergroup schemes. To find new examples outside this realm, Harman and Snowden (2022) introduced a construction based on oligomorphic groups and Fraïssé classes.
• The Core Challenge: This construction requires a measure on a Fraïssé class (a class of finite combinatorial structures satisfying specific amalgamation properties). Computing these measures is a notoriously difficult combinatorial problem.
• The Specific Gap: While measures were previously classified for uncolored trees, the classification for Cameron's treelike classes (specifically those involving node-coloring and labeling) remained incomplete. The authors aim to:
  1. Classify measures on specific treelike classes.
  2. Determine which classes admit no measures.
  3. Use these measures to construct new families of semisimple tensor categories.

2. Methodology

The authors employ a blend of model theory, combinatorics, and ring theory to solve the problem.

A. Theoretical Framework

• Fraïssé Classes & Oligomorphic Groups: They utilize the correspondence between Fraïssé classes and oligomorphic groups (groups with finitely many orbits on $n$-tuples).
• Measure Rings ($\Theta(\mathcal{F})$): Instead of computing measures directly, they compute the measure ring $\Theta(\mathcal{F})$. A measure corresponds to a ring homomorphism $\mu: \Theta(\mathcal{F}) \to \mathbb{C}$.
  • The ring is generated by formal symbols representing embeddings (specifically one-point extensions).
  • Relations in the ring arise from the amalgamation property: the measure of an embedding equals the sum of measures of its amalgamations.
• Reduction to Marked Structures: They reduce the infinite set of embeddings to a finite set of irreducible marked structures (trees with a distinguished leaf) by eliminating "separated" elements (leaves whose removal does not affect the amalgamation structure).

B. Combinatorial Analysis

The paper analyzes four specific classes of tree structures:

1. $C_nT$ and $C_nT_k$: $n$-colored trees (and those with max degree $k$).
2. $LT$: Labeled trees (with a total order on leaves).
3. $\partial T_3(n)$: Node-colored rooted binary trees (leaves are uncolored; internal nodes are colored from $\{1, \dots, n\}$).

The authors derive systems of linear and quadratic equations from the measure axioms.

• Linear equations arise from the sum of amalgamations.
• Quadratic equations arise from the commutativity of composition in the measure ring (e.g., $[T, a][T \setminus a, b] = [T, b][T \setminus b, a]$).

C. Classification via Graph Theory

For the successful case ($\partial T_3(n)$), the authors map the solutions of the measure ring equations to directed rooted trees with edge labels. They utilize properties of Directed Acyclic Graphs (DAGs) and adjacency matrices to prove the invertibility of the linear systems governing the measures, ensuring non-trivial solutions exist.

3. Key Contributions and Results

A. Non-Existence of Measures (Vanishing Rings)

The authors prove that several natural generalizations of tree structures admit no measures (their measure rings are isomorphic to the zero ring).

• Theorem 1.1 & 1.2: For $n \ge 2$, the measure rings for $n$-colored trees ($C_nT$), $n$-colored trees with bounded degree ($C_nT_k$), and labeled trees ($LT$) are all trivial ($\Theta \cong 0$).
• Significance: This highlights the extreme rigidity of the measure axioms; even slight modifications to the structure (like adding labels or specific color constraints) can force all measures to vanish.

B. Complete Classification for Node-Colored Binary Trees

The paper's main achievement is the classification of measures on $\partial T_3(n)$ (node-colored rooted binary trees).

• Theorem 1.3: There is an explicit bijection between measures on $\partial T_3(n)$ and directed rooted trees with edges labeled by $\{1, \dots, n\}$ and a distinguished vertex.
• Count: The number of distinct measures is $(2n + 2)^n$.
• Values: All measures take values in the ring $\mathbb{Z}[\frac{1}{2}]$ (dyadic rationals).
• Structure: The measure ring is isomorphic to $\mathbb{Z}[\frac{1}{2}]^{(2n+2)^n}$.

C. Induced Regular Measures on Subclasses

Since the measures on the full class $\partial T_3(n)$ are not "regular" (some embeddings map to zero), the authors identify induced subclasses where the measures become regular.

• They classify Fraïssé subclasses of $\partial T_3(n)$ based on their three-leaf substructures.
• They define $\partial T_3(n)^{\text{ord}}_I$: Subclasses where colors along any root-to-leaf path are monotonically increasing, with specific rules on repeated colors determined by a subset $I \subseteq \{1, \dots, n\}$.
• Proposition 5.19: They provide an explicit closed-form formula for the induced regular measure $\mu^I_n$ on these subclasses.

D. Construction of New Tensor Categories

Using the Harman–Snowden construction, the authors build tensor categories from these regular measures.

• Theorem 1.4: For any $n \ge 1$ and subset $I$, the category $\text{Rep}(\partial T_3(n)^{\text{ord}}_I; \mu^I_n)$ is a semisimple tensor category.
• Growth: These categories exhibit superexponential growth.
• Novelty: These categories cannot be obtained via Deligne's interpolation because the underlying oligomorphic groups do not resemble finite permutation groups.

4. Significance and Impact

1. Expansion of the Landscape: The paper significantly expands the known universe of tensor categories. It provides infinite families of semisimple tensor categories with superexponential growth, a regime that was previously difficult to access with concrete examples.
2. Methodological Rigor: The paper demonstrates a powerful method for classifying measures by reducing complex combinatorial constraints to linear algebra problems involving DAGs and adjacency matrices.
3. Boundary of Existence: By proving the non-existence of measures on $C_nT$, $C_nT_k$, and $LT$, the paper delineates the precise boundaries of where the Harman–Snowden construction is applicable, offering deep insight into the combinatorial constraints required for such measures to exist.
4. Connection to Model Theory: It strengthens the link between model theory (Fraïssé limits) and representation theory (tensor categories), showing how specific structural properties of infinite homogeneous structures dictate the existence of rich categorical invariants.

In summary, Can and Rüd have successfully completed the classification of measures on Cameron's elementary treelike classes, identified the specific structural conditions required for non-trivial measures, and leveraged these results to generate a vast new class of semisimple tensor categories that defy classical interpolation methods.