Indexed on: **22 Oct '16**Published on: **01 Nov '16**Published in: **Journal of Algebraic Combinatorics**

Abstract We define a \({D}_0\) graph to be a graph whose vertex set is a subset of permutations of n, with edges of the form \(\cdots \mathsf {bac} \cdots \leftrightsquigarrow \cdots \mathsf {bca} \cdots \) or \(\cdots \mathsf {acb} \cdots \leftrightsquigarrow \cdots \mathsf {cab} \cdots \) (Knuth transformations), or \(\cdots \mathsf {bac} \cdots \leftrightsquigarrow \cdots \mathsf {acb} \cdots \) or \(\cdots \mathsf {bca} \cdots \leftrightsquigarrow \cdots \mathsf {cab} \cdots \) (rotation transformations), such that whenever the Knuth and rotation transformations at positions \(i-1, i, i+1\) are available at a vertex, exactly one of these is an edge. The generating function of such a graph is the sum of the quasisymmetric functions associated to the descent sets of its vertices. Assaf studied D \(_0\) graphs in (Dual equivalence and Schur positivity, http://www-bcf.usc.edu/~shassaf/degs.pdf, 2014) and showed that they provide a rich source of examples of the D graphs of (Dual equivalence graphs and a combinatorial proof of LLT and Macdonald positivity, http://www-bcf.usc.edu/~shassaf/positivity.pdf, 2014). A key construction of Assaf expresses the coefficient of \(q^t\) in an LLT polynomial as the generating function of a certain D \(_0\) graph. LLT polynomials are known to be Schur positive by work of Grojnowski-Haiman, and experimentation shows that many D \(_0\) graphs have Schur positive generating functions, which suggests a vast generalization of LLT positivity in this setting. As part of a series of papers, we study D \(_0\) graphs using the Fomin-Greene theory of noncommutative Schur functions. We construct a D \(_0\) graph whose generating function is not Schur positive by solving a linear program related to a certain noncommutative Schur function. We go on to construct a D graph on the same vertex set as this D \(_0\) graph.AbstractWe define a \({D}_0\) graph to be a graph whose vertex set is a subset of permutations of n, with edges of the form \(\cdots \mathsf {bac} \cdots \leftrightsquigarrow \cdots \mathsf {bca} \cdots \) or \(\cdots \mathsf {acb} \cdots \leftrightsquigarrow \cdots \mathsf {cab} \cdots \) (Knuth transformations), or \(\cdots \mathsf {bac} \cdots \leftrightsquigarrow \cdots \mathsf {acb} \cdots \) or \(\cdots \mathsf {bca} \cdots \leftrightsquigarrow \cdots \mathsf {cab} \cdots \) (rotation transformations), such that whenever the Knuth and rotation transformations at positions \(i-1, i, i+1\) are available at a vertex, exactly one of these is an edge. The generating function of such a graph is the sum of the quasisymmetric functions associated to the descent sets of its vertices. Assaf studied D \(_0\) graphs in (Dual equivalence and Schur positivity, http://www-bcf.usc.edu/~shassaf/degs.pdf, 2014) and showed that they provide a rich source of examples of the D graphs of (Dual equivalence graphs and a combinatorial proof of LLT and Macdonald positivity, http://www-bcf.usc.edu/~shassaf/positivity.pdf, 2014). A key construction of Assaf expresses the coefficient of \(q^t\) in an LLT polynomial as the generating function of a certain D \(_0\) graph. LLT polynomials are known to be Schur positive by work of Grojnowski-Haiman, and experimentation shows that many D \(_0\) graphs have Schur positive generating functions, which suggests a vast generalization of LLT positivity in this setting. As part of a series of papers, we study D \(_0\) graphs using the Fomin-Greene theory of noncommutative Schur functions. We construct a D \(_0\) graph whose generating function is not Schur positive by solving a linear program related to a certain noncommutative Schur function. We go on to construct a D graph on the same vertex set as this D \(_0\) graph. \({D}_0\) \({D}_0\)graphn \(\cdots \mathsf {bac} \cdots \leftrightsquigarrow \cdots \mathsf {bca} \cdots \) \(\cdots \mathsf {bac} \cdots \leftrightsquigarrow \cdots \mathsf {bca} \cdots \) \(\cdots \mathsf {acb} \cdots \leftrightsquigarrow \cdots \mathsf {cab} \cdots \) \(\cdots \mathsf {acb} \cdots \leftrightsquigarrow \cdots \mathsf {cab} \cdots \)Knuth transformations \(\cdots \mathsf {bac} \cdots \leftrightsquigarrow \cdots \mathsf {acb} \cdots \) \(\cdots \mathsf {bac} \cdots \leftrightsquigarrow \cdots \mathsf {acb} \cdots \) \(\cdots \mathsf {bca} \cdots \leftrightsquigarrow \cdots \mathsf {cab} \cdots \) \(\cdots \mathsf {bca} \cdots \leftrightsquigarrow \cdots \mathsf {cab} \cdots \)rotation transformations \(i-1, i, i+1\) \(i-1, i, i+1\)generating function \(_0\) \(_0\)http://www-bcf.usc.edu/~shassaf/degs.pdf2014http://www-bcf.usc.edu/~shassaf/positivity.pdf2014 \(q^t\) \(q^t\) \(_0\) \(_0\) \(_0\) \(_0\) \(_0\) \(_0\) \(_0\) \(_0\) \(_0\) \(_0\)