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.
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.
A proposed mathematical limit on how quantum-like transformations can stretch matrix traces fails for three-by-three matrices.
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.
Answers the paper's Question 2 negatively for k = 3: a 182-vertex graph (the paper's 91-vertex G_3 with every vertex doubled into independent twins, plus pin edges from each core twin to two anchors) has an optimal Max-3-Cut coloring that is unique up to color permutation and not a strong equilibrium, so no optimal coloring is a strong equilibrium. The paper only shows that some optimal coloring can fail
Proves the conjectured equality for every n>=30000001 and every minimum proper edge coloring, establishing sharpness at all sufficiently large orders rather than only the paper's n<=12 range, the isolated n=279 case, or one congruence class
a new question answered: Evaluate every individual availability permanent as 4 on the double-3-tail staircase family, rather than merely expressing the total count as a sum of unknown permanents or proving top-row monotonicity.
Excludes perfect partitions of every integer square when the common tile area is q^s*p^t for distinct primes p,q and arbitrary exponents, and hence excludes all square sides supported on two primes. The prime-power and small prime-product exclusions of arXiv:2007.09639 Theorem 4.1 and the density theorem in HAL:hal-05729522v2 do not give this uniform common-area restriction
Excludes every square side q*p^e for distinct primes p,q with no bound on e and no ordering restriction on the primes; arXiv:2007.09639 Theorem 4.1 excludes prime powers and products of at most three primes but does not give this exponent-uniform two-prime family
Excludes perfect partitions of every integer square with common tile area q^s*r*p^a for distinct primes p,q,r with p>r+1, uniformly in a and s. This extends the two-prime common-area obstruction by using the superincreasing signed-height argument
Settles the k = 15 case of the residual even case of arXiv:2610.15635: eq(C_n^15) = 6 for every even n ≥ 3825 with 16 ∤ n, where the paper only has eq(C_n^15) ∈ {5, 6}; the first case beyond k = 3 where the exact value is now known
Settles the k = 7 case of the residual even case of arXiv:2610.15635: eq(C_n^7) = 5 for every n ≥ 98 with 8 ∤ n, where the paper only has eq(C_n^7) ∈ {4, 5} for even n ≥ 441
Answers the question left open in arXiv:2610.37187 (Sec. 9) and raised in arXiv:2506.02145: positive trace-preserving maps in dimension three can violate the universal spectral bound Tr Φ ≤ d m(Φ) + d² − d that holds for all 2-positive ones; an explicit decomposable map with trace 11/2 and eigenvalue −1/2 exceeds the bound 9/2
Answers the question of arXiv:2610.37187 (Sec. 9, raised in arXiv:2506.02145) in every dimension: for each d ≥ 3 an explicit decomposable positive trace-preserving map violates the bound Tr Φ ≤ d m(Φ) + d² − d, which holds for all 2-positive trace-preserving maps, by 2/(d − 1); so 2-positivity cannot be weakened to positivity in that theorem
Proves the failure half of the golden-ratio conjecture OP-726 for every exponent, not just at sample points: for every beta in (0, (sqrt 5 - 1)/2) there is a strictly positive binary Markov chain Y <- X -> Z on which mutual power-divergence information is strictly superadditive. The construction is a rare input symbol of probability p and a channel entry of order p, and the slack has derivative -(1-beta)a^2 - (1-(1-a)^beta)^2 + 2 kappa^beta((a+kappa)^(1-beta) - (kappa+a-a^2)^(1-beta)) at p = 0, positive for suitable a, kappa exactly when beta^2 + beta < 1. The source paper (arXiv:2610.21231) gives only sufficient conditions for subadditivity, and the knowledgebase had refutations only at beta = 1/4 and 1/2 plus numerical evidence for the threshold
Proves exact EF1 for every number of agents when m <= 2n+1, a positive guarantee beyond the general 1/2-EF1 bound and the three-agent/eight-good counterexample in arXiv:2610.23686
Extends common least-good insertion to two universally small goods with arbitrary within-pair rankings, preserving every old bundle and weakly improving all own utilities; iteration gives complete EFX for any number of agents and goods ordered in common pairs
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.
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.
maxcut_pinned_twins_optimum_rigidityEvery welfare-maximizing 3-coloring ρ of the 182-vertex pinned twins graph maxcut_pinned_twins_graph is, up to one global permutation p of…
maxcut_op89_residual_exists_negationThe residual case maxcut_op89_residual_exists of OP-89 is false: it is not true that every finite simple graph G with k ≥ 3, at least 2k+2…
maxcut_optimal_not_strong_degree_66There is a finite simple graph of maximum degree at most 66 with an optimal coloring of the Max-3-Cut game that is not a strong…
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.
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.
matroid_isFlat_interIn any matroid M, if F₁ and F₂ are flats of M, then their intersection F₁ ∩ F₂ is also a flat of M.
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.
latin_double_three_tail_count_stepThe number of tableaux of the next shape is the sum of availability permanents over all tableaux of the previous shape.
latin_double_three_tail_profile_allEvery Latin tableau in the double-3-tail staircase family has the three canonical column-symbol profiles (nine profiles before permuting…
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.
latin_double_three_tail_profile_succInduction step for the double-3-tail staircase profile: for k >= 5, if every Latin tableau of shape (k,k-1,...,4,3,3) has the canonical…
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.
mondrian_two_prime_area_sides_dvdFor a perfect admissible square partition with common area q^s*p^t and q dividing the square side, both dimensions of every tile are…
mondrian_two_prime_area_width_dvdFor a perfect admissible square partition with common area q^s*p^t and q dividing the square side, every tile width is divisible by q.
mondrian_no_perfect_prime_power_areaNo perfect admissible partition of any integer square can have common tile area equal to a prime power p^t, including exponent zero.
mondrian_perfect_partition_div_common_areaIf q divides the square side and both dimensions of every tile in a perfect partition, and the common area is q^2 times B, coordinate…
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.
mondrian_no_perfect_two_prime_powersFor any two distinct primes p and q and arbitrary natural exponents e and f, the square of side q^f*p^e has no perfect admissible integer…
mondrian_prime_free_area_shape_boundFor distinct primes p and q, if t+r=2e, at most r plus floor(log_p(q)) plus one shapes of pure p-power area p^t fit in the q times p^e…
mondrian_prime_area_shape_boundFor distinct primes p and q, if t+r=2e, at most r plus floor(log_p(q)) plus one shapes of area q times p^t fit in the q times p^e square.
mondrian_prime_square_area_shape_boundFor distinct primes p and q and t+r=2e with positive r, at most 2r unordered shapes of area q^2 times p^t fit in the q times p^e square.
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.
mondrian_no_perfect_two_prime_areaFor any distinct primes p and q and natural exponents s and t, no perfect admissible partition of any integer square can have common tile…
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.
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.
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.
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.
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.
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.
golden_ratio_quadratic_nonneg_iffFor any positive exponent beta, beta^2 + beta - 1 >= 0 if and only if (Real.sqrt 5 - 1) / 2 <= beta.
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.
round_robin_two_mul_add_one_outcome_structureRound-Robin with n agents and 2n+1 goods, any reports: there are goods a2, a3 (agent 0's picks at turns n and 2n) and b1, b2 (agent i's…
round_robin_two_mul_add_one_cover_pairsRound-Robin with n agents and 2n+1 goods, agent i ≠ 0: let a1 be agent 0's top-ranked good, a2 and a3 the goods it picks at turns n and…
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.
efx_exists_of_two_universal_small_goodsFor a positive number of agents with nonnegative real additive values, suppose each of the last two goods is weakly less valuable to every…
finite_two_bonus_ordered_assignmentFor any finite nonempty real matrix w and two nonnegative agent-dependent bonuses a and b, there is a permutation of the old columns, a…
finite_two_bonus_assignmentFor any finite nonempty real matrix w and two nonnegative agent-dependent bonus values g(false), g(true), there is a permutation of the…
is_efx_goods_permute_of_utility_leA bundle permutation that weakly improves every agent's own additive value preserves EFX for nonnegative item values.
Still open
Can the chromatic number of graphs with no induced subdivision of the complete graph on four vertices be bounded by a constant?
Does an unweighted maximum cut game always admit an optimal strong equilibrium when the maximum degree is strictly below the number of colors?
Can three distinct bent functions sum to the eight-variable quartic counterexample to Tokareva's conjecture?
Is the zero-excess decision problem for wiring diagrams in the higher Bruhat order solvable in polynomial time?
Does every integer square partition with three distinct prime area factors require non-congruent rectangles?
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.