/-
Copyright 2025 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import FormalConjecturesUtilSnake in the box
References:
@[expose] public sectionuniverse unamespace SnakeInBoxopen SimpleGraph symmDiff
A graph on the power set of Fin n, where two sets are adjacent if they differ by a single element.
def Hypercube (n : ℕ) : SimpleGraph (Finset (Fin n)) := fromRel fun a b => (a ∆ b).card = 1
A subgraph G' is a 'snake' of length k in graph G if it is an induced path of length k.
def IsSnakeInGraphOfLength {V : Type u} [DecidableEq V] (G : SimpleGraph V) (G' : Subgraph G)
(k : ℕ) : Prop :=
G'.IsInduced ∧ ∃ u v : V, ∃ (P : G.Walk u v), P.IsPath ∧ G' = P.toSubgraph ∧ P.length = k
The length of the longest induced path (or 'snake') in a graph G.
noncomputable def LongestSnakeInGraph {V : Type u} [DecidableEq V] (G : SimpleGraph V) : ℕ :=
sSup {k | ∃ (S : Subgraph G), IsSnakeInGraphOfLength G S k}
The length of the longest snake for the Hypercube n graph.
noncomputable def LongestSnakeInTheBox (n : ℕ) : ℕ := LongestSnakeInGraph <| Hypercube n
A subgraph G' is a 'coil' of length k in graph G if it is an induced cycle of length k.
def IsCoilInGraphOfLength {V : Type u} [DecidableEq V] (G : SimpleGraph V) (G' : Subgraph G)
(k : ℕ) : Prop :=
G'.IsInduced ∧ ∃ u : V, ∃ (P : G.Walk u u), P.IsCycle ∧ G' = P.toSubgraph ∧ P.length = k
The length of the longest induced cycle (or 'coil') in a graph G.
noncomputable def LongestCoilInGraph {V : Type u} [DecidableEq V] (G : SimpleGraph V) : ℕ :=
sSup {k | ∃ (S : Subgraph G), IsCoilInGraphOfLength G S k}
The length of the longest coil for the Hypercube n graph.
noncomputable def LongestCoilInTheBox (n : ℕ) : ℕ := LongestCoilInGraph <| Hypercube nThe longest snake in the $0$-dimensional cube, i.e. the cube consisting of one point, is zero, since there only is one induced path and it is of length zero.
@[category test, AMS 5]
theorem snake_zero_zero : LongestSnakeInTheBox 0 = 0 := ⊢ LongestSnakeInTheBox 0 = 0
simp_rw ⊢ LongestSnakeInTheBox 0 = 0⊢ LongestSnakeInGraph (Hypercube 0) = 0 ⊢ sSup {k | ∃ S, IsSnakeInGraphOfLength (Hypercube 0) S k} = 0 ⊢ sSup {k | ∃ S, S.IsInduced ∧ ∃ u v P, P.IsPath ∧ S = P.toSubgraph ∧ P.length = k} = 0 ⊢ sSup {k | ∃ S, S.IsInduced ∧ ∃ u v P, P.IsPath ∧ S = P.toSubgraph ∧ P.length = k} = 0]
⊢ {k | ∃ S, S.IsInduced ∧ ∃ u v P, P.IsPath ∧ S = P.toSubgraph ∧ P.length = k} = {0}
n:ℕ⊢ n ∈ {k | ∃ S, S.IsInduced ∧ ∃ u v P, P.IsPath ∧ S = P.toSubgraph ∧ P.length = k} ↔ n ∈ {0}
n:ℕx✝:n ∈ {k | ∃ S, S.IsInduced ∧ ∃ u v P, P.IsPath ∧ S = P.toSubgraph ∧ P.length = k}S:(fromRel fun a b ↦ (a ∆ b).card = 1).Subgraphh_induced:S.IsInducedu:Finset (Fin 0)v:Finset (Fin 0)P:(fromRel fun a b ↦ (a ∆ b).card = 1).Walk u vhPath:P.IsPathhSupport:S = P.toSubgraphhLength:P.length = n⊢ n ∈ {0}n:ℕ⊢ n ∈ {0} → n ∈ {k | ∃ S, S.IsInduced ∧ ∃ u v P, P.IsPath ∧ S = P.toSubgraph ∧ P.length = k}
n:ℕx✝:n ∈ {k | ∃ S, S.IsInduced ∧ ∃ u v P, P.IsPath ∧ S = P.toSubgraph ∧ P.length = k}S:(fromRel fun a b ↦ (a ∆ b).card = 1).Subgraphh_induced:S.IsInducedu:Finset (Fin 0)v:Finset (Fin 0)P:(fromRel fun a b ↦ (a ∆ b).card = 1).Walk u vhPath:P.IsPathhSupport:S = P.toSubgraphhLength:P.length = n⊢ n ∈ {0} n:ℕx✝:n ∈ {k | ∃ S, S.IsInduced ∧ ∃ u v P, P.IsPath ∧ S = P.toSubgraph ∧ P.length = k}S:(fromRel fun a b ↦ (a ∆ b).card = 1).Subgraphh_induced:S.IsInducedu:Finset (Fin 0)v:Finset (Fin 0)P:(fromRel fun a b ↦ (a ∆ b).card = 1).Walk u vhPath:P.IsPathhSupport:S = P.toSubgraphhLength:P.length = nhu:u = ∅⊢ n ∈ {0}
n:ℕx✝:n ∈ {k | ∃ S, S.IsInduced ∧ ∃ u v P, P.IsPath ∧ S = P.toSubgraph ∧ P.length = k}S:(fromRel fun a b ↦ (a ∆ b).card = 1).Subgraphh_induced:S.IsInducedu:Finset (Fin 0)v:Finset (Fin 0)P:(fromRel fun a b ↦ (a ∆ b).card = 1).Walk u vhPath:P.IsPathhSupport:S = P.toSubgraphhLength:P.length = nhu:u = ∅hv:v = ∅⊢ n ∈ {0}
n:ℕx✝:n ∈ {k | ∃ S, S.IsInduced ∧ ∃ u v P, P.IsPath ∧ S = P.toSubgraph ∧ P.length = k}S:(fromRel fun a b ↦ (a ∆ b).card = 1).Subgraphh_induced:S.IsInducedP:(fromRel fun a b ↦ (a ∆ b).card = 1).Walk ∅ ∅hPath:P.IsPathhSupport:S = P.toSubgraphhLength:P.length = n⊢ n ∈ {0}
All goals completed! 🐙
n:ℕ⊢ n ∈ {0} → n ∈ {k | ∃ S, S.IsInduced ∧ ∃ u v P, P.IsPath ∧ S = P.toSubgraph ∧ P.length = k} ⊢ 0 ∈ {k | ∃ S, S.IsInduced ∧ ∃ u v P, P.IsPath ∧ S = P.toSubgraph ∧ P.length = k}
use ⊤, ⊢ ⊤.IsInduced All goals completed! 🐙, ∅, ∅, .nil
All goals completed! 🐙The longest coil in the $0$-dimensional cube is zero, since it contains no cycles.
@[category test, AMS 5]
theorem coil_zero_zero : LongestCoilInTheBox 0 = 0 := ⊢ LongestCoilInTheBox 0 = 0
simp_rw ⊢ LongestCoilInTheBox 0 = 0⊢ LongestCoilInGraph (Hypercube 0) = 0 ⊢ sSup {k | ∃ S, IsCoilInGraphOfLength (Hypercube 0) S k} = 0 ⊢ sSup {k | ∃ S, S.IsInduced ∧ ∃ u P, P.IsCycle ∧ S = P.toSubgraph ∧ P.length = k} = 0 ⊢ sSup {k | ∃ S, S.IsInduced ∧ ∃ u P, P.IsCycle ∧ S = P.toSubgraph ∧ P.length = k} = 0]
⊢ {k | ∃ S, S.IsInduced ∧ ∃ u P, P.IsCycle ∧ S = P.toSubgraph ∧ P.length = k} = ∅
n:ℕ⊢ n ∈ {k | ∃ S, S.IsInduced ∧ ∃ u P, P.IsCycle ∧ S = P.toSubgraph ∧ P.length = k} ↔ n ∈ ∅
n:ℕ⊢ ∀ (x : (fromRel fun a b ↦ (a ∆ b).card = 1).Subgraph),
x.IsInduced →
∀ (x_1 : Finset (Fin 0)) (x_2 : (fromRel fun a b ↦ (a ∆ b).card = 1).Walk x_1 x_1),
x_2.IsCycle → x = x_2.toSubgraph → ¬x_2.length = n
n:ℕS:(fromRel fun a b ↦ (a ∆ b).card = 1).Subgrapha✝²:S.IsInducedu:Finset (Fin 0)P:(fromRel fun a b ↦ (a ∆ b).card = 1).Walk u uhCycle:P.IsCyclea✝¹:S = P.toSubgrapha✝:P.length = n⊢ False
cases P with
n:ℕS:(fromRel fun a b ↦ (a ∆ b).card = 1).Subgrapha✝²:S.IsInducedu:Finset (Fin 0)hCycle:Walk.nil.IsCyclea✝¹:S = Walk.nil.toSubgrapha✝:Walk.nil.length = n⊢ False All goals completed! 🐙
n:ℕS:(fromRel fun a b ↦ (a ∆ b).card = 1).Subgrapha✝²:S.IsInducedu:Finset (Fin 0)v:Finset (Fin 0)h:(fromRel fun a b ↦ (a ∆ b).card = 1).Adj u vp✝:(fromRel fun a b ↦ (a ∆ b).card = 1).Walk v uhCycle:(Walk.cons h p✝).IsCyclea✝¹:S = (Walk.cons h p✝).toSubgrapha✝:(Walk.cons h p✝).length = n⊢ False
n:ℕS:(fromRel fun a b ↦ (a ∆ b).card = 1).Subgrapha✝²:S.IsInducedu:Finset (Fin 0)v:Finset (Fin 0)h:(fromRel fun a b ↦ (a ∆ b).card = 1).Adj u vp✝:(fromRel fun a b ↦ (a ∆ b).card = 1).Walk v uhCycle:(Walk.cons h p✝).IsCyclea✝¹:S = (Walk.cons h p✝).toSubgrapha✝:(Walk.cons h p✝).length = nhu:u = ∅⊢ False
n:ℕS:(fromRel fun a b ↦ (a ∆ b).card = 1).Subgrapha✝²:S.IsInducedu:Finset (Fin 0)v:Finset (Fin 0)h:(fromRel fun a b ↦ (a ∆ b).card = 1).Adj u vp✝:(fromRel fun a b ↦ (a ∆ b).card = 1).Walk v uhCycle:(Walk.cons h p✝).IsCyclea✝¹:S = (Walk.cons h p✝).toSubgrapha✝:(Walk.cons h p✝).length = nhu:u = ∅hv:v = ∅⊢ False
n:ℕS:(fromRel fun a b ↦ (a ∆ b).card = 1).Subgrapha✝²:S.IsInducedh:(fromRel fun a b ↦ (a ∆ b).card = 1).Adj ∅ ∅p✝:(fromRel fun a b ↦ (a ∆ b).card = 1).Walk ∅ ∅hCycle:(Walk.cons h p✝).IsCyclea✝¹:S = (Walk.cons h p✝).toSubgrapha✝:(Walk.cons h p✝).length = n⊢ False
All goals completed! 🐙open ListThe maximum length for the snake-in-the-box problem is known for dimensions zero through eight; it is $0, 1, 2, 4, 7, 13, 26, 50, 98$.
@[category research solved, AMS 5]
theorem snake_small_dimensions :
map LongestSnakeInTheBox (range 9) = [0, 1, 2, 4, 7, 13, 26, 50, 98] := ⊢ map LongestSnakeInTheBox (range 9) = [0, 1, 2, 4, 7, 13, 26, 50, 98]
All goals completed! 🐙The maximum length for the coil-in-the-box problem is known for dimensions zero through eight; it is $0, 0, 4, 6, 8, 14, 26, 48, 96$.
@[category research solved, AMS 5]
theorem coil_small_dimensions :
map LongestCoilInTheBox (range 9) = [0, 0, 4, 6, 8, 14, 26, 48, 96] := ⊢ map LongestCoilInTheBox (range 9) = [0, 0, 4, 6, 8, 14, 26, 48, 96]
All goals completed! 🐙def snake_dim_nine.answer : ℕ := sorryFor dimension $9$, the length of the longest snake in the box is not known. This is currently the smallest dimension where this question is open.
@[category research open, question value, AMS 5]
theorem snake_dim_nine : LongestSnakeInTheBox 9 = snake_dim_nine.answer := ⊢ LongestSnakeInTheBox 9 = snake_dim_nine.answer
All goals completed! 🐙The best length found so far for dimension nine is 190.
@[category research solved, AMS 5]
theorem snake_dim_nine_lower_bound : 190 ≤ LongestSnakeInTheBox 9 := ⊢ 190 ≤ LongestSnakeInTheBox 9
All goals completed! 🐙For $n \geq 1$, an upper bound on the length of the longest snake in a box is $2^{n-1}$ (see [DK67, Theorem B]).
@[category research solved, AMS 5]
theorem snake_upper_bound (n : ℕ) (hn : 1 ≤ n) : LongestSnakeInTheBox n ≤ 2 ^ (n - 1) := n:ℕhn:1 ≤ n⊢ LongestSnakeInTheBox n ≤ 2 ^ (n - 1)
All goals completed! 🐙For $n \geq 2$, an upper bound on the maximal length of the longest coil in a box is given by $$ 1 + 2^{n-1}\frac{6n}{6n + \frac{1}{6\sqrt{6}}n^{\frac 1 2} - 7} $$ (see [Ze97]). The case $n = 1$ is excluded since the right-hand side is negative there.
@[category research solved, AMS 5]
theorem coil_upper_bound (n : ℕ) (hn : 2 ≤ n) : LongestCoilInTheBox n
≤ (1 : ℝ) + 2 ^ (n - 1) * (6 * n) / (6 * n + (1 / (6 * √6) * √n) - 7) := n:ℕhn:2 ≤ n⊢ ↑(LongestCoilInTheBox n) ≤ 1 + 2 ^ (n - 1) * (6 * ↑n) / (6 * ↑n + 1 / (6 * √6) * √↑n - 7)
All goals completed! 🐙end SnakeInBox