文献あり

SLPでBorsuk-Ulam Theoremを使ってみた！

335

　数オリの夏季セミナーでBorsuk-Ulamの定理(後述)を勉強したのですが, 組み合わせ位相幾何という分野でとても興味深い内容でした. 本に面白い(初等的な)応用例がたくさん掲載されており, 数オリの問題で使えないかとずっと探していたのですが, それをやっと見つけることができたので今回記事にします.

Borsuk-Ulamの定理, Lovasz-Kneserの定理

　夏季セミナーで使用した本, Using the Borsuk-Ulam Theorem(Jiri Matousek)中で掲載されている, Borsuk-Ulamの定理, そこから示すことのできるLovasz-Kneserの定理の主張を書きます(いずれも筆者翻訳).

Borsuk-Ulamの定理(p23, 抜粋)

任意の自然数$n\ge0$に対し, 以下が成立する:
　任意の連続写像$f:S^n\rightarrow\mathbb{R}^n$に対してある点$\mathbf{x}\in S^n$が存在して$f(\mathbf{x})=f(-\mathbf{x})$となる.

また, 同書ではKneserグラフという対象を考えています.

Kneserグラフ(p58, 定義部分のみ抜粋)

$[n]=\{1,2,\cdots,n\})$
$\binom{[n]}{k}$を$[n]$の$k$元部分集合を全部集めた集合とする.
頂点を$\binom{[n]}{k}$とし, 共通部分を持たない二つの集合の間に辺を張ったグラフをKneserグラフといい, $\text{KG}_{n,k}$で表す.
また, グラフ$G$の頂点彩色数を$\chi(G)$で表す.

彩色数とは, 隣り合う頂点を異なる色で塗り分けるのに必要な色の数の最小値です. 例えば, 以下の$\text{KG}_{5,2}$について彩色数は$3$になることが確認できます.
!FORMULA[14][164380055][0] $\text{KG}_{5, 2}$

さて, Kneserグラフの彩色数について, 一般に以下が成立します.

Lovasz-Kneserの定理(p59)

任意の$k>0$と$n\ge 2k-1$に対して, Kneserグラフ$\text{KG}_{n,k}$の彩色数は$\chi(\text{KG}_{n,k})=n-2k+2$で与えられる.

証明はここでは省きますが, 先述のBorsuk-Ulamの定理を用いて示すことが可能です.

SLP2016-A2の拡張

問題

SLP2016-A2(拡張済み))

以下が成立するような最小の実数$C>0$を求めよ:
任意の相異なるとは限らない正の実数$a_1, a_2, a_3, a_4, a_5, a_6$に対して, うまく相異なる添え字$i, j, k, l$を選ぶと
$$\bigg|\frac{a_i}{a_j}-\frac{a_k}{a_l}\bigg|\le C$$
が成立する.

原題では$a_5$まででした. Lovasz-Kneserの定理を使うとこの問題をエレガントに解くことができます.

解答

下からの評価

$(a_1, a_2, a_3, a_4, a_5, a_6)=(2, 2, 2, 3, 6, N)$とし, $N\to+\infty$なる極限を考えることで, $C<\dfrac13$で成立しないことがわかる.

上からの評価

$C=\dfrac13$で成立することを背理法で示す. 絶対値内の分数はいずれも$1$以下のもののみを考えて矛盾が言えれば十分. $\text{KG}_{6,2}$の頂点と分数を対応付け, 分数が$(0, 1/3],(1/3, 2/3],(2/3, 1]$のどの区間に属するかによって頂点を彩色すれば$KG_{6,2}$の$3$色の彩色を与えるが, Lovasz-Kneserの定理より$\chi(\text{KG}_{6,2})=4$なので矛盾.