When generalizing West’s stack-sorting map from permutations to words, a natural question is whether identical characters should be allowed to sit on top of each other in the stack. As a result, Defant and Kravitz introduced two distinct maps, <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\textsf {tortoise} $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">tortoise</mi> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\textsf {hare} $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">hare</mi> </math></EquationSource> </InlineEquation>: while <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\textsf {tortoise} $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">tortoise</mi> </math></EquationSource> </InlineEquation> does not allow identical characters to sit on top of themselves, <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\textsf {hare} $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">hare</mi> </math></EquationSource> </InlineEquation> does. For a word w, let <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\langle w\rangle _{\textsf {tortoise} }$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mo stretchy="false">⟨</mo> <mi>w</mi> <mo stretchy="false">⟩</mo> </mrow> <mi mathvariant="sans-serif">tortoise</mi> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\langle w\rangle _{\textsf {hare} }$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mo stretchy="false">⟨</mo> <mi>w</mi> <mo stretchy="false">⟩</mo> </mrow> <mi mathvariant="sans-serif">hare</mi> </msub> </math></EquationSource> </InlineEquation> be the number of iterations of <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\textsf {tortoise} $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">tortoise</mi> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\textsf {hare} $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">hare</mi> </math></EquationSource> </InlineEquation> required to sort w, respectively. For a word of length <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$\left| w \right| $</EquationSource> <EquationSource Format="MATHML"><math> <mfenced close="|" open="|"> <mi>w</mi> </mfenced> </math></EquationSource> </InlineEquation>, Defant and Kravitz conjectured <Equation ID="Equ1"> <EquationSource Format="TEX">$\begin{aligned} \langle w\rangle _{\textsf {hare} } - \langle w\rangle _{\textsf {tortoise} } \le \frac{\left| w \right| - 5}{2} \quad \text {and} \quad \langle w\rangle _{\textsf {hare} } \le 2\langle w\rangle _{\textsf {tortoise} } - 2. \end{aligned}$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mtable> <mtr> <mtd columnalign="right"> <mrow> <msub> <mrow> <mo stretchy="false">⟨</mo> <mi>w</mi> <mo stretchy="false">⟩</mo> </mrow> <mi mathvariant="sans-serif">hare</mi> </msub> <mo>-</mo> <msub> <mrow> <mo stretchy="false">⟨</mo> <mi>w</mi> <mo stretchy="false">⟩</mo> </mrow> <mi mathvariant="sans-serif">tortoise</mi> </msub> <mo>≤</mo> <mfrac> <mrow> <mfenced close="|" open="|"> <mi>w</mi> </mfenced> <mo>-</mo> <mn>5</mn> </mrow> <mn>2</mn> </mfrac> <mspace width="1em" /> <mtext>and</mtext> <mspace width="1em" /> <msub> <mrow> <mo stretchy="false">⟨</mo> <mi>w</mi> <mo stretchy="false">⟩</mo> </mrow> <mi mathvariant="sans-serif">hare</mi> </msub> <mo>≤</mo> <mn>2</mn> <msub> <mrow> <mo stretchy="false">⟨</mo> <mi>w</mi> <mo stretchy="false">⟩</mo> </mrow> <mi mathvariant="sans-serif">tortoise</mi> </msub> <mo>-</mo> <mn>2</mn> <mo>.</mo> </mrow> </mtd> </mtr> </mtable> </mrow> </math></EquationSource> </Equation>We disprove both conjectures, and our results imply <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$\langle w\rangle _{\textsf {hare} }/\langle w\rangle _{\textsf {tortoise} }$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mrow> <mo stretchy="false">⟨</mo> <mi>w</mi> <mo stretchy="false">⟩</mo> </mrow> <mi mathvariant="sans-serif">hare</mi> </msub> <mo stretchy="false">/</mo> <msub> <mrow> <mo stretchy="false">⟨</mo> <mi>w</mi> <mo stretchy="false">⟩</mo> </mrow> <mi mathvariant="sans-serif">tortoise</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> may be arbitrarily large.

A Disproof of Two Conjectures on Stack-Sorting Maps for Words

期刊论文
发表日期：

2025年12月1日

查看全文

Olivia Chen,
Michael Luo,
Jerry Zhang

摘要

When generalizing West’s stack-sorting map from permutations to words, a natural question is whether identical characters should be allowed to sit on top of each other in the stack. As a result, Defant and Kravitz introduced two distinct maps, $\textsf {tortoise} $ $tortoise$ and $\textsf {hare} $ $hare$ : while $\textsf {tortoise} $ $tortoise$ does not allow identical characters to sit on top of themselves, $\textsf {hare} $ $hare$ does. For a word w, let $\langle w\rangle _{\textsf {tortoise} }$ ${⟨ w ⟩}_{tortoise}$ and $\langle w\rangle _{\textsf {hare} }$ ${⟨ w ⟩}_{hare}$ be the number of iterations of $\textsf {tortoise} $ $tortoise$ and $\textsf {hare} $ $hare$ required to sort w, respectively. For a word of length $\left| w \right| $ $|w|$ , Defant and Kravitz conjectured $\begin{aligned} \langle w\rangle _{\textsf {hare} } - \langle w\rangle _{\textsf {tortoise} } \le \frac{\left| w \right| - 5}{2} \quad \text {and} \quad \langle w\rangle _{\textsf {hare} } \le 2\langle w\rangle _{\textsf {tortoise} } - 2. \end{aligned}$ $\begin{matrix} {⟨ w ⟩}_{hare} - {⟨ w ⟩}_{tortoise} \leq \frac{|w| - 5}{2} and {⟨ w ⟩}_{hare} \leq 2 {⟨ w ⟩}_{tortoise} - 2 . \end{matrix}$ We disprove both conjectures, and our results imply $\langle w\rangle _{\textsf {hare} }/\langle w\rangle _{\textsf {tortoise} }$ ${⟨ w ⟩}_{hare} / {⟨ w ⟩}_{tortoise}$ may be arbitrarily large.