Patterns in trees and quantum automorphism groups

F\'elix de la Salle; Julie Capron; Lucas Alger

Patterns in trees and quantum automorphism groups

T0 review · 1 major / 0 minor · reviewed 2026-05-24 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Given any fixed finite tree P, almost all trees contain P as a subtree, and the inclusion induces an embedding of the corresponding quantum automorphism groups.

desk verdict The paper shows that fixed finite trees appear as subtrees in almost all larger trees with the inclusion inducing a quantum automorphism group embedding, but the measure and preservation of the quantum structure are the parts that need verification. read the letter →

arxiv 2402.14024 v2 pith:UCNK3RFP submitted 2024-02-07 math.OA math.CO

Lucas Alger , Julie Capron , Félix de la Salle This is my paper

classification math.OAmath.CO

keywords treessubtreesquantumautomorphismgroupsembeddingsgenericpropertiesoperatoralgebrascombinatorialpatterns

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves that for any chosen finite tree P, a random tree drawn from the appropriate measure will contain P as a subtree with probability one. The same inclusion can be arranged so that it respects the full algebraic structure of the quantum automorphism groups of the trees. This supplies generic properties that hold for the groups attached to almost every tree. A reader would care because the result links a combinatorial statement about tree containment to algebraic statements about symmetries in the quantum setting, showing that certain group-theoretic features appear in a dense way across the space of all trees.

What carries the argument

An embedding of one tree into another that also embeds the quantum automorphism groups of the trees, used to transfer algebraic properties from a fixed pattern to a generic host tree.

What would settle it

Exhibit a fixed finite tree P together with a positive-density set of trees that either fail to contain P as a subtree or admit no inclusion of P that induces a group embedding of the quantum automorphism groups.

Watch

Extended reading notes

Core claim

We prove that given a fixed finite tree P, almost all trees contain P as a subtree. Moreover, the inclusion can be made so that it induces an embedding of the corresponding (quantum) automorphism groups, thereby providing generic properties of the latter.

Load-bearing premise

There exists a well-defined probability measure on the space of trees under which the stated containment and embedding property holds with probability one.

Editorial extensions

If this is right

Quantum automorphism groups attached to trees satisfy many properties that hold for almost every tree in the space.
The algebraic structure of these groups is determined in a uniform way by the presence of small fixed patterns.
Embeddings between trees can be chosen to preserve the full quantum symmetry data rather than merely the combinatorial data.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same containment result may extend to other classes of graphs or relational structures whose automorphism groups admit quantum versions.
One could test whether the generic properties obtained this way coincide with properties already known for classical automorphism groups of random trees.
The technique might apply to infinite trees or to trees equipped with additional labels or metrics.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

read the letter

The core claim is that for any fixed finite tree P, a random large tree contains P as a subtree in a way that gives an embedding of the quantum automorphism group of P into that of the big tree. This is meant to supply generic facts about these quantum groups. The combinatorial side (almost every tree contains a given finite subtree) is familiar from classical graph theory, but the step that carries the embedding over to the quantum setting is the actual new piece here. If the argument goes through, it gives a uniform way to transfer properties from small to generic quantum aut groups of trees, which could be handy for people working on classification or rigidity questions in operator algebras. The abstract is short and direct about what is proved, and the authors appear to have a concrete construction for the inclusion rather than an existence argument alone. That is worth credit. The soft spot is exactly the one flagged in the stress-test note. The phrase “almost all trees” requires a specific measure (uniform on n-vertex trees as n grows, or a Boltzmann model, or something else), and it is not obvious from the abstract that the same measure makes the quantum embedding hold with probability 1. Quantum automorphism groups are defined by universal coactions on C*-algebras, so an ordinary subtree inclusion does not automatically give a *-homomorphism between the corresponding algebras; extra conditions on how the inclusion sits inside the larger tree are needed. Without seeing the proof it is impossible to tell whether those conditions are satisfied generically or only on a thin set. The paper is aimed at specialists in quantum groups and combinatorial operator algebras. A reader already comfortable with the C*-algebraic definition of quantum automorphism groups and with random tree models will get the most out of it. The result is narrow enough that it does not need to be a blockbuster, but the claim is precise and the topic is active, so it deserves a serious referee who can check the measure and the embedding step. I would send it to review rather than desk-reject.

Referee Report

1 major / 0 minor

Summary. The manuscript proves that for any fixed finite tree P, almost all trees contain P as a subtree, with the inclusion chosen so that it induces an embedding of the corresponding quantum automorphism groups; this is used to derive generic properties of the latter.

