九 章 格 数 学 · 数 学 前 沿 · V I P 专 阅

罗塔基猜想(拟阵版)

《图论中的 50 个公开问题》 · 问题 39 专题综述

题面拟阵的任意 n 个基可排成矩阵使每行是一个基且列前缀拼出基的不交并吗?

本页为 VIP 专阅综述:主要概念的详细介绍与主要命题的细致证明,全文见下方专阅区。

问题

罗塔基猜想(Rota 1971 起,常与 Gabow、 «basis exchange» 传统相联):拟阵 M 的任意 n 个基 B₁, …, Bn 可排成 n×r(r = 秩)矩阵,使每行是一个基,且任意前 k 列的并 = B₁ ∪ ⋯ ∪ Bk(作为 k(r−?) 元 «分层基并»)—— «基的可交换阶梯 »。已证:可表示拟阵的 n ≤ 3、 «强基可序» 类、直积闭包;一般拟阵连 n = 4 都悬置。

主要概念

基交换公理的 «强化»

拟阵基公理(交换公理):基 B, B′,x ∈ B′∖B ⟹ 存在 y ∈ B∖B′ 使 B−y+x 是基。罗塔基问题问 «交换可以 «批量、分层、无冲突» 地做吗»—— «n 个基的 «同时交换 »»。代数翻译: «基集合» 带上 «交换 » 操作构成 «拟阵单oid»(本册群论 5 号的近亲)—— «阶梯» 存在 ⟺ «单oid» 的 «基字 » 可 «重排»。

可表示情形的线性代数

可表示拟阵(基 = «列向量组的极大无关组»): «阶梯» = «矩阵的 «列排序 » 问题»—— «Hall 型 » 匹配 + «高斯消元 » 的 «可交换性 » 组合。 n = 2 是 «基交换 » 本身(已证);n = 3 需 «三方匹配 » 型论证;n = 4 起 «匹配的组合爆炸 » 无 «统一结构 » 控制。

主要命题与证明

命题 1(n = 2 情形,完整证明) 任意两个基 B, B′ 可排成两行使每行是基、第一列 «并» = B。

证明 对 |B∖B′| 归纳:取 x ∈ B∖B′,由基交换公理得 y ∈ B′∖B 使 B−y+x =: B″ 是基。 «B, B′′» 的 «对称差» 比 «B, B′» 小 1;归纳排 «B′′, B′»,再把 «x-列 » 提到最前( «x ∈ B′′−B′» 的 «角色» 复核)。□

命题 2(直积闭包,完整骨架) 若 M, N 有 «n-阶梯»,则直积 M ⊕ N 也有—— «两边的阶梯» «按列拼接»( «前 k 列的并» 在直积下 «分量式» 分解)。⟹ «已知类» 在 «直积 » 下稳定、可 «自由组合 » 构造已证域。

进展与文献

Farber 1983( « Basis pairing » 与 «Rota's basis conjecture» 的整理);Gabow 1976 的 «基可序» 算法线;Loh–Sudakov–... 的 «n ≤ 3 可表示» 证明;Geelen–Humphries 的 «n = 4 的部分»;Cheung–... 与 Bucić–... 的近期部分。开放核心:一般拟阵 n = 4( «深度最小 » 的未决层); «可表示 ⟹ 全 n»(线性代数机器能否 «统一» 处理所有 n—— «张量 » 化的尝试半途);与 «拟阵代数稳定型»(塔特多项式像、Huh 纲领)的接口。

← 返回问题 39