2014/11/13 by Jonah Blasiak, Blasiak, Jonah · 1 citation
Computer Science · Mathematics · #05E05 (Primary) #90C05 (Secondary) #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Algebraic structures and combinatorial models #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05E05 #msc:90C05
paper · pdf · doi:10.48550/arxiv.1411.3624
46 pages, 6 figures; 5 attached data files, see Subsection 7.8. Version 2: minor changes, published in J. Algebraic Combin. November 2016
openalex publication_date 2014/11/13 · arxiv created 2016/12/18 · arxiv updated 2016/12/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We define a D0 graph to be a graph whose vertex set is a subset of permutations of n, with edges of the form ...bac... <--> ...bca... or ...acb... <--> ...cab... (Knuth transformations), or ...bac... <--> ...acb... or ...bca... <--> ...cab... (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 D0 graphs in the paper *Dual equivalence and Schur positivity* and showed that they provide a rich source of examples of the D graphs defined in the paper *Dual equivalence graphs and a combinatorial proof of LLT and Macdonald positivity*. A key construction of Assaf expresses the coefficient of qt in an LLT polynomial as the generating function of a certain D0 graph. LLT polynomials are known to be Schur positive by work of Grojnowski-Haiman, and experimentation shows that many D0 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 D0 graphs using the Fomin-Greene theory of noncommutative Schur functions. We construct a D0 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 D0 graph.