Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the $e$-positivity of trees and spiders
105
0
0.0
(
0
)
Authors
Kai Zheng
Ask ChatGPT about the research
No Arabic abstract
We prove that for any tree with a vertex of degree at least six, its chromatic symmetric function is not $e$-positive, that is, it cannot be written as a nonnegative linear combination of elementary symmetric functions. This makes significant progress towards a recent conjecture of Dahlberg, She, and van Willigenburg, who conjectured the result for all trees with a vertex of degree at least four. We also provide a series of conditions that can identify when the chromatic symmetric function of a spider, a tree consisting of multiple paths identified at an end, is not $e$-positive. These conditions also generalize to trees and graphs with cut vertices. Finally, by applying a result of Orellana and Scott, we provide a method to inductively calculate certain coefficients in the elementary symmetric function expansion of the chromatic symmetric function of a spider, leading to further $e$-positivity conditions for spiders.
rate research
Read More
In a 2016 ArXiv posting F. Bergeron listed a variety of symmetric functions $G[X;q]$ with the property that $G[X;1+q]$ is $e$-positive. A large subvariety of his examples could be explained by the conjecture that the Dyck path LLT polynomials exhibit the same phenomenon. In this paper we list the results of computer explorations which suggest that other examples exhibit the same phenomenon. We prove two of the resulting conjectures and propose algorithms that would prove several of our conjectures. In writing this paper we have learned that similar findings have been independently discovered by Per Alexandersson.
Motivated by Stanleys $mathbf{(3+1)}$-free conjecture on chromatic symmetric functions, Foley, Ho`{a}ng and Merkel introduced the concept of strong $e$-positivity and conjectured that a graph is strongly $e$-positive if and only if it is (claw, net)-free. In order to study strongly $e$-positive graphs, they further introduced the twinning operation on a graph $G$ with respect to a vertex $v$, which adds a vertex $v$ to $G$ such that $v$ and $v$ are adjacent and any other vertex is adjacent to both of them or neither of them. Foley, Ho`{a}ng and Merkel conjectured that if $G$ is $e$-positive, then so is the resulting twin graph $G_v$ for any vertex $v$. Based on the theory of chromatic symmetric functions in non-commuting variables developed by Gebhard and Sagan, we establish the $e$-positivity of a class of graphs called tadpole graphs. By considering the twinning operation on a subclass of these graphs with respect to certain vertices we disprove the latter conjecture of Foley, Ho`{a}ng and Merkel. We further show that if $G$ is $e$-positive, the twin graph $G_v$ and more generally the clan graphs $G^{(k)}_v$ ($k ge 1$) may not even be $s$-positive, where $G^{(k)}_v$ is obtained from $G$ by applying $k$ twinning operations to $v$.
Inspired by the recent work of Chen and Fu on the e-positivity of trivariate second-order Eulerian polynomials, we show the e-positivity of a family of multivariate k-th order Eulerian polynomials. A relationship between the coefficients of this e-positive expansion and second-order Eulerian numbers is established. Moreover, we present a grammatical proof of the fact that the joint distribution of the ascent, descent and j-plateau statistics over k-Stirling permutations are symmetric distribution. By using symmetric transformation of grammars, a symmetric expansion of trivariate Schett polynomial is also established.
Ma-Ma-Yeh made a beautiful observation that a change of the grammar of Dumont instantly leads to the $gamma$-positivity of the Eulearian polynomials. We notice that the transformed grammar bears a striking resemblance to the grammar for 0-1-2 increasing trees also due to Dumont. The appearance of the factor of two fits perfectly in a grammatical labeling of 0-1-2 increasing plane trees. Furthermore, the grammatical calculus is instrumental to the computation of the generating functions. This approach can be adapted to study the $e$-positivity of the trivariate second-order Eulerian polynomials introduced by Janson, in connection with the joint distribution of the numbers of ascents, descents and plateaux over Stirling permutations.
The firefighter problem with $k$ firefighters on an infinite graph $G$ is an iterative graph process, defined as follows: Suppose a fire breaks out at a given vertex $vin V(G)$ on Turn 1. On each subsequent even turn, $k$ firefighters protect $k$ vertices that are not on fire, and on each subsequent odd turn, any vertex that is on fire spreads the fire to all adjacent unprotected vertices. The firefighters goal is to eventually stop the spread of the fire. If there exists a strategy for $k$ firefighters to eventually stop the spread of the fire, then we say $G$ is $k$-containable. We consider the firefighter problem on the hexagonal grid, which is the graph whose vertices and edges are exactly the vertices and edges of a regular hexagonal tiling of the plane. It is not known if the hexagonal grid is $1$-containable. In arXiv:1305.7076 [math.CO], it was shown that if the firefighters have one firefighter per turn and one extra firefighter on two turns, the firefighters can contain the fire. We improve on this result by showing that even with only one extra firefighter on one turn, the firefighters can still contain the fire. In addition, we explore $k$-containability for birth sequence trees, which are infinite rooted trees that have the property that every vertex at the same level has the same degree. A birth sequence forest is an infinite forest, each component of which is a birth sequence tree. For birth sequence trees and forests, the fire always starts at the root of each tree. We provide a pseudopolynomial time algorithm to decide if all the vertices at a fixed level can be protected or not.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
