op_193_avoidance_graph
For a family of cycle-vertex sets, there is a graph whose edges are noncycle pairs not contained in any family member; each k-clique is a stable k-set meeting every family member in at most one point.
Statement
theorem op_193_avoidance_graph (m q k : ℕ) (A : Fin q → Finset (Fin m)) :
∃ G : SimpleGraph (Fin m),
(∀ x y, G.Adj x y ↔ x ≠ y ∧ ¬ (SimpleGraph.cycleGraph m).Adj x y ∧
∀ j, ¬(x ∈ A j ∧ y ∈ A j)) ∧
∀ S : Finset (Fin m), G.IsNClique k S →
S.card = k ∧ (SimpleGraph.cycleGraph m).IsIndepSet (↑S : Set (Fin m)) ∧
∀ j, (S ∩ A j).card ≤ 1- Source
- Clique construction for the anchor-avoidance reduction of OP-193.
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
To construct a graph whose edges avoid cycle edges and pairs in the family sets, we define a simple graph on Fin m with the required adjacency conditions. Its symmetry and looplessness are verified directly. Then, any k-clique in this graph has size k, is an independent set of the cycle graph because edges in the graph cannot be cycle edges, and intersects each family set in at most one vertex because edges cannot share a family set.
The adjacency relation of Inbox777Avoid.graph is symmetric.
Given an edge between x and y, x ≠ y implies y ≠ x by symmetry of inequality. Furthermore, x and y are not adjacent in the cycle graph, so neither are y and x by symmetry of cycle graph adjacency. Finally, no family member contains both x and y, so none contains both y and x.
intro x y h refine ⟨h.1.symm, ?_, ?_⟩ · intro hxy; exact h.2.1 hxy.symm · intro j hxy; exact h.2.2 j ⟨hxy.2, hxy.1⟩⟩
Inbox777Avoid.graph contains no self-loops.
Adjacency between x and x would require x ≠ x, which contradicts reflexivity x = x.
loopless := ⟨by intro x h; exact h.1 rfl⟩
Any k-clique in the graph has size k and forms an independent set in the cycle graph.
The size of the clique is k by definition. To show it is independent in the cycle graph, consider any two distinct vertices in the clique. Since they form an edge in the graph, by definition they cannot be adjacent in the cycle graph.
refine ⟨hs.card_eq, ?_, ?_⟩ · intro x hx y hy hxy hxy' exact ((hs.isClique hx hy hxy).2.1) hxy'
Any k-clique intersects each family member A j in at most one vertex.
To show |S ∩ A j| ≤ 1, it suffices by Finset.card_le_one.mpr to show that any two vertices x, y in the intersection are equal. Assuming for contradiction that x ≠ y, they form an edge in the clique, which by definition means no family member contains both x and y. But x, y ∈ A j by Finset.mem_inter.mp, giving a contradiction.
uses
Finset.card_le_one.mpr,Finset.mem_inter.mp· intro j apply Finset.card_le_one.mpr intro x hx y hy by_contra hxy have hxS := (Finset.mem_inter.mp hx).1 have hyS := (Finset.mem_inter.mp hy).1 have hxA := (Finset.mem_inter.mp hx).2 have hyA := (Finset.mem_inter.mp hy).2 exact ((hs.isClique hxS hyS hxy).2.2 j) ⟨hxA,hyA⟩
There exists a graph with the specified adjacency whose k-cliques satisfy the avoidance properties.
We instantiate the existential with Inbox777Avoid.graph. Its adjacency matches the definition by reflexivity, and its cliques satisfy the required properties by Inbox777Avoid.clique_avoids.
uses
Inbox777Avoid.graph,Inbox777Avoid.clique_avoidsexact ⟨Inbox777Avoid.graph m q A, (by intros; rfl), Inbox777Avoid.clique_avoids m q A k⟩
Finset.card_le_one.mpr- A finite set has at most one element if and only if any two of its elements are equal.
Finset.mem_inter.mp- If an element belongs to the intersection of two finite sets, it belongs to both sets.
Inbox777Avoid.graph- The graph on cycle vertices whose edges are noncycle pairs not contained in any family member.
Inbox777Avoid.clique_avoids- Every k-clique in Inbox777Avoid.graph has size k, is independent in the cycle graph, and intersects each family member in at most one vertex.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
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.
namespace Inbox777Avoidvariable (m q : ℕ) (A : Fin q → Finset (Fin m))def graph : SimpleGraph (Fin m) where Adj x y := x ≠ y ∧ ¬(SimpleGraph.cycleGraph m).Adj x y ∧ ∀ j, ¬(x ∈ A j ∧ y ∈ A j) symm := ⟨by intro x y h refine ⟨h.1.symm, ?_, ?_⟩ · intro hxy; exact h.2.1 hxy.symm · intro j hxy; exact h.2.2 j ⟨hxy.2, hxy.1⟩⟩ loopless := ⟨by intro x h; exact h.1 rfl⟩theorem clique_avoids (k : ℕ) (S : Finset (Fin m)) (hs : (graph m q A).IsNClique k S) : S.card = k ∧ (SimpleGraph.cycleGraph m).IsIndepSet (↑S : Set (Fin m)) ∧ ∀ j, (S ∩ A j).card ≤ 1 := by refine ⟨hs.card_eq, ?_, ?_⟩ · intro x hx y hy hxy hxy' exact ((hs.isClique hx hy hxy).2.1) hxy' · intro j apply Finset.card_le_one.mpr intro x hx y hy by_contra hxy have hxS := (Finset.mem_inter.mp hx).1 have hyS := (Finset.mem_inter.mp hy).1 have hxA := (Finset.mem_inter.mp hx).2 have hyA := (Finset.mem_inter.mp hy).2 exact ((hs.isClique hxS hyS hxy).2.2 j) ⟨hxA,hyA⟩end Inbox777Avoidtheorem op_193_avoidance_graph (m q k : ℕ) (A : Fin q → Finset (Fin m)) : ∃ G : SimpleGraph (Fin m), (∀ x y, G.Adj x y ↔ x ≠ y ∧ ¬ (SimpleGraph.cycleGraph m).Adj x y ∧ ∀ j, ¬(x ∈ A j ∧ y ∈ A j)) ∧ ∀ S : Finset (Fin m), G.IsNClique k S → S.card = k ∧ (SimpleGraph.cycleGraph m).IsIndepSet (↑S : Set (Fin m)) ∧ ∀ j, (S ∩ A j).card ≤ 1 := by exact ⟨Inbox777Avoid.graph m q A, (by intros; rfl), Inbox777Avoid.clique_avoids m q A k⟩