论文标题
在Tutte多项式的系数上，Brylawski定理的简短证明
Short proof of a theorem of Brylawski on the coefficients of the Tutte polynomial
论文作者
论文摘要
在此简短说明中，我们表明，一个$ m =（e，r）$，带有地面套装$ $ m $的$ e $和（等级）函数$ r：2^e \ to \ mathbb {z} _ {\ geq 0} $满足$ r（S） $ t_m（x，y）：= \ sum_ {s \ subseteq e}（x-1）^{r（e）-r（s）}（y-1）（y-1）^{| s | -r（s s）}，$$写成$ t_m（x，x，y） \ geq 0 $，我们有$ \ sum_ {i = 0}^h \ sum_ {j = 0}^{h-i} \ binom {h-i} {h-i} {j} {j}（ - 1）^jt_ {jt_ {ij} =（ij} =（ij} =（ - 1）使用以下公约，即当$ h <m $时，二项式系数$ \ binom {h-r} {h-m} $被解释为$ 0 $。这将Brylawski定理在Matroid等级函数和$ H <m $上，以及$ H \ leq m $的Gordon定理，对等级功能具有相同的假设。此处提供的证明比以前的证明要短得多。我们仅使用这样一个事实，即Tutte多项式$ T_M（X，Y）$简化为$（X-1）^{r（e）} y^{| e |} $沿Hyperbola $（X-1）（y-1）= 1 $。
In this short note we show that a system $M=(E,r)$ with a ground set $E$ of size $m$ and (rank) function $r: 2^E\to \mathbb{Z}_{\geq 0}$ satisfying $r(S)\leq \min(r(E),|S|)$ for every set $S\subseteq E$, the Tutte polynomial $$T_M(x,y):=\sum_{S\subseteq E}(x-1)^{r(E)-r(S)}(y-1)^{|S|-r(S)},$$ written as $T_M(x,y)=\sum_{i,j}t_{ij}x^iy^j$, satisfies that for any integer $h \geq 0$, we have $$\sum_{i=0}^h\sum_{j=0}^{h-i}\binom{h-i}{j}(-1)^jt_{ij}=(-1)^{m-r}\binom{h-r}{h-m},$$ where $r=r(E)$, and we use the convention that when $h<m$, the binomial coefficient $\binom{h-r}{h-m}$ is interpreted as $0$. This generalizes a theorem of Brylawski on matroid rank functions and $h<m$, and a theorem of Gordon for $h\leq m$ with the same assumptions on the rank function. The proof presented here is significantly shorter than the previous ones. We only use the fact that the Tutte polynomial $T_M(x,y)$ simplifies to $(x-1)^{r(E)}y^{|E|}$ along the hyperbola $(x-1)(y-1)=1$.
