AFTD Auto-Formalizing Theoretical Domains

Weekly report · 2026-W44 · 26 Oct – 1 Nov 2026

Social Optima Vulnerable to Coalitions, Latin Tableaux Formula, and Spectral Bounds Refuted

Short version: 3 minFull report: 13 min中文版

The week in one minute

A question in game theory was settled when researchers disproved the conjecture that socially optimal network colorings are always immune to group defections, exhibiting a 182-vertex counterexample. In combinatorics, an exact counting formula for staircase Latin tableaux was proved, and perfect Mondrian partitions were ruled out for all two-prime tile areas. In quantum theory, a proposed universal spectral bound was refuted in all dimensions three and above. Further results proved wild-number formulas and new fairness guarantees.

  • 5 Proved
  • 4 Disproved
  • 4 Partial
  • 1 New result
  • 2 Formalized
  • 5 still open

Lean accepted 1510 new theorems this week, drawn from 97 papers and 23 topics. Of these, 53 are new here, 0 correct a published claim, 150 formalize a published result and 1307 are helper lemmas. They make 14 research-level results, in 16 theorems -- they lead the report. 1276 statements posed this week are not yet proved. The reading covered 109 new papers. This report covers 16 results in 6 fields.

Research-level results

The story of the week

Socially best network choices can still be vulnerable to conspiracies

Imagine participants in a social network choosing between three teams. Each person gains satisfaction from having friends on opposing teams, which naturally encourages diversity across the network. A division into teams is socially optimal when it maximizes the total number of cross-team friendships across all members.

If a society achieves an arrangement that maximizes total welfare, could it still be destabilized from within? Specifically, could a coordinated group of participants agree to switch teams together so that every member of the conspiracy ends up strictly better off? For unweighted network games of this kind, game theorists conjectured that every network admits at least one socially optimal assignment that is completely immune to such group defections.

That conjecture has now been disproved. Researchers constructed a network of 182 participants where every single welfare-maximizing division leaves an opening for a successful conspiracy. In this network, no matter which socially optimal team assignment is chosen, some group can always coordinate to change teams such that each conspirator gains more opposing friends.

The counterexample begins with a rigid 91-vertex core, duplicates every participant into independent twins, and attaches anchor pins. This structure forces every optimal partition into a configuration where profitable group defections cannot be eliminated.

At a glance

ResultOutcomePaper
Equilibria in Games
Socially optimal cut colorings can fail to be strong equilibriaDisprovedarXiv:2610.04948
Graph Theory & Graph Algorithms
Conjectured wild number formula proved for all large complete graphsPartialarXiv:2610.22142
Hop-closed and leap-closed edge sets fail to form matroid flatsDisprovedarXiv:2610.18463
Combinatorics for TCS
Exact counting formula proved for Latin tableaux with double-three tailsProvedarXiv:2610.29291
Every Latin tableau in the double-three staircase family extends in four waysNew resultarXiv:2610.29291
No integer square admits a perfect rectangle tiling of two-prime areaProvedarXiv:2610.19193
Perfect Mondrian partitions impossible for sides of form q times p^eProvedarXiv:2610.19193
Three-prime common areas with one linear factor admit no perfect partitionProvedarXiv:2610.19193
Exact equivalence covering number determined for fifteenth cycle powersPartialarXiv:2610.15635
Exact equivalence covering number determined for seventh cycle powersPartialarXiv:2610.15635
Long non-transitive dominance cycles exist for eleven-sided diceFormalizedarXiv:2610.40321
Quantum Computation
Universal spectral bound fails for positive trace-preserving maps in dimension threeDisprovedarXiv:2610.37187
Universal spectral bound fails in every dimension from three upDisprovedarXiv:2610.37187
Information Theory & Coding
Mutual information subadditivity fails below the golden ratio conjugateFormalizedarXiv:2610.21231
Fair Division
Round-robin drafting equilibria are fair up to one good for at most 2n+1 itemsProvedarXiv:2610.23686
Two universally small goods can be added while preserving EFXPartialarXiv:1707.04769

Equilibria in Games

A question on whether social optimality prevents coalitional defections in maximum cut games was resolved in the negative using an explicit 182-vertex construction.

Disproved

Socially optimal cut colorings can fail to be strong equilibria

In network games where players seek opposing colors, an arrangement that maximizes total cut edges can still be vulnerable to group defections.

Before

It was conjectured that every unweighted maximum cut game admits at least one socially optimal coloring that is immune to coordinated group deviations.

