AFTD Auto-Formalizing Theoretical Domains

Monthly report · 2026-10 · October 2026 (so far: the month is not over)

Optimal Graph Partitions, Quantum Parity Bounds, and Tableau Enumeration Settled

Short version: 2 minFull report: 5 min中文版

The month in one minute

This month settled open questions across discrete mathematics. Optimal graph cuts were shown to fail coalitional stability. Exact parity bounds for line cubic circuits were proved. A Latin tableau enumeration formula was established, and squares resist two-prime tile partitions.

  • 3 Proved
  • 1 Disproved
  • 3 Partial
  • 1 Formalized
  • 5 still open

Lean accepted 3307 new theorems this month so far, drawn from 205 papers and 34 topics. Of these, 198 are new here, 8 correct a published claim, 484 formalize a published result and 2617 are helper lemmas. They make 17 research-level results, in 20 theorems -- they lead the report. 1808 statements posed this month are not yet proved. The reading covered 330 new papers. This report covers 8 results in 6 fields.

Research-level results

The story of the month

Optimal Graph Cuts Can Collapse Under Group Collusion

Imagine players coloring vertices in a network to disagree with neighbors. When edges between differently colored vertices earn rewards, colorings maximizing cut achieve greatest welfare. While some optimal colorings were known unstable, researchers asked whether every network admits an optimal coloring resisting colluding teams.

The answer is no. A 182-vertex network shows an unweighted cut game can fail to admit any optimal strong equilibrium.

In this network, every coloring achieving maximum social welfare allows a coalition to switch colors together, strictly improving each member's payoff.

At a glance

Equilibria in Games

Optimal graph colorings can fail to prevent group deviations.

Disproved

Unweighted Max-3-Cut games can fail to admit any optimal strong equilibrium

Even when seeking to maximize severed connections, some networks have no optimal coloring immune to colluding teams.

Before

It was open whether every unweighted Max-k-Cut game has an optimal coloring that is a strong equilibrium.

Now

Question 2 of arXiv:2610.04948 fails for k = 3: an explicit 182-vertex graph has no optimal three-cut coloring that is a strong equilibrium.

Why it matters
Shows that socially optimal colorings can never achieve coalitional stability in some unweighted networks.
3 supporting theorems

Quantum Computation

Parity representations determine line cubic circuit costs.

Proved

Line cubic quantum syndrome has exact size 2n + 1 parity representation

A family of quantum circuits can always be implemented using an exact, minimal number of parity operations.

Before

Parity representations of size 2n + 1 for line cubic syndromes were known only through n = 12.

Now

For every n ≥ 5, the line cubic syndrome admits a parity representation of cardinality exactly 2n + 1.

Why it matters
Resolves the general case left open in arXiv:2610.01024.
3 supporting theorems
  • line_cubic_boundary_extensionRemoving the two designated boundary supports, adjoining the new index to every other support and adding four boundary supports preserves…
  • line_cubic_nat_family_existsEvery n at least five admits a bounded natural-index support family of size 2n+1 with the required line cubic moments and the boundary…
  • line_cubic_t_count_lower_boundFor any n ≥ 5, every parity representation of the line cubic syndrome has cardinality at least 2n + 1.

Combinatorics for TCS

Tableaux counts and square dissections are resolved.

Proved

Latin tableaux with double-three tail numbered by closed formula

The number of filled grid shapes with a specific staircase tail follows an exact exponential formula.

Before

Conjecture 6.3 of arXiv:2610.29291 conjectured the total count was 9 · 4^(k−3) for k ≥ 5.

Now

The number of Latin tableaux of shape (k, k−1, ..., 4, 3, 3) equals 9 · 4^(k−3) for every k ≥ 5.

Why it matters
Settles OP-512 on exact tableau enumeration.
4 supporting theorems

Partial

Squares have no perfect partitions with two-prime tile areas

No integer square can be sliced into unequal rectangles that all share an identical two-prime area.

Before

Equal-area non-congruent rectangle partitions were excluded for prime powers and small products, leaving two-prime areas open.

Now

No perfect partition of an integer square has common tile area q^s · p^t for distinct primes p, q.

Why it matters
Excludes perfect zero-defect Mondrian partitions for square sides supported on two primes.
2 supporting theorems

Graph Theory & Graph Algorithms

Equivalence covering and wild numbers are determined.

Partial

Wild number of complete graphs equals lower bound for large orders

Connecting single-color components in large edge-colored complete networks requires the minimum possible number of edges.

Before

Sharpness of the lower bound ⌊4⌈n/2⌉/3⌋ was verified only for n ≤ 12 and n = 279.

Now

For every n ≥ 30000001, the wild number under every minimum proper edge coloring of K_n equals ⌊4⌈n/2⌉/3⌋.

Why it matters
Settles the complete-graph wild number conjecture for all sufficiently large orders.
2 supporting theorems

Proved

Equivalence covering number of fifteenth cycle power is six

Covering the fifteenth power of large even cycles whose lengths avoid multiples of sixteen requires six equivalence layers.

Before

Theorems 1.3 and 1.4 of arXiv:2610.15635 established only values 5 or 6 for even n not divisible by 16.

Now

For every even n ≥ 3825 not divisible by 16, the equivalence covering number of C_n^15 is exactly 6.

Why it matters
Settles the k = 15 case of cycle power covering.
2 supporting theorems

Elementary Number Theory

The negative three-stamp basis gap is classified.

Partial

Negative three-stamp number determined for odd orders outside residue 59 modulo 60

Allowing negative denominations reduces the range of three-stamp bases by an exact gap for almost all odd thresholds.

Before

Theorem 4.1 of arXiv:2610.19470 showed n♭_h(2) < n_h(2) for odd h, leaving the exact difference open.

Now

For odd h ≥ 5 with h ≢ 59 (mod 60), the gap n_h(2) − n♭_h(2) is 1 for h ≡ 9, 3 for h ≡ 11, and 2 otherwise (mod 12).

Why it matters
Provides an exact formula for the negative three-stamp number across almost all odd thresholds.
3 supporting theorems

Information Theory & Coding

Mutual information subadditivity fails below the golden ratio.

Formalized

Subadditivity of mutual power divergence fails below golden ratio conjugate

Information shared across a simple three-variable Markov chain fails subadditivity whenever the power parameter lies below the golden ratio conjugate.

Before

OP-726 conjectured that mutual power-divergence information is subadditive along Markov chains iff beta exceeds the golden ratio conjugate.

What is checked

arXiv:2610.21231 shows that for every beta in (0, (sqrt 5 - 1)/2), a strictly positive binary Markov chain violates subadditivity; Lean now checks the proof.

Why it matters
Settles the failure half of OP-726 uniformly across all subcritical exponents.
2 supporting theorems

Still open

Terms

OP
OP: open problem designations tracked in the knowledgebase
TCS
TCS: theoretical computer science and related discrete mathematics

Written by a model (gemini-3.8-flash) from the month's Lean-verified results. Every declaration named here was checked by Lean; this summary is a reading aid and is not itself machine-checked.