arXiv:2607.23500cs.LOcs.AI2026-07

用形式化证明工具验证图论中的极值不等式,确保结论绝对可靠。

Formalizing Flag Algebras in Lean

  • 将拉兹博罗夫的旗代数方法完整形式化,构建可机器验证的证明体系。
  • 自动生成并验证7个极值图论上界,包括曼特尔定理和埃爾多斯五边形定理。
  • 适合数学证明严谨性要求高的研究者,尤其关注形式化验证与组合优化者。

Razborov的旗代数方法是极值图论中证明渐近不等式的强大工具,常将问题转化为通过半定规划寻找有限证书。本文对有限简单图的旗代数方法进行了机器可验证的形式化,包含一个证书到证明的编译器,将外部生成的证书数据转化为由Lean验证的代数证明。形式化涵盖方法基础:部分标记图、其在大图中的密度、密度表达式的商代数、通过正同态的图极限语义,以及用于平均标签的向下算子。编译器将外部半定规划输出视为候选数据而非可信输入:Lean独立计算所需密度与乘法关系,精确在有理数域验证半正定性,并执行旗代数证明中的代数标准化步骤。案例研究生成了七个图论上界的形式化证明,包括曼特尔定理、埃爾多斯五边形定理、三角形自由图的C₄密度界,以及K₄-自由、K₅-自由和C₅-自由图的边密度界。独立于编译器,我们形式化了对应极值构造,完成曼特尔定理与埃爾多斯五边形定理的精确极值密度证明,并证明了两组古德曼不等式。受限语义还引发对两种图约束处理方式的元理论比较:在旗代数中从一开始就嵌入遗传约束,或事后在随机标记的受限图极限中测试不等式。我们提出了根植可植性准则,刻画两种方法一致的条件;完整论述将在后续论文中给出。

原文摘要 · Abstract (English)

Razborov's flag algebra method is a powerful tool for proving asymptotic inequalities in extremal graph theory, often reducing the task to finding a finite certificate by semidefinite programming. We present a machine-checked formalization of the method for finite simple graphs, together with a certificate-to-proof compiler that turns externally generated certificate data into algebraic proofs checked by Lean. The formalization covers the foundations of the method: partially labeled graphs, their densities in large graphs, the quotient algebra of density expressions, graph-limit semantics through positive homomorphisms, and the downward operators used to average out labels. The compiler treats the external semidefinite programming output as candidate data rather than trusted input: Lean independently computes the required density and multiplication facts, verifies positive semidefiniteness exactly over $\mathbb{Q}$, and carries out the algebraic normalization steps of flag-algebra proofs. Our case studies yield formal proofs of seven Turán-type upper bounds, including Mantel's theorem and the Erdős pentagon theorem, a $C_4$-density bound for triangle-free graphs, and edge-density bounds for $K_4$-free, $K_5$-free, and $C_5$-free graphs. Independently of the compiler, we formalize the matching constructions that complete the exact Turán densities of Mantel's theorem and the Erdős pentagon theorem, and prove two inequalities of Goodman. Our constrained semantics also prompted a meta-theoretic comparison of two ways of imposing graph constraints: building a hereditary constraint into the flag algebra from the start, or testing inequalities afterward on constrained graph limits with labels chosen at random. We state the resulting root-plantability criterion characterizing when the two approaches agree; a forthcoming paper will present the complete account.

形式化证明图论旗代数自动验证

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。