didericis
1749f702cf
Introduces the maximal_planar_graph_edge_flipping paper, motivating flip-symmetry as a structural restriction on minimum-order five-chromatic counterexamples, and reports an exhaustive census showing |F_n|/|T_n| decays geometrically (factor ~1/2 per step from n=10 to n=14). The census driver lives in flip_symmetric_census.py. Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
74 lines
3.0 KiB
Python
74 lines
3.0 KiB
Python
"""Census of flip-symmetric maximal planar graphs.
|
|
|
|
A maximal planar graph G is *flip-symmetric* if some admissible edge uv
|
|
satisfies G^flip(uv) ~= G, where flip(uv) replaces uv with wx (the third
|
|
vertices of the two triangular faces incident to uv), and admissible
|
|
means wx is not already an edge of G.
|
|
"""
|
|
from typing import Iterator
|
|
from sage.all import Graph, graphs # type: ignore[attr-defined] # pylint: disable=no-name-in-module
|
|
|
|
|
|
def triangular_face_pairs(g: Graph) -> dict[frozenset, tuple]:
|
|
"""For each edge of g (a triangulation), return the two third-vertices
|
|
of its incident triangular faces, keyed by frozenset({u, v})."""
|
|
g_emb = g.copy()
|
|
if not g_emb.is_planar(set_embedding=True):
|
|
raise ValueError("graph is not planar")
|
|
pairs: dict[frozenset, list] = {}
|
|
for face in g_emb.faces():
|
|
if len(face) != 3:
|
|
raise ValueError("graph is not a triangulation")
|
|
a, b, c = face[0][0], face[1][0], face[2][0]
|
|
for u, v, third in [(a, b, c), (b, c, a), (c, a, b)]:
|
|
pairs.setdefault(frozenset((u, v)), []).append(third)
|
|
return {k: tuple(v) for k, v in pairs.items()}
|
|
|
|
|
|
def is_flip_symmetric(g: Graph) -> bool:
|
|
"""Return True iff g admits some admissible flip uv -> wx with G^flip ~= G."""
|
|
pairs = triangular_face_pairs(g)
|
|
for u, v in g.edges(labels=False):
|
|
thirds = pairs.get(frozenset((u, v)))
|
|
if thirds is None or len(thirds) != 2:
|
|
continue
|
|
w, x = thirds
|
|
if g.has_edge(w, x):
|
|
continue
|
|
flipped = g.copy()
|
|
flipped.delete_edge(u, v)
|
|
flipped.add_edge(w, x)
|
|
if g.is_isomorphic(flipped):
|
|
return True
|
|
return False
|
|
|
|
|
|
def census(min_order: int, max_order: int, minimum_degree: int | None = None) -> None:
|
|
"""Enumerate every maximal planar graph of order in [min_order, max_order]
|
|
(optionally restricted by minimum_degree) and print counts and density
|
|
of flip-symmetric graphs at each order."""
|
|
for n in range(min_order, max_order + 1):
|
|
kwargs = {"minimum_connectivity": 3, "maximum_face_size": 3}
|
|
if minimum_degree is not None:
|
|
kwargs["minimum_degree"] = minimum_degree
|
|
total = 0
|
|
flip_sym = 0
|
|
gen: Iterator[Graph] = graphs.planar_graphs(n, **kwargs)
|
|
for g in gen:
|
|
total += 1
|
|
if is_flip_symmetric(g):
|
|
flip_sym += 1
|
|
if total % 1000 == 0:
|
|
print(f" order {n}: {total} checked, {flip_sym} flip-symmetric")
|
|
density = (flip_sym / total) if total else 0.0
|
|
tag = f" (min_degree {minimum_degree})" if minimum_degree is not None else ""
|
|
print(f"n={n}{tag}: total={total} flip_symmetric={flip_sym} density={density:.6f}")
|
|
|
|
|
|
if __name__ == "__main__":
|
|
import sys
|
|
max_order = int(sys.argv[1]) if len(sys.argv) > 1 else 12
|
|
min_order = int(sys.argv[2]) if len(sys.argv) > 2 else 4
|
|
min_deg = int(sys.argv[3]) if len(sys.argv) > 3 else None
|
|
census(min_order, max_order, minimum_degree=min_deg)
|