精读笔记
Problem Setting
【Symmetric Extension Complexity of the Spanning Tree Polytope】（arXiv preprint / 2026）
这篇论文实际解决的是 PST(Kn) 的 symmetric extension complexity，而不是普通 extension complexity。具体地，在 Sn 顶点重标号作用下，证明任何 Sn-symmetric extended formulation 至少需要 binom(n,3) 个 inequalities；结合 Martin/Wong 的 O(n^3) 对称 formulation，得到 xcs(PST(Kn))=Θ(n^3)。
真正困难点在于 spanning tree polytope 是一个很反常的对象：它有 Edmonds 的指数级原空间描述，也有 Martin 的多项式 extended formulation；但普通 lower bound 只有 Ω(n^2)，基本来自维数/秩，而不是 polytope 的复杂 facet 结构。已有 lower-bound 技术，尤其是 support-based 方法，被 Khoshkhah–Theis 一类结果表明很难突破二次量级。
关键矛盾是：Martin formulation 的 cubic size 看起来可能只是构造技术的代价，也可能是对称性天然强制的代价。本文证明的是后者：只要 formulation 尊重顶点重标号对称性，cubic 不再是 artifact，而是必要规模。但这并不排除 asymmetric formulation 可以更小。
Motivation
已有路线不够的根源是普通 EF lower bound 工具对 spanning tree polytope 不够敏感。rank/dimension 只看线性代数级别，support-only 方法只看 slack pattern，二者都难以捕捉 subtour inequalities 与 spanning tree vertices 之间更细的代数权重结构。
作者的核心观察是：对称 formulation 的 small size 会强迫 facet stabilizer 很大。通过 permutation group 的 small-index theorem，如果 facet orbit 少于 binom(n,3)，则 stabilizer 必须包含某个 A([n]\W), |W|≤2。这极大压缩了需要验证的结构：不用理解所有 facets，只要构造一个 signed affine combination，它在这些大 alternating subgroup 的 orbit 上表现“像非负组合”，但在某个有效不等式上越界。
所以关键缺口不是找到更好的 spanning tree EF，也不是改进 slack matrix 的普通 nonnegative rank lower bound，而是找到一个能利用 symmetry forced orbit structure 的 certificate。论文的贡献恰好是给出这个 certificate，并证明它能从 K6 局部稳定 lift 到 Kn。
Core Idea
核心思想可以概括为：用一个局部 signed certificate 欺骗所有由小对称 EF 能看到的 orbit tests，但让它违反 triangle subtour inequality。若存在小的 symmetric EF，Braun–Pokutta orbit criterion 会迫使任何满足 orbit-sum nonnegativity 的 affine combination 落在 polytope 内；而作者构造的 combination 明确落在 polytope 外，于是矛盾。
这个方法改变了 lower bound 的建模方式：不是直接证明 slack matrix 的 nonnegative rank 大，而是把 symmetric EF 的存在性转成 group action 下的 orbit-sum 可行性问题。新引入的 inductive bias 是“局部六点结构 + 大群 orbit 不可区分性”。K6 gadget 在局部违反 triangle slack；lift 操作把剩余点作为 leaves 挂到 core 上，使全局 spanning tree 条件不破坏局部证书，同时 attachment bijection 保证 orbit-sum nonnegativity 在 n 维中继续成立。
和 prior 的本质区别在于，这不是一般 lower-bound machinery 的又一次套用，而是为 spanning tree polytope 设计了一个非常小的 signed obstruction。Yannakakis/Kaibel 的 matching lower bound 思路提供了哲学框架，但这里的 certificate 与 lift 方式是新的，且专门利用 triangle subtour inequality。
Method
1. Orbit criterion：它解决的是如何把“存在小 symmetric EF”转成可证伪的代数条件。若每个 facet stabilizer 的 orbit partition 上 signed coefficients 都非负，且总和为 1，则该 affine combination 必须属于 P。这个步骤的必要性在于它绕开了直接分析所有可能 EF 的不可能性，把问题降到构造一个 signed vector。
2. Small-index reduction：它解决的是 facet stabilizer 不可控的问题。若 symmetric EF facets 少于 binom(n,3)，每个 facet orbit 都小，于是 stabilizer index 小；small-index theorem 推出 stabilizer 包含 A([n]\W), |W|≤2。核心变化是：需要检查的 orbit 从未知 Gj-orbits 变成统一的、可处理的 alternating subgroup orbits。
3. K6 base certificate：在 S={1,2,3} 与 B={4,5,6} 上取四个 S3×S3 orbits，三个正权、一个负权。它解决的是如何同时做到 total weight positive 与 triangle slack negative。正总质量保证归一化后是 affine combination；负 triangle slack 保证越过 x(E(S))≤2。
4. Orbit-sum verification：对 |W|≤2 的 A((S∪B)\W)-orbits 做有限分类，验证每个 orbit 上正负权相加非负。这是证明中最工程化的一块，但不可省，因为整个 orbit criterion 需要逐 orbit nonnegativity。
5. Leaf-attachment lift：对每个 B⊂[n]\S 以及每个 attachment map，把 core 外顶点作为 leaves 接到 core。它解决的是如何从 K6 gadget 扩展到 Kn 而不改变局部 triangle violation。attachment-count invariance 是关键：A([n]\W)-invariant predicate 下，F 与 ρF 的 attachment 数相同，因此 base orbit nonnegativity 自动 lift。
Key Insight / Why It Works
最核心的有效性来自两个结构的精确咬合：small symmetric EF 只能产生大 stabilizer，而大 stabilizer 的 orbits 太粗，无法区分作者构造的 signed local mixture；但 triangle subtour inequality 是一个局部可见的线性 functional，能直接看到该 mixture 的负 slack。
这不是 scaling，也不是更强 rank bound；它本质上是 better certificate design under symmetry。六点 gadget 是核心贡献，因为它同时满足三个互相冲突的条件：正总权重、对所有 |W|≤2 alternating subgroup orbits 非负、对 triangle slack 为负。任何一个条件失败，orbit criterion 都无法导出矛盾。
lift 部分的贡献也很实质，但更像结构保持机制而非新的 lower-bound 源泉。把剩余点挂成 leaves 的选择非常干净：它不引入新的 core cycles，不改变 S 内边数，同时 attachment maps 在群作用下有自然 bijection。因此全局复杂性没有稀释局部 violation。
有限 orbit 表格有一定 engineering 味道：它是证明 certificate 成立的必要枚举，但 insight 不在表格本身。真正值得迁移的是“局部 signed obstruction + invariant attachment lift + small-index stabilizer forcing”这一组合。
需要注意，证明强度完全来自 symmetry。若去掉 Sn-symmetry，facet stabilizer 结构消失，orbit-sum criterion没有可用抓手；因此不能把该结果误读为普通 extension complexity 的证据。它证明的是 symmetry 的价格，而不是 spanning tree polytope intrinsically 需要 cubic EF。
Relation To Prior Work
最接近的谱系是 Yannakakis 的 symmetric lower bounds、Kaibel–Pashkovich–Theis 的 symmetry matters 框架，以及 Braun–Pokutta 的 algebraic orbit criterion。本文不是发明新的 EF lower-bound 框架，而是在这个框架内找到一个针对 spanning tree polytope 的 sharp certificate。
与 Martin/Wong 的关系很直接：Martin formulation 已知 O(n^3) 且对称；本文证明任何对称 formulation 都不能 asymptotically 改进它。因此 Martin 的 cubic size 在 symmetric category 内是最优的。
与普通 EF lower bounds 的差异也必须强调：Fiorini/Rothvoß 等 exponential lower bounds 处理的是 TSP、matching 等普通 extension complexity 已经很大的对象；spanning tree polytope 当前普通 lower bound 仍弱。本文没有沿通信复杂度、unique disjointness、nonnegative rank hard matrix 这条线走，而是利用 group action 的 stabilizer orbit 结构。
和 permutahedron 的已知现象类似，它再次说明 symmetric xc 与 ordinary xc 可以有本质差距。不同的是，spanning tree polytope 的 ordinary xc 是否低于 cubic 尚未知，因此本文更像是在给 open problem 加边界条件：任何 o(n^3) 的突破必须明显打破顶点重标号对称性。
Dataset / Evaluation
这是组合优化/多面体理论论文，不存在 dataset 或实验 evaluation。核心 claim 由形式化数学证明支撑，evaluation 的对应物是：lower bound 是否与已知 upper bound 匹配、证明条件是否覆盖目标模型、certificate 是否确实满足 orbit criterion 的全部前提。
从验证范围看，结论覆盖 complete graph Kn 的 Sn-symmetric linear extended formulations，且包括自然保持对称性的 LP hierarchy，例如 Sherali–Adams 类框架。它不覆盖 SDP、非线性 lift，也不覆盖 arbitrary asymmetric LP EF。
证明对核心 claim 的支持是充分的：binom(n,3) lower bound 与 O(n^3) upper bound 匹配。但它验证的 claim 非常精确也非常受限，即 symmetric extension complexity；不能外推到普通 extension complexity。
Limitation
最大限制是 symmetry assumption。所有关键步骤——facet orbit、stabilizer index、alternating subgroup、orbit-sum nonnegativity——都依赖 Sn-symmetric EF。一旦允许 asymmetric formulation，证明几乎没有剩余结构可用。因此这篇论文没有缩小普通 xc(PST(Kn)) 的 Ω(n^2)–O(n^3) gap。
第二个限制是 certificate 的局部性既是优点也是上限。它只利用 triangle subtour inequality 和六点 gadget，因此给出的 lower bound 自然停在 binom(n,3) 量级。若想得到更强的 symmetric lower bound 不可能，因为已有 O(n^3) upper bound；但若想迁移到其他 polytopes，需要找到类似的局部 violated inequality 与 orbit-positive signed gadget，文中未充分说明这种构造是否系统化。
第三，base orbit-sum 的有限分类略显 ad hoc。它证明正确，但没有揭示为什么这四个 paths 是唯一自然选择，或是否存在更概念化的 representation-theoretic 解释。这里的增益不是来自 scaling / data，而是来自手工 certificate；可迁移性取决于能否复用这种 certificate 设计模式。
第四，n≥13 来自 small-index theorem 的保守阈值。作者指出 k=3 情况可更早成立，但主定理保留 n≥13。这个不是本质缺陷，但说明边界情形没有被精细处理。
Takeaway
- 1. 对 spanning tree polytope，Martin/Wong 的 O(n^3) formulation 在 symmetric LP EF 模型内已经最优；未来若要找 o(n^3)，必须主动破坏 vertex-relabeling symmetry。
- 2. 这篇最值得迁移的不是具体 K6 表格，而是 lower-bound 模板：small-index stabilizer forcing + local signed certificate + orbit-preserving lift。
- 3. Symmetry lower bound 仍然是处理普通 lower-bound 技术失效对象的一条有效旁路；它不能解决 ordinary xc，但能精确定位“自然 formulation”为何不能更小。
- 4. 对其他 matroid/base polytopes，值得寻找类似的局部 inequality violation gadget；真正问题是能否系统化构造 orbit-positive signed affine combinations，而不是继续堆 support-based lower bound。
一句话总结
这篇论文在对称 extended formulation 谱系中给出了 spanning tree polytope 的 sharp Θ(n^3) lower bound，真正贡献是用一个六点 signed orbit certificate 证明 cubic Martin formulation 的规模是 symmetry 强制的，而非普通 extension complexity 的最终答案。