hypercube_max_coil_disjoint_squares_pos
For n ≥ 13, if S is a maximum coil in Q_n with degree count y_0 > 0, then the number F_5 of squares disjoint from S is strictly positive.
Statement
open scoped Classical in theorem hypercube_max_coil_disjoint_squares_pos (n : ℕ) (hn : 13 ≤ n) (S : Finset (Fin n → Bool)) (hS : is_max_hypercube_coil n S) (hy0 : 0 < hypercube_degree_count n S 0) : 0 < hypercube_disjoint_squares_count n S
- Source
- arXiv:2610.36461 Corollary 3
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- is_max_hypercube_coilA coil S in Q_n is a maximum coil if its cardinality is at least that of any other coil in Q_n.
- hypercube_degree_countThe degree count y_m is the number of vertices x in the complement of S having exactly m neighbors in S.
- hypercube_disjoint_squares_countThe count F_5 is the number of squares in Q_n that contain no vertex of S.
- is_hypercube_squareA subset of 4 vertices in the hypercube Q_n is a square if its induced subgraph is isomorphic to the 4-cycle C_4.
- hypercube_coilA subset S of vertices in the hypercube Q_n is a coil if it has size at least 4 and its induced subgraph is isomorphic to a cycle graph of…
- simple_graph_hypercubeThe hypercube graph Q_n on vertex set Fin n → Bool, where two vertices are adjacent if and only if they differ at exactly one coordinate.
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Read back from the Lean
For any natural number $n \ge 13$ and any subset $S$ of vertices of the $n$-dimensional hypercube $\{0, 1\}^n$, if $S$ is a maximum-cardinality coil (that is, $S$ induces a cycle graph of length at least 4 in the hypercube graph, and no other coil in the hypercube has strictly greater cardinality than $S$) and there is at least one vertex in $\{0, 1\}^n \setminus S$ that has zero neighbors in $S$, then there exists at least one 4-cycle (square) in the hypercube that is disjoint from $S$ (meaning the count of such disjoint squares is strictly positive).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To show that any maximum coil S in Q_n (with n ≥ 13) having y_0 > 0 has at least one disjoint square, we argue by contradiction and suppose no square is disjoint from S. The condition y_0 > 0 gives a vertex x with no neighbors in S. For any two distinct coordinates i and j, the 4-cycle formed by x, x^{{i}}, x^{{j}}, and x^{{i,j}} must intersect S; since the first three vertices lie outside S, every double flip x^{{i,j}} must belong to S. Picking two distinct coordinates 0 and 1, the vertex x^{{0,1}} ∈ S has a neighbor z in S, which must be a single flip along a third coordinate k ∉ {0, 1}. But then z has three distinct neighbors in S—namely the double flips on {0,1}, {1,k}, and {0,k}—contradicting the fact that every vertex in a cycle has at most two neighbors.
Flipping the same coordinate twice is the identity operation
At coordinate i the boolean is negated twice, which simplifies to the original value, while all other coordinates are unchanged.
uses
Function.update_applyfunext t; simp only [hmc363_flip, Function.update_apply]; split_ifs <;> simp_all
Flipping two coordinates commutes
If the two indices are equal, the operations are identical. If they are distinct, evaluating at any coordinate t affects only bit i or bit j independently, so the order of flipping does not matter.
uses
Function.update_apply,Ne.symmby_cases hij : i = j · subst hij; rfl funext t simp only [hmc363_flip, Function.update_apply] by_cases hti : t = i · subst hti; simp [hij] · by_cases htj : t = j · subst htj; simp [hti, Ne.symm hij] · simp [hti, htj]
Two vertices in Q_n are adjacent if and only if they differ in exactly one coordinate
By definition, Q_n is the graph from the relation of differing at a unique index. Since differing at an index is symmetric, the relation holds symmetrically between distinct vertices.
uses
SimpleGraph.fromRel_adj,Or.inlunfold simple_graph_hypercube rw [SimpleGraph.fromRel_adj] constructor · rintro ⟨hne, h | h⟩ · exact ⟨hne, h⟩ · obtain ⟨k, hk, hu⟩ := h exact ⟨hne, k, fun e => hk e.symm, fun t ht => hu t (fun e => ht e.symm)⟩ · rintro ⟨hne, h⟩; exact ⟨hne, Or.inl h⟩
Flipping a single coordinate produces an adjacent vertex
The vertex x and flip(x, i) differ at coordinate i and agree everywhere else, which matches the characterization of hypercube adjacency.
uses
hmc363_adj_iff,congrFun,Function.update_applyrw [hmc363_adj_iff] refine ⟨fun e => ?_, i, by simp [hmc363_flip], fun t ht => ?_⟩ · have := congrFun e i; simp [hmc363_flip] at this · by_contra hti; exact ht (by simp [hmc363_flip, Function.update_apply, hti])
Flipping two distinct coordinates produces a non-adjacent vertex
The vertex x and the double flip flip(flip(x, i), j) differ at both coordinate i and coordinate j. Since i ≠ j, they cannot differ at a unique coordinate, so they are not adjacent.
uses
hmc363_adj_iff,Function.update_apply,Ne.symmrw [hmc363_adj_iff] rintro ⟨-, k, -, hu⟩ have hi := hu i (by simp [hmc363_flip, Function.update_apply, hij]) have hj := hu j (by simp [hmc363_flip, Function.update_apply, hij, Ne.symm hij]) exact hij (hi.trans hj.symm)
Every neighbor of x in Q_n is obtained by flipping a unique coordinate
Adjacency implies x and y differ at a unique coordinate k. Thus y(k) is the negation of x(k) while agreeing with x at all other coordinates, so y = flip(x, k).
uses
hmc363_adj_iff,Function.update_self,Function.update_apply,if_false,Ne.symmrw [hmc363_adj_iff] at h obtain ⟨-, k, hk, hu⟩ := h refine ⟨k, funext fun t => ?_⟩ by_cases htk : t = k · subst htk; simp only [hmc363_flip, Function.update_self] cases hx : x t <;> cases hy : y t <;> simp_all · simp only [hmc363_flip, Function.update_apply, htk, if_false] by_contra hne; exact htk (hu t (Ne.symm hne))
Every vertex in a cycle graph of length at least 3 has a neighbor, and has at most two neighbors
Via the graph isomorphism f to a standard cycle graph, neighbors of f(v) are f(v) - 1 and f(v) + 1. Thus f^{-1}(f(v) + 1) is a neighbor of v. By the pigeonhole principle, any three neighbors must send at least two vertices to the same neighbor in the cycle, which forces those two vertices to be equal by injectivity.
uses
SimpleGraph.cycleGraph_neighborSet,RelIso.apply_symm_apply,SimpleGraph.cycleGraph_adj,Or.inl,Or.inrhave key : ∀ a, H.Adj v a → f a = f v - 1 ∨ f a = f v + 1 := by intro a ha have h' : (SimpleGraph.cycleGraph (m + 1 + 2)).Adj (f v) (f a) := f.map_adj_iff.mpr ha have : f a ∈ (SimpleGraph.cycleGraph (m + 1 + 2)).neighborSet (f v) := h' rw [SimpleGraph.cycleGraph_neighborSet] at this simpa using this refine ⟨⟨f.symm (f v + 1), ?_⟩, fun a b c ha hb hc => ?_⟩ · rw [← f.map_adj_iff, RelIso.apply_symm_apply] show (SimpleGraph.cycleGraph (m + 1 + 2)).Adj _ _ rw [SimpleGraph.cycleGraph_adj]; right; simp · rcases key a ha with h1 | h1 <;> rcases key b hb with h2 | h2 <;> rcases key c hc with h3 | h3 all_goals first | exact Or.inl (f.injective (h1.trans h2.symm)) | exact Or.inr (Or.inl (f.injective (h1.trans h3.symm))) | exact Or.inr (Or.inr (f.injective (h2.trans h3.symm)))
Every vertex in a coil S has a neighbor in S, and no vertex has three pairwise distinct neighbors in S
A coil S induces a cycle graph of size at least 4. Transferring the cycle neighbor property to S shows that every vertex has a neighbor in S and cannot have three pairwise distinct neighbors in S.
uses
hmc363_cycle_nbrs,Or.inl,congrArg,Subtype.val,Or.inrobtain ⟨h4, ⟨f⟩⟩ := hcoil have hm : S.card = (S.card - 3) + 3 := by omega rw [hm] at f obtain ⟨⟨⟨y, hy⟩, hxy⟩, h2⟩ := hmc363_cycle_nbrs _ _ f ⟨x, hx⟩ refine ⟨⟨y, hy, hxy⟩, fun a b c ha hb hc hxa hxb hxc => ?_⟩ rcases h2 ⟨a, ha⟩ ⟨b, hb⟩ ⟨c, hc⟩ hxa hxb hxc with h | h | h · exact Or.inl (congrArg Subtype.val h) · exact Or.inr (Or.inl (congrArg Subtype.val h)) · exact Or.inr (Or.inr (congrArg Subtype.val h))
Flipping distinct coordinates produces distinct vertices
Evaluating flip(z, p) and flip(z, q) at coordinate p shows that the former flips z(p) while the latter keeps z(p), so they cannot be equal.
uses
congrFun,Function.update_applyintro h have := congrFun h p simp [hmc363_flip, Function.update_apply, hpq] at this
The four vertices formed by flipping coordinates i and j form an induced 4-cycle in Q_n
Consecutive pairs differ in one coordinate and are adjacent, while opposite pairs differ in two distinct coordinates and are not adjacent. Exhaustive verification across all pairs in Fin 4 confirms it is an induced C_4.
uses
hmc363_adj_flip,hmc363_flip_comm,hmc363_not_adj_double,hmc363_flip_fliphave h01 := hmc363_adj_flip v i have h12 := hmc363_adj_flip (hmc363_flip v i) j have h23 : (simple_graph_hypercube n).Adj (hmc363_flip (hmc363_flip v i) j) (hmc363_flip v j) := by rw [hmc363_flip_comm]; exact (hmc363_adj_flip (hmc363_flip v j) i).symm have h30 := (hmc363_adj_flip v j).symm have h02 := hmc363_not_adj_double v hij have h13 : ¬ (simple_graph_hypercube n).Adj (hmc363_flip v i) (hmc363_flip v j) := by have := hmc363_not_adj_double (hmc363_flip v i) hij rwa [hmc363_flip_flip] at this have h10 := h01.symm have h21 := h12.symm have h32 := h23.symm have h03 := h30.symm have h20 : ¬ (simple_graph_hypercube n).Adj _ _ := fun h => h02 h.symm have h31 : ¬ (simple_graph_hypercube n).Adj _ _ := fun h => h13 h.symm fin_cases a <;> fin_cases b <;> simp [hmc363_pt, SimpleGraph.cycleGraph_adj', h01, h12, h23, h30, h02, h13, h10, h21, h32, h03, h20, h31] <;> decide
Assume for contradiction that there are no squares disjoint from S
We assume the negation of the goal, namely that the count of disjoint squares is not strictly positive.
by_contra hFThere exists a vertex x not in S with no neighbors in S
Since the degree count y_0 is strictly positive, there exists at least one vertex x outside S whose hypercube neighborhood is completely disjoint from S.
uses
Finset.card_pos,Finset.mem_filter,Finset.mem_sdiff,Finset.card_eq_zero,Finset.eq_empty_iff_forall_notMemunfold hypercube_degree_count at hy0 obtain ⟨x, hx⟩ := Finset.card_pos.mp hy0 rw [Finset.mem_filter, Finset.mem_sdiff] at hx have hxS : x ∉ S := hx.1.2 have hN : ∀ y, (simple_graph_hypercube n).Adj x y → y ∉ S := by intro y hy hyS have h0 := Finset.card_eq_zero.mp hx.2 rw [Finset.eq_empty_iff_forall_notMem] at h0 exact h0 y (by simp [hy, hyS])
For any two distinct coordinates i and j, flipping both coordinates of x gives a vertex in S
If flipping coordinates i and j gave a vertex outside S, then the four vertices x, flip(x, i), flip(flip(x, i), j), and flip(x, j) would form an induced 4-cycle in Q_n disjoint from S (since x has no neighbors in S and the double flip is assumed outside S), contradicting the assumption that no such squares exist.
uses
Function.Injective,congrFun,Ne.symm,Function.update_apply,Finset.card_pos,Finset.mem_filter,Finset.mem_powerset,Finset.subset_univ,true_and,Finset.card_image_of_injective,Equiv.ofBijective,congrArg,Subtype.val,Finset.coe_image,Finset.coe_univ,Set.image_univ,Set.mem_range,hmc363_pt_adj_iff,Finset.disjoint_left,Finset.mem_image,hmc363_adj_fliphave step2 : ∀ i j : Fin n, i ≠ j → hmc363_flip (hmc363_flip x i) j ∈ S := by intro i j hij by_contra hnot apply hF have hinj : Function.Injective (hmc363_pt x i j) := by intro a b hab have hi := congrFun hab i have hj := congrFun hab j fin_cases a <;> fin_cases b <;> simp [hmc363_pt, hmc363_flip, Function.update_apply, hij, Ne.symm hij] at hi hj ⊢ unfold hypercube_disjoint_squares_count apply Finset.card_pos.mpr refine ⟨Finset.univ.image (hmc363_pt x i j), ?_⟩ simp only [Finset.mem_filter, Finset.mem_powerset, Finset.subset_univ, true_and] refine ⟨⟨?_, ?_⟩, ?_⟩ · rw [Finset.card_image_of_injective _ hinj]; simp · let e : Fin 4 ≃ ↥((Finset.univ.image (hmc363_pt x i j) : Finset _) : Set (Fin n → Bool)) := Equiv.ofBijective (fun k => ⟨hmc363_pt x i j k, by simp⟩) ⟨fun a b hab => hinj (congrArg Subtype.val hab), fun ⟨y, hy⟩ => by simp only [Finset.coe_image, Finset.coe_univ, Set.image_univ, Set.mem_range] at hy obtain ⟨k, rfl⟩ := hy exact ⟨k, rfl⟩⟩ exact ⟨(⟨e, fun {a b} => hmc363_pt_adj_iff x hij a b⟩ : SimpleGraph.cycleGraph 4 ≃g (simple_graph_hypercube n).induce _).symm⟩ · rw [Finset.disjoint_left] intro a ha obtain ⟨k, -, rfl⟩ := Finset.mem_image.mp ha fin_cases k · exact hxS · exact hN _ (hmc363_adj_flip x i) · exact hnot · exact hN _ (hmc363_adj_flip x j)
A neighbor z of the double flip along coordinates 0 and 1 in S must differ in a third coordinate k distinct from 0 and 1
Since n ≥ 13, coordinates 0 and 1 are distinct. The double flip y at 0 and 1 lies in S, and since S is a coil, y has a neighbor z in S, which must be obtained by flipping some coordinate k of y. If k were 0 or 1, z would be a single flip of x, which cannot belong to S because x has no neighbors in S. Hence k is distinct from both 0 and 1.
uses
hmc363_coil_nbrs,hmc363_eq_flip_of_adj,hmc363_adj_flip,hmc363_flip_comm,hmc363_flip_fliphave hi0 : (⟨0, by omega⟩ : Fin n) ≠ ⟨1, by omega⟩ := by simp set i : Fin n := ⟨0, by omega⟩ set j : Fin n := ⟨1, by omega⟩ obtain ⟨z, hzS, hyz⟩ := (hmc363_coil_nbrs hS.1 (step2 i j hi0)).1 obtain ⟨k, rfl⟩ := hmc363_eq_flip_of_adj hyz have hki : k ≠ i := by rintro rfl apply hN _ (hmc363_adj_flip x j) rwa [hmc363_flip_comm (hmc363_flip x i) j i, hmc363_flip_flip] at hzS have hkj : k ≠ j := by rintro rfl apply hN _ (hmc363_adj_flip x i) rwa [hmc363_flip_flip] at hzS
The vertex z has three distinct neighbors in S, contradicting that S is a cycle
The vertex z = flip(flip(flip(x, 0), 1), k) has three neighbors obtained by flipping k, 0, or 1, which evaluate to the double flips at {0, 1}, {1, k}, and {0, k}. By the double-flip property, all three neighbors lie in S. However, every vertex in a coil has at most two neighbors in S, so two of these three neighbors must coincide. But since 0, 1, and k are pairwise distinct, flipping different coordinates produces distinct vertices, giving a contradiction in all three cases.
uses
hmc363_flip_flip,hmc363_flip_comm,Ne.symm,hmc363_coil_nbrs,hmc363_adj_flip,hmc363_flip_neset z := hmc363_flip (hmc363_flip (hmc363_flip x i) j) k with hz have ha : hmc363_flip z k ∈ S := by rw [hz, hmc363_flip_flip]; exact step2 i j hi0 have hb : hmc363_flip z i ∈ S := by rw [hz, hmc363_flip_comm (hmc363_flip (hmc363_flip x i) j) k i, hmc363_flip_comm (hmc363_flip x i) j i, hmc363_flip_flip] exact step2 j k (Ne.symm hkj) have hc : hmc363_flip z j ∈ S := by rw [hz, hmc363_flip_comm (hmc363_flip (hmc363_flip x i) j) k j, hmc363_flip_flip] exact step2 i k (Ne.symm hki) rcases (hmc363_coil_nbrs hS.1 hzS).2 _ _ _ ha hb hc (hmc363_adj_flip z k) (hmc363_adj_flip z i) (hmc363_adj_flip z j) with h | h | h · exact hmc363_flip_ne z hki h · exact hmc363_flip_ne z hkj h · exact hmc363_flip_ne z hi0 h
Function.update_apply- Evaluation of Function.update f a' b at a equals b if a = a' and f(a) otherwise
Ne.symm- Inequality is symmetric: if a ≠ b then b ≠ a
SimpleGraph.fromRel_adj- Two vertices v and w are adjacent in SimpleGraph.fromRel r iff v ≠ w and either r v w or r w v holds
Or.inl- A disjunction a ∨ b holds if its left disjunct a holds
hmc363_adj_iff- Two vertices in the hypercube Q_n are adjacent if and only if they are distinct and differ in exactly one coordinate
congrFun- Equal functions take equal values at any argument
Function.update_self- Updating a function at argument a with value v and then evaluating at a yields v
if_false- An if-then-else whose condition is False simplifies to the else branch
SimpleGraph.cycleGraph_neighborSet- The neighbor set of a vertex v in the cycle graph C_{n+2} consists of v - 1 and v + 1
RelIso.apply_symm_apply- Applying a relational isomorphism to the image of an element under its inverse yields the element
SimpleGraph.cycleGraph_adj- Two vertices u and v are adjacent in the cycle graph C_{n+2} iff u - v = 1 or v - u = 1
Or.inr- A disjunction a ∨ b holds if its right disjunct b holds
hmc363_cycle_nbrs- Every vertex in a cycle graph of length at least 3 has a neighbor, and any three neighbors must contain a duplicate
congrArg- A function applied to equal arguments yields equal results
Subtype.val- The projection from a subtype element to its underlying value
hmc363_adj_flip- A vertex in Q_n is adjacent to the vertex obtained by flipping any single coordinate
hmc363_flip_comm- Flipping coordinate i then coordinate j gives the same vertex as flipping j then i
hmc363_not_adj_double- Flipping two distinct coordinates of a vertex produces a vertex not adjacent to the original vertex
hmc363_flip_flip- Flipping the same coordinate twice returns the original vertex
Finset.card_pos- A finite set has positive cardinality if and only if it is nonempty
Finset.mem_filter- An element belongs to a filtered finset iff it belongs to the base set and satisfies the predicate
Finset.mem_sdiff- An element belongs to the difference s \\ t iff it belongs to s and does not belong to t
Finset.card_eq_zero- A finite set has cardinality zero if and only if it is empty
Finset.eq_empty_iff_forall_notMem- A finite set is empty if and only if none of its elements belong to it
Function.Injective- A function is injective if distinct arguments have distinct values
Finset.mem_powerset- A finset belongs to the powerset of s iff it is a subset of s
Finset.subset_univ- Every finset of elements of a finite type is a subset of the universal finset
true_and- The conjunction of True and p is equivalent to p
Finset.card_image_of_injective- The image of a finset under an injective map has the same cardinality as the finset
Equiv.ofBijective- A bijective function gives an equivalence (bijection) between types
Finset.coe_image- Coercing the image of a finset to a set equals the set image of the coerced finset
Finset.coe_univ- Coercing the universal finset to a set yields the universal set
Set.image_univ- The image of the universal set under a function is the range of the function
Set.mem_range- An element is in the range of f iff it equals f(k) for some k
hmc363_pt_adj_iff- The four vertices generated by flipping coordinates i and j form an induced 4-cycle in Q_n
Finset.disjoint_left- Two finsets are disjoint iff no element of the first belongs to the second
Finset.mem_image- An element is in the image of a finset under f iff it equals f(x) for some x in the finset
hmc363_coil_nbrs- Every vertex in a coil S has a neighbor in S and cannot have three pairwise distinct neighbors in S
hmc363_eq_flip_of_adj- If two vertices in Q_n are adjacent, one is obtained from the other by flipping a coordinate
hmc363_flip_ne- Flipping two distinct coordinates of a vertex yields two distinct vertices
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.
def hmc363_flip {n : ℕ} (x : Fin n → Bool) (i : Fin n) : Fin n → Bool := Function.update x i (!x i)theorem hmc363_flip_flip {n : ℕ} (x : Fin n → Bool) (i : Fin n) : hmc363_flip (hmc363_flip x i) i = x := by funext t; simp only [hmc363_flip, Function.update_apply]; split_ifs <;> simp_alltheorem hmc363_flip_comm {n : ℕ} (x : Fin n → Bool) (i j : Fin n) : hmc363_flip (hmc363_flip x i) j = hmc363_flip (hmc363_flip x j) i := by by_cases hij : i = j · subst hij; rfl funext t simp only [hmc363_flip, Function.update_apply] by_cases hti : t = i · subst hti; simp [hij] · by_cases htj : t = j · subst htj; simp [hti, Ne.symm hij] · simp [hti, htj]theorem hmc363_adj_iff {n : ℕ} (x y : Fin n → Bool) : (simple_graph_hypercube n).Adj x y ↔ x ≠ y ∧ ∃! k, x k ≠ y k := by unfold simple_graph_hypercube rw [SimpleGraph.fromRel_adj] constructor · rintro ⟨hne, h | h⟩ · exact ⟨hne, h⟩ · obtain ⟨k, hk, hu⟩ := h exact ⟨hne, k, fun e => hk e.symm, fun t ht => hu t (fun e => ht e.symm)⟩ · rintro ⟨hne, h⟩; exact ⟨hne, Or.inl h⟩theorem hmc363_adj_flip {n : ℕ} (x : Fin n → Bool) (i : Fin n) : (simple_graph_hypercube n).Adj x (hmc363_flip x i) := by rw [hmc363_adj_iff] refine ⟨fun e => ?_, i, by simp [hmc363_flip], fun t ht => ?_⟩ · have := congrFun e i; simp [hmc363_flip] at this · by_contra hti; exact ht (by simp [hmc363_flip, Function.update_apply, hti])theorem hmc363_not_adj_double {n : ℕ} (x : Fin n → Bool) {i j : Fin n} (hij : i ≠ j) : ¬ (simple_graph_hypercube n).Adj x (hmc363_flip (hmc363_flip x i) j) := by rw [hmc363_adj_iff] rintro ⟨-, k, -, hu⟩ have hi := hu i (by simp [hmc363_flip, Function.update_apply, hij]) have hj := hu j (by simp [hmc363_flip, Function.update_apply, hij, Ne.symm hij]) exact hij (hi.trans hj.symm)theorem hmc363_eq_flip_of_adj {n : ℕ} {x y : Fin n → Bool} (h : (simple_graph_hypercube n).Adj x y) : ∃ k, y = hmc363_flip x k := by rw [hmc363_adj_iff] at h obtain ⟨-, k, hk, hu⟩ := h refine ⟨k, funext fun t => ?_⟩ by_cases htk : t = k · subst htk; simp only [hmc363_flip, Function.update_self] cases hx : x t <;> cases hy : y t <;> simp_all · simp only [hmc363_flip, Function.update_apply, htk, if_false] by_contra hne; exact htk (hu t (Ne.symm hne))/-- A vertex of a cycle has a neighbour, and no three distinct neighbours. -/theorem hmc363_cycle_nbrs {α : Type*} (H : SimpleGraph α) (m : ℕ) (f : H ≃g SimpleGraph.cycleGraph (m + 3)) (v : α) : (∃ w, H.Adj v w) ∧ ∀ a b c, H.Adj v a → H.Adj v b → H.Adj v c → a = b ∨ a = c ∨ b = c := by have key : ∀ a, H.Adj v a → f a = f v - 1 ∨ f a = f v + 1 := by intro a ha have h' : (SimpleGraph.cycleGraph (m + 1 + 2)).Adj (f v) (f a) := f.map_adj_iff.mpr ha have : f a ∈ (SimpleGraph.cycleGraph (m + 1 + 2)).neighborSet (f v) := h' rw [SimpleGraph.cycleGraph_neighborSet] at this simpa using this refine ⟨⟨f.symm (f v + 1), ?_⟩, fun a b c ha hb hc => ?_⟩ · rw [← f.map_adj_iff, RelIso.apply_symm_apply] show (SimpleGraph.cycleGraph (m + 1 + 2)).Adj _ _ rw [SimpleGraph.cycleGraph_adj]; right; simp · rcases key a ha with h1 | h1 <;> rcases key b hb with h2 | h2 <;> rcases key c hc with h3 | h3 all_goals first | exact Or.inl (f.injective (h1.trans h2.symm)) | exact Or.inr (Or.inl (f.injective (h1.trans h3.symm))) | exact Or.inr (Or.inr (f.injective (h2.trans h3.symm)))theorem hmc363_coil_nbrs {n : ℕ} {S : Finset (Fin n → Bool)} (hcoil : hypercube_coil n S) {x : Fin n → Bool} (hx : x ∈ S) : (∃ y ∈ S, (simple_graph_hypercube n).Adj x y) ∧ ∀ a b c, a ∈ S → b ∈ S → c ∈ S → (simple_graph_hypercube n).Adj x a → (simple_graph_hypercube n).Adj x b → (simple_graph_hypercube n).Adj x c → a = b ∨ a = c ∨ b = c := by obtain ⟨h4, ⟨f⟩⟩ := hcoil have hm : S.card = (S.card - 3) + 3 := by omega rw [hm] at f obtain ⟨⟨⟨y, hy⟩, hxy⟩, h2⟩ := hmc363_cycle_nbrs _ _ f ⟨x, hx⟩ refine ⟨⟨y, hy, hxy⟩, fun a b c ha hb hc hxa hxb hxc => ?_⟩ rcases h2 ⟨a, ha⟩ ⟨b, hb⟩ ⟨c, hc⟩ hxa hxb hxc with h | h | h · exact Or.inl (congrArg Subtype.val h) · exact Or.inr (Or.inl (congrArg Subtype.val h)) · exact Or.inr (Or.inr (congrArg Subtype.val h))theorem hmc363_flip_ne {n : ℕ} (z : Fin n → Bool) {p q : Fin n} (hpq : p ≠ q) : hmc363_flip z p ≠ hmc363_flip z q := by intro h have := congrFun h p simp [hmc363_flip, Function.update_apply, hpq] at thisdef hmc363_pt {n : ℕ} (v : Fin n → Bool) (i j : Fin n) : Fin 4 → (Fin n → Bool) := ![v, hmc363_flip v i, hmc363_flip (hmc363_flip v i) j, hmc363_flip v j]theorem hmc363_pt_adj_iff {n : ℕ} (v : Fin n → Bool) {i j : Fin n} (hij : i ≠ j) (a b : Fin 4) : (simple_graph_hypercube n).Adj (hmc363_pt v i j a) (hmc363_pt v i j b) ↔ (SimpleGraph.cycleGraph 4).Adj a b := by have h01 := hmc363_adj_flip v i have h12 := hmc363_adj_flip (hmc363_flip v i) j have h23 : (simple_graph_hypercube n).Adj (hmc363_flip (hmc363_flip v i) j) (hmc363_flip v j) := by rw [hmc363_flip_comm]; exact (hmc363_adj_flip (hmc363_flip v j) i).symm have h30 := (hmc363_adj_flip v j).symm have h02 := hmc363_not_adj_double v hij have h13 : ¬ (simple_graph_hypercube n).Adj (hmc363_flip v i) (hmc363_flip v j) := by have := hmc363_not_adj_double (hmc363_flip v i) hij rwa [hmc363_flip_flip] at this have h10 := h01.symm have h21 := h12.symm have h32 := h23.symm have h03 := h30.symm have h20 : ¬ (simple_graph_hypercube n).Adj _ _ := fun h => h02 h.symm have h31 : ¬ (simple_graph_hypercube n).Adj _ _ := fun h => h13 h.symm fin_cases a <;> fin_cases b <;> simp [hmc363_pt, SimpleGraph.cycleGraph_adj', h01, h12, h23, h30, h02, h13, h10, h21, h32, h03, h20, h31] <;> decideopen scoped Classical in/-- A maximum coil with y_0 > 0 has at least one disjoint square. -/theorem hypercube_max_coil_disjoint_squares_pos (n : ℕ) (hn : 13 ≤ n) (S : Finset (Fin n → Bool)) (hS : is_max_hypercube_coil n S) (hy0 : 0 < hypercube_degree_count n S 0) : 0 < hypercube_disjoint_squares_count n S := by by_contra hF unfold hypercube_degree_count at hy0 obtain ⟨x, hx⟩ := Finset.card_pos.mp hy0 rw [Finset.mem_filter, Finset.mem_sdiff] at hx have hxS : x ∉ S := hx.1.2 have hN : ∀ y, (simple_graph_hypercube n).Adj x y → y ∉ S := by intro y hy hyS have h0 := Finset.card_eq_zero.mp hx.2 rw [Finset.eq_empty_iff_forall_notMem] at h0 exact h0 y (by simp [hy, hyS]) have step2 : ∀ i j : Fin n, i ≠ j → hmc363_flip (hmc363_flip x i) j ∈ S := by intro i j hij by_contra hnot apply hF have hinj : Function.Injective (hmc363_pt x i j) := by intro a b hab have hi := congrFun hab i have hj := congrFun hab j fin_cases a <;> fin_cases b <;> simp [hmc363_pt, hmc363_flip, Function.update_apply, hij, Ne.symm hij] at hi hj ⊢ unfold hypercube_disjoint_squares_count apply Finset.card_pos.mpr refine ⟨Finset.univ.image (hmc363_pt x i j), ?_⟩ simp only [Finset.mem_filter, Finset.mem_powerset, Finset.subset_univ, true_and] refine ⟨⟨?_, ?_⟩, ?_⟩ · rw [Finset.card_image_of_injective _ hinj]; simp · let e : Fin 4 ≃ ↥((Finset.univ.image (hmc363_pt x i j) : Finset _) : Set (Fin n → Bool)) := Equiv.ofBijective (fun k => ⟨hmc363_pt x i j k, by simp⟩) ⟨fun a b hab => hinj (congrArg Subtype.val hab), fun ⟨y, hy⟩ => by simp only [Finset.coe_image, Finset.coe_univ, Set.image_univ, Set.mem_range] at hy obtain ⟨k, rfl⟩ := hy exact ⟨k, rfl⟩⟩ exact ⟨(⟨e, fun {a b} => hmc363_pt_adj_iff x hij a b⟩ : SimpleGraph.cycleGraph 4 ≃g (simple_graph_hypercube n).induce _).symm⟩ · rw [Finset.disjoint_left] intro a ha obtain ⟨k, -, rfl⟩ := Finset.mem_image.mp ha fin_cases k · exact hxS · exact hN _ (hmc363_adj_flip x i) · exact hnot · exact hN _ (hmc363_adj_flip x j) have hi0 : (⟨0, by omega⟩ : Fin n) ≠ ⟨1, by omega⟩ := by simp set i : Fin n := ⟨0, by omega⟩ set j : Fin n := ⟨1, by omega⟩ obtain ⟨z, hzS, hyz⟩ := (hmc363_coil_nbrs hS.1 (step2 i j hi0)).1 obtain ⟨k, rfl⟩ := hmc363_eq_flip_of_adj hyz have hki : k ≠ i := by rintro rfl apply hN _ (hmc363_adj_flip x j) rwa [hmc363_flip_comm (hmc363_flip x i) j i, hmc363_flip_flip] at hzS have hkj : k ≠ j := by rintro rfl apply hN _ (hmc363_adj_flip x i) rwa [hmc363_flip_flip] at hzS set z := hmc363_flip (hmc363_flip (hmc363_flip x i) j) k with hz have ha : hmc363_flip z k ∈ S := by rw [hz, hmc363_flip_flip]; exact step2 i j hi0 have hb : hmc363_flip z i ∈ S := by rw [hz, hmc363_flip_comm (hmc363_flip (hmc363_flip x i) j) k i, hmc363_flip_comm (hmc363_flip x i) j i, hmc363_flip_flip] exact step2 j k (Ne.symm hkj) have hc : hmc363_flip z j ∈ S := by rw [hz, hmc363_flip_comm (hmc363_flip (hmc363_flip x i) j) k j, hmc363_flip_flip] exact step2 i k (Ne.symm hki) rcases (hmc363_coil_nbrs hS.1 hzS).2 _ _ _ ha hb hc (hmc363_adj_flip z k) (hmc363_adj_flip z i) (hmc363_adj_flip z j) with h | h | h · exact hmc363_flip_ne z hki h · exact hmc363_flip_ne z hkj h · exact hmc363_flip_ne z hi0 h