The Kepler Conjecture 2025, 47 - Tame Graphs

An n-cycle is a finite set C with cardinality n, and a cyclic permutation operator s on C. Write v → s(v, C) ∀ v ∈ C with s(v, C) being the successor v in C. A cycle is an n-cycle for some natural number n. By abuse of language, we identify C with the cycle. The natural number n is the length of the cycle. The nonempty finite set of cycles (faces) G of length ≥ 3, with vertices of G as the elements, and unordered pair of vertices {v, w} s.t. one element is the successor of the other in some face is an "edge". v, w are "adjacent". THe set G is a plane graph if

• for some face F, s(v, F) = w ⇒ there is a unique face in G with s(v, G) = w.
• ∀ v: F → s'(F, v) is a cyclic permutation of the set of faces containing v
• Euler's formula holds relating the number of vertices V
• The set of vertices is connected.

Define len as the length function on faces. Faces of length 3 are "triangles", length 4 are "quadrilaterals" etc. Define tri(v) the number of triangles containing a vertex v. A face of length 5 are "exceptional faces". Two plane graphs are properly isomorphic if there is a bijection of vertices (and faces). For each plane graph there is an opposite plane graph G^op obtained by reversing the cyclic order of vertices in each face. The degree of a vertex is the number of faces it belongs to. An n-circuit in G is a cycle C in the vertex-set of G, s.t. for all v ∈ C, it forms an edge in G with its successor.

The type of a vertex is defined to be a triple of nonnegative integers (p, q, r) where p is the number of triangles in the vertex, q is the number of quadrilaterals, and r the number of exceptional faces. Abbreviate from the right. A set of V vertices is a "separated set" of vertices if

• ∀ v ∈ V ∃ an exceptional face F with v ∈ F
• No two vertices in V are adjacent,
• or lie in a common quadrilateral
• Each vertex in V has degree 5

The weight assignment of a plane graph G is w: G → ℝ, taking values in the set of nonnegative real numbers if

• the face F has length n, so w(F) ≥ d(n)
• if v has type (p, q) ⇒ Σ_{F: v∈F} w(F) ≥ b(p, q)
• for a set of vertices of type (5, 0), if cardinality of V is k ≤ 4, then Σ_{F: V∩F≠∅}w(F) ≥ 0.55k
• If V is a separated set of vertices, then Σ_{F: V∩F ≠ ∅}(w(F) - d(len(F))) ≥ Σ_v∈V a(tri(v))
• Σ_Fw(F) is the "total weight" of w

A plane graph is tame if

• the length of each face is between 3 and 8
• Every 3-circuit is a face or a face's opposite
• Every 4-circuit surrounds a tame 4-circuit
• The degree of every vertex is between 2 and 6
• If a vertex is contained in an exceptional face, its degree is at most 5
• Σ_Fc(len(F)) ≥ 8
• There is an admissable weight assignment of total weight less than tgt
• There are never two adjacent vertices of type (4, 0)