做a网站,找人给公司做网站去哪找,淘宝客的wordpress模板,wordpress转域名收费吗本文本来是想放在Borsuk-Ulam定理的应用这篇文章当中。但是这个文章实在是太长#xff0c;导致有喧宾夺主之嫌#xff0c;从而独立出为一篇文章#xff0c;仅供参考。$\newcommand{\di}{\mathrm{dist}}$ #xff08;图1#xff1a;Kneser叙述他的猜想原文手稿#xff09;… 本文本来是想放在Borsuk-Ulam定理的应用这篇文章当中。但是这个文章实在是太长导致有喧宾夺主之嫌从而独立出为一篇文章仅供参考。$\newcommand{\di}{\mathrm{dist}}$ 图1Kneser叙述他的猜想原文手稿 引理1Borsuk-Ulam 对于任意$f:S^n\to\mathbb{R}^n$连续存在$x\in S^n$使得$f(-x)f(x)$。 目录 1 Lyusternik-Shnirelman定理与Greene定理2 Kneser猜想与Greene的证明3 Lovász的证明大意4 Bárány的证明与Schrijver定理5 Dolnikov定理与超图上的Kneser猜想6 Matoušek的组合证明以及推广7 拓扑组合的历史注记8 鸣谢与拓展阅读 1. Lyusternik-Shnirelman定理与Greene定理 这个猜想的证明主要使用了Lyusternik与Shnirelman版本的Borsuk-Ulam定理它的具体表述如下 引理2Lyusternik-Shnirelman 令$F_1,F_2,\cdots,F_{n1}$为闭集且其覆盖住$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)_i0$成立即第$i$个分量为$0$,那么由定义可知$-y\in F_i$(由于$F_i$闭)。如果任意$i\le n$都没有$f(y)_i0$,也就是$y,-y\in F_{n1}$。$\square$ 但是只是用闭集不能满足我们的要求我们还需要球用开或闭集覆盖 推论3开集的LS定理 令$F_1,F_2,\cdots,F_{n1}$为开集且其覆盖住$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$ 推论4Greene 令$F_1,F_2\cdots,F_{n1}$为开集或闭集且覆盖$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_{k1},\cdots,F_{n1}$满足推论3的条件。那么存在$x_i,-x_i$在某个集合里面。如果在$i\ge k1$的开集里面那证明结束。如果不在那么令$\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提出了如下猜想 猜想5Kneser 对于任意$k0$以及$n\ge 2k-1$,我们有$\chi(KG_{n,k})n-2k2$,其中$\chi$为染色数。 首先我们可以注意到上界是简单的。我们只需要定义染色$c:\binom{[n]}{k}\to\{1,2,\cdots,n-2k2\}$为\[c(S)\min\{\min(S),n-2k2\}\] 如果$c(S)c(S)n-2k2$,那么$\min{S}$与$\min{S}$有相同的最小元显然$S$与$S$相交。而如果$c(S)c(S)n-2k2$,根据抽屉原理它们还是有公共元素。因此$c$的确是图的染色。$\square$ 但是对于下界的证明并不是显然的。1953年Lovász首次得到了这个猜想的证明。Lovász用到了大量的代数拓扑工具比较复杂。而在2003年还是本科生的Greene发现了其中的组合本质因此得到了如今广为人知的简单证明。它因为这个美妙的证明而拿了当年的Morgan奖。 证明考虑$KG_{n,k}$以及$dn-2k1$,那么令$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\rangle0\},\]也即在$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_{d1}S^d\backslash(A_1\cup\cdots\cup A_d).\] 显然有$A_i$在$i\le d$时候是开集因为稍微变动一点开的上半球面还是会覆盖住染色为$i$集合中的点从而$A_{d1}$是开集。而由于上面的推论4存在$i$使得$x,-x\in A_i$。如果$i\le d$,这表明存在$S$和$S$不相交染了同样的颜色显然不行。从而只能$x,-x\in A_{d1}$。 但是对于这种情况我们有$|H(x)\cap X|,|H(-x)\cap X|\le k-1$成立。但是这样的话$d-1$维的超平面$S^d\backslash (H(x)\cup H(-x))$就会包含$n-2k2d1$个点与假设的一般位置矛盾。$\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-$连通那么它不是$n2$可染色的。 我们可见上图是$0-$连通因为$0-$连通就是连通而它不是$2-$可染色的。同时它不是$1-$连通因为$1\to2\to3\to1$构成环。 由于图的$(m2)-$染色诱导了图同态$G\to K_{m2}$,其中$K_{m2}$为完全图。这个图同态也就给出了拓扑空间$\mathcal{N}(G)\to\mathcal{N}(K_{m2})$的连续函数。很容易验证$\mathcal{N}(K_{m2})$是一个$m-$维球。那么如果$\mathcal{N}(G)$是$n-$连通的利用连续函数$\mathcal{N}(G)\to\mathcal{N}(K_{m2})$我们就可以构造出一个对径的连续映射(antipodal map)$f:S^{n1}\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 引理。该引理叙述如下 引理6Gale 对于任意$d\ge 0$以及任意$k\ge 1$,存在包含$2kd$个点的集合$X\subset S^d$使得任意$S^d$的开半球必包含$k$个$X$中的点。 图4一种开半球的分划 对于该引理的证明我们略去但是这个引理能够给出Kneser猜想的证明。 证明对于$dn-2k$,我们取$X\subset S^d$为满足Gale引理的点集。那么假设我们有$(d1)-$染色同样定义$A_i$为$x\in S^d$,使得$H(x)$包含了某个被染色为$i$的集合$S\in\binom{X}{k}$中的所有点。注意到这次我们可以定义$1\le i \le d1$是因为我们染色是$(d1)-$染色。而由于Gale引理得知所有点都属于某个$A_i$。但是再利用推论3我们知道存在$x,-x\in A_i$。但这与Kneser图的定义矛盾。$\square$ 我们可见Bárány的证明虽然利用了Gale引理但是它同样可以用在其他一些集合上。比如说Schrijver图。有如下定义 定义7Schrijver 定义一个集合$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-2k2$。而答案是肯定的显然上界成立而下界的给出则是Ziegler对于Gale引理的加强 引理8Ziegler加强的Gale引理 对于任意$d\ge 0$以及任意$k\ge 1$,存在包含$2kd$个点的集合$X\subset S^d$使得任意$S^d$的开半球必包含$k$个$X$中的点。且这$k$个点的集合是$2-$稳定的。 这个引理的证明可见Matoušek书上的76页。而有了这个引理Bárány的证明可以很简单地就应用到Schrijver图上且证明完全相同。 5. Dolnikov定理与超图上的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-2k2$。这是由于如果去除$n-2k2$个点那么剩下$2k-2$个点只需要将$k-1$个点染成$1$,另外$k-1$个点染成$2$即可得到一个$2-$染色。而去除$n-2k1$个点根据抽屉原理存在一个染色必然包含至少$k$个点。那么这$k$个点的超边就不是$2-$染色了。 因此我们通过观察就有了如下的结论 定理12Dolnikov 对于任意有限的超图$\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_{d1}S^d\backslash(A_1\cup\cdots\cup A_d)$。 由于Greene定理对于某$i$存在$x,-x\in A_i$。若$1\le i\le d$,与Kneser图染色矛盾所以只能$id1$。令$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超图。 定义13Kneser超图 $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年作出如下猜想 猜想14Erdő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 Tuckers 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šekKneser猜想是正确的。(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-2k1$,那么通过前面的八面体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_{i1}\in B$;$x_i\in B$ 则 $x_{i1}\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定理 定理18Schrijver Schrijver图染色数是$n-2k2$ 证明假设$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-2k1$且$(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$ 我们类似地可以证明Dolnikov定理以下的证明来自Ziegler 定理12Dolnikov 对于任意有限的超图$\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年的定理 定理19Dold 令$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]Knesers 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
