AFTD Auto-Formalizing Theoretical Domains

Weekly report · 2026-W45 · 2–8 Nov 2026

Unweighted network games cycle indefinitely, oriented half-covers hold, and ternary zero-sums settled

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

The week in one minute

This week resolved several open questions in network games, directed graphs, fair resource allocation, and additive combinatorics. An explicit network game proved that players can cycle forever through profitable moves even without edge weights and with minimal teams. In graph theory, researchers established half-neighborhood coverage for oriented graphs with kernels in non-neighborhoods and disproved a conjectured cluster partition bound on subcubic networks. Other settled problems include a sharp threshold for three-dimensional zero-sum vector sequences and improved guarantees for dividing indivisible chores between two people.

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

Lean accepted 879 new theorems this week, drawn from 134 papers and 25 topics. Of these, 39 are new here, 0 correct a published claim, 145 formalize a published result and 695 are helper lemmas. They make 7 research-level results -- they lead the report. 1509 statements posed this week are not yet proved. The reading covered 183 new papers. This report covers 16 results in 7 fields.

Research-level results

The story of the week

Coloring games cycle forever even when deviating teams are minimal

Imagine participants on a network who each choose one of 3 colors, trying to differ from their neighbors. A group of participants can coordinate a simultaneous color change if every member strictly increases their score of different-colored neighbors.

When single individuals switch, the total score across the network rises, guaranteeing that the game eventually halts. But can coordinated groups cycle forever? Previous cycles required weighted connections. It remained open whether unweighted networks can cycle when deviations are restricted to minimal coalitions that contain no smaller profitable subgroup.

A new construction proves that unweighted networks can cycle indefinitely under minimal group deviations. On an explicit 71-vertex network, 33 successive colorings form an infinite loop. The cycle begins with 32 core players changing colors in a single coordinated move that no subgroup can achieve alone. Then 32 individual adjustments restore the original coloring one player at a time, ruling out any potential function.

At a glance

ResultOutcomePaper
Equilibria in Games
Unweighted network cut games admit endless cycles of minimal coalitional deviationsProvedarXiv:1810.09278
Unweighted three-color network cut games admit cyclic coalitional deviationsProvedarXiv:1810.09278
Fairness and coalitional stability are mutually exclusive in a nine-vertex cut gameProvedarXiv:2610.04948
History-aware repair breaks the one-player extension barrier for approximate equilibriaFormalizedarXiv:2611.06076
Graph Theory & Graph Algorithms
Non-neighborhood kernels guarantee weighted half-neighborhood coverage in oriented graphsProvedarXiv:2610.23487
Möbius ladder refutes component-order partition conjecture for subcubic graphsDisprovedarXiv:2611.05178
Explicit directed graph shows local expansion ratio for outdegree 4 is at least five-fourthsPartialarXiv:2601.11847
Diameter-three nut graphs possess non-row binary vectors in their adjacency row spaceFormalizedarXiv:2611.08244
Combinatorics for TCS
Minimal zero-sum sequence length in three-dimensional ternary space equals 13PartialarXiv:2610.19965
Binomial and linear bounds established for layers in one-layered set familiesFormalizedarXiv:2611.08071
Ten-point configuration beats the regular centered nine-gon for Mordell distance productFormalizedarXiv:2611.03088
Fair Division
Two-agent chore division achieves sharp (r+1)/2 maximin share under equal marginalsPartialarXiv:2609.35280
Identically ordered chore instances satisfy one-third and four-thirds cost boundsFormalizedarXiv:2611.04884
Computability & Recursion Theory
Matrix mortality for two-by-two matrices reduces to line reachabilityFormalizedarXiv:2611.06562
Online Algorithms
Dominant resource fairness has competitive ratio at least one plus square root of resourcesFormalizedarXiv:2611.07905
Quantum Computation
Families of d² measurements are incompatible globally but jointly measurable on every subspaceFormalizedarXiv:2610.37347

Equilibria in Games

Unweighted network cut games were shown to admit cycles of profitable coalitional deviations even when coalitions are inclusion-minimal, ruling out strong potential functions. A separate fairness obstruction proved that high social welfare cannot generally be reconciled with coalitional stability.

Proved

Unweighted network cut games admit endless cycles of minimal coalitional deviations

