AFTD Auto-Formalizing Theoretical Domains

Research Blogs

An Unweighted 71-Vertex Graph Admits a 33-Step Cycle of Inclusion-Minimal Profitable Deviations in Three-Color Max-Cut

medium tier2026-11-03reviewed by Claude Code中文版

Abstract

In the max $k$-cut game each vertex of a graph chooses one of $k$ colors and earns the number of its neighbors with a different color. arXiv:1810.09278 showed on a weighted graph that improving deviations performed by minimal coalitions can cycle, so that weighted games admit no strong potential function even when only minimal coalitions may deviate; its concluding section leaves open whether a strong potential function exists on unweighted graphs. We answer this negatively for three colors. On an explicit unweighted graph with 71 vertices, made of four core blocks of eight vertices and three anchor blocks of thirteen, we give a cycle of 33 strong improvements that returns to its starting coloring: the 32 core vertices first deviate jointly, each gaining exactly one, and then return to their original colors one at a time, each again gaining one. Every step is inclusion-minimal: from the coloring where the step starts, no proper subset of the changing vertices has any profitable joint deviation. The joint step lowers the cut by 32 and each of the 32 single moves raises it by one. The definitions, the cycle and its minimality are verified in Lean 4.

1. Introduction

In a finite game a potential function is a real function on strategy profiles that strictly increases whenever a player improves its payoff by a unilateral change. A strong potential function strictly increases also under every strong improvement, that is, every joint change of strategy by a coalition in which all members strictly gain. Such a function forbids cycles of strong improvements and, when it exists, proves that strong equilibria exist, because the improvement dynamics must stop. It is one of the main tools for proving the existence of strong equilibria.

The max $k$-cut game is played on a finite undirected graph $G = (V, E)$. Each vertex is a player choosing one of $k$ colors, and its payoff is the total weight of its incident edges whose other endpoint has a different color; on an unweighted graph this is the number of differently colored neighbors. The cut value is an exact potential for unilateral moves, so Nash equilibria exist. Whether strong equilibria always exist is open.

arXiv:1810.09278 studies strong equilibria of this game. A strong improvement there is minimal if no proper subset of the deviating coalition can perform an improvement by itself. Its Proposition 2 exhibits a weighted graph with a cycle of strong improvements performed by minimal coalitions only (the joint deviation of four players followed by four single-player improvements), so that on weighted graphs no strong potential function exists even when only minimal coalitions are allowed to deviate. For unweighted graphs the paper proves positive results: from a Nash equilibrium, minimal strong improvements by coalitions of at most five players increase the cut value, and every optimal coloring is a 5-strong equilibrium. It also shows that the cut value itself is not a strong potential function on unweighted graphs. Its concluding section states that it is still unknown whether a strong potential function exists on unweighted graphs.

This post answers that question negatively for three colors, in the strong form of the weighted result. We give an explicit unweighted graph maxcut_cycle71_graph on 71 vertices and a sequence of 33 three-colorings that returns to its start, in which every step is a strong improvement by the set of vertices that change color, and every step is inclusion-minimal: from the coloring where the step starts, no proper subset of the changing vertices has any profitable joint deviation at all. A function that strictly increased along every minimal strong improvement would increase strictly around this cycle, which is impossible. So unweighted three-color max-cut games admit no strong potential function, even when only minimal coalitions may deviate.

The cycle has a simple shape. One step is a joint deviation of 32 core vertices that lowers the cut by 32 while each core vertex gains exactly one; the other 32 steps are single vertices returning to their old colors, each raising the cut by one. The whole construction is formalized and machine-checked in Lean 4 as maxcut_unweighted_minimal_deviation_cycle_exists.

2. Preliminaries

Let $V$ be a finite vertex set and $G$ a simple graph on $V$. In a three-color Max-Cut game, each vertex chooses a color from $\{0, 1, 2\}$, formalized as $\text{Fin } 3$. The utility of vertex $v$ under coloring $\sigma : V \to \text{Fin } 3$ is the number of neighbors of $v$ assigned a color distinct from $\sigma(v)$: $$ u_v(\sigma) = |\{ w \in V : G\text{.Adj}(v, w) \land \sigma(w) \neq \sigma(v) \}|. $$ Maximizing utility is equivalent to minimizing the number of neighbors sharing the same color.

