Eppstein and Frishberg recently proved that the mixing time for the simple random walk on the 1-skeleton of the associahedron is <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_750_Article_IEq1.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="86" /> </InlineMediaObject> <EquationSource Format="TEX">$O(n^3\log ^3 n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>3</mn> </msup> <msup> <mo>log</mo> <mn>3</mn> </msup> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. We obtain similar rapid mixing results for the simple random walks on the 1-skeleta of the type-B and type-D associahedra. We adapt Eppstein and Frishberg’s technique to obtain the same bound of <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_750_Article_IEq1.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="86" /> </InlineMediaObject> <EquationSource Format="TEX">$O(n^3\log ^3 n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>3</mn> </msup> <msup> <mo>log</mo> <mn>3</mn> </msup> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> in type B and a bound of <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_750_Article_IEq3.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="92" /> </InlineMediaObject> <EquationSource Format="TEX">$O(n^{13} \log ^2 n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>13</mn> </msup> <msup> <mo>log</mo> <mn>2</mn> </msup> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> in type D; in the process, we establish an expansion bound that is tight up to logarithmic factors in type B.

Mixing on Generalized Associahedra

期刊论文
发表日期：

2025年3月18日

查看全文

William Chang,
Colin Defant,
Daniel Frishberg

摘要

Eppstein and Frishberg recently proved that the mixing time for the simple random walk on the 1-skeleton of the associahedron is $O(n^3\log ^3 n)$ $O (n^{3} {log}^{3} n)$ . We obtain similar rapid mixing results for the simple random walks on the 1-skeleta of the type-B and type-D associahedra. We adapt Eppstein and Frishberg’s technique to obtain the same bound of $O(n^3\log ^3 n)$ $O (n^{3} {log}^{3} n)$ in type B and a bound of $O(n^{13} \log ^2 n)$ $O (n^{13} {log}^{2} n)$ in type D; in the process, we establish an expansion bound that is tight up to logarithmic factors in type B.