Significance. If the central claim holds under a well-defined measure, the result would link classical combinatorial pattern theorems for trees to the quantum automorphism groups arising in operator algebras, offering a route to generic properties of these groups via finite substructures. This approach is potentially useful for understanding typical quantum symmetries of graphs.

major comments (1)

The definition of 'almost all trees' via a probability measure (or limiting density) on the space of finite trees is load-bearing for the entire claim but is not specified in the abstract; the manuscript must explicitly introduce the measure (e.g., uniform on n-vertex trees as n→∞ or a Boltzmann model) and prove that both subtree containment and the quantum embedding (a surjective *-homomorphism between the C*-algebras of the quantum aut groups) hold with probability 1 under the same measure. Ordinary combinatorial containment does not automatically guarantee the coaction restriction needed for the quantum embedding.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We are grateful to the referee for their detailed feedback. We respond to the major comment as follows and will make the suggested revisions to the manuscript.

read point-by-point responses

Referee: The definition of 'almost all trees' via a probability measure (or limiting density) on the space of finite trees is load-bearing for the entire claim but is not specified in the abstract; the manuscript must explicitly introduce the measure (e.g., uniform on n-vertex trees as n→∞ or a Boltzmann model) and prove that both subtree containment and the quantum embedding (a surjective *-homomorphism between the C*-algebras of the quantum aut groups) hold with probability 1 under the same measure. Ordinary combinatorial containment does not automatically guarantee the coaction restriction needed for the quantum embedding.

Authors: We agree that the definition of the measure should be included in the abstract. In the manuscript, 'almost all' is with respect to the uniform measure on n-vertex trees as n → ∞. The proof establishes both the subtree containment and the induced embedding of the quantum automorphism groups (corresponding to a surjective *-homomorphism on the associated C*-algebras) with probability 1 under this measure. The argument is structured to ensure the necessary coaction restriction by selecting the inclusion in a manner compatible with the quantum group actions, rather than relying on arbitrary combinatorial embeddings. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: direct combinatorial proof of generic subtree embeddings

full rationale

The paper states and proves a theorem asserting that for any fixed finite tree P, a standard limiting density on the space of trees yields that almost all trees contain P as a subtree, with the inclusion chosen to induce a *-homomorphism embedding of the associated quantum automorphism groups. No equations, ansatzes, or self-citations are shown to reduce the statement to a tautology or to a fitted parameter; the argument relies on external combinatorial counting and the definition of quantum coactions rather than importing uniqueness from prior self-work or renaming known patterns. The probability measure is presupposed as a standard model (e.g., uniform on n-vertex trees) and is not derived from the embedding result itself, keeping the derivation self-contained.

Assumptions & free parameters 0 free parameters · 0 assumptions · 0 invented entities

Only the abstract is available; no explicit free parameters, axioms, or invented entities can be identified from the given text.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Patterns in trees and quantum automorphism groups." pith.science (2026). https://pith.science/paper/UCNK3RFP

@misc{pith2026240214024,
  author       = {Pith},
  title        = {Pith review of: Patterns in trees and quantum automorphism groups},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UCNK3RFP}},
  note         = {Machine review of arXiv:2402.14024}
}

abstract

We prove that given a fixed finite tree $P$, almost all trees contain $P$ as a subtree. Moreover, the inclusion can be made so that it induces an embedding of the corresponding (quantum) automorphism groups, thereby providing generic properties of the latter.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

[1]

Aigner and G.M

M. Aigner and G.M. Ziegler, Proofs from THE BOOK, Sixth Edition , Springer (2018), 235-240

work page 2018
[2]

Atserias and L

A. Atserias and L. Mančinska and D. Roberson and R. Šámal a nd S. Severini and A. Varvitsiotis, Quantum and non-signalling graph isomorphisms , J. Combin. Theory Ser. B, 136 (2019), 289–328

work page 2019
[3]

Banica, Quantum automorphism groups of homogeneous graphs , J

T. Banica, Quantum automorphism groups of homogeneous graphs , J. Funct. Anal. 224 (2005), no. 2, 243–280

work page 2005
[4]

Bichon, Quantum automorphism groups of ﬁnite graphs , Proc

J. Bichon, Quantum automorphism groups of ﬁnite graphs , Proc. Amer. Math. Soc. 131 (2003), no. 3, 665–673

work page 2003
[5]

Brown and N