Now

The conjecture fails for three colors on an explicit 182-vertex graph formed by doubling a 91-vertex core with anchor pins: every welfare-maximizing partition admits a profitable group deviation.

Why it matters
Refutes Question 2 of arXiv:2610.04948, showing that global efficiency does not imply coalitional stability in unweighted cut games.
The idea
The 182-vertex pinned twins graph has rigid welfare-maximizing colorings whose monochromatic edge structure permits a strict joint deviation.
4 supporting theorems

Graph Theory & Graph Algorithms

The wild number conjecture was proved for all large complete graphs, while hop-closed and leap-closed edge sets were shown not to form matroid flats.

Partial

Conjectured wild number formula proved for all large complete graphs

The minimum number of wild edges needed to connect every color class in an optimal edge coloring of a complete graph meets its lower bound for large networks.

Before

The exact wild number formula floor(4·ceil(n/2)/3) was conjectured in arXiv:2610.22142, but proved only for orders up to twelve and the isolated order 279.

Now

For every order n ≥ 30000001 and every minimum proper edge coloring of the complete graph K_n, the wild number equals floor(4·ceil(n/2)/3).

Why it matters
Settles the Section 6 conjecture of arXiv:2610.22142 for all sufficiently large orders, proving sharpness without congruence restrictions.
The idea
Reduces the question to odd orders via vertex restriction and constructs optimal block partitions satisfying cut-crossing criteria through probabilistic avoidance.
4 supporting theorems

Disproved

Hop-closed and leap-closed edge sets fail to form matroid flats

In graph permutation theory, edge subsets that cannot be expanded without adding new permutations do not form the closed sets of any matroid.

Before

Question 5.9 of arXiv:2610.18463 asked whether the maximal edge subsets inducing the same hop or leap group form the flats of a matroid.

Now

Neither collection forms matroid flats: on the 3-vertex complete graph, the intersection of two hop-closed edge sets is not hop-closed, and similarly for leap-closed sets.

Why it matters
Refutes Question 5.9 of arXiv:2610.18463, showing that matroid theory cannot govern the closure operators of graph derangement groups.
The idea
Exhibits two two-edge paths in the triangle whose intersection is a single edge admitting no hops, violating closure under intersection.
3 supporting theorems

Combinatorics for TCS

New results settled counting conjectures for staircase Latin tableaux, established obstructions to zero-defect Mondrian partitions for two-prime areas, and determined exact equivalence covering numbers for cycle powers.

Proved

Exact counting formula proved for Latin tableaux with double-three tails

Grid arrangements with decreasing row lengths and no repeated numbers in rows or columns have an exact count of nine times four to a power.

Before

Conjecture 6.3 of arXiv:2610.29291 proposed that the number of Latin tableaux of shape (k, k-1, ..., 4, 3, 3) is exactly 9·4^(k-3) for all k ≥ 5.

Now

The formula is true for all k ≥ 5: the base case k = 5 has 144 tableaux, and each step multiplies the count by 4.

Why it matters
Settles Open Problem OP-512, completing the enumeration of this infinite family of staircase tableaux.
The idea
Induction on k using a classification of column symbol profiles that forces every top-row availability matrix to have permanent equal to 4.
3 supporting theorems

New result

Every Latin tableau in the double-three staircase family extends in four ways

Adding a new row of the next size to any valid grid in this staircase family always yields exactly four valid completions.

Before

arXiv:2610.29291 left open whether individual tableaux extend uniformly, establishing only that total counts relate to sums of unknown availability permanents.

Now

For every k ≥ 5, every individual Latin tableau of shape (k, k-1, ..., 4, 3, 3) extends in exactly 4 ways to shape k + 1.

Why it matters
Explains the factor of 4 in the global counting formula at the level of individual combinatorial objects.
The idea
Classifies all column contents into canonical profiles and computes the permanent of the resulting (k+1)-by-(k+1) availability matrices directly.
3 supporting theorems

Proved

No integer square admits a perfect rectangle tiling of two-prime area

It is impossible to divide a square into non-congruent rectangles of equal area when that common area has only two prime factors.

Before

Mondrian partitions with defect zero were known to be impossible for prime-power tile areas and products of at most three primes under size constraints.

Now

For any distinct primes p and q and exponents s and t, no integer square has an admissible partition into non-congruent rectangles of common area q^s·p^t.

