Hall algebras of graphs and rooted trees

Abstract

Hall algebras can be associated with a broad class of combinatorial structures through the theory of 2-Segal sets. In this paper, we study the Hall algebras arising from the 2-Segal sets of rooted trees, undirected graphs, and directed graphs. In each case, we establish an analogue of Green's theorem giving a twisted bialgebra structure to the Hall algebra, describe the primitive elements, and derive a presentation by generators and relations. As an application, we realize the Hall algebra of an undirected graph as the cohomology ring of a topological space. In the case of directed graphs, we introduce the Hall polynomial, defined as the Poincar{é} polynomial of the space of primitive elements. The Hall polynomial is an invariant of the underlying undirected graph which we show to be closely related to the Tutte polynomial. We furthermore give examples of graphs with equal Tutte polynomials but distinct Hall polynomials showing thus that the Hall polynomial encodes different information from that of the Tutte polynomial.

A new polynomial invariant of graphs through Hall algebras
Lucas Toury
HAL17 Sep 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsHAL
Compactness of composition operators on Hardy spaces of homogeneous rooted trees
Lei Liu, Wanxin Ma
arXiv24 Oct 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv
Dynamics of Weighted Backward Shifts on Cesàro Spaces of Rooted Trees
Xiang Chen, Meng-Huan Cheng, Liang Zhang +1
arXiv18 Sep 2026PreprintarXiv licenceFull textAnalysis & PDEs Dynamical systemsarXiv
The automorphism tower of groups acting on rooted trees
Laurent Bartholdi, Said N. Sidki
Transactions of the American Mathematical Society3 Nov 2026Peer-reviewedPublic domainFull text10 citedAlgebra & number theoryHAL
Hardy--Littlewood Maximal Operator and Two-Layer Muckenhoupt Weights on Infinite Rooted k-Ary Trees
Dachun Yang, Wen Yuan, Mingdong Zhang
arXiv11 Sep 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv

Cite

BibTeX RIS

BibTeX

@misc{toury2026hall,
  title = {{Hall algebras of graphs and rooted trees}},
  author = {Lucas Toury},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.16849},
  eprint = {2609.16849},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.16849},
}

RIS

TY  - UNPB
TI  - Hall algebras of graphs and rooted trees
AU  - Lucas Toury
PY  - 2026
DA  - 2026/09/15
PB  - arXiv
DO  - 10.48550/arxiv.2609.16849
UR  - https://arxiv.org/abs/2609.16849
AB  - Hall algebras can be associated with a broad class of combinatorial structures through the theory of 2-Segal sets. In this paper, we study the Hall algebras arising from the 2-Segal sets of rooted trees, undirected graphs, and directed graphs. In each case, we establish an analogue of Green's theorem giving a twisted bialgebra structure to the Hall algebra, describe the primitive elements, and derive a presentation by generators and relations. As an application, we realize the Hall algebra of an undirected graph as the cohomology ring of a topological space. In the case of directed graphs, we introduce the Hall polynomial, defined as the Poincar{é} polynomial of the space of primitive elements. The Hall polynomial is an invariant of the underlying undirected graph which we show to be closely related to the Tutte polynomial. We furthermore give examples of graphs with equal Tutte polynomials but distinct Hall polynomials showing thus that the Hall polynomial encodes different information from that of the Tutte polynomial.
ER  -

Abstract

Related

Cite