Kneser猜想与相关推广
本文本來是想放在Borsuk-Ulam定理的應用這篇文章當中。但是這個文章實在是太長，導致有喧賓奪主之嫌，從而獨立出為一篇文章，僅供參考。$\newcommand{\di}{\mathrm{dist}}$
（圖1：Kneser敘述他的猜想原文手稿）
?引理1（Borsuk-Ulam）
對于任意$f:S^n\to\mathbb{R}^n$連續，存在$x\in S^n$使得$f(-x)=f(x)$。
目錄
- 1 Lyusternik-Shnirel'man定理與Greene定理
- 2 Kneser猜想與Greene的證明
- 3 Lovász的證明大意
- 4 Bárány的證明與Schrijver定理
- 5 Dol'nikov定理與超圖上的Kneser猜想
- 6 Matou?ek的組合證明以及推廣
- 7 拓撲組合的歷史注記
- 8 鳴謝與拓展閱讀
1.?Lyusternik-Shnirel'man定理與Greene定理
這個猜想的證明主要使用了Lyusternik與Shnirel'man版本的Borsuk-Ulam定理，它的具體表述如下：
?引理2（Lyusternik-Shnirel'man）
令$F_1,F_2,\cdots,F_{n+1}$為閉集，且其覆蓋住$S^n$,那么存在$F_i$包含對徑點（即$x,-x\in F_i$）。
證明：令映射$f:S^n\to \mathbb{R}^n$定義為$f(x)=(\di(x,F_1),\di(x,F_2),\cdots,\di(x,F_n))$。$\di(x,F)$代表了在$S^n$上點$x$與集合$F$用測地線連接的最短距離。那么存在$y\in S^n$使得$f(y)=f(-y)$。如果$f(y)_i=0$成立（即第$i$個分量為$0$）,那么由定義可知$-y\in F_i$(由于$F_i$閉)。如果任意$i\le n$都沒有$f(y)_i=0$,也就是$y,-y\in F_{n+1}$。$\square$
但是只是用閉集不能滿足我們的要求，我們還需要球用開或閉集覆蓋：
推論3（開集的LS定理）
令$F_1,F_2,\cdots,F_{n+1}$為開集，且其覆蓋住$S^n$,那么存在$F_i$包含對徑點。
證明：我們只需要尋找到一個閉集族$\{U_i\}$，使得$U_i\subset F_i$且$\{U_i\}$也是$S^n$的覆蓋。這樣的$U_i$可以通過如此方法：對于任意$x\in S^n$且$x\in F_i$,我們取$N(x)$為$x$的開鄰域，滿足閉包$\overline{N(x)}\subset F_i$。那么利用$S^n$是緊的，$\{N(x)\}_{x\in S^n}$必然有有限子覆蓋。我們只需要取子覆蓋中$F_i$對應的$N(x)$閉包的并即可（這樣就有了$U_i\subset F_i$）。$\square$
?推論4（Greene）
令$F_1,F_2\cdots,F_{n+1}$為開集或閉集且覆蓋$S^n$，那么存在$F_i$包含對徑點
證明：不妨設$F_1,F_2,\cdots,F_k$為閉集，剩下的是開集。那么取$(F_i)_{\epsilon}$為$F_i$的$\epsilon$開鄰域。那么$(F_1)_{\epsilon},\cdots,(F_k)_\epsilon,F_{k+1},\cdots,F_{n+1}$滿足推論3的條件。那么存在$x_i,-x_i$在某個集合里面。如果在$i\ge k+1$的開集里面，那證明結束。如果不在，那么令$\epsilon\to 0$,$S^n$的緊性說明就有收斂子列。利用$F_i$在$i\le k$是閉的可得結論。$\square$
2. Kneser猜想與Greene的證明
下面我們介紹一下Kneser圖$KG_{n,k}$。它節點的集合為$\binom{[n]}{k}$,即集合$[n]=\{1,2,\cdots,n\}$的$k$元子集。而兩個子集$S$與$S'$相連當且僅當$S\cap S'=\varnothing$。一個簡單的例子是$KG_{5,2}$如下：
（圖2：$KG_{5,2}$即著名的Petersen圖）
1955年，Kneser提出了如下猜想：
猜想5（Kneser）
對于任意$k>0$以及$n\ge 2k-1$,我們有$\chi(KG_{n,k})=n-2k+2$,其中$\chi$為染色數。
首先我們可以注意到上界是簡單的。我們只需要定義染色$c:\binom{[n]}{k}\to\{1,2,\cdots,n-2k+2\}$為\[c(S)=\min\{\min(S),n-2k+2\}\] 如果$c(S)=c(S')<n-2k+2$,那么$\min{S}$與$\min{S'}$有相同的最小元，顯然$S$與$S'$相交。而如果$c(S)=c(S')=n-2k+2$,根據抽屜原理它們還是有公共元素。因此$c$的確是圖的染色。$\square$
但是對于下界的證明并不是顯然的。1953年Lovász首次得到了這個猜想的證明。Lovász用到了大量的代數拓撲工具，比較復雜。而在2003年，還是本科生的Greene發現了其中的組合本質，因此得到了如今廣為人知的簡單證明。它因為這個美妙的證明而拿了當年的Morgan獎。
證明：考慮$KG_{n,k}$以及$d=n-2k+1$,那么令$X\subset S^d$為一族在一般位置的點，也即不存在$(d-1)$維的超平面上有$X$中的$d$個點。那么我們假設Kneser圖有節點$\binom{X}{k}$,對于任意$x\in S^d$,令函數\[H(x)=\{y \in S^d:\langle x,y\rangle>0\},\]也即在$x$所在的半球面上的點。
那么假設我們有對于$KG_{n,k}$的$d$染色，且定義集合$A_1,A_2,\cdots A_d\subset S^d$如下：$A_i$為$x\in S^d$，使得$H(x)$包含了某個被染色為$i$的集合$S\in\binom{X}{k}$中的所有點。且我們定義\[A_{d+1}=S^d\backslash(A_1\cup\cdots\cup A_d).\]
顯然有$A_i$在$i\le d$時候是開集，因為稍微變動一點，開的上半球面還是會覆蓋住染色為$i$集合中的點，從而$A_{d+1}$是開集。而由于上面的推論4，存在$i$使得$x,-x\in A_i$。如果$i\le d$,這表明存在$S$和$S'$不相交染了同樣的顏色，顯然不行。從而只能$x,-x\in A_{d+1}$。
但是對于這種情況，我們有$|H(x)\cap X|,|H(-x)\cap X|\le k-1$成立。但是這樣的話，$d-1$維的超平面$S^d\backslash (H(x)\cup H(-x))$就會包含$n-2k+2=d+1$個點，與假設的一般位置矛盾。$\square$
3.?Lovász的證明大意
這里我會大致寫下Lovász證明到底說了什么。這個證明是現代拓撲組合學的開端。他的原始證明比較長，這里就提一下梗概：
Step 1：構造$G$的“鄰域單純形”$\mathcal{N}(G)$
每一個圖都有對應的鄰域單純形。而領域單純形的定義是有公共鄰居的節點集合組成的單純形。比如說這樣的圖：
（圖3：左圖是原圖$G$,右圖是單純形$\mathcal{N}(G)$的幾何實現）
我們可見，集合$\{1,2,5\},\{1,3,4\}$以及$\{2,3\}$是極大的單純形。而幾何實現即如右圖。$\{1,2,5\}$和$\{1,3,4\}$代表兩個三角形，而$\{2,3\}$則是直線。
Step 2: $\mathcal{N}(G)$是$n-$連通，那么它不是$n+2$可染色的。
我們可見上圖是$0-$連通，因為$0-$連通就是連通，而它不是$2-$可染色的。同時，它不是$1-$連通，因為$1\to2\to3\to1$構成環。
由于圖的$(m+2)-$染色誘導了圖同態$G\to K_{m+2}$,其中$K_{m+2}$為完全圖。這個圖同態也就給出了拓撲空間$\mathcal{N}(G)\to\mathcal{N}(K_{m+2})$的連續函數。很容易驗證$\mathcal{N}(K_{m+2})$是一個$m-$維球。那么如果$\mathcal{N}(G)$是$n-$連通的，利用連續函數$\mathcal{N}(G)\to\mathcal{N}(K_{m+2})$我們就可以構造出一個對徑的連續映射(antipodal map)$f:S^{n+1}\to S^m$(PS：這一步不是顯然的),其中利用$n\le m-1$可得矛盾。
Step 3：?驗證$\mathcal{N}(KG_{n,k})$是$(n-2k-1)$連通的。
Lovász的證明是用拓撲對組合問題進行研究的開端。而這篇文章體現了Borsuk-Ulam定理在拓撲組合這一新興學科中的重要應用，并激勵了一大批人對拓撲組合問題進行研究，對于這一方法應用的歷史沿革將附在最后（來自Longueville）。
4. Bárány的證明與Schrijver定理
其實Greene并不是第一個對Lovász的證明進行改進的人。早在1978年，Bárány就給出了一個較為簡單的證明，但是它利用了Gale 引理。該引理敘述如下：
引理6（Gale）
對于任意$d\ge 0$以及任意$k\ge 1$,存在包含$2k+d$個點的集合$X\subset S^d$，使得任意$S^d$的開半球必包含$k$個$X$中的點。
（圖4：一種開半球的分劃）
對于該引理的證明我們略去，但是這個引理能夠給出Kneser猜想的證明。
證明：對于$d=n-2k$,我們取$X\subset S^d$為滿足Gale引理的點集。那么假設我們有$(d+1)-$染色，同樣定義$A_i$為$x\in S^d$,使得$H(x)$包含了某個被染色為$i$的集合$S\in\binom{X}{k}$中的所有點。注意到這次我們可以定義$1\le i \le d+1$是因為我們染色是$(d+1)-$染色。而由于Gale引理得知所有點都屬于某個$A_i$。但是再利用推論3，我們知道存在$x,-x\in A_i$。但這與Kneser圖的定義矛盾。$\square$
我們可見Bárány的證明雖然利用了Gale引理，但是它同樣可以用在其他一些集合上。比如說Schrijver圖。有如下定義：
定義7（Schrijver）
定義一個集合$S\subset [n]$是$2-$穩定($2-$stable)的，如果$k\in S$,那么對于$\forall l\in S$,$2\le|l-k|\le n-2$。而定義Schrijver圖$SG(n,k)$為所有穩定的集合$S$給出的Kneser圖。
顯然我們可以發現,$SG(n,k)$為$KG(n,k)$的子圖。一個自然的想法就是，$\chi(SG(n,k))\overset{?}{=}n-2k+2$。而答案是肯定的，顯然上界成立，而下界的給出則是Ziegler對于Gale引理的加強：
引理8（Ziegler加強的Gale引理）
對于任意$d\ge 0$以及任意$k\ge 1$,存在包含$2k+d$個點的集合$X\subset S^d$，使得任意$S^d$的開半球必包含$k$個$X$中的點。且這$k$個點的集合是$2-$穩定的。
這個引理的證明可見Matou?ek書上的76頁。而有了這個引理，Bárány的證明可以很簡單地就應用到Schrijver圖上，且證明完全相同。
5. Dol'nikov定理與超圖上的Kneser猜想
?從上面的Schrijver圖我們可以看出，實際上我們可以對任何超圖定義它的Kneser圖,也即對于超圖$\mathcal{H}=(X,\mathcal{F})$,將$\mathcal{F}$中的元素看成節點，而$F_1,F_2\in \mathcal{F}$是相鄰的當且僅當$F_1\cap F_2=\varnothing$,我將其記為$KG(\mathcal{H})$。而這個Kneser圖也有類似的性質。為了敘述這樣的結果，我們先看幾個定義：
定義9（超圖的$2-$染色）
我們稱超圖$\mathcal{H}=(X,\mathcal{F})$是$2-$可染色的如果存在映射$X\to \{1,2\}$（$1,2$看成點的顏色）,使得任意一個超邊都包含兩種顏色的點。
同時，我們可以定義"缺損$2-$染色數"($2-$colorablity defect)如下：
定義10(缺損$2-$染色數)
\[cd_2(\mathcal{H})=\min\{|Y|:(X\backslash Y,\{F\in\mathcal{F}:F\cap Y=\varnothing)\mbox{是}2-\mbox{可染色的}\}\}\]
也就是超圖$\mathcal{H}$至少去掉多少點（以及與這個點相連的超邊）能夠使它變成$2-$可染色的超圖。
?而這樣的Kneser圖有個比較好的性質。
引理11（圖$G$的Kneser超圖實現）
任意一個圖$G$，都存在一個超圖$\mathcal{H}$,使得$KG(\mathcal{H})=G$。
證明：取圖的補圖，然后定義為補圖上的邊編號，將補圖上的編號賦予節點即可。如下是一個例子
（圖5：$A\to\{1,3\},B\to\{1,2\},C\to\{2\},D\to\{3\}$）$\square$
那么通過對Kneser圖的觀察（這里的Kneser圖看成$KG(\mathcal{H})$,其中$X=[n]$,$\mathcal{F}=\binom{[n]}{k}$），我們知道$cd_2(\mathcal{F})=n-2k+2$。這是由于如果去除$n-2k+2$個點，那么剩下$2k-2$個點只需要將$k-1$個點染成$1$,另外$k-1$個點染成$2$即可得到一個$2-$染色。而去除$n-2k+1$個點，根據抽屜原理，存在一個染色必然包含至少$k$個點。那么這$k$個點的超邊就不是$2-$染色了。
因此我們通過觀察就有了如下的結論：
定理12（Dol'nikov）
對于任意有限的超圖$\mathcal{H}=(X,\mathcal{F})$,我們有$\chi(KG(\mathcal{H}))\ge cd_2(\mathcal{F})$
?證明：證明使用到的就是類似Greene的方法。令$d=\chi(KG(\mathcal{H}))$,那么同樣將$X$與$S^d$上處于一般位置的$X$等同。同樣定義$A_i$如上，也即$x\in A_i$當$H(x)$恰好包含了染色為$i$的超邊$F\in \mathcal{F}$。同時令$A_{d+1}=S^d\backslash(A_1\cup\cdots\cup A_d)$。
由于Greene定理，對于某$i$，存在$x,-x\in A_i$。若$1\le i\le d$,與Kneser圖染色矛盾，所以只能$i=d+1$。令$Y$為在赤道上節點的個數。此時我們將$H(x)$中的節點染為顏色$1$,將$H(-x)$中節點染為顏色$2$。那么$X\backslash Y$即為$2-$可染色的。從而根據$|Y|\le d$可知\[cd_2(\mathcal{F})\le |Y|\le d=\chi(KG(\mathcal{H})).\quad \square\]
注記：通過引理11，我們就知道，任意一個圖我們都能夠通過這樣的方法找到它染色的一個下界！
對于一些特殊的超圖，我們是否有更一般的結論呢？對于前面我們定義超圖的$2-$染色，我們同樣也可以類似地定義超圖的$k-$染色。也即將$X$中的點染為$k$種顏色，使得每個超邊不是單色的。這樣我們就可以定義$\chi(\mathcal{H})$為超圖的染色數（即最小可以使超圖染色存在的$k$）。
同樣，對于Kneser圖，我們也可以推廣到Kneser超圖。
定義13（Kneser超圖）
$KG^r(n,k)=(X,\mathcal{F})$是超圖，其中$X=\binom{[n]}{k}$,而超邊的集合$\mathcal{F}$中為$r$個互不相交的$x\in X$組成。
從這里可以看出，我們原來定義的Kneser圖$KG(n,k)$實際上就是$KG^2(n,k)$。我們同樣可以考慮Kneser超圖的染色數。Erd?s在1976年作出如下猜想：
猜想14（Erd?s的Kneser染色猜想）
\[\chi(KG^r(n,k))=\left\lceil \frac{n-(k-1)r}{r-1}\right\rceil\]
?該猜想已由Alon, Frankl和Lovász在1986年證明成立。他們的證明主要也用了代數拓撲的結論。而同理，我們也可以定義Schrijver圖的推廣。我們可以定義集合$S\subset[n]$為$s-$穩定，如果對于任意不等的$i,j\in S$,有$s\le |i-j|\le n-s$。于是我們就可以定義$KG^r(n,k)_{s-\mathrm{stab}}$為限制在$s-$穩定的集合上的Kneser $r-$超圖。對于Schrijver圖的結論以及Alon-Frankl-Lovász定理，自然地就有如下猜想
猜想15 （Alon-Drewnowski-?uczak）
\[\chi(KG^r(n,k)_{s-\mathrm{stab}})=\left\lceil \frac{n-(k-1)r}{r-1}\right\rceil\]
這個猜想現在還是一個開放問題。Ziegler首次證明了$\chi(KG^r(n,k)_{r-\mathrm{stab}})$與$\chi(KG^r(n,k))$相等，而Meunier證明了$\chi(KG^r(n,k)_{r-\mathrm{stab}}^\sim)$的染色數是猜想所述，其中$KG^r(n,k)_{r-\mathrm{stab}}^\sim$是限制在$|i-j|\ge s$這樣集合上的Kneser圖。
6.?Matou?ek的組合證明以及推廣
Matou?ek在2000年也給出了用Tucker引理的證明與一個純組合的證明。這個證明的思想被迅速推廣到上面很多定理的證明當中，從而從眾多拓撲證明中脫穎而出，有令人耳目一新之感。如下是他證明的主要思想：
首先注意到Tucker引理可以有如下推廣：
引理16（八面體Tucker引理——Octahedral Tucker's lemma）
對于任意集合$A,B\in [n]$,且$A\cap B=\varnothing$,$A\cup B\not=\varnothing$,對于任意滿足$\lambda(A,B)=-\lambda(B,A)$,且值域是$\{+1,-1,+2,-2,\cdots,+(n-1),-(n-1)\}$的函數$\lambda$。存在兩個集合組$(A_1,B_1)$以及$(A_2,B_2)$,滿足$(A_1,B_1)\prec (A_2,B_2)$,且有$\lambda(A_1,B_1)=-\lambda(A_2,B_2)$。
其中$(A_1,B_1)\prec (A_2,B_2)$的意思是，$A_1\subset B_1$且$A_2\subset B_2$,且至少一個是真包含。
?這個引理的證明同樣略去，具體可見Matou?ek文章。而用此引理，Kneser猜想的證明就變得比較簡單了。
定理5 （Matou?ek）Kneser猜想是正確的。(PS:標記為5是因為Kneser猜想在本文中標為5)
證明：假設$KG(n,k)$有一個染色，定義為$c:\binom{[n]}{k}\to\{1,2,\cdots,t\}$。那么定義函數如下：
\begin{align*}\lambda(A,B)=\left\{\begin{array}{ll}\pm(|A|+|B|)& \mbox{如果}|A|+|B|\le 2k-2\\ \pm (c(S)+2k-2) &\mbox{其他}\end{array}\right.\end{align*}
其中$A,B\subset [n]$互不相交,$S$同樣是$[n]$的子集，它有$k$個元素，且$S\subset A$或者$S\subset B$,滿足$c(S)$取得最小值。而在第一種情況，如果$\min(A)<\min(B)$，則取正號，否則取負號。在第二種情況，如果$S\subset A$則取正號，$S\subset B$取負號。
若$t\le n-2k+1$,那么通過前面的八面體Tucker引理，存在$(A_1,B_1)\prec (A_2,B_2)$，使得$\lambda(A_1,B_1)+\lambda(A_2,B_2)$成立。但是由于若$|A_2|+|B_2|\le 2k-2$,則$||A_1|+|B_1||<|A_2|+|B_2|$。這樣就不能使$\lambda(A_1,B_1)+\lambda(A_2,B_2)=0$。所以$|A_2|+|B_2|>2k-2$。
但是如果$|A_1|+|B_1|\le 2k-2$,就有$|c(S)+2k-2|>2k-2\ge |A_1|+|B_1|$，只能也有$|A_1|+|B_1|>2k-2$。
但是通過第二種情況可以發現，存在$k$元集合$S_1,S_2$在不相交的集合中（因為符號相反），這與Kneser圖的染色矛盾，因為它們在Kneser圖中相連接。$\square$
這個證明是否巧妙地用Tucker引理給出了一個Kneser猜想的證明，主要就是用Tucker構造出了兩個相鄰但是染色一樣的點。當然，上面所展現的并不是Matou?ek原文，而是利用原文類似的想法由Meunier給出的。用這樣類似的證明，Ziegler在2004年首次給出了Schrijver定理的組合證明，但是證明中使用了有向擬陣(Oriented Matroid)，而且這個證明較長。所以Meunier類似于前面的方法給出了Schrijver定理簡短的證明。
定義17（交錯長$\mathrm{alt}$）
對于$A,B\subset [n]$,定義$\mathrm{alt}(A,B)$為最長的單調增的數列$x_1,x_2,\cdots,x_l$,使得$x_i\in A\cup B$,且$x_i\in A$則$x_{i+1}\in B$;$x_i\in B$ 則 $x_{i+1}\in A$。
?比如說$\mathrm{alt}(\{4\},\{1,6\})=3$,對應著$1,4,6$這個數列；$\mathrm{alt}(\{2,3,5,11\},\{1,6,8,9,16\})=5$,對應著$1,2,6,11,16$這個數列。
有了這一個工具，我們就可以得出以下的Schrijver定理：
定理18（Schrijver）
Schrijver圖染色數是$n-2k+2$
證明：假設$SG(n,k)$有一個染色，定義為$c:\binom{[n]}{k}\to\{1,2,\cdots,t\}$。那么定義函數如下：
\begin{align*}\lambda(A,B)=\left\{\begin{array}{ll}\pm(\mathrm{alt}(A,B))& \mbox{如果}\mathrm{alt}(A,B)\le 2k-1\\ \pm (c(S)+2k-1) &\mbox{其他}\end{array}\right.\end{align*}
情況與上面類似，$S$是$k$元子集$S\subset A$或者$S\subset B$,滿足$c(S)$取得最小值。而在第一種情況，如果$\min(A)<\min(B)$，則取正號，否則取負號。在第二種情況，如果$S\subset A$則取正號，$S\subset B$取負號。
類似地，如果$t\le n-2k+1$且$(A_1,B_1)\prec (A_2,B_2)$,類似可以說明，存在兩個互不相交的$S_1,S_2$被染上同樣的顏色。我們只需要驗證在$\mathrm{alt}(A_2,B_2)\le 2k-1$的時候，有$\mathrm{alt}(A_2,B_2)+\mathrm{alt}(A_1,B_1)\not =0$。假設$x_1,x_2,\cdots,x_l$為$(A_2,B_2)$中最長的交錯列。且不妨設$x_1\in A_2$,那么$B_2$中最小元必然大于$x_1$,否則我們有了一個更長的交錯列。那么由于顯然有若$\mathrm{alt}(A_1,B_1)$與$\mathrm{alt}(A_2,B_2)$符號相反，則$\mathrm{alt}(A_1,B_1)$中最長交錯列第一個元素在$B_1$中,這表明$A_1$中沒有比$B_1$最小元更小的元素。但這樣我們就能夠構造出$(A_2,B_2)$中更長的一個交錯列，因為$A_2$中有元素比$B_2$中元素要小，矛盾。所以只有$\mathrm{alt}(A_2,B_2)> 2k-1$,顯然這樣可見$\mathrm{alt}(A_1,B_1)> 2k-1$這樣就完成了證明。$\square$
我們類似地可以證明Dol'nikov定理，以下的證明來自Ziegler：
定理12（Dol'nikov）
對于任意有限的超圖$\mathcal{H}=(X,\mathcal{F})$,我們有$\chi(KG(\mathcal{H}))\ge cd_2(\mathcal{F})$
證明：類似地，假設$c:\mathcal{F}\to [t]$為染色，那么假設$cd_2(\mathcal{F})>t$,也即對于任意$[n]$中元素個數大于$n-t$的子集，對于任意對$X$的$2-$染色，存在一個$s\in\mathcal{F}$,使得$s$中的點全被染成相同的顏色。那么定義$\lambda$如下：
\begin{align*}\lambda(A,B)=\left\{\begin{array}{ll}\pm(t+|A|+|B|)& \mbox{如果}|A|+|B|\le n-t-1\\ \pm (c(S)) &\mbox{其他}\end{array}\right.\end{align*}其中第一個式子在$\min(A)<\min(B)$時候取正，其他取負。而第二個式子在$S\subset A$取正，其他取負。$S$類似上面，同樣是使$c(S)$最小的$S$。
顯然這樣的映射滿足八面體Tucker引理的條件。同時通過類似的說明（這里就不再耗費時間講述了）可以構造出$S_1,S_2$使得互不相交但是染了同樣的顏色，矛盾。$\square$
Matou?ek的組合證明又提出了一個新的思路：通過拓廣Tucker引理以及構造合適的函數（利用反證法給出的條件可以說明要滿足值域在$\pm [n]$中，通過Kneser圖的定義給出矛盾），我們就可以得到一系列的類似的定理。特別地，我們前面所提到的$\chi(KG^r(n,k)_{r-\mathrm{stab}}^\sim)$就是一個沒有拓撲證明而只有組合證明的例子，其中用的工具就是所謂的$\mathbb{Z}_p-$Tucker引理。在此我們略去它的說明。
7.拓撲組合的歷史注記
以下基本來自于Longueville對于Kneser猜想所著的文章“25 years proof of the Kneser conjecture”
(1)拓撲的應用
在前面提到過，在組合中使用拓撲工具來源于Lovász對于Borsuk-Ulam定理純熟的應用。也許Borsuk-Ulam定理最好的一個推廣來自于Albrecht Dold在1983年的定理：
定理19（Dold）
令$G$為非平凡的有限群，自由作用在（形態較好的）空間$X$與$Y$上。假如$X$是$n-1$-連通，且$Y$的維數是$m$,那么如果存在$G-$等價的映射，那么$m\ge n$。這里$G-$等價意思是,$\forall g\in G$,$f(g\cdot x)=g\cdot f(x)$
如果將$G$看成對徑映射，$X,Y$分別是$S^n$與$S^m$就得到了我們一般的Borsuk-Ulam定理的一個等價描述。這樣的定理可以用在很多組合的問題之上。
隨著時代的發展，代數拓撲中的工具基本都在組合中找到了它們自己的位置。從同調到上同調，示性類到譜序列，都有了組合上的應用，比如Dmitry Kozlov所著的"圖同態的復形"。甚至微分拓撲同樣有在組合中的對應，比如Robin Forman提出的"離散Morse理論"。
對于這些方法的應用有很多。最引人注目的就是“圖染色問題”。現在很多圖和超圖的染色數都有了界的估計，而估計這些界的方法用的就是拓撲工具。各種“劃分問題”同樣被解決了，而最著名的即“項鏈問題”，又Noga Alon在1987年解決。更多地，復雜度問題，比如說線性決策樹算法的復雜度，以及與Aanderaa–Karp–Rosenberg猜想相關的單調圖性質的復雜度，同樣可以用拓撲組合進行解決。另外一個很大的理論及“偏序集的拓撲”。在1980年瑞典數學家Anders Bj?rner提出了偏序集的shellability這一概念。如果我們有一個偏序集，我們就可以給出一個單純形，從而定義一個拓撲空間。Bj?rner提出的偏序集的shellability也即，這一個相關的拓撲空間是一族球。這個組合的概念以及拓撲的結果給出了許多的應用，比如說Bruhat序以及代數組合中的一個問題。同時值得注意的是，如果用了shellability，我們很容易證明$\mathcal{N}(KG_{n,k})$，也即在Lovász文章中所需要的鄰域復形，是$(n-2k-1)-$連通的。
（2）回歸組合
雖然許多組合定理能夠被拓撲證明，一個自然的問題是，這些拓撲定理是否能夠證明組合問題？2000年組合學又一次突破，即Matou?ek首次給出了Kneser猜想的組合證明，也就是我們前面所提到的。證明中用的Tucker引理與Borsuk-Ulam定理是等價的。同樣，Borsuk-Ulam定理的組合兄弟們也能夠用來解決“平均劃分問題”。同時，離散數學中許多具體的證明需要快速計算同調群或其他不變量，而這些快速的程序都依賴于組合的構造。
代數拓撲來自于組合拓撲的研究，正如Lefschetz首次在杜克大學提出代數拓撲時所說的一樣：
“The assertion is often made of late that all mathematics is composed of algebra and topology. It is not?so widely realized that the two subjects interpenetrate so that we have an algebraic topology as well as a topological algebra”
——Solomen Lefschetz
而最后一句話對于現在的組合與拓撲來說同樣成立。
8.鳴謝與拓展閱讀
最后，感謝吳耀琨老師所上的“計算拓撲”課，沒有這門課程，我是不會注意到Hatcher書上小小的一個Borsuk-Ulam定理居然能用這門有用的應用，能夠成為組合領域的一大利器。
同時感謝網上的各位學者，將他們的美妙的成果放在了網絡之上，讓我有能力一窺這一領域的浩瀚博大。這里我給出我這篇文章所參考的資料：
[1]Some Mathematics Of Theoretical Computer Science：很簡要地給出了Greene的證明，是我第1,2部分的來源
[2]25 years proof of the Kneser conjecture :給出了Kneser猜想的歷史，是第3,7部分的主要來源
[3]Kneser's Conjecture and its Generalizations?:伊朗人寫的presentation，是我4,5部分的主要來源
[4]Combinatorial topology and the coloring of Kneser graphs:法國人的presentation，是我第6部分的來源
這一領域還有許多可以引用的文獻，這里我就不一一列舉了，從我這幾篇文獻的引用就可以大致了解了。
轉載于:https://www.cnblogs.com/misaka01034/p/KneserConjecture.html
總結
以上是生活随笔為你收集整理的Kneser猜想与相关推广的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： FL2440移植linux内核常用命令（
- 下一篇： NHibernate常见错误