遇见数据集

A Structural Reduction of Tuza's Conjecture via Primal–Dual Decomposition, Equality Cores, and Residual Absorption

收藏
Zenodo2026-04-25 更新2026-05-26 收录
官方服务:

资源简介:

We present a complete combinatorial proof of Tuza's conjecture, tau(G) <= 2 nu(G), via a primal-dual structural framework. The architecture rests on the optimal fractional solution of the triangle packing/covering LP. The dual crest U_{1/2} := { e in E(G) : y_e^* >= 1/2 } decomposes the graph into a boundary regime and a subcritical interior. The interior decomposes further into equality cores, rigid structures saturating tau = 2 nu, and residual cells, each carrying strict structural excess sigma_i >= 1. The conjecture reduces to two local blocks: Block A (strict residual excess): tau(R_i) <= 2 nu(R_i) - sigma_i for every nonempty residual R_i. Block B (terminal crest absorption): delta_odd(H_cr, w) + sum_i B_i <= (1/2) sum_i sigma_i. Block A is established via equality-core extraction and the certified reduction program. Block B is established by three independent combinatorial routes: the matching polytope with odd-set inequalities, the augmented b-matching framework with residual reservoirs, and a local potential monotonicity argument under certified reductions. All three routes reduce to the same local absorption mechanism: the excess generated in each residual cell exactly covers the fractional deficit imposed by the crest. Once both blocks are in place, the global inequality follows by an exact algebraic cancellation of the sigma_i terms, with no approximation and no additional hypotheses. The proof is self-contained and purely combinatorial. A complete set of affine algebraic certificates for all 13 primitive open templates is provided in Appendix B. These certificates are polynomial in the LP variables and valid for every definition of the crest satisfying y_e >= 1/2.

提供机构:
Zenodo
创建时间:
2026-04-25
二维码
社区交流群
二维码
科研交流群
商业服务