Heron–Rota–Welsh予想

1．ループ $\ell$ について $r(A+\ell)=r(A)$ である（$r(A)\le r(A+\ell)\le r(A)+r(\{\ell\})=r(A)$）。$\ell\notin A$ となる $A$ と $A+\ell$ を組にすると、2 つの項は指数が同じで符号が逆なので打ち消し合う。
2．$r(A)=0$ となるのは $A$ の元がすべてループのときなので、ループがなければ $\lambda^r$ の項は $A=\emptyset$ だけから来て係数は $1$ である。$r(A)\ge0$ なので次数は $r$ 以下である。
3．$\chi_M(1)=\sum_{A\subset E}(-1)^{|A|}=(1-1)^{|E|}=0$ である。
4．和を $e\notin A$ と $e\in A$ に分ける。$e$ はコループでないので $r(E-e)=r$ であり、$e\notin A$ の部分は $\sum_{A\subset E-e}(-1)^{|A|}\lambda^{r(E-e)-r(A)}=\chi_{M\setminus e}(\lambda)$ である。$e\in A$ の部分は $A=B+e$（$B\subset E-e$）と書けて、$r_{M/e}(E-e)=r-1$、$r_{M/e}(B)=r(B+e)-1$ なので
$$ \sum_{B\subset E-e}(-1)^{|B|+1}\lambda^{\,r-r(B+e)}=-\sum_{B\subset E-e}(-1)^{|B|}\lambda^{\,r_{M/e}(E-e)-r_{M/e}(B)}=-\chi_{M/e}(\lambda) $$
である。
5．$|E|$ についての帰納法で示す。すべての元がコループなら、$E$ は独立で $r(A)=|A|$ なので $\chi_M(\lambda)=\sum_A(-1)^{|A|}\lambda^{|E|-|A|}=(\lambda-1)^{r}$ であり、$w_k=\binom rk>0$ である。そうでなければ、コループでない $e$ をとる（ループはない）。$M\setminus e$ はループをもたず階数 $r$ で、帰納法の仮定が当てはまる。$M/e$ がループをもてば 1 により $\chi_{M/e}=0$ で、4 から $\chi_M=\chi_{M\setminus e}$ である。$M/e$ がループをもたなければ、階数 $r-1$ で帰納法の仮定が当てはまり、4 の $\lambda^{r-k}$ の係数は
$$ (-1)^kw_k(M\setminus e)-(-1)^{k-1}w_{k-1}(M/e)=(-1)^k\bigl(w_k(M\setminus e)+w_{k-1}(M/e)\bigr) $$
である（$w_{-1}:=0$）。どちらの場合も符号は $(-1)^k$ で、絶対値は正である。$\square$

段 1（包除原理）．頂点の $q$ 色の塗り方全体を $\Omega$ とし、辺 $e$ について、$e$ の両端が同じ色である塗り方の集合を $S_e$ とする。$P_G(q)=\bigl|\Omega\setminus\bigcup_eS_e\bigr|$ であり、包除原理により
$$ P_G(q)=\sum_{A\subset E}(-1)^{|A|}\Bigl|\bigcap_{e\in A}S_e\Bigr| $$
である（$A=\emptyset$ の項は $|\Omega|$）。$\bigcap_{e\in A}S_e$ は、$A$ の各辺の両端が同じ色である塗り方の集合で、これは $(V,A)$ の各連結成分の中で色が一定の塗り方にほかならない。成分ごとに $q$ 通りの色を選べるので、その個数は $q^{c(A)}$ である。
段 2（階数との関係）．マトロイド の命題「グラフ的マトロイド」により、森 $F$ について $c(F)=|V|-|F|$ である。$A\subset E$ の中の極大な森 $F$ は $(V,A)$ の各成分の全域木からなるので $c(A)=c(F)=|V|-|F|=|V|-r(A)$ であり、特に $c(G)=|V|-r(E)$ である。よって $c(A)=c(G)+r(E)-r(A)$ で、
$$ \sum_{A\subset E}(-1)^{|A|}q^{\,c(A)}=q^{\,c(G)}\sum_{A\subset E}(-1)^{|A|}q^{\,r(E)-r(A)}=q^{\,c(G)}\chi_{M(G)}(q) $$
である。$\square$

$t:=Q(a,\ell)/Q(\ell,\ell)$、$p:=a-t\ell$ とおくと $Q(\ell,p)=0$ なので $p\in P$ である。$Q(a,\ell)=tQ(\ell,\ell)$、$Q(a,a)=t^2Q(\ell,\ell)+Q(p,p)$ だから
$$ Q(a,\ell)^2-Q(a,a)Q(\ell,\ell)=-Q(p,p)\,Q(\ell,\ell)\ge0 $$
であり、等号は $Q(p,p)=0$、すなわち $p=0$ のときに限る。$\square$