Definition 1 (is_maxcut_strong_deviation). Let $G$ be a simple graph on a finite type $V$ with decidable adjacency, and let $k \ge 1$. Given a profile $\sigma : V \to \text{Fin } k$, a coalition $S \subseteq V$, and a profile $\tau : V \to \text{Fin } k$, the predicate is_maxcut_strong_deviation holds if:

  1. $S$ is nonempty;
  2. $\tau(v) = \sigma(v)$ for all $v \notin S$;
  3. $u_v(\sigma) < u_v(\tau)$ for all $v \in S$.

Remark on Definition 1. In arXiv:1810.09278 the members of a deviating coalition change their strategies. The Lean definition does not require this. Along the cycle below, each step's coalition is exactly the set of vertices whose color changes, so every member does change color. For minimality the Lean definition only makes the statement stronger: it rules out profitable deviations of proper subcoalitions in which members may also keep their colors.

Definition 2 (maxcut_cycle71_field). The anchor degree function maxcut_cycle71_field assigns the number of edges from core vertex $u$ to anchor block $j \in \{0, 1, 2\}$: - For $u < 8$: 0 for $j=0$, 13 for $j=1$, and 7 for $j=2$. - For $8 \le u < 16$: 1 for $j=0$, 2 for $j=1$, and 13 for $j=2$. - For $16 \le u < 24$: 13 for $j=0$, 1 for $j=1$, and 2 for $j=2$. - For $24 \le u < 32$: 0 for $j=0$, 7 for $j=1$, and 13 for $j=2$. For $u \ge 32$, the field is 0.

Remark on Definition 2. Each anchor block has 13 vertices. A value of 13 connects $u$ to all vertices in that anchor block, while 0 creates no edges.

Definition 3 (maxcut_cycle71_graph). The graph maxcut_cycle71_graph is an unweighted simple graph on $V = \text{Fin } 71 = \{0, \dots, 70\}$. Vertices are partitioned into four core blocks of eight ($B_0 = \{0, \dots, 7\}$, $B_1 = \{8, \dots, 15\}$, $B_2 = \{16, \dots, 23\}$, $B_3 = \{24, \dots, 31\}$) and three anchor blocks of thirteen ($A_0 = \{32, \dots, 44\}$, $A_1 = \{45, \dots, 57\}$, $A_2 = \{58, \dots, 70\}$). An edge $\{u, v\}$ exists if and only if $u \neq v$ and $(R(u, v) \lor R(v, u))$, where $R(u, v)$ is the disjunction of six conditions:

  1. $u \in B_0, v \in B_1$, and $(v - 8 + 8 - u) \pmod 8 \ge 2$;
  2. $u \in B_0, v \in B_2$, and $(v - 16 + 8 - u) \pmod 8 < 2$;
  3. $u \in B_0$ and $v \in B_3$;
  4. $u \in B_1, v \in B_2$, and $(v - 16 + 8 - (u - 8)) \pmod 8 < 4$;
  5. $u \in B_1, v \in B_3$, and $(v - 24 + 8 - (u - 8)) \pmod 8 \ge 2$;
  6. $u < 32, v \ge 32$, and $(v - 32) \pmod{13} < \text{field}(u, (v - 32) / 13)$.

Remark on Definition 3. There are no edges within core blocks, between $B_2$ and $B_3$, or within/between anchor blocks. The conditions modulo 8 define regular cyclic connections among core blocks.

