Branching Rules for Splint Root Systems Crew, Logan; Kirillov, Alexandre A.; Yeo, Yao-Rui
Algebras and representation theory,
08/2022, Letnik:
25, Številka:
4
Journal Article
Recenzirano
Odprti dostop
A root system is
splint
if it is a decomposition into a union of two disjoint root systems. Examples of such root systems arise naturally in studying embeddings of reductive Lie subalgebras into ...simple Lie algebras. Given a splint root system, one can try to understand its branching rule. In this paper we discuss methods to understand such branching rules, and give precise formulas for specific cases, including the restriction functor from the exceptional Lie algebra
g
2
to
s
l
3
.
For a tree T, consider its smallest subtree T∘ containing all vertices of degree at least 3. Then the remaining edges of T lie on edge-disjoint paths each with one endpoint on T∘. We show that the ...chromatic symmetric function of T determines the size of T∘, and the multiset of the lengths of these incident paths. In particular, this generalizes a proof of Martin, Morin, and Wagner that the chromatic symmetric function distinguishes spiders.
We extend the definition of the chromatic symmetric function XG to include graphs G with a vertex-weight function w:V(G)→N. We show how this provides the chromatic symmetric function with a natural ...deletion–contraction relation analogous to that of the chromatic polynomial. Using this relation we derive new properties of the chromatic symmetric function, and we give alternate proofs of many fundamental properties of XG.
Many graph polynomials may be derived from the coefficients of the chromatic symmetric function X
G ${X}_{G}$ of a graph G $G$ when expressed in different bases. For instance, the chromatic ...polynomial is obtained by mapping p
n
→
x ${p}_{n}\to x$ for each n $n$ in this function, while a polynomial whose coefficients enumerate acyclic orientations is obtained by mapping e
n
→
x ${e}_{n}\to x$ for each n $n$. In this paper, we study a new polynomial we call the tree polynomial arising by mapping X
P
n
→
x ${X}_{{P}_{n}}\to x$, where X
P
n ${X}_{{P}_{n}}$ is the chromatic symmetric function of a path with n $n$ vertices. In particular, we show that this polynomial has a deletion‐contraction relation and has properties closely related to the chromatic polynomial while having coefficients that enumerate certain spanning trees and edge cutsets.
Plethysm is a fundamental operation in symmetric function theory, derived directly from its connection with representation theory. However, it does not admit a simple combinatorial interpretation, ...and finding coefficients of Schur function plethysms is a major open question.
In this paper, we introduce a graph-theoretic interpretation for any plethysm based on the chromatic symmetric function. We use this interpretation to give simple proofs of new and previously known plethystic identities, as well as chromatic symmetric function identities.
For a graph G, its Tutte symmetric function XBG generalizes both the Tutte polynomial TG and the chromatic symmetric function XG. We may also consider XB as a map from the t-extended Hopf algebra Gt ...of labeled graphs to symmetric functions.
We show that the kernel of XB is generated by vertex-relabellings and a finite set of modular relations, in the same style as a recent analogous result by Penaguião on the chromatic symmetric function X. In particular, we find one such relation that generalizes the well-known triangular modular relation of Orellana and Scott, and build upon this to give a modular relation of the Tutte symmetric function for any two-edge-connected graph that generalizes the n-cycle relation of Dahlberg and van Willigenburg. Additionally, we give a structural characterization of all local modular relations of the chromatic and Tutte symmetric functions, and prove that there is no single local modification that preserves either function on simple graphs.
In this paper, we extend the chromatic symmetric function X to a chromatic k-multisymmetric functionXk, defined for graphs equipped with a partition of their vertex set into k parts. We demonstrate ...that this new function retains the basic properties and basis expansions of X, and we give a method for systematically deriving new linear relationships for X from previous ones by passing them through Xk.
In particular, we show how to take advantage of homogeneous sets of G (those S⊆V(G) such that each vertex of V(G)﹨S is either adjacent to all of S or is nonadjacent to all of S) to relate the chromatic symmetric function of G to those of simpler graphs. Furthermore, we show how extending this idea to homogeneous pairs S1⊔S2⊆V(G) generalizes the process used by Guay-Paquet to reduce the Stanley-Stembridge conjecture to unit interval graphs.
Disproportionate division Crew, Logan; Narayanan, Bhargav; Spirkl, Sophie
The Bulletin of the London Mathematical Society,
October 2020, 2020-10-00, Letnik:
52, Številka:
5
Journal Article
Recenzirano
Odprti dostop
We study the disproportionate version of the classical cake‐cutting problem: how efficiently can we divide a cake, here 0,1, among n⩾2 agents with different demands α1,α2,⋯,αn summing to 1? When all ...the agents have equal demands of α1=α2=⋯=αn=1/n, it is well known that there exists a fair division with n−1 cuts, and this is optimal. For arbitrary demands on the other hand, folklore arguments from algebraic topology show that O(nlogn) cuts suffice, and this has been the state of the art for decades. Here, we improve the state of affairs in two ways: we prove that disproportionate division may always be achieved with 3n−4 cuts, and also give an effective algorithm to construct such a division. We additionally offer a topological conjecture that implies that 2n−2 cuts suffice in general, which would be optimal.
This paper has two main parts. First, we consider the Tutte symmetric function XB, a generalization of the chromatic symmetric function. We introduce a vertex-weighted version of XB and show that ...this function admits a deletion-contraction relation. We also demonstrate that the vertex-weighted XB admits spanning-tree and spanning-forest expansions generalizing those of the Tutte polynomial by connecting XB to other graph functions. Second, we give several methods for constructing nonisomorphic graphs with equal chromatic and Tutte symmetric functions, and use them to provide specific examples.
PDF
