Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userProper caterpillars are distinguished by their symmetric chromatic function
129
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
This paper deals with the so-called Stanley conjecture, which asks whether they are non-isomorphic trees with the same symmetric function generalization of the chromatic polynomial. By establishing a correspondence between caterpillars trees and integer compositions, we prove that caterpillars in a large class (we call trees in this class proper) have the same symmetric chromatic function generalization of the chromatic polynomial if and only if they are isomorphic.
rate research
Read More
In this paper, we propose an algebraic approach to determine whether two non-isomorphic caterpillar trees can have the same symmetric function generalization of the chromatic polynomial. On the set of all composition on integers, we introduce: An operation, which we call composition product; and a combinatorial polynomial, which we call the composition-lattice polynomial or L-polynomial, that mimics the weighted graph polynomial of Noble and Welsh. We prove a unique irreducible factorization theorem and establish a connection between the L-polynomial of a composition and its irreducible factorization, namely that reversing irreducible factors does not change L, and conjecture that is the only way of generating such compositions. Finally, we find a sufficient condition for two caterpillars have a different symmetric function generalization of the chromatic polynomial, and use this condition to show that if our conjecture were to hold, then the symmetric function generalization of the chromatic polynomial distinguishes among a large class of caterpillars.
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.
While every rooted binary phylogenetic tree is determined by its set of displayed rooted triples, such a result does not hold for an arbitrary rooted binary phylogenetic network. In particular, there exist two non-isomorphic rooted binary temporal normal networks that display the same set of rooted triples. Moreover, without any structural constraint on the rooted phylogenetic networks under consideration, similarly negative results have also been established for binets and trinets which are rooted subnetworks on two and three leaves, respectively. Hence, in general, piecing together a rooted phylogenetic network from such a set of small building blocks appears insurmountable. In contrast to these results, in this paper, we show that a rooted binary normal network is determined by its sets of displayed caterpillars (particular type of subtrees) on three and four leaves. The proof is constructive and realises a polynomial-time algorithm that takes the sets of caterpillars on three and four leaves displayed by a rooted binary normal network and, up to isomorphism, reconstructs this network.
Motivated by the study of Macdonald polynomials, J. Haglund and A. Wilson introduced a nonsymmetric polynomial analogue of the chromatic quasisymmetric function called the emph{chromatic nonsymmetric polynomial} of a Dyck graph. We give a positive expansion for this polynomial in the basis of fundamental slide polynomials using recent work of Assaf-Bergeron on flagged $(P,rho)$-partitions. We then derive the known expansion for the chromatic quasisymmetric function of Dyck graphs in terms of Gessels fundamental basis by taking a backstable limit of our expansion.
We introduce a quasisymmetric class function associated with a group acting on a double poset or on a directed graph. The latter is a generalization of the chromatic quasisymmetric function of a digraph introduced by Ellzey, while the latter is a generalization of a quasisymmetric function introduced by Grinberg. We prove representation-theoretic analogues of classical and recent results, including $F$-positivity, and combinatorial reciprocity theorems. We also deduce results for orbital quasisymmetric functions. We also study a generalization of the notion of strongly flawless sequences.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