Definition 4 (maxcut_cycle71_return_stages). Let $\sigma^{(0)}$ and $\sigma^{(1)}$ be the two three-colorings that agree on the anchors, which are colored by block ($A_0$ color 0, $A_1$ color 1, $A_2$ color 2), and color the core blocks as follows: $\sigma^{(0)}$ gives $B_0, B_1, B_2, B_3$ the colors $0, 1, 2, 0$, and $\sigma^{(1)}$ gives them $2, 0, 1, 1$. The rank of a core vertex is its position in the order in which the core vertices return: first $B_3$, then $B_1$, then $B_2$, then $B_0$, each block in increasing order of vertices; ranks run over $\{0, \dots, 31\}$. For each $i \in \text{Fin } 33 = \{0, \dots, 32\}$, the profile $\sigma_i$ given by maxcut_cycle71_return_stages at $i$ is: $$ \sigma_i(v) = \begin{cases} \sigma^{(0)}(v) & \text{if } i = 0 \lor (v < 32 \land \text{rank}(v) < i - 1), \\ \sigma^{(1)}(v) & \text{otherwise.} \end{cases} $$

Remark on Definition 4. At stage 0 the coloring is $\sigma^{(0)}$. At stage 1 all 32 core vertices have their $\sigma^{(1)}$ colors. From stage $i$ to stage $i+1$, for $i = 1, \dots, 32$ (with stage 33 read as stage 0), the core vertex of rank $i - 1$ returns to its $\sigma^{(0)}$ color. The anchor vertices never change color.

3. Main result

The main theorem establishes the existence of an infinite periodic sequence of strong deviations in the three-color Max-Cut game on the unweighted 71-vertex graph maxcut_cycle71_graph, returning to its initial profile after 33 steps, where every step is inclusion-minimal.

Theorem (maxcut_unweighted_minimal_deviation_cycle_exists). There exists a decidable adjacency relation $d$ on maxcut_cycle71_graph and a sequence of three-colorings $f : \mathbb{N} \to (\text{Fin } 71 \to \text{Fin } 3)$ such that: 1. The sequence returns to its start after 33 transitions: $f(33) = f(0)$; 2. For every $n \in \mathbb{N}$, the profile transition from $f(n)$ to $f(n+1)$ is a strong deviation (is_maxcut_strong_deviation) by the set of changing vertices, $S_n = \{ v \in \text{Fin } 71 : f(n+1)(v) \neq f(n)(v) \}$; 3. For every $n \in \mathbb{N}$, the deviation $S_n$ is inclusion-minimal: for every proper subset $S \subsetneq S_n$, there exists no three-coloring $\tau : \text{Fin } 71 \to \text{Fin } 3$ such that $(S, \tau)$ is a strong deviation from $f(n)$ on maxcut_cycle71_graph.

What this result establishes: a strong potential function would strictly increase along every step of a sequence of strong improvements, so it cannot exist when such a sequence returns to its start. The theorem gives such a sequence on an unweighted graph with three colors, and every step of it is inclusion-minimal. Hence no strong potential function exists for the unweighted three-color max-cut game, even if it is only required to increase along strong improvements by minimal coalitions. This is the unweighted counterpart of Proposition 2 of arXiv:1810.09278 and answers the question its concluding section leaves open, for $k = 3$.

Theorem maxcut_unweighted_minimal_deviation_cycle_exists (Lean 4, verified)
theorem maxcut_unweighted_minimal_deviation_cycle_exists :
    ∃ (d : DecidableRel maxcut_cycle71_graph.Adj) (f : ℕ → Fin 71 → Fin 3),
      f 33 = f 0 ∧ ∀ n,
        @is_maxcut_strong_deviation _ _ maxcut_cycle71_graph d 3 (f n)
          (Finset.univ.filter fun v => f (n + 1) v ≠ f n v) (f (n + 1)) ∧
        ∀ S : Finset (Fin 71),
          S ⊂ (Finset.univ.filter fun v => f (n + 1) v ≠ f n v) →
          ¬ ∃ τ : Fin 71 → Fin 3,
            @is_maxcut_strong_deviation _ _ maxcut_cycle71_graph d 3 (f n) S τ

4. Proof

We outline the proof of maxcut_unweighted_minimal_deviation_cycle_exists. The sequence is $f(n) = \sigma_{n \bmod 33}$, where $\sigma_i$ is maxcut_cycle71_return_stages at $i$. Everything then reduces to one statement about the 33 consecutive pairs of stages.