Why it matters
Rules out all two-prime tile areas for the Mondrian art problem unconditionally on exponents.
The idea
Strong induction on the exponents, using horizontal moment identities to force every tile dimension to share prime factors with the square side.
4 supporting theorems

Proved

Perfect Mondrian partitions impossible for sides of form q times p^e

No square whose side is a prime multiplied by any prime power can be split into non-identical rectangles of the same area.

Before

Known nonexistence results covered prime powers and small prime products, but left open sides q·p^e for arbitrary exponents e.

Now

For distinct primes p and q and any natural exponent e, the square of side q·p^e admits no admissible equal-area integer partition with zero defect.

Why it matters
Extends the geometric obstruction from specific prime factors to an infinite family of square dimensions.
The idea
Combines the two-prime area obstruction with shape counting bounds that compare available factor pairs to tile counts.
4 supporting theorems

Proved

Three-prime common areas with one linear factor admit no perfect partition

Dividing a square into non-congruent rectangles of identical area remains impossible when the tile area involves three primes with one appearing to power one.

Before

The two-prime area obstruction left open whether three distinct prime factors could enable a zero-defect Mondrian partition.

Now

For distinct primes p, q, r with p > r + 1, no integer square has a zero-defect partition into rectangles of area q^s·r·p^a for any natural a, s.

Why it matters
Takes the first step toward settling the three-prime common area case of the Mondrian problem.
The idea
Uses strong induction on the exponent of q and a height chain argument to propagate divisibility constraints.
2 supporting theorems

Partial

Exact equivalence covering number determined for fifteenth cycle powers

Covering all short-distance edges of a large cycle when steps up to fifteen are connected requires exactly six cluster graphs.

Before

arXiv:2610.15635 established that the equivalence covering number of C_n^15 lies in {5, 6} for even n not divisible by 16, leaving the exact value open.

Now

For every even n ≥ 3825 not divisible by 16, the equivalence covering number of the fifteenth power of the n-cycle is exactly 6.

Why it matters
Settles the k = 15 case of Open Problem OP-205, providing the first exact value beyond k = 3.
The idea
Specializes a dyadic classification theorem, refuting five-layer covers through automated case splits on class-type sequences.
2 supporting theorems

Partial

Exact equivalence covering number determined for seventh cycle powers

Covering all edges between vertices at distance at most seven on a ring requires exactly five equivalence subgraphs.

Before

Theorems 1.3 and 1.4 of arXiv:2610.15635 left the covering number of C_n^7 pinned only within {4, 5} for even n ≥ 441 with 8 ∤ n.

Now

For every n ≥ 98 not divisible by 8, the equivalence covering number of the seventh power of the n-cycle is exactly 5.

Why it matters
Settles the k = 7 case of Open Problem OP-205 for all orders down to 98.
The idea
Matches a general dyadic upper bound of 5 with an exact lower bound derived from dyadic weight conservation.
2 supporting theorems

Formalized

Long non-transitive dominance cycles exist for eleven-sided dice

A set of eleven-sided dice can form a loop of at least twelve dice where each die is more likely to beat the next.

Before

Section 3 of arXiv:2610.40321 constructed non-transitive cycles for various dice sizes, including a directed cycle of length at least 12 for 11-sided dice.

What is checked

arXiv:2610.40321 shows that the 11-sided dice graph contains a directed simple cycle of length at least 12; Lean now checks the proof.

Why it matters
Formally verifies Open Problem OP-744 on the existence of long dominance cycles in non-transitive dice systems.
The idea
Verifies that twelve explicit non-decreasing eleven-tuples form a simple cycle under the minimal winning advantage margin of 61 matchups.
4 supporting theorems
  • op744_dice7_has_cycle_fourteenThe relation (dice_graph 7).Adj has a directed simple cycle of length 14, has_directed_cycle (dice_graph 7).Adj 14.
  • op744_dice6_has_cycle_sixThe relation (dice_graph 6).Adj has a directed simple cycle of length 6, has_directed_cycle (dice_graph 6).Adj 6.
  • op744_dice3_no_cycle_threeThe relation (dice_graph 3).Adj contains no directed simple cycle of length 3, that is, ¬ has_directed_cycle (dice_graph 3).Adj 3.
  • minimal_advantage_elevenThe minimal winning advantage threshold for 11-sided dice is 61.

Quantum Computation

A conjectured universal spectral bound for positive trace-preserving maps was disproved in dimension three and shown to fail in all dimensions three and higher.

Disproved

