Baranyaiの定理

同義語:Baranyai's theoremBaranyai theorem

概要

Baranyaiの定理(Baranyai's theorem)とは、$k$ が $n$ を割り切るとき、$n$ 元集合の $k$ 元部分集合の全体を、それぞれが全体集合の分割になる $\binom{n-1}{k-1}$ 個の平行類に分けられる、すなわち完全 $k$-一様ハイパーグラフが $1$-因子分解をもつという定理である。頂点を 1 個ずつ増やしながら途中の組分けを育て、各段で分数の解が明らかなネットワークに最大流の整数性を当てると得られる。$k\nmid n$ では平行類が存在しない。系として $k\mid n$ の場合の Erdős–Ko–Rado の不等式が直ちに従う。

$$\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}} $$

前提知識: ハイパーグラフ, 最大流最小カット定理, 二項係数

Baranyaiの定理(Baranyai's theorem)とは、$k$ が $n$ を割り切るとき、$n$ 元集合の $k$ 元部分集合の全体を、それぞれが全体集合の分割になる組(平行類)に分けられる、という定理である。ハイパーグラフの言葉では、完全 $k$-一様ハイパーグラフ $K_n^{(k)}$ の辺集合が完全マッチングに分割できる($1$-因子分解をもつ)。平行類の個数は $\binom{n-1}{k-1}$ である。
たとえば $n=15$、$k=3$ なら、15 人から作れる 3 人組 455 組すべてを、「毎日全員を 5 組の 3 人組に分ける」予定で、同じ組を繰り返さず 91 日で使い切れる。$k=2$ は総当たりの試合の日程で、昔から明示的な作り方が知られている(prop-bar-k2)。$k=3$ は Peltesohn が 1936 年に解決し、一般の $k$ は Baranyai が 1975 年に証明した(HHM22 p. 1、Bar75)。
不思議なのは証明の形である。平行類を直接作るのではなく、頂点を 1 個ずつ増やしながら「途中まで作った組分け」を育て、各段で分数の解が明らかなネットワークに 最大流最小カット定理 の整数性を当てて、整数の解に丸める。組合せ的な構成の難しさを、流れの整数性が肩代わりする。

主張内容この記事で
thm-bar-main$k\mid n$ なら平行類に分割できる証明する
lem-bar-stage途中の段の組分けの存在(主定理より強い形)証明する
cor-bar-ekr$k\mid n$ のときの Erdős-Ko-Radoの定理証明する
prop-bar-k2$k=2$ の明示的な分割証明する
rem-bar-general非一様な場合への拡張主張と所在

主張

$[n]:=\{1,\dots,n\}$ とし、$[n]$ の $k$ 元部分集合の全体を $\binom{[n]}{k}$ と書く。これは完全 $k$-一様ハイパーグラフ $K_n^{(k)}$ の辺集合である。

平行類と分割

$1\le k\le n$ とする。$\binom{[n]}{k}$ の部分集合で、その元が互いに交わらず和が $[n]$ になるものを 平行類(parallel class)という。これは $K_n^{(k)}$ の完全マッチング($1$-因子)と同じものである。$\binom{[n]}{k}$ を平行類に分けること、すなわちどの $k$ 元部分集合もちょうど 1 つの平行類に属するようにすることを、$K_n^{(k)}$ の $1$-因子分解 という。

平行類があれば $[n]$ が $k$ 元集合に分割されるので、$k\mid n$ が必要である。$n=km$ とすると、平行類は $m$ 個の元をもち、分割の個数は
$$ M:=\frac1m\binom nk=\frac kn\binom nk=\binom{n-1}{k-1} $$
に決まる。頂点 $1$ を含む $k$ 元部分集合が $\binom{n-1}{k-1}$ 個あり、各平行類がそのちょうど 1 つを含むと数えてもよい。

Baranyai の定理

$k,m\ge1$、$n=km$ とする。$\binom{[n]}{k}$ は $\binom{n-1}{k-1}$ 個の平行類に分割できる。

証明の所在

lem-bar-stage の $\ell=n$ の場合で、証明は prf-bar-main にある。$m=1$($k=n$)の分割は全体集合 1 個の類だけで、$k=1$ の分割は $\{\{1\},\dots,\{n\}\}$ の 1 個の類だけである。

途中の段を数える

主定理の分割があるとして、各平行類の各元を $[\ell]$ に制限する($T\mapsto T\cap[\ell]$)。すると、平行類ごとに $[\ell]$ の分割(空集合を含んでよい)が得られ、$S\subseteq[\ell]$ は「$T\cap[\ell]=S$ となる $k$ 元集合 $T$ の個数」、すなわち $\binom{n-\ell}{k-\lvert S\rvert}$ 回現れる。この数え上げの条件だけを課して、$\ell$ についての帰納法で作る。これが証明の着想である。
二項係数は整数 $a\ge0$ と任意の整数 $b$ について、$b< 0$ または $b>a$ なら $\binom ab=0$ と約束する。このとき $a\ge1$ で
$$ \binom ab=\binom{a-1}b+\binom{a-1}{b-1},\qquad\frac ba\binom ab=\binom{a-1}{b-1}\quad(b\ge0)\qquad(1) $$
が成り立つ。

$\ell$ 段の組分け

$n=km$、$M=\binom{n-1}{k-1}$、$0\le\ell\le n$ とする。$\ell$ 段の組分け とは、$M$ 個の多重集合 $\mathcal{A}_1,\dots,\mathcal{A}_M$ の組で、次を満たすものをいう。

  1. 各 $\mathcal{A}_i$ は $[\ell]$ の部分集合をちょうど $m$ 個(重複を数えて)もち、それらは互いに交わらず、和は $[\ell]$ である。空集合は何回現れてもよい。
  2. 各 $S\subseteq[\ell]$ について、$S$ が $\mathcal{A}_1,\dots,\mathcal{A}_M$ に現れる回数の総和は $\binom{n-\ell}{k-\lvert S\rvert}$ である。

条件 2 から、$\lvert S\rvert>k$ の集合は現れない。空でない $S$ は 1 つの $\mathcal{A}_i$ に高々 1 回しか現れないが、空集合は同じ $\mathcal{A}_i$ に何回も現れうる。

すべての段の組分けの存在

$n=km$ のとき、すべての $0\le\ell\le n$ について $\ell$ 段の組分けが存在する。

分数の流れを整数に丸める

$\ell$ についての帰納法による。
$\ell=0$. すべての $\mathcal{A}_i$ を空集合 $m$ 個とする。空集合の総回数は $mM=\binom nk$ で、条件 2 を満たす。
$\ell$ から $\ell+1$ へ($\ell< n$). $\ell$ 段の組分け $\mathcal{A}_1,\dots,\mathcal{A}_M$ が与えられたとする。各 $\mathcal{A}_i$ から元を 1 つ選んで新しい頂点 $\ell+1$ を加えれば、条件 1 は保たれる。どの元を選ぶかを流れで決める。
ネットワークを次のように作る。頂点は、始点 $s$、終点 $t$、各 $i$ に対する $a_i$、現れる $S\subseteq[\ell]$ に対する $b_S$ である。弧と容量は次のとおりとする。

  • $s\to a_i$:容量 $1$。
  • $a_i\to b_S$:容量は $S$ が $\mathcal{A}_i$ に現れる回数。
  • $b_S\to t$:容量 $\binom{n-\ell-1}{k-\lvert S\rvert-1}$。
    容量はすべて $0$ 以上の整数である。

分数の流れ. 比 $\frac{k-\lvert S\rvert}{n-\ell}$ は、$T\cap[\ell]=S$ となる $k$ 元集合 $T$ のうち $\ell+1$ を含むものの割合である。そこで弧 $s\to a_i$ に $1$ を流し、弧 $a_i\to b_S$ に($S$ が $\mathcal{A}_i$ に現れる回数)$\times\frac{k-\lvert S\rvert}{n-\ell}$ を流し、$b_S\to t$ には入ってきた量を流す。現れる $S$ は条件 2 の回数 $\binom{n-\ell}{k-\lvert S\rvert}$ が正なので $0\le k-\lvert S\rvert\le n-\ell$ を満たし、$0\le\frac{k-\lvert S\rvert}{n-\ell}\le1$ である。よって弧 $a_i\to b_S$ の容量を超えない。各点で流量が保存されることを確かめる。

  • $a_i$ から出る量は、条件 1 により
    $$ \sum_{S\in\mathcal{A}_i}\frac{k-\lvert S\rvert}{n-\ell}=\frac{mk-\ell}{n-\ell}=1 $$
    である(和は $\mathcal{A}_i$ の $m$ 個の元を重複を数えて動く)。
  • $b_S$ に入る量は、条件 2 と (1) により
    $$ \binom{n-\ell}{k-\lvert S\rvert}\frac{k-\lvert S\rvert}{n-\ell}=\binom{n-\ell-1}{k-\lvert S\rvert-1} $$
    で、$b_S\to t$ の容量に等しい。
    よってこの流れは容量を守り、値は $M$ である。$s$ から出る弧の容量の和が $M$ なので、これは最大流である。

整数の流れ. 容量がすべて整数なので、最大流最小カット定理 の記事の整数性定理により、整数値の最大流 $f$ がある。その値は $M$ である。よって $f$ はすべての $s\to a_i$ で $1$ であり、各 $a_i$ から出る弧のうちちょうど 1 本 $a_i\to b_{S_i}$ だけで値が $1$ で、他は $0$ である。$b_S\to t$ の容量の和も $M$ なので、これらの弧もすべて満たされる。すなわち、$S_i=S$ となる $i$ の個数は $\binom{n-\ell-1}{k-\lvert S\rvert-1}$ である。現れない $S$ では $\binom{n-\ell}{k-\lvert S\rvert}=0$ なので $k-\lvert S\rvert$ は $0$ 未満か $n-\ell$ より大きく、この二項係数も $0$ で、等式はそのまま成り立つ。また $f(a_i\to b_{S_i})=1$ は容量以下なので、$S_i$ は $\mathcal{A}_i$ に現れる。
更新. 各 $i$ について、$\mathcal{A}_i$ の元 $S_i$ の 1 つを $S_i\cup\{\ell+1\}$ に替えたものを $\mathcal{A}_i'$ とする。条件 1 は明らかである。条件 2 を確かめる。$T\subseteq[\ell+1]$ とする。

  • $\ell+1\in T$ のとき、$S:=T\setminus\{\ell+1\}$ とすると、$T$ の回数は $S_i=S$ となる $i$ の個数で、$\binom{n-\ell-1}{k-\lvert S\rvert-1}=\binom{n-(\ell+1)}{k-\lvert T\rvert}$ である。
  • $\ell+1\notin T$ のとき、$T$ の回数はもとの回数から選ばれた回数を引いたもので、(1) により
    $$ \binom{n-\ell}{k-\lvert T\rvert}-\binom{n-\ell-1}{k-\lvert T\rvert-1}=\binom{n-(\ell+1)}{k-\lvert T\rvert} $$
    である。
    よって $\mathcal{A}_1',\dots,\mathcal{A}_M'$ は $\ell+1$ 段の組分けである。$\square$
最後の段から読み取る

lem-bar-stage で $\ell=n$ とする。条件 2 により、$S\subseteq[n]$ の回数の総和は $\binom0{k-\lvert S\rvert}$ で、$\lvert S\rvert=k$ なら $1$、それ以外なら $0$ である。よって各 $\mathcal{A}_i$ の $m$ 個の元はすべて $k$ 元集合で($k\ge1$ なので空集合も現れない)、条件 1 により $\mathcal{A}_i$ は平行類である。各 $k$ 元部分集合はちょうど 1 つの $\mathcal{A}_i$ にちょうど 1 回現れる。$\square$

例

$n=4$、$k=2$ の段の変化

$m=2$、$M=3$ である。条件 2 の回数は、$\ell=2$ で空集合 $1$、$1$ 元集合 $2$、$2$ 元集合 $1$ である。各段の組分けの一例は次のとおりである。

$\ell$$\mathcal{A}_1$$\mathcal{A}_2$$\mathcal{A}_3$
$0$$\emptyset,\emptyset$$\emptyset,\emptyset$$\emptyset,\emptyset$
$1$$\{1\},\emptyset$$\{1\},\emptyset$$\{1\},\emptyset$
$2$$\{1,2\},\emptyset$$\{1\},\{2\}$$\{1\},\{2\}$
$3$$\{1,2\},\{3\}$$\{1,3\},\{2\}$$\{1\},\{2,3\}$
$4$$\{1,2\},\{3,4\}$$\{1,3\},\{2,4\}$$\{1,4\},\{2,3\}$

$\ell=1$ から $\ell=2$ への段で、$\mathcal{A}_1$ だけが $\{1\}$ を選び、他の 2 つは空集合を選ぶ。回数の条件は $S_i=\{1\}$ が $\binom{2}{0}=1$ 回、$S_i=\emptyset$ が $\binom{2}{1}=2$ 回である。ここで $\frac{k-\lvert S\rvert}{n-\ell}$ は $\{1\}$ で $\frac13$、空集合で $\frac23$ で、分数の流れでは各 $\mathcal{A}_i$ がどちらも少しずつ選んでいる。その平均的な選び方を丸めたものが表の選択である。

小さい場合
  1. $n=6$、$k=3$:平行類は $\{S,[6]\setminus S\}$ の形に決まり、$\binom52=10$ 個である。
  2. $n=9$、$k=3$:$M=\binom82=28$ である。証明の手順を実際に回すと、たとえば
    $$ \{1,2,3\},\{4,5,6\},\{7,8,9\}\quad\text{と}\quad\{1,6,7\},\{2,3,4\},\{5,8,9\} $$
    を含む 28 個の平行類が得られる。
  3. $(n,k)=(8,4),(10,5),(12,3),(12,4),(12,6)$ でも同じ手順で最大流を解き、$35,126,55,165,462$ 個の平行類への分割を得て、すべての $k$ 元集合がちょうど 1 回現れることを確かめた。
$k=2$ の明示的な分割

$n=2m$ とする。頂点集合を $\mathbb{Z}/(2m-1)\cup\{\infty\}$ とし、$i\in\mathbb{Z}/(2m-1)$ に対して
$$ \mathcal{P}_i:=\{\{\infty,i\}\}\cup\{\{i-t,i+t\}\mid t=1,\dots,m-1\} $$
とおく。$\mathcal{P}_0,\dots,\mathcal{P}_{2m-2}$ は $K_{2m}$ の $1$-因子分解である。とくに $K_{2m}$ の辺彩色数は $2m-1$ である。

$\pm t$($t=1,\dots,m-1$)は $0$ 以外の元をちょうど 1 回ずつ尽くすので、$\mathcal{P}_i$ は平行類である。辺 $\{a,b\}$($a\ne b$、ともに有限)は、$a+b=2i$ を満たす $i$ の類にだけ属する。$2$ は $\mathbb{Z}/(2m-1)$ で可逆なので、そのような $i$ はただ 1 つである。辺 $\{\infty,i\}$ は $\mathcal{P}_i$ にだけ属する。辺彩色数は、各頂点の次数 $2m-1$ が下界で、この分割が上界を与える。$\square$

応用

$k\mid n$ の Erdős–Ko–Rado

$k\mid n$、$n\ge2k$ とし、$\mathcal{F}\subseteq\binom{[n]}k$ のどの 2 元も交わるとする。このとき $\lvert\mathcal{F}\rvert\le\binom{n-1}{k-1}$ である。

thm-bar-main の分割をとる。1 つの平行類の元は互いに交わらないので、$\mathcal{F}$ は各平行類の元を高々 1 つしか含まない。平行類は $\binom{n-1}{k-1}$ 個である。$\square$

等号は頂点 $1$ を含むすべての $k$ 元集合の族で成り立つ。一般の $n\ge2k$ の不等式は Erdős-Ko-Radoの定理 の記事にある。$k\nmid n$ ではこの議論は使えない。
同じ考えで、$\binom{[n]}k$ の辺彩色(交わる 2 元に異なる色を塗る)の最小の色数は、$k\mid n$ なら $\binom{n-1}{k-1}$ である。1 色の元は高々 $m$ 個なので下界が出て、thm-bar-main が上界を与える。

$n\equiv-1\pmod k$ の場合

$k\ge2$、$n=km-1$ とする。$[n]$ の $k$ 元部分集合と $(k-1)$ 元部分集合をすべて合わせた族は、$\binom n{k-1}$ 個の $[n]$ の分割に分けられ、各分割は $(k-1)$ 元集合 1 個と $k$ 元集合 $m-1$ 個からなる。

$[n+1]$ に thm-bar-main を当て、各平行類の元から頂点 $n+1$ を除く。各平行類の中で $n+1$ を含む元はちょうど 1 つで、それが $(k-1)$ 元集合になる。$[n]$ の $(k-1)$ 元集合 $S$ は $S\cup\{n+1\}$ の属する類に、$k$ 元集合はそのままの類に、ちょうど 1 回ずつ現れる。類の個数は $\binom{n}{k-1}$ である。$\square$

$(k-1)$ 元集合を捨てれば、$k\nmid n$ でも $n\equiv-1$ なら、$k$ 元集合の全体を、それぞれ $k-1$ 個の頂点を残すだけの互いに素な族に分けられる。$k=2$、$n=5$ では、$K_5$ の 10 本の辺が、1 頂点だけ残す 2 本ずつの組 5 個に分かれる。
Kirkmanの女学生問題 との違いに注意する。Kirkman の問題は 15 人を 3 人組に分ける日程を 7 日作り、どの 2 人も 1 回だけ同じ組になるようにする(Steiner系 の分解可能性の問題)。Baranyai の定理は 3 人組をすべて使い切るもので、どの 2 人も $13$ 回同じ組になる。どちらかがもう一方を含むわけではない。

手順としての証明

証明は $n$ 回の最大流の計算からなる手順で、各段のネットワークの頂点は $M+\binom nk+2$ 個以下である(異なる $S$ は多くとも $mM=\binom nk$ 個)。よって時間は $\binom nk$ の多項式で抑えられる。しかし途中の選択に任せたまま進むので、できる平行類を式で書き表すものではない。$k=2$ の prop-bar-k2 のような公式は、証明からは出てこない。

反例:条件を外すと成り立たないこと

外すもの反例成り立たなくなるもの
$k\mid n$$n=5$、$k=2$:奇数個の頂点は 2 元集合に分割できない平行類の存在そのもの
完全であること$n=6$、$k=3$ で辺 $S$ を 1 つ除く:$[6]\setminus S$ と交わらない 3 元集合は $S$ だけなので、$[6]\setminus S$ を含む平行類がない残りの辺の平行類への分割
頂点ごとに全類へ同時に配ること平行類を 1 つずつ順に選ぶ(ex-bar-greedy)途中までの平行類が全体の分割に延びること
欲張りが止まる

$n=6$、$k=2$ で、頂点を $\{1,2,3\}$ と $\{4,5,6\}$ に分け、完全二部グラフ $K_{3,3}$ を 3 つの平行類 $\{14,25,36\}$、$\{15,26,34\}$、$\{16,24,35\}$ に分ける。どれも $K_6$ の平行類として正しいが、残った辺は 2 つの三角形 $123$、$456$ で、完全マッチングをもたない。よって途中まで選んだ平行類は、全体の分割に延ばせるとは限らない。全体の分割には 5 個の平行類が要るのに、この選び方では 3 個で止まる。lem-bar-stage は平行類を 1 個ずつ決めるのではなく、頂点を 1 個ずつ全類に同時に配るので、この行き詰まりが起きない。

拡張

この記事では証明しない。Baranyai の定理の一般化は多くある(HHM22 p. 2 の文献)。たとえば、$k$ 元以下の空でない部分集合すべてを $[n]$ の分割に分ける問題は、$k$ を固定して $n$ を十分大きくとると、$n\equiv0,-1\pmod k$ のときに限り解ける(HHM22 の序、同じ流れの論法による)。

文献

定理は Bar75 による。この記事の証明は、Bar75 の着想(流れの整数性を当てる。HHM22 p. 2、§2)に沿って、段の組分けの形で書き直したものである。$k=3$ の場合は Pel36 による。

関連項目

参考文献

[1]
Zs. Baranyai, On the factorization of the complete uniform hypergraph, Colloquia Mathematica Societatis János Bolyai, 1975, 91–108
[2]
Jinye He, Hao Huang, Jie Ma, A non-uniform extension of Baranyai's Theorem, arXiv preprint, 2022, Theorem 1.1(p. 1)、§1(pp. 1–2)、§2
[3]
R. Peltesohn, Das Turnierproblem für Spiele zu je dreien, Inaugural dissertation, Berlin, 1936

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