Lemma 1 (maxcut_cycle71_minimal_cycle_steps). For every $i \in \text{Fin } 33$, with $i + 1$ taken in $\text{Fin } 33$, let $$ D_i = \{ v \in \text{Fin } 71 : \sigma_{i+1}(v) \neq \sigma_i(v) \}. $$ Then $(D_i, \sigma_{i+1})$ is a strong deviation from $\sigma_i$, and for every proper subset $S \subsetneq D_i$ there is no coloring $\tau$ such that $(S, \tau)$ is a strong deviation from $\sigma_i$.

The 33 steps fall into two kinds: the joint deviation from stage 0 to stage 1, and the 32 single-vertex returns.

The single-vertex returns. For each of the 32 steps from stage $i$ to stage $i+1$ with $i \in \{1, \dots, 32\}$, a helper lemma checks by kernel evaluation that the set $D_i$ of changing vertices is the single core vertex $v_i$ of rank $i - 1$, and that $v_i$ strictly gains by returning from its $\sigma^{(1)}$ color to its $\sigma^{(0)}$ color, the rest of the coloring being fixed. In fact each such vertex gains exactly one, and each return raises the cut by one. Minimality is immediate here: the only proper subset of a singleton is empty, and a strong deviation requires a nonempty coalition.

The joint deviation. From stage 0 to stage 1 exactly the 32 core vertices change color, since the anchors have the same color in $\sigma^{(0)}$ and $\sigma^{(1)}$. That $(B_0 \cup B_1 \cup B_2 \cup B_3, \sigma^{(1)})$ is a strong deviation from $\sigma^{(0)}$ is again checked by kernel evaluation: every core vertex gains exactly one. For orientation, the degrees are 36 in $B_0$ (6 neighbors in $B_1$, 2 in $B_2$, 8 in $B_3$ and 20 anchors), 32 in $B_1$, 22 in $B_2$ and 34 in $B_3$; the cut drops from 688 edges to 656 at this step and climbs back by one per return.

Minimality of the joint deviation is the substantive part. Suppose a proper subset $S$ of the core and a coloring $\tau$ form a strong deviation from $\sigma^{(0)}$, and let $M \subseteq S$ be the members whose color actually changes. $M$ is nonempty: if no member changed color, $\tau$ would equal $\sigma^{(0)}$ and nobody would gain.

The argument rests on one finite count, checked by kernel evaluation: for each core vertex $v$ and each color $c \neq \sigma^{(0)}(v)$, the number of neighbors of $v$ that are core vertices or have a $\sigma^{(0)}$ color different from $c$ is at most $u_v(\sigma^{(0)})$, plus one if $c = \sigma^{(1)}(v)$. Since every vertex outside $S$ keeps its $\sigma^{(0)}$ color and $S$ lies in the core, this count bounds $u_v(\tau)$ for a member $v$ moving to $c$, whatever the other core vertices do. Two consequences follow for every $v \in M$:

  • $v$ must move to its $\sigma^{(1)}$ color; any other new color gives $u_v(\tau) \le u_v(\sigma^{(0)})$.
  • If $v$ has a core neighbor $w$ whose $\sigma^{(0)}$ color is $\sigma^{(1)}(v)$, then $w \in M$. Otherwise $w$ keeps that color, the edge $vw$ is monochromatic under $\tau$, and the bound drops by one to $u_v(\tau) \le u_v(\sigma^{(0)})$, so $v$ does not gain.

So $M$ is a nonempty set of core vertices closed under the forcing relation: $v$ forces each core neighbor whose initial color is $v$'s new color. Between blocks this relation goes $B_0 \to B_2$ (new color 2), $B_2 \to B_1$ (new color 1), $B_1 \to B_0$ and $B_1 \to B_3$ (new color 0), and $B_3 \to B_1$ (new color 1). A further lemma shows, by an explicit closed walk of 40 forcing steps through all 32 core vertices, that every nonempty closed set contains the whole core. Hence $M$, and with it $S$, contains all 32 core vertices, contradicting $S \subsetneq D_0$.

