For <InlineEquation ID="IEq1"> <EquationSource Format="TEX">${\textbf {b}}=(b_1,\dots ,b_n)\in \mathbb {Z}_{>0}^n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold">b</mi> <mo>=</mo> <mrow> <mo stretchy="false">(</mo> <msub> <mi>b</mi> <mn>1</mn> </msub> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msub> <mi>b</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>∈</mo> <msubsup> <mi mathvariant="double-struck">Z</mi> <mrow> <mo>></mo> <mn>0</mn> </mrow> <mi>n</mi> </msubsup> </mrow> </math></EquationSource> </InlineEquation>, a <InlineEquation ID="IEq2"> <EquationSource Format="TEX">${\textbf {b}}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="bold">b</mi> </math></EquationSource> </InlineEquation>-parking function is defined to be a sequence <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$(\beta _1,\dots ,\beta _n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msub> <mi>β</mi> <mn>1</mn> </msub> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msub> <mi>β</mi> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> of positive integers whose nondecreasing rearrangement <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\beta '_1\le \beta '_2\le \cdots \le \beta '_n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>β</mi> <mn>1</mn> <mo>′</mo> </msubsup> <mo>≤</mo> <msubsup> <mi>β</mi> <mn>2</mn> <mo>′</mo> </msubsup> <mo>≤</mo> <mo>⋯</mo> <mo>≤</mo> <msubsup> <mi>β</mi> <mi>n</mi> <mo>′</mo> </msubsup> </mrow> </math></EquationSource> </InlineEquation> satisfies <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\beta '_i\le b_1+\cdots + b_i$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>β</mi> <mi>i</mi> <mo>′</mo> </msubsup> <mo>≤</mo> <msub> <mi>b</mi> <mn>1</mn> </msub> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <msub> <mi>b</mi> <mi>i</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>. The <InlineEquation ID="IEq6"> <EquationSource Format="TEX">${\textbf {b}}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="bold">b</mi> </math></EquationSource> </InlineEquation>-parking-function polytope <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\mathfrak {X}_{n}({\textbf {b}})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi mathvariant="fraktur">X</mi> <mi>n</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="bold">b</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is the convex hull of all <InlineEquation ID="IEq8"> <EquationSource Format="TEX">${\textbf {b}}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="bold">b</mi> </math></EquationSource> </InlineEquation>-parking functions of length n in <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$\mathbb {R}^n$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mi>n</mi> </msup> </math></EquationSource> </InlineEquation>. Geometric properties of <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$\mathfrak {X}_{n}({\textbf {b}})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi mathvariant="fraktur">X</mi> <mi>n</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="bold">b</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> were previously explored in the specific case where <InlineEquation ID="IEq11"> <EquationSource Format="TEX">${\textbf {b}}=(a,b,b,\dots ,b)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold">b</mi> <mo>=</mo> <mo stretchy="false">(</mo> <mi>a</mi> <mo>,</mo> <mi>b</mi> <mo>,</mo> <mi>b</mi> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <mi>b</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and were shown to generalize those of the classical parking-function polytope. In this work, we study <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$\mathfrak {X}_{n}({\textbf {b}})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi mathvariant="fraktur">X</mi> <mi>n</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="bold">b</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> in full generality. We present a minimal inequality and vertex description for <InlineEquation ID="IEq13"> <EquationSource Format="TEX">$\mathfrak {X}_{n}({\textbf {b}})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi mathvariant="fraktur">X</mi> <mi>n</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="bold">b</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, prove it is a generalized permutahedron, and study its h-polynomial. Furthermore, we investigate <InlineEquation ID="IEq14"> <EquationSource Format="TEX">$\mathfrak {X}_{n}({\textbf {b}})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi mathvariant="fraktur">X</mi> <mi>n</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="bold">b</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> through the perspectives of building sets and polymatroids, allowing us to identify its combinatorial types and obtain bounds on its combinatorial and circuit diameters.

Combinatorics of Generalized Parking-Function Polytopes

期刊论文
出版模式：

开放获取
发表日期：

2025年9月12日

查看全文

Margaret M. Bayer,
Steffen Borgwardt,
Teressa Chambers,
Spencer Daugherty,
Aleyah Dawkins,
Danai Deligeorgaki,
Hsin-Chieh Liao,
Tyrrell McAllister,
Angela Morrison,
Garrett Nelson,
Andrés R. Vindas-Meléndez

摘要

For ${\textbf {b}}=(b_1,\dots ,b_n)\in \mathbb {Z}_{>0}^n$ $b = (b_{1}, \dots, b_{n}) \in Z_{> 0}^{n}$ , a ${\textbf {b}}$ $b$ -parking function is defined to be a sequence $(\beta _1,\dots ,\beta _n)$ $(β_{1}, \dots, β_{n})$ of positive integers whose nondecreasing rearrangement $\beta '_1\le \beta '_2\le \cdots \le \beta '_n$ $β_{1}^{'} \leq β_{2}^{'} \leq \dots \leq β_{n}^{'}$ satisfies $\beta '_i\le b_1+\cdots + b_i$ $β_{i}^{'} \leq b_{1} + \dots + b_{i}$ . The ${\textbf {b}}$ $b$ -parking-function polytope $\mathfrak {X}_{n}({\textbf {b}})$ $X_{n} (b)$ is the convex hull of all ${\textbf {b}}$ $b$ -parking functions of length n in $\mathbb {R}^n$ $R^{n}$ . Geometric properties of $\mathfrak {X}_{n}({\textbf {b}})$ $X_{n} (b)$ were previously explored in the specific case where ${\textbf {b}}=(a,b,b,\dots ,b)$ $b = (a, b, b, \dots, b)$ and were shown to generalize those of the classical parking-function polytope. In this work, we study $\mathfrak {X}_{n}({\textbf {b}})$ $X_{n} (b)$ in full generality. We present a minimal inequality and vertex description for $\mathfrak {X}_{n}({\textbf {b}})$ $X_{n} (b)$ , prove it is a generalized permutahedron, and study its h-polynomial. Furthermore, we investigate $\mathfrak {X}_{n}({\textbf {b}})$ $X_{n} (b)$ through the perspectives of building sets and polymatroids, allowing us to identify its combinatorial types and obtain bounds on its combinatorial and circuit diameters.