Ridge-visible access in the two-leftover regime
ProvedHirsch.ridge_visible_neighbor_of_n_le_two_d_add_threeLet be a bounded simple H-polytope with inequalities. Simplicity means every vertex is tight on exactly rows. Let be a describing row that is tight at two distinct vertices . Then every vertex of is at graph distance at most from the ridge-visible set of row .
Ridge-visible means is tight on row , or tight on some other row that meets row inside . The cases (distance ), and (distance at most ) are already proved. The new layer is .
If is not ridge-visible, its tight rows are far from , and contribute at least near rows. That leaves at most two leftover far inequalities . The one-collision case (every leave-one ray from enters the same leftover) is the simplex argument of : is that simplex, all generators are strictly slack on , contradiction.
When the two leftovers are mixed, the far rows are exactly the rows . Non-ridge-visible vertices have tight sets that are -subsets of these rows (Johnson graph ). Vertices that share tight rows bound an edge. Consequently every far vertex is at graph distance at most from .
A linear height uniquely minimized at (dual-basis cone) has a minimizer among the finitely many ridge-visible vertices. A decreasing neighbour of cannot be ridge-visible, hence is far, hence is at distance from . The path has length at most and ends in the ridge-visible set.
for simple bounded H-polytopes, on any row attained at two vertices.
This is the two-leftover layer of the ridge-visible recurrence. It does not treat , and it does not by itself close the polynomial Hirsch conjecture.
Formalization Note Boundedness guarantees leave-one rays hit a new inequality. Dual-basis coordinates uniquely minimize the height at . Extreme points inject into -subsets of the rows, so the ridge-visible set is finite. Sharing tight rows produces an equality-face edge.
import Mathlib import Definitions.Def_Hirsch_model open scoped RealInnerProductSpace open Set Hirsch
namespace Hirsch
theorem ridge_visible_neighbor_of_n_le_two_d_add_three
{d n : ℕ} (hn : n ≤ 2 * d + 3)
(a : Fin n → EuclideanSpace ℝ (Fin d)) (b : Fin n → ℝ)
(hbd : Bornology.IsBounded (Hpoly a b))
(hsimple : ∀ x ∈ extremePoints ℝ (Hpoly a b),
(Finset.univ.filter (fun j : Fin n => ⟪a j, x⟫ = b j)).card = d)
(i : Fin n)
{z₁ z₂ : EuclideanSpace ℝ (Fin d)}
(hz₁ : z₁ ∈ extremePoints ℝ (Hpoly a b))
(hz₂ : z₂ ∈ extremePoints ℝ (Hpoly a b))
(hne : z₁ ≠ z₂)
(hzi₁ : ⟪a i, z₁⟫ = b i)
(hzi₂ : ⟪a i, z₂⟫ = b i)
(u : EuclideanSpace ℝ (Fin d))
(hu : u ∈ extremePoints ℝ (Hpoly a b)) :
(⟪a i, u⟫ = b i ∨
∃ r : Fin n, r ≠ i ∧ ⟪a r, u⟫ = b r ∧
∃ x ∈ Hpoly a b, ⟪a i, x⟫ = b i ∧ ⟪a r, x⟫ = b r) ∨
(∃ w, w ∈ extremePoints ℝ (Hpoly a b) ∧ Adj (Hpoly a b) u w ∧
(⟪a i, w⟫ = b i ∨
∃ r : Fin n, r ≠ i ∧ ⟪a r, w⟫ = b r ∧
∃ x ∈ Hpoly a b, ⟪a i, x⟫ = b i ∧ ⟪a r, x⟫ = b r)) ∨
(∃ w v, w ∈ extremePoints ℝ (Hpoly a b) ∧ v ∈ extremePoints ℝ (Hpoly a b) ∧
Adj (Hpoly a b) u w ∧ Adj (Hpoly a b) w v ∧
(⟪a i, v⟫ = b i ∨
∃ r : Fin n, r ≠ i ∧ ⟪a r, v⟫ = b r ∧
∃ x ∈ Hpoly a b, ⟪a i, x⟫ = b i ∧ ⟪a r, x⟫ = b r)) ∨
∃ w v z, w ∈ extremePoints ℝ (Hpoly a b) ∧
v ∈ extremePoints ℝ (Hpoly a b) ∧ z ∈ extremePoints ℝ (Hpoly a b) ∧
Adj (Hpoly a b) u w ∧ Adj (Hpoly a b) w v ∧ Adj (Hpoly a b) v z ∧
(⟪a i, z⟫ = b i ∨
∃ r : Fin n, r ≠ i ∧ ⟪a r, z⟫ = b r ∧
∃ x ∈ Hpoly a b, ⟪a i, x⟫ = b i ∧ ⟪a r, x⟫ = b r) := by sorry
end Hirsch