AFTD Auto-Formalizing Theoretical Domains

poc_linkedness_conjecture_counterexample

theoremverifiedoriginal

Counterexample to arXiv:1908.05433 Conjecture 3.10 for two agents: there is a graph G on 8 vertices that is (2,3)-linked but not (2,4)-linked, so the conjecture (with k = 4) predicts PoC(G,2) = 8/7, yet with u = (5,5,5,1,1,1,12,0) the maximin share is 15 (split {0,1,2,7} versus the rest) while every bipartition of G into two connected parts gives the poorer part at most 13. Hence PoC(G,2) ≥ 15/13 > 8/7.

Statement

theorem poc_linkedness_conjecture_counterexample :
    ∃ G : SimpleGraph (Fin 8), is_ab_linked G 2 3 ∧ ¬ is_ab_linked G 2 4 ∧
      ∃ u : Fin 8 → ℝ, (∀ v, 0 ≤ u v) ∧ ∃ S : Finset (Fin 8), ∀ T : Finset (Fin 8),
        is_connected_vertex_set G (↑T : Set (Fin 8)) →
        is_connected_vertex_set G (↑(Tᶜ) : Set (Fin 8)) →
          8 * min (∑ v ∈ T, u v) (∑ v ∈ Tᶜ, u v) < 7 * min (∑ v ∈ S, u v) (∑ v ∈ Sᶜ, u v)
Related work
refutes arXiv:1908.05433, Conjecture 3.10 (a (2,k-1)- but not (2,k)-linked graph has two-agent price of connectivity 2k/(2k-1)); 8-vertex graph, (2,3)- but not (2,4)-linked, price at least 15/13 > 8/7
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 11
  • poc8_linked_two_threeThe 8-vertex graph G is (2,3)-linked: any 2 terminals and 3 further terminals are separated by a connected bipartition of G.
  • poc8_not_linked_two_fourG is not (2,4)-linked: for M1 = {0,1} and M2 = {2,5,6,7}, any S1 ⊇ M1 disjoint from S2 ⊇ M2 lies in {0,1,3,4}, and {0,4} is cut off from…
  • poc8_gmms_checkEvery bipartition (P, not P) of the eight vertices passes the bipartition check.
  • poc8_gmms_okCheck for a bipartition (P, not P): 8 times the smaller part value is below 105 = 7·15, or one of the two parts is disconnected.
  • poc8_val_eqThe folded value agrees with the real sum of u over the selected vertices.
  • poc8_discb_soundIf the Boolean disconnectedness test accepts S, then S does not induce a connected subgraph of G.
  • poc8_uThe valuation u = (5, 5, 5, 1, 1, 1, 12, 0) on the eight vertices.
  • is_ab_linkedA graph G is (a,b)-linked if for any disjoint vertex sets M1, M2 with |M1| = a and |M2| = b there are disjoint vertex sets S1 ⊇ M1 and S2…
  • is_connected_vertex_setA vertex set S of a graph G is connected if the subgraph of G induced by S is connected (in particular S is nonempty).
  • poc8_graphThe 8-vertex graph G with edges 04, 05, 06, 07, 13, 15, 16, 17, 23, 24, 26, 27, 36, 37, 45, 47, 57, 67.
  • poc8_valThe total u-value of the vertex set selected by P, computed by a fold.

Read back from the Lean

There exists a simple graph $G$ on the 8-element vertex set $\text{Fin } 8$ such that all of the following hold: 1. $G$ is $(2, 3)$-linked: for every pair of disjoint subsets $M_1, M_2 \subseteq \text{Fin } 8$ with $|M_1| = 2$ and $|M_2| = 3$, there exist disjoint subsets $S_1, S_2 \subseteq \text{Fin } 8$ such that $M_1 \subseteq S_1$, $M_2 \subseteq S_2$, and the induced subgraphs $G[S_1]$ and $G[S_2]$ are both connected. 2. $G$ is not $(2, 4)$-linked: it is not the case that for every pair of disjoint subsets $M_1, M_2 \subseteq \text{Fin } 8$ with $|M_1| = 2$ and $|M_2| = 4$, there exist disjoint subsets $S_1, S_2 \subseteq \text{Fin } 8$ such that $M_1 \subseteq S_1$, $M_2 \subseteq S_2$, and both $G[S_1]$ and $G[S_2]$ are connected. 3. There exists a non-negative vertex-weight function $u : \text{Fin } 8 \to \mathbb{R}$ (i.e., $u(v) \ge 0$ for all $v \in \text{Fin } 8$) and a subset $S \subseteq \text{Fin } 8$ such that for every subset $T \subseteq \text{Fin } 8$, if both the induced subgraph on $T$ and the induced subgraph on its complement $T^c = \text{Fin } 8 \setminus T$ are connected, then $$8 \cdot \min\left(\sum_{v \in T} u(v), \sum_{v \in T^c} u(v)\right) < 7 \cdot \min\left(\sum_{v \in S} u(v), \sum_{v \in S^c} u(v)\right).$$

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

