Matching algebras and their Dunkl subalgebras
math.CO, math.AC
Submitted: 2026-09-28
Updated: 2026-11-01
Comments: 32 pages. Produced using GPT-5.6 based on third author's notes; significantly edited and fully proofread. v3 simplifies (and details) some proofs in Section 5 (no more ear-decomposition) and improves references in Section 4. Comments are welcome!
License: http://creativecommons.org/publicdomain/zero/1.0/
The gist: For a finite simple graph G = (V, E), we consider the quotient algebra M(G) of the polynomial ring in the variables u e (for e in E) by the ideal generated by all products u e u f for non-disjoint…
Terminology
Abstract
For a finite simple graph G = (V, E), we consider the quotient algebra M(G) of the polynomial ring in the variables u e (for e in E) by the ideal generated by all products u e u f for non-disjoint edges e and f (including all squares u e squared). This quotient is called the matching algebra of G, since it has a basis indexed by the matchings of G. In this quotient, we define a subalgebra D(G) generated by the signed incidence sums θ v= sum e=(v,w) u e-sum e=(w,v) u e for all v in V (where all edges of G are oriented arbitrarily); we call this the Dunkl matching algebra. We show that, as a graded vector space, D(G) is dual to the span of all polynomials p M = product(i,j) in M (x i - x j), where M ranges over all matchings of G. For the complete graph K n, the latter span is a direct sum of two-row Specht modules (one in each degree); thus its Hilbert series is that of the Catalan triangle, and, in characteristic zero, the Dunkl matching algebra can be presented by linear and quadratic relations. For arbitrary graphs, we formulate the saturation problem of deciding when the selected matching Specht generators p M in a given degree k span the full two-row Specht module S(n-k,k). We show that saturation in degree k forces k-connectivity, that saturation in degree 2 is equivalent to 2-connectivity, and that k-linked graphs are saturated in degree k. We also prove saturation in every possible degree whenever the complement of G is a matching. We show that the Dunkl matching algebra equals the full matching algebra exactly for forests, and give an explicit Hilbert series formula for unicyclic graphs.
Sources
- The Graph Algebra I: Representation-Theoretic Structure
- Conjectures on the reduced Kronecker coefficients
- The Lefschetz property for an algebra defined by matchings
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality