poc_linkedness_conjecture_counterexample
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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)