段 1（Chow 環．引用）．$M$ の空でも全体でもないフラット $F$ ごとに変数 $x_F$ をおいた多項式環 $S_M=\mathbb R[x_F]$ を、比較できない 2 つのフラットの積 $x_{F_1}x_{F_2}$ と、相異なる $i_1,i_2\in E$ についての 1 次式 $\sum_{F\ni i_1}x_F-\sum_{F\ni i_2}x_F$ で生成されるイデアルで割った環を $A(M)$ と書き、$M$ の Chow 環 という（AHK18 Definition 1.3、p. 2。Feichtner–Yuzvinsky による）。$A(M)=\bigoplus_{q=0}^rA^q(M)$ と次数付けられ、フラットの旗 $F_1\subsetneq\dots\subsetneq F_r$ について $\deg(x_{F_1}\cdots x_{F_r})=1$ となる線形同型 $\deg\colon A^r(M)\to\mathbb R$ がある（同 p. 3、Proposition 5.10、p. 24）。狭義劣モジュラな関数から作られる $\ell\in A^1(M)$ について、Hard Lefschetz 定理と Hodge–Riemann の関係が成り立つ（同 Theorem 1.4、p. 4）。この部分は AHK18 の §2〜§8 の全体を使い、この記事では証明しない。
段 2（1 次の部分での不等式）．$r\ge2$ とする（$r\le1$ では示すべき不等式がない）。段 1 の $\ell$ について、$A^1(M)$ 上の対称双線形形式 $Q(a,b):=\deg(ab\,\ell^{r-2})$ を考える。Hodge–Riemann の関係の $q=0$ の場合は $Q(\ell,\ell)=\deg(\ell^r)>0$ を、$q=1$ の場合は $\ell^{r-1}a=0$ となる $0$ でない $a\in A^1(M)$ について $Q(a,a)< 0$ を意味する。$\deg$ は同型なので、$\ell^{r-1}a=0$ は $Q(\ell,a)=\deg(\ell^{r-1}a)=0$ と同値である。よって lem-hrw-reverse-cs の仮定がみたされ、すべての $a\in A^1(M)$ について $\deg(a^2\ell^{r-2})\deg(\ell^r)\le\deg(a\ell^{r-1})^2$ である。AHK18 Lemma 9.6（pp. 58–59）は、極限をとってこれを $\ell$ が「nef」な元の場合に広げている。
段 3（係数を次数で表す．引用）．$\overline\chi_M(\lambda):=\chi_M(\lambda)/(\lambda-1)=\sum_{k=0}^r(-1)^k\mu_k\lambda^{r-k}$ とおく（prop-hrw-basic の 3 により割り切れる）。$A^1(M)$ の 2 つの nef な元 $\alpha,\beta$ があって、$\mu_k=\deg(\alpha^{r-k}\beta^k)$ である（AHK18 Definition 5.7（p. 23）、Proposition 9.5（p. 58）、Lemma 9.7（p. 59））。段 2 の不等式を $a=\alpha$、$\ell=\beta$ に当てると $\mu_{r-2}\mu_r\le\mu_{r-1}^2$ であり、階数を下げたマトロイド（打ち切り）に同じ議論を当てて、$0< k< r$ で $\mu_{k-1}\mu_{k+1}\le\mu_k^2$ を得る（同 Proposition 9.8、pp. 59–60）。
段 4（畳み込み）．$\chi_M=(\lambda-1)\overline\chi_M$ の $\lambda^{r+1-j}$ の係数を比べると
$$ (-1)^jw_j=(-1)^j\mu_j-(-1)^{j-1}\mu_{j-1},\qquad\text{つまり}\quad w_j=\mu_j+\mu_{j-1} $$
である（範囲外は $0$）。すなわち $(w_j)$ は $(\mu_k)$ と $(1,1)$ の畳み込みである。$\mu_k$ はすべて正である（AHK18 §9.1、pp. 56–57。$\mu_k=w_k-w_{k-1}+\dots\pm w_0$ で $\mu_r$ は Möbius 関数の値の絶対値）。$(1,1)$ と $(\mu_k)$ は内部に零をもたない非負の対数凹列なので、対数凹性 の定理「畳み込みは対数凹性を保つ」により $(w_j)$ は対数凹である。これが 1 である。
段 5（独立集合の個数）．Brylawski の結果により、$f_k(M)$ は別のマトロイドの（被約）特性多項式の係数の絶対値として表されるので、2 は 1 から従う（AHK18 Theorem 9.9 の証明、p. 60）。3 は上で述べたとおり 1 と thm-hrw-chromatic から従う。$\square$