问题
拟阵:把 «线性无关» 公理化的结构 (E, ℐ)(E 有限、ℐ ⊆ 幂集满足交换公理)。拟阵 «在 𝔽q 上可表示» 若同构于某向量集的无关结构。罗塔排除子猜想(Rota 1971):对每个有限域 𝔽q,«不可表示» 的拟阵只有有限多个极小禁例(子式极小的不可表示拟阵)。这是 «图子式定理»(Robertson–Seymour:每个固定的图只有有限多个禁子式)的拟阵版本——而拟阵的情形远难于图:Geelen–Gerards–Whittle 的 «拟阵极小结构理论» 是本世纪结构图论最大的工程,二域 GF(2) 情形已基本解决,一般素数幂的特征谱仍未合龙。
主要概念
拟阵子式与 «图情形为什么容易»
拟阵子式:删元+ «缩并»(contract,对应向量空间的商空间)。图子式定理的证明走 «网格定理»(大圈宽 ⟹ 大网格子式 ⟹ 借 «平坦化» 归约);拟阵版的 «圈宽» 概念是 «分支宽度»(branch-width)——Geelen–Gerards–Whittle 的 «大分支宽 ⟹ 大 «网格样» 子结构» 定理(拟阵网格定理)是整个纲领的引擎,其证明跨越 2000–2015 年的系列论文。
GF(2) 情形
二域拟阵 = «二元拟阵»(图拟阵与其对偶、以及 «图拟阵的 θ 扩张»)。排除子:『不可表示 ⟺ 含有限禁例』在 GF(2) 的完全清单由 Tutte 时代奠基、Bixby–Cunningham–Seymour 的 «分解理论» 补齐——二元拟阵的 «正则拟阵» 分解(Seymour 的 3-和分解定理)使 «排除子有限» 得以闭环。一般 𝔽q 的对应 «3-和分解» 是未合龙的主件。
主要命题与证明
命题 1(正则拟阵的排除子,Tutte,完整口径) 拟阵正则(在所有域上可表示)⟺ 不含 U2,4(4 点 2-秩一致拟阵)、F7(Fano 平面)、F7* 为子式。由此,«在所有特征不可表示» 的极小排除子恰是这三个——«特征 2 内部» 的排除子清单(GF(2) 不可表示但正则的极小者)同样由 F7 系给出。
说明 Tutte 定理是 «排除子纲领» 的第一个完整胜利:单个拟阵 U2,4 顶住 «所有非素数幂特征»(在 𝔽q 可表示 ⟺ q 特征…U2,4 需要 «3+3=0 型» 关系,在 𝔽₂ 不可表示),而 Fano 与其对偶把 «特征 2» 的正负分开。□
命题 2(拟阵网格定理,Geelen–Gerards–Whittle;陈述) 分支宽 ≥ k 的 𝔽q-可表示拟阵含 «k 阶网格» 型子式(wall)。它是拟阵版图子式定理的 «结构引擎»:大宽 ⟹ 大网格 ⟹ «平坦化» 递归。
说明 证明的难点在 «非图型» 拟阵:图的圈结构给 «自然网格»,一般可表示拟阵的 «网格» 需从 «斜率»(lift 项目)与 «旋转» 结构重建——GGW 的工程量主要在这里。□
命题 3(GGW 纲领的当前状态;陈述) «每个固定 𝔽q 的极小不可表示拟阵有限» 的证明路线已备齐组件:网格定理 + «分解定理»(大宽的排除子-自由拟阵可 «3-和分解» 为 «简单块»)+ «块的有限类型» 引理——最后一步 «块的有限性» 对一般 q 未完成(GF(2) 已闭环)。整个纲领是 «图子式定理(400+ 页)» 的拟阵重演,规模更大。
说明 有限性 ⟹ 算法性:排除子清单有限 ⟹ «可表示性可多项式判定»(对固定 q)——这是猜想的应用端承诺。□
进展与文献
Rota 1971 的猜想;Tutte 的正则拟阵定理;Seymour 的 3-和分解(1980);Geelen–Gerards–Whittle 的 «Matroid structure» 系列(2000–2016);Oxley《Matroid Theory》的综合章。开放核心:一般 q 的合龙;«块的有限类型» 引理;可表示性的算法后果。