Rota基底予想

同義語:Rotaの基底予想Rota's basis conjectureRota basis conjecture

概要

Rota基底予想(Rota's basis conjecture)とは、階数 $n$ のマトロイドの $n$ 個の基を $n\times n$ の表の行に並べるとき、各行の並べ方を選んですべての列も基にできる、すなわち互いに素な横断基が $n$ 個とれるという未解決の予想である。横断基が 1 つあることと $n=2$ の場合は増加公理と閉包から示せる。体 $K$ の上のベクトルの場合には、列の行列式の積の符号つきの和が、偶と奇のラテン方陣の個数の差 $\mathrm{AT}(n)$ と各基の行列式の積の積に等しく、$\mathrm{AT}(n)$ が $K$ で $0$ でなければ予想が成り立つが、奇数の $n\ge3$ では $\mathrm{AT}(n)=0$ である。一般のマトロイドでは、互いに素な横断基を $(1/2-o(1))n$ 個とれることなどが知られている。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: マトロイド, ラテン方陣, 行列式

Rota基底予想(Rota's basis conjecture)は、階数 $n$ のマトロイドの $n$ 個の基 $B_1,\dots,B_n$ を $n\times n$ の表の行に並べるとき、各行の並べ方をうまく選べば、すべての列も基になる、という予想である。Rota が 1989 年に $n$ 次元ベクトル空間(標数 $0$ の体の上)の基について述べ、マトロイドへの一般化も Rota が考えた(BKPS20 pp. 1–2。同論文は予想の出典として Huang と Rota の論文 HR94 を挙げる)。マトロイドの特性多項式についての Heron–Rota–Welsh予想 とは別の予想である。
予想は 未解決 である(BKPS20 p. 1、Pok25 p. 1)。$n$ 個のうち何個の「列」を基にできるかについては、$(1/2-o(1))n$ 個(BKPS20 Theorem 1.1、p. 2)などの部分的な結果がある。標数 $0$ の体の上のベクトルについては、予想がラテン方陣の符号つきの個数と結びつき、位数 $n$ のラテン方陣の偶のものと奇のものの個数が異なれば予想が成り立つ。
この記事では、予想の定式化と同値な言い換えを述べ、易しい場合(横断基が 1 つあること、$n=2$)を証明する。主な結果として、行列式の恒等式によってベクトルの場合の予想をラテン方陣の数え上げに帰着する定理(thm-rbc-identity)を証明し、$n=2,4$ で予想が成り立つことを導く。

内容場所
横断基と予想def-rbc-transversal、conj-rbc-main
易しい場合prop-rbc-greedy、prop-rbc-two
行列式の恒等式def-rbc-sign、thm-rbc-identity、cor-rbc-vector
奇数の位数prop-rbc-odd
部分的な結果rem-rbc-progress
例と反例ex-rbc-latin、ex-rbc-counter

定式化

マトロイドの公理、基、階数、閉包は マトロイド のとおりとする。基 $B_1,\dots,B_n$ には同じ元が含まれてもよいので、$B_i$ の元 $x$ を、どの基から取ったかを覚えた組 $(x,i)$ として扱う。

横断基

$M$ を有限集合 $S$ の上の階数 $n$ のマトロイドとし、$B_1,\dots,B_n$ を $M$ の基とする。$x_i\in B_i$($i=1,\dots,n$)の選び方で、$x_1,\dots,x_n$ が相異なり $\{x_1,\dots,x_n\}$ が $M$ の基になるものを 横断基 という。2 つの横断基 $(x_i)$、$(y_i)$ は、すべての $i$ で $x_i\ne y_i$ のとき 互いに素 であるという。

Rota基底予想

階数 $n$ のマトロイドの基 $B_1,\dots,B_n$ について、互いに素な横断基が $n$ 個ある。

$n$ 個の互いに素な横断基 $(x^{(1)}_i)_i,\dots,(x^{(n)}_i)_i$ があれば、各 $i$ で $x^{(1)}_i,\dots,x^{(n)}_i$ は $B_i$ の相異なる $n$ 元、すなわち $B_i$ の並べ替えである。よって予想は次と同値である:$n\times n$ の表の第 $i$ 行に $B_i$ の元を並べ、各行の並べ方を選んで、どの列も相異なる元からなる基にできる。この表を 基になる配置 と呼ぶ。$S$ が体 $K$ の上の $n$ 次元ベクトル空間 $K^n$ の有限部分集合で、独立性が線形独立性の線形マトロイドのとき(マトロイド の命題「線形マトロイド」)、Rota の最初の形の予想になる。

すべての基が同じ場合とラテン方陣

$B_1=\dots=B_n=B=\{b_1,\dots,b_n\}$ とする。基になる配置の各列は $B$ の相異なる $n$ 元、すなわち $B$ 全体を 1 回ずつ含む。第 $i$ 行第 $j$ 列の元を $b_{L(i,j)}$ と書くと、行も列も $\{1,\dots,n\}$ の並べ替えになるので、$L$ は ラテン方陣 である。逆にラテン方陣 $L$ から基になる配置が得られる。たとえば $L(i,j)\equiv i+j\pmod n$ の巡回的なラテン方陣を使えばよい。この場合、予想は $M$ によらず成り立つ。

易しい場合

横断基の存在

def-rbc-transversal の状況で、どの $x_1\in B_1$ についても、それを第 1 成分とする横断基がある。

$\{x_1,\dots,x_i\}$($x_l\in B_l$、相異なる)が独立で $i< n$ とする。$\lvert B_{i+1}\rvert=n>i$ なので、(I3)により $x_{i+1}\in B_{i+1}\setminus\{x_1,\dots,x_i\}$ で $\{x_1,\dots,x_{i+1}\}$ が独立になるものがある。$i=1$ から始めて $i=n$ まで続けると、$n$ 元の独立集合、すなわち基が得られる。$x_1$ は基 $B_1$ の元なのでループでなく、$\{x_1\}$ は独立である。$\square$

予想の難しさは、横断基を $n$ 個、互いに素にとる点にある。1 つずつ貪欲にとると、残った元で次の横断基が作れなくなることがある。

n=2 の場合

階数 $2$ のマトロイドの基 $B_1=\{a_1,a_2\}$、$B_2=\{b_1,b_2\}$ について、$\{a_1,b_1\},\{a_2,b_2\}$ がともに基であるか、$\{a_1,b_2\},\{a_2,b_1\}$ がともに基である。

基の元はループでない。$a\in B_1$、$b\in B_2$ について $\{a,b\}$ が基でない($a=b$ か、$\{a,b\}$ が従属)とき、$a,b$ は くっつく ということにする。このとき $r(\{a,b\})\le1=r(\{a\})$ なので $b\in\operatorname{cl}(\{a\})$ である。
$a_1$ が $b_1,b_2$ の両方とくっつくなら、$\{b_1,b_2\}\subseteq\operatorname{cl}(\{a_1\})$ であり、マトロイド の命題「閉包とフラットの性質」の 1 と(R2)から $r(\{b_1,b_2\})\le r(\operatorname{cl}(\{a_1\}))=1$ となって $B_2$ が基であることに反する。よって各 $a_i$ がくっつく $b_j$ は 1 つ以下であり、同様に($a$ と $b$ の役を替えて)各 $b_j$ がくっつく $a_i$ も 1 つ以下である。
$\{a_1,b_1\},\{a_2,b_2\}$ のどちらかが基でないとし、$a_1,b_1$ がくっつくとする($a_2,b_2$ の場合も同じ)。すると $a_1$ は $b_2$ とくっつかず、$b_1$ は $a_2$ とくっつかないので、$\{a_1,b_2\},\{a_2,b_1\}$ はともに基である。$\square$

$n\le4$ のすべてのマトロイドで予想が成り立つことは、計算機を使った確認として報告されている(BKPS20 p. 2 は、Cheung による未刊行の原稿として紹介する)。

行列式の恒等式とラテン方陣

この節では $K$ を体とし、$M$ は $K^n$ のベクトルの線形マトロイドとする。$i$ 番目の基を $v_{i,1},\dots,v_{i,n}\in K^n$ とし、$c$ 行目が $v_{i,c}$ である行列を $A_i$ とする。ベクトル $v$ の第 $s$ 成分を $v[s]$ と書く。$n$ 個のベクトルが基であることと、それを行に並べた行列の行列式が $0$ でないことは同値である(行列式 の定理「正則性の判定」)。
$\sigma=(\sigma_1,\dots,\sigma_n)\in S_n^{\,n}$ ごとに、第 $i$ 行を $v_{i,\sigma_i(1)},\dots,v_{i,\sigma_i(n)}$ と並べた表を考え、その第 $j$ 列の $n$ 本のベクトルを行に並べた行列の行列式を
$$ D_j(\sigma):=\det\bigl(v_{1,\sigma_1(j)},v_{2,\sigma_2(j)},\dots,v_{n,\sigma_n(j)}\bigr) $$
とおく(行列式 の定義の、行ベクトルを並べる記法)。この表が基になる配置であることは、すべての $j$ で $D_j(\sigma)\ne0$ であることと同値である。

ラテン方陣の符号

位数 $n$ のラテン方陣 $L$(成分は $\{1,\dots,n\}$)について、第 $i$ 行を置換 $\rho_i\colon j\mapsto L(i,j)$、第 $j$ 列を置換 $\kappa_j\colon i\mapsto L(i,j)$ とみて、
$$ \operatorname{sgn}L:=\prod_{i=1}^n\operatorname{sgn}\rho_i\prod_{j=1}^n\operatorname{sgn}\kappa_j $$
と定める。$\operatorname{sgn}L=1$ のとき $L$ は 偶、$-1$ のとき 奇 であるという。位数 $n$ のラテン方陣全体にわたる和 $\operatorname{AT}(n):=\sum_L\operatorname{sgn}L$(偶の個数から奇の個数を引いたもの)を考える。

色つきの行列式の恒等式

上の状況で
$$ F:=\sum_{\sigma\in S_n^{\,n}}\Bigl(\prod_{i=1}^n\operatorname{sgn}\sigma_i\Bigr)\prod_{j=1}^nD_j(\sigma)=\operatorname{AT}(n)\prod_{i=1}^n\det A_i $$
が成り立つ。ここで右辺の整数 $\operatorname{AT}(n)$ は $K$ の元とみる。

展開.$D_j(\sigma)$ を 行列式 の定義「Leibnizの公式による定義」で展開すると、第 $i$ 行 $v_{i,\sigma_i(j)}$ から第 $\tau_j(i)$ 成分を選ぶ項の和として
$$ D_j(\sigma)=\sum_{\tau_j\in S_n}\operatorname{sgn}\tau_j\prod_{i=1}^nv_{i,\sigma_i(j)}[\tau_j(i)] $$
である。$j=1,\dots,n$ について掛けて展開し、$\tau=(\tau_1,\dots,\tau_n)$ に $n\times n$ の表 $L(i,j):=\tau_j(i)$ を対応させる。これは $S_n^{\,n}$ と「各列が $\{1,\dots,n\}$ の並べ替えである表」の全体との全単射で、$\tau_j$ は $L$ の第 $j$ 列の置換 $\kappa_j$ である。和の順序を入れ替えると
$$ F=\sum_L\Bigl(\prod_{j=1}^n\operatorname{sgn}\kappa_j\Bigr)\prod_{i=1}^nG_i(L),\qquad G_i(L):=\sum_{\sigma_i\in S_n}\operatorname{sgn}\sigma_i\prod_{j=1}^nv_{i,\sigma_i(j)}[L(i,j)] $$
となる($L$ は各列が並べ替えである表全体を動く)。
$G_i(L)$ の計算.$(c,j)$ 成分が $v_{i,c}[L(i,j)]$ である行列を $N$ とする。$N$ の第 $j$ 列は $A_i$ の第 $L(i,j)$ 列である。積の添字を $c=\sigma_i(j)$ に取り替え、$\pi:=\sigma_i^{-1}$($\operatorname{sgn}\pi=\operatorname{sgn}\sigma_i$)とおくと
$$ G_i(L)=\sum_{\pi\in S_n}\operatorname{sgn}\pi\prod_{c=1}^nN[c,\pi(c)]=\det N $$
である。$j\mapsto L(i,j)$ が単射でなければ、$N$ は等しい 2 つの列をもつので、行列式 の命題「転置と行列式」と定理「多重線形性と交代性」の 2 により $\det N=0$ である。単射なら、それは第 $i$ 行の置換 $\rho_i$ であり、$N$ は $A_i$ の列を $\rho_i$ で並べ替えた行列である。$\rho_i$ を互換の積に書き、2 つの列の入れ替えごとに行列式が $-1$ 倍になること(同じ命題と定理の 3)と符号の乗法性から、$\det N=\operatorname{sgn}\rho_i\det A_i$ である。
まとめ.$G_i(L)\ne0$ となりうるのは、すべての行が並べ替え、すなわち $L$ がラテン方陣のときだけである。そのとき $\prod_iG_i(L)=\prod_i\operatorname{sgn}\rho_i\prod_i\det A_i$ なので
$$ F=\sum_{L}\prod_j\operatorname{sgn}\kappa_j\prod_i\operatorname{sgn}\rho_i\prod_i\det A_i=\operatorname{AT}(n)\prod_{i=1}^n\det A_i $$
であり、和は位数 $n$ のラテン方陣全体にわたる。$\square$

ベクトルの場合の予想

$v_{i,1},\dots,v_{i,n}$($i=1,\dots,n$)がそれぞれ $K^n$ の基で、$\operatorname{AT}(n)$ が $K$ で $0$ でないとする。このとき $F\ne0$ であり、基になる配置がある。特に $K$ の標数が $0$ で $\operatorname{AT}(n)\ne0$ なら、$K^n$ の $n$ 個の基について Rota基底予想が成り立つ。

各 $A_i$ の行は基なので $\det A_i\ne0$ であり、thm-rbc-identity により $F=\operatorname{AT}(n)\prod_i\det A_i\ne0$ である。$F$ は $\prod_jD_j(\sigma)$ の符号つきの和なので、ある $\sigma$ で $\prod_jD_j(\sigma)\ne0$、すなわちすべての $j$ で $D_j(\sigma)\ne0$ であり、その $\sigma$ の表は基になる配置である。標数 $0$ では整数 $\operatorname{AT}(n)\ne0$ は $K$ でも $0$ でない。$\square$

奇数の位数

$n\ge3$ が奇数なら $\operatorname{AT}(n)=0$ である。したがって奇数の $n\ge3$ では thm-rbc-identity の $F$ はつねに $0$ である。

ラテン方陣 $L$ の第 1 行と第 2 行を入れ替えた表を $L'$ とすると、$L'$ もラテン方陣であり、$L\mapsto L'$ は 2 回で元に戻る。$L'(1,1)=L(2,1)\ne L(1,1)$ なので $L'\ne L$ であり、ラテン方陣全体は $\{L,L'\}$ の対に分かれる。$L'$ の行の置換は $L$ の行の置換を並べ替えたものなので、行の符号の積は変わらない。$L'$ の第 $j$ 列の置換は $\kappa_j$ に互換 $(1\ 2)$ を右から合成したものなので、各列の符号は $-1$ 倍になり、$n$ 列で $(-1)^n=-1$ 倍になる。よって $\operatorname{sgn}L'=-\operatorname{sgn}L$ であり、対ごとの和は $0$、したがって $\operatorname{AT}(n)=0$ である。$\square$

$n$ が偶数のときは同じ入れ替えで符号は変わらない。偶数の $n$ で $\operatorname{AT}(n)\ne0$、すなわち偶のラテン方陣と奇のラテン方陣の個数が異なるという予想は、Alon–Tarsi 予想と呼ばれる(BKPS20 p. 1 は偶と奇のラテン方陣の数え上げについての予想として触れる)。ベクトルの場合の予想とこの数え上げとの結びつきは Huang と Rota が見いだし、Onn が簡単にした(BKPS20 pp. 1–2)。Drisko と Glynn の Alon–Tarsi 予想についての結果により、標数 $0$ の体の上のベクトルについての Rota基底予想は、偶数の $n$ が素数 $p$ によって $n=p+1$ または $n=p-1$ と書けるときに成り立つことが知られている(BKPS20 p. 2)。

小さい位数の値

$\operatorname{AT}(1)=1$、$\operatorname{AT}(2)=2$、$\operatorname{AT}(3)=0$、$\operatorname{AT}(4)=576$ である。位数 $2$ のラテン方陣は $\begin{pmatrix}1&2\\2&1\end{pmatrix}$ と $\begin{pmatrix}2&1\\1&2\end{pmatrix}$ の 2 個で、どちらも行の符号の積が $-1$、列の符号の積が $-1$ なので偶である。位数 $4$ のラテン方陣 576 個を数え上げると、すべてが偶である。したがって cor-rbc-vector から、標数が $2$ でない体 $K$ では $K^2$ の、標数が $2,3$ でない体では $K^4$ の基について予想が成り立つ($576=2^6\cdot3^2$)。$n=2$ の場合は体によらず prop-rbc-two で示してある。

部分的な結果

現況と部分的な結果

次の結果が知られている(BKPS20 pp. 1–2、Pok25 pp. 1–2 の紹介による)。

  • 特別なマトロイドの族:強基順序可能(strongly base orderable)なマトロイド(Wild)、ペービングマトロイド(Geelen と Humphries)で予想は成り立つ。
  • 互いに素な横断基の個数:$\Omega(\sqrt n)$ 個(Geelen と Webb)、$\Omega(n/\log n)$ 個(Dong と Geelen)と改善され、任意の $\varepsilon>0$ について、十分大きい $n$ では $(1/2-\varepsilon)n$ 個とれる(BKPS20 Theorem 1.1、p. 2)。
  • 大きさ $n-o(n)$ の互いに素な横断独立集合(各 $B_i$ から高々 1 元ずつとった独立集合)が $n-o(n)$ 個とれる(Pok25 の要旨、p. 1)。
  • $B_1\cup\dots\cup B_n$ の元は $2n$ 個の横断独立集合で覆える(Aharoni と Berger。BKPS20 p. 2)。

反例

外した仮定・替えた条件反例成り立たなくなる結論
$M$ がマトロイド(conj-rbc-main)$K_4$ の辺の上の、マッチング(端点を共有しない辺の集合)を独立とする族。$n=2$、$B_1=\{12,34\}$、$B_2=\{13,24\}$基になる配置がない
$\operatorname{AT}(n)\ne0$($K$ で)(cor-rbc-vector)$K=\mathbb F_2$、$n=2$、$B_1=B_2=\{e_1,e_2\}$$F=2\cdot1\cdot1=0$ で、$F\ne0$ が成り立たない
$\operatorname{AT}(n)\ne0$($n$ を奇数にとる)(cor-rbc-vector)$n=3$、$K=\mathbb Q$、任意の 3 個の基$F=0$ で、$F\ne0$ が成り立たない
反例の確かめ

どの行も、右の欄の主張を直接確かめられる。

確かめを開く

1 行目:$K_4$ のマッチングの最大の大きさは 2 で、$B_1,B_2$ はどちらも大きさ 2 の極大な独立集合である。配置の列は $B_1$ の辺 1 本と $B_2$ の辺 1 本からなるが、$12$ と $13$、$12$ と $24$、$34$ と $13$、$34$ と $24$ はどれも端点を共有するので、どの列もマッチングにならない。この族は(I3)をみたさない($\{12\}$ に $13$ も $24$ も加えられない)ので、外した仮定はマトロイドであることだけである。

2 行目:thm-rbc-identity により $F=\operatorname{AT}(2)\det A_1\det A_2=2=0$ である。それでも $B_1$ の並びをそのまま、$B_2$ の並びを入れ替えれば、列 $\{e_1,e_2\}$、$\{e_2,e_1\}$ はどちらも基であり、配置の存在そのものは prop-rbc-two で保証される。恒等式から配置の存在を読み取る議論だけが働かなくなる。

3 行目:prop-rbc-odd により $\operatorname{AT}(3)=0$ なので $F=0$ である。

関連項目

参考文献

[1]
Matija Bucić; Matthew Kwan; Alexey Pokrovskiy; Benny Sudakov, Halfway to Rota's basis conjecture, International Mathematics Research Notices, 2020, 刊行版 pp. 8007–8026。arXiv 版 v1(arXiv:1810.07462)の頁:序論 pp. 1–2、Theorem 1.1 p. 2
[2]
Alexey Pokrovskiy, Rota's Basis Conjecture holds asymptotically, Proceedings of the American Mathematical Society, 2025, arXiv 版 v1(arXiv:2008.06045、2020)の頁:要旨 p. 1、序論 pp. 1–2
[3]
Rosa Huang; Gian-Carlo Rota, On the relations of various conjectures on Latin squares and straightening coefficients, Discrete Mathematics, 1994, 225–236

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する