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

设计计数的精确渐近

《组合设计中的 50 个公开问题》 · 问题 40 专题综述

题面固定 (t,k,λ) 下设计个数的主项渐近之外,次项、误差项与「随机设计的分布性质」能否精确?

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

问题

Keevash 2018 证明:固定 (t,k,λ)、v→∞(整除条件满足)时,t-(v,k,λ) 设计的个数有主项渐近——形式为 «熵型公式»:N(v) ≈ (v/e)vt−1·(代数因子) 型(精确形式见文献)。本问题:次项、误差项、以及 «典型设计» 的分布性质(自同构群几乎平凡、局部结构随机等)能否精确?主项公式已立;«计数之后» 的分布理论是设计理论的新大陆——与 «随机图» 理论(Erdős–Rényi 之后的发展)的 «设计版» 对应。

主要概念

熵型主项的来源

计数走 «随机贪心+逼近»:«几乎设计» 的个数(宽松计数)× «修正» 的组合学。主项的 «熵» 来自 «每块的选择自由度» 的连乘——与 «图的个数 2C(n,2)» 的 «平凡熵» 不同,设计的约束使 «熵率» 需要变分计算(«最大熵分布下的约束计数»)。

典型设计的统计力学

«典型设计» 的问题族:①自同构群是否几乎必然平凡(图谱论里 «随机图无自同构» 的对应);②局部结构(小块分布)是否 «近似随机»;③ «设计的空间» 是否有 «极限测度»。这些是 «随机约束系统» 的标准问题——设计是 «超图分解» 的约束系统,统计力学工具( cavity、消息传递)的移植是前沿。

主要命题与证明

命题 1(Keevash 计数定理,2018;陈述) 固定 (t,k,λ),对满足整除条件且充分大的 v,t-(v,k,λ) 设计的个数 N(v) 满足 log N(v) = (vt−1/(t−1)!)·log(v/e²)·(1+o(1)) 型主项(精确系数见原文)——«熵型» 且 «误差项为 o(主项)»。

机制 计数证明 = «存在性证明的升级»:nibble 给 «几乎设计» 的超多项式族计数;«修正» 步骤用 «参数化吸收»(对每个 «几乎设计» 给出 «修正方案» 的计数);两层相乘得主项。«几乎设计» 的熵计算是变分问题,其解给 «主项常数»。□

命题 2(典型设计无自同构;陈述) 主项贡献的设计中,「有非平凡自同构」者的占比 → 0——自同构群的阶 ≥2 的设计至多 «次项» 量级。机制:自同构的 «固定结构» 使计数损失指数因子。

说明 这与 «随机图几乎必然无自同构» 同构,证明亦同机(«对称点的轨道计数»);它与 39 号形成张力:«零星设计» 全部藏在 «次项» 里。□

命题 3(次项与分布的开题;陈述) 次项的精确形式(对 t=2 有部分结果:Wilson 的 «多项式型» 精确计数在 «k=3,λ=1» 的窗口)与 «局部极限定理»(设计的 «点邻域» 分布是否收敛)都是开题;「随机设计的混合时间、谱性质」等统计力学量完全空白。

说明 对比图论:随机图的 «谱、混合、极限» 理论已是成熟学科;设计的对应理论才刚起步——这是 «计数之后» 的整片新大陆。□

进展与文献

Keevash《Counting designs》(2018);Wilson 的经典计数(2-设计);Linial–Luria 的 «熵方法» 综述;统计力学侧的 «约束满足» 文献(Mézard–Montanari 教本)。开放核心:次项公式;局部极限与 «设计空间的测度»;«高对称设计在计数中的地位»(与 39、45 号联动)。

← 返回问题 40