Proof of the main theorem. The decidability witness for adjacency is obtained by unfolding the definitions of maxcut_cycle71_graph and maxcut_cycle71_field. The sequence is $f(n) = \sigma_{\langle n \bmod 33 \rangle}$. Then $f(33) = f(0)$ holds by reflexivity, since $33 \bmod 33 = 0$. For any $n$, the stage index of $n + 1$ equals $i + 1$ in $\text{Fin } 33$ where $i$ is the index of $n$, by a short modular computation. So the step from $f(n)$ to $f(n+1)$ is the step from $\sigma_i$ to $\sigma_{i+1}$, and Lemma 1 at index $i$ gives both the strong deviation of the changing set and the absence of profitable deviations for its proper subsets.

5. Discussion

Theorem maxcut_unweighted_minimal_deviation_cycle_exists answers, for three colors, the question left open in the concluding section of arXiv:1810.09278: unweighted max-cut games admit no strong potential function, and this remains so when only minimal coalitions may deviate, as the paper had shown for weighted graphs. The weighted cycle there is a coalition of 4 followed by 4 single moves; here it is a coalition of 32 followed by 32 single moves. The anchor blocks of 13 vertices play the role of the heavy edges of the weighted example: they fix which colors each core vertex can profitably take.

Scope and Boundaries of the Result:

1. Colors: The counterexample operates in three-color Max-$k$-Cut ($k = 3$). The material does not address whether inclusion-minimal cycles can exist for two colors ($k = 2$). For $k = 2$ each player has a single alternative color, and the construction, which uses all three colors on the anchors, does not adapt directly.

2. Graph Order: The construction uses 71 vertices: 32 core vertices partitioned into four cyclic blocks of 8, and 39 anchor vertices partitioned into three blocks of 13. The result does not determine whether 71 vertices is the minimal graph size required to support an inclusion-minimal cycle, or whether a smaller unweighted graph could produce a similar cycle.

3. Graph Topologies: The construction of maxcut_cycle71_graph makes essential use of dense bipartite interconnections between core blocks and asymmetric connections to anchor blocks. The material does not cover structured graph families, such as planar graphs, graphs of bounded treewidth, or regular graphs.

What the construction shows. The cut value increases under every unilateral improvement, so any cycle of strong improvements needs coalitional steps that lower the cut. Here a single minimal coalition lowers it by 32, and 32 single moves, each a strict improvement, raise it back. The starting coloring $\sigma^{(0)}$ is not a Nash equilibrium (some anchor vertices can improve alone), so the cycle does not bear on the paper's cut-value argument for minimal coalitions of at most five players deviating from a Nash equilibrium; what it rules out is any strong potential function, which would have to increase along every strong improvement from every coloring. The question of whether every unweighted max $k$-cut game has a strong equilibrium, which the same paper leaves open with the conjecture that optimal colorings are strong equilibria, is not settled by this cycle: the cycle only rules out proofs of existence by a strong potential function.

Next Questions:

1. Does there exist an unweighted graph supporting a cycle of inclusion-minimal strong deviations for $k = 2$ colors?

2. What is the minimum number of vertices $n$ for which an unweighted graph admits an inclusion-minimal strong deviation cycle in three-color Max-Cut?

3. Can structural graph restrictions, such as planarity or bounded degree, guarantee the convergence of inclusion-minimal coalitional dynamics?

Why it is research-level

  • 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

Lean declarations

  • maxcut_unweighted_minimal_deviation_cycle_existsOn the specified unweighted 71-vertex graph there is an infinite three-color strong-deviation sequence returning after 33 steps, and every…
  • maxcut_cycle71_graphThe explicit 71-vertex finite simple graph with four core blocks of eight and three anchor blocks of thirteen, with edges determined by…
  • is_maxcut_strong_deviationA strong deviation from σ is a nonempty coalition S ⊆ V with a coloring τ agreeing with σ outside S such that u_v(τ) > u_v(σ) for every v…
  • maxcut_cycle71_fieldThe number of anchor neighbors of each fixed color assigned to each core block in the regular 71-vertex construction.
  • maxcut_cycle71_return_stagesThe 33 profiles of the displayed 71-vertex cycle: the initial profile, the joint deviation, and the partial singleton restorations.
  • 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…

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

References

  1. arXiv:1810.09278

Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.