バラニャイの定理

組合せ数学において、バラニヤイの定理（ゾルト・バラニヤイによって証明され、バラニヤイにちなんで名付けられた）は、完全ハイパーグラフの分解を扱っています。

結果は、 が整数でr がk を割り切る場合、完全なハイパーグラフは1 因子に分解される、というものです。はk頂点を持つハイパーグラフで、 r頂点のすべてのサブセットがハイパーエッジを形成します。このハイパーグラフの 1 因子は、各頂点にちょうど 1 回接するハイパーエッジの集合、または頂点をサイズ rのサブセットに分割することと同等です。したがって、定理は、ハイパーグラフのk頂点をさまざまな方法でr頂点のサブセットに分割し、各r要素のサブセットが 1 つのパーティションにのみ出現するようにすることができると述べています。 ${\displaystyle 2\leq r<k}$ ${\displaystyle K_{r}^{k}}$${\displaystyle K_{r}^{k}}$${\displaystyle {\binom {k}{r}}{\frac {r}{k}}={\binom {k-1}{r-1}}}$

特別なケースでは、頂点上に完全なグラフがあり、各色のエッジが完全に一致するようにエッジを色で着色します。バラニャイの定理によれば、が偶数のときはいつでもこれを実行できます。 ${\displaystyle r=2}$${\displaystyle K_{n}}$${\displaystyle n}$${\displaystyle {\binom {n}{2}}{\frac {2}{n}}=n-1}$${\displaystyle n}$

r  = 2 の場合は、頂点数が偶数であるすべての完全グラフには、次数に等しい色の数の辺彩色がある、または同等に、その辺は完全マッチング に分割できる、と言い換えることができます。これは、ラウンドロビントーナメントのスケジュール設定に使用でき、その解法は 19 世紀にすでに知られていました。k  = 2 rの場合も簡単です。

r = 3 の場合は 1936 年に R. Peltesohn によって確立されました。 一般的な場合は1975 年にZsolt Baranyaiによって証明されました。

• バラニャイ、Zs. (1975)、「完全な一様ハイパーグラフの因数分解について」、Hajnal、A. ;ラドー、R. ; Sós、VT (編)、Infinite and Finite Sets、Proc.コル。ケストヘイ、1973 年、コロキア数学。社会ヤノス・ボリャイ、vol. 10、北オランダ、91–107 ページ。
• ヴァン・リント、JH、ウィルソン、RM（2001）、組合せ論講座（第2版）、ケンブリッジ大学出版局。
• Peltesohn, R. (1936)、Das Turnierproblem für Spiele zu je dreien、就任学位論文、ベルリン{{citation}}: CS1 メンテナンス: 場所が見つかりません 発行者 (リンク)。