Universal spectral bound fails for positive trace-preserving maps in dimension three

A proposed mathematical limit on how quantum-like transformations can stretch matrix traces fails for three-by-three matrices.

Before

A universal spectral bound holding for all two-positive maps was conjectured to extend to all positive trace-preserving maps in dimension three or higher.

Now

The bound trace(Φ) ≤ d·m(Φ) + d² - d fails: for d = 3, an explicit map Φ(X) = K X K + (3/4) P Xᵀ P violates the inequality.

Why it matters
Answers the open question from Section 9 of arXiv:2610.37187 and arXiv:2506.02145 in the negative.
The idea
Constructs a decomposable map summing a completely positive congruence and a partial transpose whose peripheral spectrum exceeds the bound.
1 supporting theorem

Disproved

Universal spectral bound fails in every dimension from three up

In every matrix dimension three or greater, there are positive transformations preserving traces that exceed the proposed universal spectral limit.

Before

arXiv:2610.37187 proved the bound for two-positive maps and raised whether positivity alone suffices in each dimension d ≥ 3.

Now

For every d ≥ 3, there exists an explicit positive trace-preserving linear map on d-by-d complex matrices strictly violating trace(Φ) ≤ d·m(Φ) + d² - d.

Why it matters
Settles Open Problem OP-733 in full generality across all dimensions d ≥ 3.
The idea
Generalizes the three-dimensional counterexample by adjusting diagonal weights to preserve trace while violating the spectral inequality.
1 supporting theorem

Information Theory & Coding

The necessity half of the golden ratio conjecture for mutual power-divergence information was settled, confirming that subadditivity fails whenever the exponent is strictly below the golden ratio conjugate.

Formalized

Mutual information subadditivity fails below the golden ratio conjugate

In information theory, a standard subadditivity inequality for power divergences breaks down whenever the exponent is strictly below the golden ratio conjugate.

Before

Open Problem OP-726 conjectured that mutual power-divergence information is subadditive on Markov chains if and only if the parameter β is at least (√5 - 1)/2.

What is checked

arXiv:2610.21231 shows that for every β in (0, (√5 - 1)/2), an explicit binary Markov chain strictly violates subadditivity; Lean now checks the proof.

Why it matters
Settles the necessity half of Open Problem OP-726, showing that the golden ratio conjugate is a sharp lower threshold.
The idea
Constructs binary distributions where joint power-divergence mutual information strictly exceeds the sum of marginal divergences.
5 supporting theorems

Fair Division

Equilibria in round-robin item drafting were proved fair up to one good for up to 2n+1 items, and an extension theorem incorporated two universally small goods while preserving fairness.

Proved

Round-robin drafting equilibria are fair up to one good for at most 2n+1 items

When players take turns picking items, every stable game outcome is fair up to one item whenever the item count is at most twice the player count plus one.

Before

arXiv:2610.23686 showed that pure Nash equilibria of round-robin can fail EF1 for 3 agents with 8 goods, leaving the exact frontier open.

Now

For any number of agents n and at most 2n + 1 goods with nonnegative additive valuations, every pure Nash equilibrium of Round-Robin is EF1.

Why it matters
Establishes a positive fairness guarantee beyond known bounds, proving sharpness at 2n + 1 for three players.
The idea
Identifies the unique agent receiving three goods and constructs deviation certificates from alternative picking strategies.
4 supporting theorems

Partial

Two universally small goods can be added while preserving EFX

Two new items that every person values less than existing items can always be assigned without breaking fairness up to any single item.

Before

Techniques based on inserting universally least-valued goods could handle at most one small good at a time without breaking EFX guarantees.

Now

Adding two goods, each valued weakly less than all old goods by every agent, preserves EFX via bundle permutation and bonus assignment without requiring within-pair agreement.

Why it matters
Advances progress on the open problem of EFX existence for four agents by enabling two-item inductive steps.
The idea
Applies an extremal potential argument on candidate bundle permutations and bonus orderings to weakly improve all initial utilities.
4 supporting theorems

Still open

Terms

EF1
Envy-free up to one item: any envy disappears once some single item is removed (a good from the envied bundle, or a chore from the envious agent's own).
EFX
Envy-free up to any item: envy disappears whichever single item is removed (any good from the envied bundle, or any chore from the envious agent's own).
OP
Open Problem: a designated open question in the knowledgebase
TCS
TCS: theoretical computer science, spanning discrete mathematics and computational complexity

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