The Multiorbital Bivariate Chromatic Polynomial: A Subgroup-Lattice Refinement
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: We're looking at the paper: "The Multiorbital Bivariate Chromatic Polynomial".
Emmy: Here's the gist of the paper. The paper introduces the multiorbital bivariate chromatic polynomial to aggregate orbital bivariate chromatic polynomials over the subgroup lattice of a finite group acting on a graph, which provides a structural decomposition connecting group theory, graph structure, and element-wise actions The central structural identity is the element-wise expansion of this polynomial into a sum over group elements weighted by coefficients derived from the subgroup lattice The Core Construction The main purpose of this paper is to study the subgroup-lattice aggregation of orbital bivariate chromatic polynomials and the coefficient system induced by this aggregation The construction defines the multiorbital bivariate chromatic polynomial as a sum over all subgroups of the acting group, where each term involves an average of quotient graph polynomials Specifically, for every subgroup H ≤ G, the orbital bivariate chromatic polynomial is defined as (5) O PΓ,H (x, y):= 1/H Σ h∈H PΓ/h (x, y) The multiorbital polynomial is then defined by (6) FΓ (G; x, y):= Σ H≤G O PΓ,H (x, y) Structural Decomposition of Coefficients The element-wise representation of the multiorbital polynomial is given by (8) FΓ (G; x, y) = Σ g∈G cG (g) PΓ/g (x, y) The coefficient function cG(g) is defined as cG(g):= Σ H≤G g∈H 1/H A key structural result is that this coefficient depends only on the cyclic subgroup generated by the group element and is constant on conjugacy classes This leads to a decomposition of the polynomial into a purely group-theoretic coefficient function cG and graph-theoretic quotient polynomials PΓ/g Möbius Inversion and Probabilistic Interpretation The coefficient function cG(g) admits a natural Möbius inversion because it is the upper zeta transform of the function H ↦→ H−1 on the subgroup lattice This allows for a description of the weights in terms of subgroups rather than individual group elements Furthermore, after normalization, the coefficients define a probability distribution on G obtained by choosing a subgroup uniformly at random and then an element uniformly from that subgroup The normalized polynomial FbΓ (G; x, y) is interpreted as the expected quotient polynomial E PΓ/g (x, y) Connections to Classical Invariants The multiorbital polynomial admits several natural specializations, including a chromatic specialization where the bivariate chromatic polynomial satisfies PΛ(x, x) = χΛ(x) Under this condition, FΓ (G; x, x) = Σ g∈G cG (g) χΓ/g (x) For edgeless graphs, the polynomial simplifies to a weighted cycle-index expression given by FΓ (G; x, y) = Σ g∈G cG (g) x Orb⟨g⟩(V(Γ)) Diagonal Multiplicativity and Examples The construction yields a diagonal multiplicativity relation for disjoint unions of graphs preserved by the group action, where FΓ1⊔Γ2 (G; x, y) = Σ g∈G cG (g) PΓ1/g (x, y) PΓ2/g (x, y) The coefficient function is also compatible with conjugation, implying that if g and h are conjugate, then Γ/g is isomorphic to Γ/h An example involving the symmetric group S3 shows that the normalized polynomial FbΓ (S3; x, y) equals E PΓ/g (x, y) for the distribution derived from subgroup selection The coefficient values b cS3(e), b cS3(t), and b cS3(c) are calculated to sum to 1, confirming the probabilistic interpretation The resulting framework connects three structures: the subgroup lattice of G, the cyclic and conjugacy structure of its elements, and the graph polynomials of the corresponding quotient graphs The construction provides a bridge between these structures through the coefficient function cG(g), which depends only on ⟨g⟩ This framework is not a new orbit-counting theorem but an aggregation of existing element-wise orbital contributions over the entire subgroup lattice The resulting polynomial FΓ (G; x, y) can be viewed as the expected quotient polynomial associated with a two-stage random experiment involving subgroup and element selection References
1: I.
Ada: Averbouch, B.
Emmy: Godlin, and J.
Ada: A.
Paper summary: Ada: So, wrapping up on "The Multiorbital Bivariate Chromatic Polynomial: A Subgroup-Lattice Refinement," the authors have shown how to aggregate those orbital bivariate chromatic polynomials using this new structure. They moved from a complex sum of sums down to an element-wise expansion where the weights are determined by subgroup properties.
Emmy: It’s like they found a way to organize all those different ways you could count colorings or flows, and they showed that it's all governed by these coefficients c G g which depend only on the cyclic subgroup and conjugacy class of the element.
Kolya: So, what does this mean for the broader context of graph theory and group actions? Is this just a neat tool, or does it actually change how we think about these enumerations?
Ada: It’s more about providing a better lens. They connect three different areas: the subgroup lattice of the group, the cyclic structure of its elements, and the polynomials describing those quotient graphs <ref:2609.01866#pg3>. It provides a bridge between those structures.
Emmy: The implication is that you can study these complex graph invariants not just by looking at one element at a time, but by understanding how they are weighted across the entire subgroup structure of the acting group <ref:2609.01866#pg2>.
Kolya: I guess for someone who only cares about the practical counting, it means we have a probabilistic interpretation—the expected quotient polynomial—which is useful for modeling random processes on graphs <ref:2609.01866#pg3>.
Ada: Exactly. It’s not a new theorem, but it’s a refined way to view the existing contributions. It helps us see the relationship between group theory and graph structure much more clearly through that coefficient function c G g <ref:2609.01866#pg3>.
Conclusion: Ada: So, we've seen how they build this multiorbital polynomial by summing up orbital polynomials over all subgroups of a group acting on a graph <ref:2609.01866#pg1>.
Emmy: And they show you can reorganize that big sum into something much cleaner, an element-wise expansion where the weights depend only on the cyclic subgroup generated by each individual element <ref:2609.01866#pg2>.
Kolya: It’s essentially taking all those different ways to count things—the orbital ones—and putting them into a structure dictated by how the group elements move around in terms of their cyclic subgroups and conjugacy classes.
Ada: The authors call it the multiorbital bivariate chromatic polynomial, and they emphasize this structural decomposition connecting group theory, graph structure, and element actions.
Emmy: What this means for us is that we can't just look at one part of the group action in isolation anymore; we have a way to aggregate everything across the whole subgroup lattice.
Kolya: And they give us a probabilistic interpretation too, after you normalize these coefficients, so you’re essentially looking at an expected quotient polynomial from picking a subgroup and then picking an element randomly within that subgroup.
Ada: It’s like taking a huge collection of data points—all the orbital counts—and finding the underlying pattern that governs how those counts relate to each other through the group's structure.
Emmy: The result is this coefficient function, c G g, which is key because it depends only on the cyclic subgroup generated by the element and stays constant across conjugacy classes.
Kolya: That’s a strong property because it means you can decompose those polynomials based on the simple cyclic subgroups and conjugacy classes of the group elements.
Ada: It links these things together beautifully, providing a way to see how local actions, like what one element does, contribute to the global polynomial structure.
Emmy: This framework is quite powerful because it allows us to use tools from subgroup lattice theory and Möbius inversion to understand these weights in a very natural way.
Kolya: It’s less of a new counting theorem and more of a sophisticated aggregation method for existing orbital contributions, which is actually really insightful for modeling random processes on graphs.
Ada: The paper's authors are showing us that we can use the subgroup lattice to refine and understand these complex graph invariants.
Emmy: And they’ve set the stage by showing how this structure lets us connect everything from group theory to specific graph polynomials.
Kolya: Next, we're going to look at how this whole setup plays out when you specialize it, like looking at edgeless graphs or chromatic specializations.
MELANIE GERLING
math.CO, math.GR
Submitted: 2026-09-01
Updated: 2026-11-05
Comments: 26 pages
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 92/100
The gist: The paper introduces the multiorbital bivariate chromatic polynomial to aggregate orbital bivariate chromatic polynomials over the subgroup lattice of a finite group acting on a graph…
Key concepts
- Multiorbital Bivariate Chromatic Polynomial
- This is a new polynomial that combines the orbital bivariate chromatic polynomials of all subgroups of a group G acting on a graph $\Gamma$. It aggregates these individual polynomials into one comprehensive structure, allowing for structural decomposition based on the group's subgroup lattice.
- Orbital Bivariate Chromatic Polynomial ($OP_{\Gamma,H}(x, y)$)
- This polynomial is derived from applying Burnside's lemma to count $\mu$-proper $\lambda$-colourings under the action of a subgroup $H$ on the graph. It represents the fixed-point contribution of an element in a Burnside average related to coloring problems.
- Element-wise Representation ($F_{\Gamma}(G; x, y) = \sum_{g\in G} c_G(g) P_{\Gamma/g}(x, y)$)
- This is the structural decomposition of the multiorbital polynomial. It shows that the aggregated polynomial can be expressed as a weighted sum over all group elements $g$, where the weights $c_G(g)$ depend only on $\langle g \rangle$, simplifying analysis based on cyclic subgroups and conjugacy classes.
- Probabilistic Interpretation
- After normalization, the coefficients $c_G(g)$ define a probability distribution on G. This means the multiorbital polynomial can be viewed as the expected quotient polynomial obtained by first choosing a subgroup uniformly at random and then choosing an element uniformly from that subgroup.
Terminology
Summary
The paper introduces the multiorbital bivariate chromatic polynomial to aggregate orbital bivariate chromatic polynomials over the subgroup lattice of a finite group acting on a graph, which provides a structural decomposition connecting group theory, graph structure, and element-wise actions The central structural identity is the element-wise expansion of this polynomial into a sum over group elements weighted by coefficients derived from the subgroup lattice
The Core Construction
The main purpose of this paper is to study the subgroup-lattice aggregation of orbital bivariate chromatic polynomials and the coefficient system induced by this aggregation The construction defines the multiorbital bivariate chromatic polynomial as a sum over all subgroups of the acting group, where each term involves an average of quotient graph polynomials Specifically, for every subgroup H ≤ G, the orbital bivariate chromatic polynomial is defined as (5) O PΓ,H (x, y):= 1/H Σ h∈H PΓ/h (x, y) The multiorbital polynomial is then defined by (6) FΓ (G; x, y):= Σ H≤G O PΓ,H (x, y)
Structural Decomposition of Coefficients
The element-wise representation of the multiorbital polynomial is given by (8) FΓ (G; x, y) = Σ g∈G cG (g) PΓ/g (x, y) The coefficient function cG(g) is defined as cG(g):= Σ H≤G g∈H 1/H A key structural result is that this coefficient depends only on the cyclic subgroup generated by the group element and is constant on conjugacy classes This leads to a decomposition of the polynomial into a purely group-theoretic coefficient function cG and graph-theoretic quotient polynomials PΓ/g
Möbius Inversion and Probabilistic Interpretation
The coefficient function cG(g) admits a natural Möbius inversion because it is the upper zeta transform of the function H ↦→ H−1 on the subgroup lattice This allows for a description of the weights in terms of subgroups rather than individual group elements Furthermore, after normalization, the coefficients define a probability distribution on G obtained by choosing a subgroup uniformly at random and then an element uniformly from that subgroup The normalized polynomial FbΓ (G; x, y) is interpreted as the expected quotient polynomial E PΓ/g (x, y)
Connections to Classical Invariants
The multiorbital polynomial admits several natural specializations, including a chromatic specialization where the bivariate chromatic polynomial satisfies PΛ(x, x) = χΛ(x) Under this condition, FΓ (G; x, x) = Σ g∈G cG (g) χΓ/g (x) For edgeless graphs, the polynomial simplifies to a weighted cycle-index expression given by FΓ (G; x, y) = Σ g∈G cG (g) x Orb⟨g⟩(V(Γ))
Diagonal Multiplicativity and Examples
The construction yields a diagonal multiplicativity relation for disjoint unions of graphs preserved by the group action, where FΓ1⊔Γ2 (G; x, y) = Σ g∈G cG (g) PΓ1/g (x, y) PΓ2/g (x, y) The coefficient function is also compatible with conjugation, implying that if g and h are conjugate, then Γ/g is isomorphic to Γ/h An example involving the symmetric group S3 shows that the normalized polynomial FbΓ (S3; x, y) equals E PΓ/g (x, y) for the distribution derived from subgroup selection The coefficient values b cS3(e), b cS3(t), and b cS3(c) are calculated to sum to 1, confirming the probabilistic interpretation
Conclusion
The resulting framework connects three structures: the subgroup lattice of G, the cyclic and conjugacy structure of its elements, and the graph polynomials of the corresponding quotient graphs The construction provides a bridge between these structures through the coefficient function cG(g), which depends only on ⟨g⟩ This framework is not a new orbit-counting theorem but an aggregation of existing element-wise orbital contributions over the entire subgroup lattice The resulting polynomial FΓ (G; x, y) can be viewed as the expected quotient polynomial associated with a two-stage random experiment involving subgroup and element selection
References
[1] I. Averbouch, B. p. 0 Godlin, and J. p. 0 A. Makowsky, An extension of the bivariate chromatic polynomial, European Journal of Combinatorics, 31(1) (2010), 1–17
[2] G. D. Birkhoff, A Determinant Formula for the Number of Ways of Coloring a Map, Annals of Mathematics, 14(1) (1912), 42–46
[3] P. J. Cameron and K. p. 0 K. Kayibi, Orbital Chromatic and Flow Roots, Combinatorics, Probability and Computing, 16(3) (2007), 401–407
[4] P. J. Cameron, B. p. 0 Jackson, and J. p. 0 D. Rudd, Orbit-counting polynomials for graphs and codes, Discrete Mathematics, 308(5–6) (2008), 920–930
[5] K. Dohmen and M. p. 0 Lange-Geisler, The Orbital Bivariate Chromatic Polynomial, arXiv:2009. p. 308235 [math. p. 0CO], version 5, 2026
[6] K. Dohmen, A Pönitz, and P. p. 0 Tittmann, A new two-variable generalization of the chromatic polynomial, Discrete Mathematics and Theoretical Computer Science, 6(1) (2003), 69–90
[7] M. J. Klass, A generalization of Burnside’s combinatorial lemma, Journal of Combinatorial Theory, Series A, 20(3) (1976), 273–278
--- Page 1 ---
THE MULTIORBITAL BIVARIATE CHROMATIC POLYNOMIAL
MELANIE GERLING
Abstract. We introduce the multiorbital bivariate chromatic polynomial FΓ (G; x, y) = Σ H≤G 1/H Σ h∈H PΓ/h (x, y), which aggregates orbital bivariate chromatic polynomials over the subgroup lattice of a finite group acting on a graph We derive an equivalent element-wise representation FΓ (G; x, y) = Σ g∈G cG (g)PΓ/g (x, y), cG (g) = Σ H≤G g∈H 1/H and the coefficient function depends only on the cyclic subgroup generated by the group element and is constant on conjugacy classes This yields corresponding decompositions by cyclic subgroups and conjugacy classes, as well as a natural Möbius-theoretic interpretation After normalization, the coefficients define a probability distribution on the acting group, giving a probabilistic interpretation of the multiorbital polynomial as an expected quotient polynomial We further investigate its behaviour under disjoint unions and its specialization to edgeless graphs, where a weighted cycle-index expression is obtained
--- Page 2 ---
MELANIE GERLING
and showed that their framework encompasses various orbital colouring, flow, and tension enumerators A bivariate version of this framework was introduced by Dohmen and LangeGeisler [5] The main purpose of this paper is to study the subgroup-lattice aggregation of orbital bivariate chromatic polynomials and the coefficient system induced by this aggregation Let Γ be a finite graph and let G ≤ Aut(Γ) For an element g ∈ G, let Γ/g denote the quotient graph obtained from the orbits of the cyclic subgroup ⟨g⟩ on V(Γ) We define (1) FΓ (G; x, y):= Σ H≤G 1/H Σ h∈H PΓ/h (x, y) After interchanging the finite sums, this becomes (2) FΓ (G; x, y) = Σ g∈G cG (g)PΓ/g (x, y), cG(g) = Σ ⟨g⟩≤H≤G 1/H Thus, the subgroup-lattice aggregation induces a natural weight on the cyclic actions of G We show that these weights admit equivalent descriptions in terms of cyclic subgroups and conjugacy classes, arise as a zeta transform on the subgroup lattice, and define, after normalization, a probability distribution on G The resulting polynomial can therefore be viewed both as a subgroup-lattice aggregate of orbital polynomials and as a weighted average of quotient graph polynomials
--- Page 3 ---
THE MULTIORBITAL BIVARIATE CHROMATIC POLYNOMIAL 3
First, cG (g) depends only on the cyclic subgroup ⟨g⟩ and is constant on conjugacy classes Consequently, the polynomial admits both a cyclic-subgroup decomposition and a conjugacy-class decomposition Second, the coefficient function is the upper zeta transform of H ↦→ H−1 on the subgroup lattice and therefore admits a natural Möbius inversion Third, after normalization, the coefficients define a probability distribution on G: one may choose a subgroup uniformly at random and then choose an element uniformly from that subgroup The resulting distribution is precisely the normalized coefficient function cG (g) Fourth, we investigate the behaviour of FΓ (G; x, y) under standard graph operations and specializations For disjoint unions preserved by the group action, the ordinary multiplicativity of the bivariate chromatic polynomial yields a diagonal multiplicativity relation For edgeless graphs, we obtain a weighted cycle-index expression
--- Page 4 ---
MELANIE GERLING
and showed that their framework encompasses various orbital colouring, flow, and tension enumerators Cameron and Kayibi [3] studied orbital chromatic and flow polynomials More generally, Cameron, Jackson, and Rudd introduced orbital Tutte-type polynomials associated with group actions on matrices Independent Researcher, Germany A bivariate version of this framework was introduced by Dohmen and Lange-Geisler [5] In particular, for a finite graph Γ, a finite group G ≤ Aut(Γ), and admissible parameters (lambda, μ), the orbital bivariate chromatic polynomial is obtained by applying Burnside’s lemma to the action of G on the set of μ-proper λ-colourings The quotient polynomial PΓ/g therefore arises naturally as the fixed-point contribution of the element g in the corresponding Burnside average
--- Page 5 ---
THE MULTIORBITAL BIVARIATE CHROMATIC POLYNOMIAL
and showed that their framework encompasses various orbital colouring, flow, and tension enumerators A bivariate version of this framework was introduced by Dohmen and Lange-Geisler [5] In particular, for a finite graph Γ, a finite group G ≤ Aut(Γ), and admissible parameters (lambda, μ), the orbital bivariate chromatic polynomial is obtained by applying Burnside’s lemma to the action of G on the set of μ-proper λ-colourings The quotient polynomial PΓ/g therefore arises naturally as the fixed-point contribution of the element g in the corresponding Burnside average
--- Page 7 ---
THE MULTIORBITAL BIVARIATE CHROMATIC POLYNOMIAL
We use the following formulation of the orbital bivariate chromatic polynomial of Dohmen and Lange-Geisler [5] Proposition 3.1 (Orbital bivariate chromatic polynomial). p. 0 Let Γ be a finite graph and let G ≤ Aut(Γ) For admissible parameters (λ, μ), the orbital bivariate chromatic polynomial satisfies OPΓ,G (λ, μ) = 1/G Σ g∈G PΓ/g (λ, μ) In particular, the polynomial PΓ/g is the fixed-point contribution of the element g in the corresponding Burnside average
--- Page 8 ---
MELANIE GERLING
The preceding proposition is the starting point for the present construction We retain the element-wise quotient polynomials but change the way in which they are aggregated
--- Page 9 ---
THE MULTIORBITAL BIVARIATE CHROMATIC POLYNOMIAL
Definition 3.2 (Multiorbital bivariate chromatic polynomial). p. 0
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved AI can perform expected quotient polynomial calculations by using a probability distribution on group elements derived from subgroup lattice aggregation, specifically P(g) = b cG (g) = cG (g) / H (G).
-
The improved system can decompose the multiorbital polynomial into element-wise contributions: FΓ (G; x, y) = sum g∈G cG (g) PΓ/g (x, y), separating group-theoretic weights from graph-theoretic quotient polynomials.
-
The system can leverage the cyclic subgroup decomposition: FΓ (G; x, y) = sum C∈ C(G) phi(C) cG (C) PΓ/C (x, y), allowing analysis based on the structure of cyclic subgroups rather than individual elements.
-
The AI can perform Möbius inversion on the subgroup lattice to determine the coefficient function cG (g), which is described as
the value of the upper zeta transform at the cyclic subgroup ⟨g⟩.
-
The system can interpret FΓ (G; x, y) as an expectation E[PΓ/g (x, y)] under a two-stage random experiment: first choosing a subgroup H uniformly at random, and then choosing an element g in H uniformly at random.
-
For edgeless graphs where G is a permutation group on n vertices, the system can compute the weighted cycle index expression FΓ (G; x, y) = sum g∈G cG (g) x cycles(g).
Sources
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