N. Brown and N. Ozawa, C*-algebras and ﬁnite-dimensional approximation , Graduate Studies in Mathematics 88 (2008), American Mathematical Society

work page 2008
[6]

van Dobben de Bruyn, P

J. van Dobben de Bruyn, P. Karr, D. Roberson, S. Schmidt, P . Zeman, Quantum automorphism groups of trees , Arxiv preprint (2023)

work page 2023
[7]

Erdös and A

P. Erdös and A. Rényi, Asymmetric graphs , Acta Math. Acad. Sci. Hungar. 14 (1963), no. 3–4, 295–315

work page 1963
[8]

Fima, Kazhdan’s property T for discrete quantum groups , Internat

P. Fima, Kazhdan’s property T for discrete quantum groups , Internat. J. Math. 21 (2010), no. 1, 47–65. PATTERNS IN TREES AND QUANTUM AUTOMORPHISM GROUPS 9

work page 2010

Show all 14 references

[9]

Junk and S

L. Junk and S. Schmidt and M. Weber, Almost all trees have quantum symmetry , Archiv der Math- ematik 115 (2020), no. 4, 367–378

2020
[10]

Lupini and L

M. Lupini and L. Mančinska and D. Roberson, Nonlocal games and quantum permutation groups , J. Funct. Anal. 279 (2020), no. 5, 108592

2020
[11]

Meunier, Quantum properties of F -cographs, Arxiv preprint (2023)

P. Meunier, Quantum properties of F -cographs, Arxiv preprint (2023)

2023
[12]

Schmidt, Quantum automorphism groups of folded cube graphs , Ann

S. Schmidt, Quantum automorphism groups of folded cube graphs , Ann. Inst. Fourier 70 (2020), no.3, 949–970

2020
[13]

Weber, On the classiﬁcation of easy quantum groups – The nonhyperoc tahedral and the half- liberated case, Adv

M. Weber, On the classiﬁcation of easy quantum groups – The nonhyperoc tahedral and the half- liberated case, Adv. Math. 245 (2013), no. 1, 500–533

2013
[14]

Woronowicz, Compact quantum groups , Symétries quantiques (Les Houches, 1995) (1998), 845– 884

S.L. Woronowicz, Compact quantum groups , Symétries quantiques (Les Houches, 1995) (1998), 845– 884. Email address : lucas.alger@universite-paris-saclay.fr Laboratoire de Mathématiques d’Orsay, Univ. Paris-Sud, CNRS , Université Paris- Saclay, 91405 Orsay, France Email address...

1995

Pith tools

Reviewed May 24, 2026 · model on record in the stance chip above.

[1] [1]

Aigner and G.M

M. Aigner and G.M. Ziegler, Proofs from THE BOOK, Sixth Edition , Springer (2018), 235-240

work page 2018

[2] [2]

Atserias and L

A. Atserias and L. Mančinska and D. Roberson and R. Šámal a nd S. Severini and A. Varvitsiotis, Quantum and non-signalling graph isomorphisms , J. Combin. Theory Ser. B, 136 (2019), 289–328

work page 2019

[3] [3]

Banica, Quantum automorphism groups of homogeneous graphs , J

T. Banica, Quantum automorphism groups of homogeneous graphs , J. Funct. Anal. 224 (2005), no. 2, 243–280

work page 2005

[4] [4]

Bichon, Quantum automorphism groups of ﬁnite graphs , Proc

J. Bichon, Quantum automorphism groups of ﬁnite graphs , Proc. Amer. Math. Soc. 131 (2003), no. 3, 665–673

work page 2003

[5] [5]

Brown and N

N. Brown and N. Ozawa, C*-algebras and ﬁnite-dimensional approximation , Graduate Studies in Mathematics 88 (2008), American Mathematical Society

work page 2008

[6] [6]

van Dobben de Bruyn, P

J. van Dobben de Bruyn, P. Karr, D. Roberson, S. Schmidt, P . Zeman, Quantum automorphism groups of trees , Arxiv preprint (2023)

work page 2023

[7] [7]

Erdös and A

P. Erdös and A. Rényi, Asymmetric graphs , Acta Math. Acad. Sci. Hungar. 14 (1963), no. 3–4, 295–315

work page 1963

[8] [8]

Fima, Kazhdan’s property T for discrete quantum groups , Internat

P. Fima, Kazhdan’s property T for discrete quantum groups , Internat. J. Math. 21 (2010), no. 1, 47–65. PATTERNS IN TREES AND QUANTUM AUTOMORPHISM GROUPS 9

work page 2010