theorem poc_linkedness_conjecture_counterexample :    ∃ G : SimpleGraph (Fin 8), is_ab_linked G 2 3 ∧ ¬ is_ab_linked G 2 4 ∧      ∃ u : Fin 8 → ℝ, (∀ v, 0 ≤ u v) ∧ ∃ S : Finset (Fin 8), ∀ T : Finset (Fin 8),        is_connected_vertex_set G (↑T : Set (Fin 8)) →        is_connected_vertex_set G (↑(Tᶜ) : Set (Fin 8)) →          8 * min (∑ v ∈ T, u v) (∑ v ∈ Tᶜ, u v) < 7 * min (∑ v ∈ S, u v) (∑ v ∈ Sᶜ, u v) := by  refine ⟨poc8_graph, poc8_linked_two_three, poc8_not_linked_two_four, fun v => (poc8_u v : ℝ),    fun v => Nat.cast_nonneg _, {0, 1, 2, 7}, fun T hT hTc => ?_⟩  have hok := poc8_gmms_check (fun v => decide (v ∈ T))  simp only [poc8_gmms_ok, Bool.or_eq_true, decide_eq_true_eq] at hok  have eT : {x | decide (x ∈ T) = true} = (↑T : Set (Fin 8)) := by ext; simp  have eTc : {x | (!decide (x ∈ T)) = true} = (↑(Tᶜ) : Set (Fin 8)) := by ext; simp  rcases hok with (h | h) | h  · have fT : Finset.univ.filter (fun v => decide (v ∈ T) = true) = T := by ext; simp    have fTc : Finset.univ.filter (fun v => (!decide (v ∈ T)) = true) = Tᶜ := by ext; simp    have vT := poc8_val_eq (fun v => decide (v ∈ T))    have vTc := poc8_val_eq (fun v => !decide (v ∈ T))    rw [fT] at vT    rw [fTc] at vTc    have nS : poc8_val (fun v => decide (v ∈ ({0, 1, 2, 7} : Finset (Fin 8)))) = 15 := by decide    have nSc : poc8_val (fun v => !decide (v ∈ ({0, 1, 2, 7} : Finset (Fin 8)))) = 15 := by decide    have vS := poc8_val_eq (fun v => decide (v ∈ ({0, 1, 2, 7} : Finset (Fin 8))))    have vSc := poc8_val_eq (fun v => !decide (v ∈ ({0, 1, 2, 7} : Finset (Fin 8))))    have fS : Finset.univ.filter (fun v => decide (v ∈ ({0, 1, 2, 7} : Finset (Fin 8))) = true) =        {0, 1, 2, 7} := by ext; simp    have fSc : Finset.univ.filter        (fun v => (!decide (v ∈ ({0, 1, 2, 7} : Finset (Fin 8)))) = true) =        ({0, 1, 2, 7} : Finset (Fin 8))ᶜ := by ext; simp    rw [fS, nS] at vS    rw [fSc, nSc] at vSc    rw [← vT, ← vTc, ← vS, ← vSc]    have h' : ((8 * min (poc8_val fun v => decide (v ∈ T)) (poc8_val fun v => !decide (v ∈ T)) : ℕ)        : ℝ) < 105 := by exact_mod_cast h    push_cast at h'    norm_num    linarith  · exact absurd hT (by rw [← eT]; exact poc8_discb_sound _ h)  · exact absurd hTc (by rw [← eTc]; exact poc8_discb_sound _ h)
See it in the graphDiscuss this resultChallenge it