math-research/papers/face_monochromatic_pairs/experiments/audit_tight_coverage.py

"""Audit: how many (G, v, i) triples are covered by the
structurally-TIGHT subset of the partial proof (dropping the
n_i = 6 case which has a gap in sub-case (ii.B) of the flank-covering
lemma)?

Tight cases:
  (a') n_i = 5 (= F_flank length 4, P adjacent to both A_i and A_{i+1});
  (b') n_{i+1} = 5 (symmetric);
  (c)  n_{i+2} = n_{i+4} = 5 (= F_outer length 7, both intermediates
       adjacent to A_{i+3}, A_{i+4} ∈ V(K_b) ∩ V(K_c) via merged).

Loose cases (the proof formally claims these but has a gap on
sub-case (ii.B)):
  (a) n_i = 6
  (b) n_{i+1} = 6

This script reports per (G, v, i) whether tight-only coverage suffices.

Run with: sage experiments/audit_tight_coverage.py
"""
import os
import sys
import time

from sage.all import Graph
from sage.graphs.graph_generators import graphs

HERE = os.path.dirname(os.path.abspath(__file__))
sys.path.insert(0, HERE)


def main(max_n=20, time_budget_per_n=1200):
    print("Audit of structurally TIGHT coverage of the deciding-face\n"
          "partial proof. Restricts to cases (a' = n_i = 5),\n"
          "(b' = n_{i+1} = 5), (c = n_{i+2} = n_{i+4} = 5);\n"
          "drops the (a)/(b) cases at n_k = 6 due to a gap in\n"
          "Lemma 'Flank covering, n_i = 6' (sub-case ii.B).\n")
    print(f"n_G in [12, {max_n}]\n")

    grand_triples = 0
    grand_loose_covered = 0     # by full partial proof (with gap)
    grand_tight_covered = 0     # by tight-only subset
    grand_loose_uncovered = 0   # empirical bad triples
    grand_loose_not_tight = 0   # loose-covered but not tight (= n_i = 6 reliance)
    grand_examples = []

    for n in range(12, max_n + 1):
        start = time.time()
        try:
            triangulations = list(graphs.triangulations(n, minimum_degree=5))
        except Exception as ex:
            print(f"n={n}: cannot enumerate ({ex})")
            continue
        n_t = 0; n_loose = 0; n_tight = 0; n_diff = 0
        for tri_idx, G in enumerate(triangulations):
            if time.time() - start > time_budget_per_n:
                print(f"  n={n}: timeout at tri {tri_idx}/{len(triangulations)}")
                break
            G.is_planar(set_embedding=True)
            emb = G.get_embedding()
            for v in G.vertex_iterator():
                if G.degree(v) != 5: continue
                cyc = [G.degree(u) for u in emb[v]]
                for i in range(5):
                    n_t += 1
                    n_i = cyc[(i + 1) % 5]
                    n_ip1 = cyc[(i + 2) % 5]
                    n_ip2 = cyc[(i + 3) % 5]
                    n_ip3 = cyc[(i + 4) % 5]
                    n_ip4 = cyc[(i + 5) % 5]
                    loose_a = (n_i in (5, 6))
                    loose_b = (n_ip1 in (5, 6))
                    case_c = (n_ip2 == 5 and n_ip4 == 5)
                    tight_a = (n_i == 5)
                    tight_b = (n_ip1 == 5)
                    loose = loose_a or loose_b or case_c
                    tight = tight_a or tight_b or case_c
                    if loose: n_loose += 1
                    if tight: n_tight += 1
                    if loose and not tight: n_diff += 1
                    if loose and not tight and len(grand_examples) < 10:
                        grand_examples.append({
                            'n_G': n, 'tri_idx': tri_idx, 'v': v, 'i': i,
                            'cyc': cyc,
                            'n_tuple': (n_i, n_ip1, n_ip2, n_ip3, n_ip4),
                        })
        elapsed = time.time() - start
        print(f"n={n}: {n_t} triples, loose-covered={n_loose} "
              f"({100*n_loose/max(n_t,1):.1f}%), "
              f"tight-only={n_tight} ({100*n_tight/max(n_t,1):.1f}%); "
              f"loose-not-tight={n_diff} [{elapsed:.0f}s]")
        sys.stdout.flush()
        grand_triples += n_t
        grand_loose_covered += n_loose
        grand_tight_covered += n_tight
        grand_loose_not_tight += n_diff

    grand_loose_uncovered = grand_triples - grand_loose_covered
    grand_tight_uncovered = grand_triples - grand_tight_covered
    print()
    print("=" * 70)
    print(f"Grand totals across n_G in [12, {max_n}]:")
    print(f"  (G, v, i) triples:                       {grand_triples}")
    print(f"  loose-covered (full partial proof):      "
          f"{grand_loose_covered} "
          f"({100*grand_loose_covered/max(grand_triples,1):.2f}%)")
    print(f"  loose-uncovered (= empirical bad):       "
          f"{grand_loose_uncovered} "
          f"({100*grand_loose_uncovered/max(grand_triples,1):.2f}%)")
    print(f"  tight-covered (drop n_i = 6 gap-case):   "
          f"{grand_tight_covered} "
          f"({100*grand_tight_covered/max(grand_triples,1):.2f}%)")
    print(f"  tight-uncovered (needs n_i = 6 lemma):   "
          f"{grand_tight_uncovered} "
          f"({100*grand_tight_uncovered/max(grand_triples,1):.2f}%)")
    print(f"  loose-not-tight (needs n_i = 6 lemma):   "
          f"{grand_loose_not_tight}")
    if grand_examples:
        print()
        print("  Sample triples that need the n_i = 6 lemma "
              "(NOT covered by tight subset):")
        for ex in grand_examples[:10]:
            print(f"    n={ex['n_G']}, tri#{ex['tri_idx']}, "
                  f"v={ex['v']}, i={ex['i']}: cyc={ex['cyc']}, "
                  f"(n_i,n_{{i+1}},n_{{i+2}},n_{{i+3}},n_{{i+4}})={ex['n_tuple']}")


if __name__ == '__main__':
    main()