In network games where players choose colors to differ from neighbors, teams can cycle through color changes forever even when no subgroup could profitably act on its own.

Before

Whether unweighted network cut games admit a strong potential function when coalitional deviations are restricted to inclusion-minimal profitable subcoalitions remained open after cycles were found for weighted games.

Now

An explicit unweighted 71-vertex graph with 3 colors possesses an infinite 33-step cycle of profitable deviations where every deviating coalition is inclusion-minimal.

Why it matters
Precludes the existence of a strong potential function in unweighted cut games even under the minimal-deviation restriction.
The idea
Chains a verified 32-player minimal deviation with 32 single-player restoration moves on a 71-vertex graph into a periodic 33-step deviation cycle.
4 supporting theorems
  • maxcut_cycle71_minimal_cycle_stepsEvery successive pair of the 33 profiles forms a strong deviation, and no proper subcoalition of its changing vertices has a profitable…
  • maxcut_cycle71_return_stepsEvery one of the 32 successive restoration moves, including the wraparound, is a profitable deviation by the displayed single vertex and…
  • maxcut_cycle71_first_deviation_minimalThe 32 core vertices have a profitable deviation from the first displayed profile to the second, and no proper subcoalition can profitably…
  • maxcut_cycle71_force_closed_coreAny nonempty set of core vertices closed under adjacent vertices whose initial color is the first vertex’s deviation color contains all 32…

Proved

Unweighted three-color network cut games admit cyclic coalitional deviations

Even without edge weights, players in a network coloring game can cycle through group color changes indefinitely.

Before

Earlier work proved that edge-weighted network cut games can cycle under group deviations, leaving open whether unweighted cut games could also cycle.

Now

An explicit unweighted 46-vertex graph with 3 colors exhibits an infinite sequence of profitable coalitional deviations that returns to its starting coloring every 5 steps.

Why it matters
Extends the non-existence of strong potential functions from edge-weighted to unweighted network cut games.
The idea
Constructs 5 explicit colorings of a 46-vertex graph where each successive transition is a profitable coalitional deviation by the changing vertices.
2 supporting theorems
  • maxcut_cycle46_deviationsEach successive pair of the five displayed colorings, including the transition from the fifth to the first, is a strong deviation on the…
  • maxcut_five_cycle_repeatsAny five colorings that form a directed cycle of strong deviations repeat periodically to yield an infinite strong-deviation sequence…

Proved

Fairness and coalitional stability are mutually exclusive in a nine-vertex cut game

In a 9-player coloring game, individual stability can guarantee 4 points to every player, but group stability forces at least one player below 4 points.

Before

Whether unweighted network cut games always admit equilibria that simultaneously protect individual fairness benchmarks and resist coalitional deviations was unknown.

Now

On a 9-vertex 3-color graph, an equilibrium against individual deviations gives every vertex payoff at least 4, but no coalitional equilibrium achieves payoff at least 4 everywhere.

Why it matters
Demonstrates that selecting coalitionally stable profiles can strictly degrade individual fairness guarantees in network games.
The idea
Exhaustive verification that every 3-color profile with minimum payoff at least 4 admits a profitable coalitional deviation.
4 supporting theorems

Formalized

History-aware repair breaks the one-player extension barrier for approximate equilibria

In games with many players, an approximate equilibrium can be extended to an additional player with an explicit mixing bound.

Before

Extending approximate equilibria to additional players in multiplayer normal-form games typically degraded approximation guarantees or required restrictive potential assumptions.

What is checked

In an (r+1)-player game with payoffs in [0, 1], mixing the fixed action with a best response at weight 1/(2-α) extends an α-approximate equilibrium to a 1/(2-α)-approximate equilibrium.

Why it matters
Formalizes the foundational lemma enabling polynomial-time history-aware repair for multiplayer approximate equilibria.
The idea
Balances deviation regret for the added player and existing players by tuning a single scalar mixture weight.
1 supporting theorem

Graph Theory & Graph Algorithms

This week resolved several structural questions in directed and undirected graphs: weighted half-neighborhood coverage was extended to all oriented graphs with non-neighborhood kernels, a subcubic component-order conjecture was refuted by the Wagner graph, and new local expansion bounds were proved.

Proved

Non-neighborhood kernels guarantee weighted half-neighborhood coverage in oriented graphs

