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

"""For colourings whose K_b Heawood pattern is "almost constant" (flip
count <= some threshold), identify *which* vertex carries the
minority Heawood. Is it consistently a "named" structural vertex
(v_n, A_{i+1}, A_{i+3}, A_{i+4}, ...) or distributed across
non-structural vertices?

If the minority vertex is always a specific structural vertex, that
gives a *local* structural proof:  the embedding + chord-apex forces
the minority's Heawood to differ from the majority's, ruling out
constancy on V(K_b).

Run with: sage experiments/check_minority_location.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)

from check_conj_final_scaled import (
    apply_reduction,
    proper_3_edge_colorings,
    matches_chord_apex_kempe,
    trace_kempe_cycle,
    edge_idx,
    kempe_cycle_set,
)
from check_heawood_on_kempe import dual_of, heawood_numbers, vertices_of_kempe


def named_vertices(named, v_n=9999):
    def other(fs, v):
        return next(iter(fs - {v}))
    A_i  = other(named['side_0'], v_n)
    A_i1 = other(named['spike'],  v_n)
    A_i2 = other(named['side_1'], v_n)
    A_i3, A_i4 = sorted(named['merged'])
    return {'v_n': v_n, 'A_i': A_i, 'A_i1': A_i1, 'A_i2': A_i2,
            'A_i3': A_i3, 'A_i4': A_i4}


def test_one(D, flip_threshold=4):
    D.is_planar(set_embedding=True)
    n_col = 0
    # For colourings with K_b flip count <= flip_threshold, record what
    # type of vertex carries the minority h on V(K_b).
    minority_types = {}     # 'v_n', 'A_i1', etc., or 'other' -> count
    # Also: number of minority vertices on V(K_b) in these colourings.
    minority_size_dist = {}
    for face in D.faces():
        if len(face) != 5: continue
        for i_red in range(5):
            res = apply_reduction(D, face, i_red, 9999)
            if res is None: continue
            H = res['H']; named = res['named']
            H.is_planar(set_embedding=True)
            edges, colorings = proper_3_edge_colorings(H)
            cand = [c for c in colorings
                    if matches_chord_apex_kempe(edges, c, named)]
            named_v = named_vertices(named, 9999)
            inv_named = {v: name for name, v in named_v.items()}
            for col in cand:
                n_col += 1
                try:
                    h = heawood_numbers(H, edges, col)
                except RuntimeError:
                    continue
                merged_idx = edge_idx(edges, named['merged'])
                a = col[merged_idx]
                bs = [c for c in range(3) if c != a]
                kc_b = kempe_cycle_set(edges, col, merged_idx, (a, bs[0]))
                V_b = vertices_of_kempe(edges, kc_b)
                # Compute flip count on K_b walk
                walk = trace_kempe_cycle(edges, col, merged_idx, (a, bs[0]))
                L = len(walk)
                h_seq = [h[walk[k][1]] for k in range(L)]
                flips = sum(1 for k in range(L) if h_seq[k] != h_seq[(k+1) % L])
                if flips > flip_threshold: continue
                # Identify minority on V(K_b)
                plus = sum(1 for v in V_b if h[v] == 1)
                minus = sum(1 for v in V_b if h[v] == -1)
                if plus == minus: continue  # tie -- skip
                minority_h = 1 if plus < minus else -1
                minority_vs = [v for v in V_b if h[v] == minority_h]
                minority_size_dist[len(minority_vs)] = \
                    minority_size_dist.get(len(minority_vs), 0) + 1
                for v in minority_vs:
                    name = inv_named.get(v, 'other')
                    minority_types[name] = minority_types.get(name, 0) + 1
    return n_col, minority_types, minority_size_dist


def main(max_n=18, time_budget_per_n=1800, flip_threshold=4):
    print(f"Minority-vertex location on K_b for low-flip colourings, "
          f"n in [12, {max_n}], flip <= {flip_threshold}\n")
    grand_col = 0
    grand_types = {}
    grand_sizes = {}
    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_col_n = 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)
            D = dual_of(G)
            ni, mt, ms = test_one(D, flip_threshold)
            n_col_n += ni
            for k, v in mt.items(): grand_types[k] = grand_types.get(k, 0) + v
            for k, v in ms.items(): grand_sizes[k] = grand_sizes.get(k, 0) + v
        elapsed = time.time() - start
        print(f"n={n}: {n_col_n} col., [{elapsed:.0f}s]")
        sys.stdout.flush()
        grand_col += n_col_n
    print()
    print("=" * 78)
    print(f"Grand totals: colourings with K_b flip-count <= {flip_threshold} "
          f"({grand_col} total colourings)")
    total_min = sum(grand_sizes.values())
    print(f"\n  Minority-set size distribution on V(K_b) "
          f"(of low-flip colourings): {sorted(grand_sizes.items())}")
    print(f"\n  Type breakdown of minority vertices "
          f"(over {sum(grand_types.values())} minority-vertex incidences):")
    for name in ['v_n', 'A_i', 'A_i1', 'A_i2', 'A_i3', 'A_i4', 'other']:
        c = grand_types.get(name, 0)
        pct = 100 * c / max(1, sum(grand_types.values()))
        print(f"    {name:>5}: {c}  ({pct:.2f}%)")


if __name__ == '__main__':
    main()