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.
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.
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.
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.
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.
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.
Exhibits an unweighted three-color Max-k-Cut game with a cycle of inclusion-minimal profitable deviations, ruling out a strong potential even when deviations are restricted to minimal coalitions
Exhibits a cycle of profitable coalitional deviations in an unweighted three-color game, ruling out a strong potential for all such deviations; the cited cycle used weighted edges. This does not assert that the large coalition is minimal or resolve strong-equilibrium existence
Establishes weighted half-neighborhood coverage for oriented graphs whose every induced non-neighborhood has an out-kernel, including graphs outside the tournament–acyclic class treated in arXiv:2610.23487
An explicit source-free oriented graph of maximum outdegree four gives f(4) at least 5/4 for the uniform source-neighborhood inequality in arXiv:2601.11847, Problem 5.2, while itself having a small quasi-kernel
Settles the case r = n = 3 of the paper's Question 3.1 (does w_r(n) = 2r(n-1)+1?): w_3(3) = 13, the first exact value with r >= 3 and n >= 3, where the paper has only w_r(2) = 2r+1 and w_2(n) = 4n-3 for some n; the proof classifies every w-bad sequence modulo 9 up to GL_3(F_3) by a kernel-checked orbit certificate
For two agents with bivalued costs of common ratio 1 ≤ r < 2, establishes an equal-marginal lottery with ex-post (r+1)/2 maximin-share guarantee, improving the general 3/2 equal-marginal guarantee in https://arxiv.org/abs/2609.35280
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.
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.
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.
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.
maxcut_fair9_witnessA specified three-color profile on the nine-vertex graph has utility at least four for every vertex and admits no profitable singleton…
maxcut_fair9_stable_exampleA specified three-color profile is a strong equilibrium of the nine-vertex graph.
maxcut_fair9_no_maxmin_strong_nashOn the specified nine-vertex graph, no strong equilibrium has minimum utility at least that of every singleton-stable three-coloring.
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.
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.
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.
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.
digraph_local_four_witness_sources_sinksFor the explicit 24-vertex maximum-outdegree-four witness, every source left after deleting a closed out-neighborhood is a sink.
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.
simple_graph_adj_row_add_mem_rangeFor any two vertices u and v of a finite simple graph, the sum of their adjacency matrix rows lies in the row space (the range of the…
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.
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.
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.
mordell_ten_integer_norm_sumThe sum of squared norms of the ten integer points in the witness configuration W is 9999608174.
mordell_ten_integer_witness_ineqFor the ten integer points W = ![(11183, 0), (-11183, 0), (32765, 14669), (32765, -14669), (-32765, 14669), (-32765, -14669), (12323,…
mordell_ten_exists_feasible_gt_chalkThere exists a configuration of ten points z : Fin 10 → ℂ in the complex plane satisfying ∑ i : Fin 10, ‖z i‖^2 = 10 such that ∏ i : Fin…
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.
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.
two_agent_balanced_symmetric_swap_lotteryIf both bundles of a two-way partition cost at most alpha times the maximin share of each agent, the equal mixture of that allocation and…
four_type_simultaneous_balance_countsFour type counts can be halved so that the total and each of the two high-type marginals are balanced to within one.
two_finite_subsets_simultaneously_balancedGiven two subsets of a finite set, one can split the underlying set into two parts so that the two part sizes and the counts of elements…
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.
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.
matrix_rank_one_sandwich_identityFor vectors u, v and a square matrix W over a commutative ring, (u v^T) W (u v^T) = (v · (W u)) • (u v^T).
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.
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.
not_can_certify_noiseless_codes_oneFor any dimension d, a single binary measurement cannot certify noiseless quantum codes, so ¬ can_certify_noiseless_codes d 1 holds.
Does there exist a polynomial-time online paging algorithm achieving competitive ratio strictly less than 2 for Markov sources?
Can the tight instances for the Lonely Runner Conjecture be completely classified across all dimensions?
What is the optimal competitive ratio for online budgeted allocation under arbitrary bidding distributions?
Does Seymour's conjecture on openly disjoint directed cycles hold for oriented graphs of maximum outdegrees four and five?
What is the exact asymptotic ratio of the clique packing number in graphs with quadratic excess edges?
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.