In any network where every non-adjacent set of points has a kernel, one can always find a small hub covering at least half of any given positive weights.

Before

Weighted half-neighborhood coverage was established only for tournament-acyclic oriented graphs, leaving general oriented graphs with non-neighborhood kernels open.

Now

Every finite loopless oriented graph whose induced non-neighborhoods all possess out-kernels has a quasi-kernel whose closed out-neighborhood contains at least half the total weight for any nonnegative integer weighting.

Why it matters
Extends weighted half-neighborhood coverage far beyond tournament-acyclic graphs to the full class with non-neighborhood out-kernels.
The idea
Uses a neighborhood-preserving completion lemma to iteratively lift kernels from induced non-neighborhoods to a global quasi-kernel covering half the total weight.
1 supporting theorem

Disproved

Möbius ladder refutes component-order partition conjecture for subcubic graphs

It is not always possible to split a network where every node has at most 3 connections into one scattered group and small clusters of at most 3 nodes.

Before

Question 5.4 in arXiv:2611.05178 asked whether every finite simple graph with maximum degree at most 3, no triangles, and not bipartite admits an independent set whose complement has components of order at most 3.

Now

The 8-vertex Wagner graph, a triangle-free 3-regular graph formed by an 8-cycle with 4 diameter chords, admits no partition into an independent set and components of size at most 3.

Why it matters
Refutes Question 5.4 in arXiv:2611.05178 and shows that maximum degree 3 does not bound the component order of the complement of an independent set.
The idea
Finite exhaustion verifies that every independent set in the 8-vertex Möbius ladder leaves an induced component of size at least 4 in its complement.
1 supporting theorem

Partial

Explicit directed graph shows local expansion ratio for outdegree 4 is at least five-fourths

An oriented network on 24 vertices shows that deleting closed neighborhoods can expand the number of sources beyond the outdegree bound.

Before

Problem 5.2 in arXiv:2601.11847 investigated whether the ratio f(Δ) between source expansion and closed out-neighborhoods in source-free oriented graphs of maximum outdegree Δ can be bounded near 1.

Now

An explicit 24-vertex oriented graph of maximum outdegree 4 establishes f(4) ≥ 5/4, with 8 vertices of outdegree 4 and 16 sinks of outdegree 0.

Why it matters
Establishes a concrete lower bound for the source-neighborhood expansion ratio at degree 4, ruling out smaller uniform constants.
The idea
Constructs an oriented 24-vertex graph where all sources created by deleting any closed out-neighborhood are original sinks, producing an expansion ratio of exactly 5/4.
2 supporting theorems

Formalized

Diameter-three nut graphs possess non-row binary vectors in their adjacency row space

In certain graphs where every node participates in the null space, the sum of rows from points at distance 3 forms a new zero-or-one vector.

Before

Characterizing which graphs have non-trivial binary vectors in their adjacency row space that do not appear as matrix rows was open for various graph classes.

What is checked

Every finite simple nut graph of diameter 3 has a non-zero (0,1)-vector in its adjacency row space that does not equal any row of the adjacency matrix.

Why it matters
Lean checks Theorem 4.1 of arXiv:2611.08244, confirming the presence of novel binary vectors from distance-3 vertex pairs.
The idea
Sums the adjacency rows of two vertices at distance 3; because they share no neighbors, their sum is a (0,1)-vector not matching any single row.
3 supporting theorems

Combinatorics for TCS

A zero-sum sequence question was settled for the first 3-dimensional ternary case. Other developments included upper bounds on layers in simplicial complexes close to flag complexes and extremal configurations for Mordell distance products.

Partial

Minimal zero-sum sequence length in three-dimensional ternary space equals 13

Any list of 13 non-zero vectors in 3 dimensions using numbers modulo 3 must contain a sublist summing to zero modulo 3 but not zero modulo 9.

Before

Question 3.1 in arXiv:2610.19965 asked whether w_r(n) = 2r(n-1)+1; earlier work verified only w_r(2) = 2r+1 and w_2(n) = 4n-3, with no higher cases settled.

Now

w_3(3) = 13: every sequence of 13 non-zero vectors in ℤ^3 contains a non-empty subsequence summing to 0 mod 3 but not 0 mod 9, and 13 is minimal.

