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

完全图的直线交叉数

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

题面完全图 Kn 的直线交叉数(凸位置)确切公式是什么?

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

问题

把 Kn 的顶点放在凸位置(圆周上),直线画边,数 «对角线对» 的交叉数——rectilinear crossing number rect(Kn)。确切公式未知(已知到 n = 27);它与 «随机四点凸» 的概率直接相联:rect(Kn) = 每四点组合 «凸» 的计数和。

主要概念

跨数(k-set 多项式)工具

统计 «≤3-交叉的 K4 数» 等多项式不变量(crossing counts),每类计数既被 «几何» 约束(凸/凹四点的几何分类)又被 «组合» 约束(双计数); «跨数不等式» 族给出 rect 的逐级下界——当前最好下界来自 «所有 k ≤ 27 的 Kk 计数» 的联合线性规划。

构造侧

fabila(Fabila-Monroy 与 López)的 «优化圆周位置» 程序给出候选极小构型;极限常数 rect(Kn)/C(n,4) → c ≈ 0.379972⁻ 已知存在于窄带内(0.3796 与 0.3805 之间)—— «常数收敛» 已证、 «常数闭式» 未得。

主要命题与证明

命题 1(凸四点双计数,完整推导) 凸位置画法中,每个 «凸四点组» 贡献 1 个交叉,每个 «凹四点组» 贡献 0——故 rect(Kn) = #{四点组 凸}。

证明 凸位置四点 {A,B,C,D}:恰有一对 «对角» 边(AC, BD)相交——几何上 «两弦相交 ⟺ 端点交错排列于圆周»,凸四点组给出且仅给出一个 «交错对»,即一次交叉。凹(在凸位置不可能)——恒等式立得。□

命题 2(Ábrego–Fernández-Merchant 下界机器骨架) 对每个 k, «k 点子构型的凸四点计数» 的双计数不等式给 rect 的下界多项式;联合所有 k ≤ 27 的实测值做 LP,得 rect(Kn) ≥ 0.3796·C(n,4) 级。

进展与文献

Harary–Hill 的原始 «thickness/rect» 问题族;Guy 的早期表格( «Guy 数»);Ábrego–Fernández-Merchant–Neubauer–Watkins 的跨数不等式系列;Aichholzer 的 «有序点集数据库»(n ≤ 27 的极小构型库,OSMC 项目)与 fabila 的优化程序。开放核心:n ≥ 28 的精确值需要 «交叉计数代数»(把 «对称多项式 + 几何约束» 做成可解系统)——目前的 LP 机器在 28+ 因 «变量爆炸» 失灵;极限常数 0.379972… 的闭式( «随机序的凸概率»)独立成趣。

← 返回问题 31