<p>We study Defant and Kravitz’s generalization of Schützenberger’s promotion operator to arbitrary labelings of finite posets in two directions. Defant and Kravitz showed that applying the promotion operator <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\({n-1}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> times to a labeling of a poset on <i>n</i> elements always gives a natural labeling of the poset and called a labeling <i>tangled</i> if it requires the full <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\({n-1}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> promotions to reach a natural labeling. They also conjectured that there are at most <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\({(n-1)!}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>!</mo> </mrow> </math></EquationSource> </InlineEquation> tangled labelings for any poset on <i>n</i> elements. We propose a strengthening of their conjecture by partitioning tangled labelings according to the element labeled <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\({n-1}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> and prove that this stronger conjecture holds for <i>inflated rooted forest posets</i> and a new class of posets called <i>shoelace posets</i>. We also introduce sorting generating functions and cumulative generating functions for the number of labelings that require <i>k</i> applications of the promotion operator to give a natural labeling. We prove that the coefficients of the cumulative generating function of the ordinal sum of antichains are log-concave and obtain a refinement of the weak order on the symmetric group.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Promotion, Tangled Labelings, and Sorting Generating Functions

  • Margaret Bayer,
  • Herman Chau,
  • Mark Denker,
  • Owen Goff,
  • Jamie Kimble,
  • Yi-Lin Lee,
  • Jinting Liang

摘要

We study Defant and Kravitz’s generalization of Schützenberger’s promotion operator to arbitrary labelings of finite posets in two directions. Defant and Kravitz showed that applying the promotion operator \({n-1}\) n - 1 times to a labeling of a poset on n elements always gives a natural labeling of the poset and called a labeling tangled if it requires the full \({n-1}\) n - 1 promotions to reach a natural labeling. They also conjectured that there are at most \({(n-1)!}\) ( n - 1 ) ! tangled labelings for any poset on n elements. We propose a strengthening of their conjecture by partitioning tangled labelings according to the element labeled \({n-1}\) n - 1 and prove that this stronger conjecture holds for inflated rooted forest posets and a new class of posets called shoelace posets. We also introduce sorting generating functions and cumulative generating functions for the number of labelings that require k applications of the promotion operator to give a natural labeling. We prove that the coefficients of the cumulative generating function of the ordinal sum of antichains are log-concave and obtain a refinement of the weak order on the symmetric group.