Why it matters
Settles the first case with both r ≥ 3 and n ≥ 3, confirming the formula 2·3·(3-1)+1 = 13.
The idea
Classifies all admissible 13-vector sequences over the ternary cube, showing that avoiding 0 mod 9 zero-sums is impossible at length 13.

Formalized

Binomial and linear bounds established for layers in one-layered set families

Collections of sets where each layer is disjoint can be bounded in size by both a linear formula and a logarithmic binomial coefficient.

Before

Bounding the diameter of complexes close to flag or normal complexes required sharp layer bounds on 1-layered families of r-subsets.

What is checked

arXiv:2611.08071 Theorem 2.1 proves that any 1-layered family of r-subsets on at most m vertices has at most (m-r+1)·choose(⌊log₂(m-r+1)⌋+r-1, r-1) layers; Lean now checks the proof.

Why it matters
Supplies verified bounds on layer counts that directly govern diameter bounds for simplicial complexes.
The idea
Partitions the layers into prefix, suffix, and middle blocks to set up a three-term divide-and-conquer recurrence.
4 supporting theorems
  • one_layered_recurrenceFor integers r ≥ 2 and m ≥ r, the maximum number of layers F(m, r) satisfies F(m, r) ≤ F(⌊(m - 1) / 2⌋, r) + F(⌈(m - 1) / 2⌉, r) + F(m -…
  • one_layered_linear_boundFor all integers r ≥ 1 and m ≥ r, the maximum number of layers F(m, r) in a 1-layered family of r-subsets on at most m vertices satisfies…
  • one_layered_family_upper_boundsFor all integers r ≥ 1 and m ≥ r, the maximum number of layers F(m, r) of a 1-layered family of r-subsets on at most m vertices satisfies…
  • one_layered_binomial_bound_le_powerFor integers r ≥ 1 and m ≥ r, the binomial bound (m - r + 1) * choose(⌊log_2(m - r + 1)⌋ + r - 1, r - 1) is at most (m - r + 1)^(1 + log_2…

Formalized

Ten-point configuration beats the regular centered nine-gon for Mordell distance product

Ten points in the plane can be arranged so that their multiplied pairwise distances strictly exceed the longstanding benchmark from a regular polygon.

Before

The centered regular 9-gon configuration achieving distance product 10⁴⁵ / 9³⁶ was suspected to be optimal for Mordell's 10-point problem in the complex plane.

What is checked

arXiv:2611.03088 proves that the supremum of squared distance products for 10 points strictly exceeds 10⁴⁵ / 9³⁶, witnessed by an explicit scaled integer configuration; Lean now checks the proof.

Why it matters
Refutes the optimality of the regular polygon benchmark in Mordell's 10-point problem.
The idea
Evaluates the squared distance product of an explicit 10-point integer configuration with reflection symmetry and verifies the inequality via exact integer arithmetic.
3 supporting theorems

Fair Division

New results in fair chore division established a sharp (r+1)/2 maximin-share guarantee for 2 agents with bivalued costs, improving on the general 3/2 bound. Properties of identically ordered chore allocations were also verified.

Partial

Two-agent chore division achieves sharp (r+1)/2 maximin share under equal marginals

Two people sharing chores whose costs take 2 values in ratio r can flip a coin between 2 assignments to guarantee at most (r+1)/2 times their fair share.

Before

arXiv:2609.35280 established a general 3/2 equal-marginal maximin-share guarantee for chores, but the sharp bound for 2 agents with bivalued costs remained open.

Now

For 2 agents with bivalued chore costs of ratio 1 ≤ r < 2, an equal-marginal lottery guarantees an ex-post cost of at most (r + 1)/2 times each agent's maximin share.

Why it matters
Improves the equal-marginal maximin-share approximation ratio from 3/2 down to (r + 1)/2 for two-agent bivalued chore instances.
The idea
Partitions chores into 4 regions via Venn diagram parity analysis, balancing counts within each region and taking an equal-weight swap lottery.
4 supporting theorems

Formalized

Identically ordered chore instances satisfy one-third and four-thirds cost bounds

When all people agree on how difficult chores rank, chores left over after pairing cost at most one-third of the fair share.

Before

Establishing best-of-many-worlds guarantees with sublinear disposals required bounds on remaining chores and opposite-pair bundles in identically ordered instances.

What is checked

arXiv:2611.04884 Lemma 4.1 proves that when maximin shares equal 1, every chore beyond 2n costs at most 1/3 and every opposite pair costs at most 4/3; Lean now checks the proof.

Why it matters
Verifies the core structural bounds used for best-of-many-worlds chore allocations.
The idea
Pigeonhole arguments on chore partitions bound the cost of large-index chores and combined opposite pairs.
3 supporting theorems
  • ido_remaining_chores_cost_le_one_thirdIn an identically ordered instance with nonnegative costs and maximin share 1 for each agent, every remaining chore g in V (with index at…
  • ido_opposite_pair_cost_le_four_thirdsIn an identically ordered instance of m chores and n agents with 2 * n ≤ m and nonnegative costs c where every agent has maximin share 1,…
  • chore_opposite_pair_cardGiven implicit natural numbers m and n, a hypothesis h2n : 2 * n ≤ m, and an element j : Fin n, the cardinality of chore_opposite_pair h2n…

Computability & Recursion Theory

Formalization resolved the reachability equivalence underlying the undecidability of matrix mortality for 2×2 rational and integer matrices.

Formalized

Matrix mortality for two-by-two matrices reduces to line reachability

Determining whether a set of 2×2 matrices can multiply to zero is equivalent to asking whether some sequence of matrices maps one line to another.

Before

Whether mortality for 2×2 integer matrices is decidable was a longstanding open problem in algorithmic algebra.

What is checked

arXiv:2611.06562 Lemma 3.1 proves that a finite set of invertible 2×2 rational matrices with 1 rank-one matrix is mortal if and only if some word maps the linear span of u to the kernel of λ; Lean now checks the proof.

Why it matters
Checks the core reduction connecting matrix mortality to projective line reachability, which underpins the undecidability proof for 2×2 integer matrix mortality.
The idea
Minimal zero products must have rank-one outer factors whose sandwich product collapses to zero exactly when the inner product vanishes.
1 supporting theorem

Online Algorithms

Tight competitive bounds were established for dominant resource fairness in multi-resource scheduling.

Formalized

Dominant resource fairness has competitive ratio at least one plus square root of resources

In systems sharing multiple resources among tasks, any scheduling policy based on dominant shares has a worst-case delay factor growing with the square root of the number of resources.

Before

Dominant resource fairness was widely deployed in cloud scheduling, but tight worst-case completion-time competitive ratios remained uncharacterized.

What is checked

arXiv:2611.07905 Proposition 1 proves that for D resources, the competitive ratio of dominant resource fairness (DRF) is at least 1 + √D; Lean now checks the proof.

Why it matters
Formalizes the lower bound confirming that DRF suffers an unavoidable square-root penalty in completion time as resource count increases.
The idea
Constructs an explicit sequence of scheduling instances where the ratio of algorithm cost to optimal bound converges to 1 + √D.
1 supporting theorem
  • drf_prop1_ratio_tendstoFor every natural number D with 1 ≤ D, the sequence fun m : ℕ => drf_prop1_ratio D m converges to 1 + Real.sqrt (D : ℝ) along…

Quantum Computation

Investigations of quantum measurement incompatibility established that d² binary measurements suffice to witness incompatibility on the full space while being jointly measurable on every proper subspace.

Formalized

Families of d² measurements are incompatible globally but jointly measurable on every subspace

In d dimensions, a set of d² simple measurements can be impossible to measure simultaneously overall, yet perfectly compatible when restricted to any smaller subspace.

Before

Whether quantum measurement incompatibility can be hidden in proper subspaces while remaining globally incompatible was investigated for noiseless quantum code certification.

What is checked

arXiv:2610.37347 Corollary 1 proves that for every d ≥ 2, there exists a family of d² binary measurements on ℂ^d incompatible on ℂ^d but jointly measurable on every proper subspace; Lean now checks the proof.

Why it matters
Confirms that measurement incompatibility can be fully concealed within proper subspaces, establishing the boundary dimension d².
The idea
Constructs the measurement family from a minimal informationally complete rank-one measurement and dual functionals.
2 supporting theorems

Still open

Terms

DRF
dominant resource fairness: a multi-resource allocation policy that equalizes the dominant resource shares assigned to competing users
TCS
TCS: combinatorics and discrete structures arising in the study of computation

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.