didericis
1a71658349
Findings at n=9 (50 triangulations, orbits fully exhaustible): - 36 bridge-derived, 14 NOT bridge-derived. So bridge-derived is a PROPER subclass of derived (49 derived at n=9). All 14 non-bridge graphs are intertwining trees -- as are all 50, necessarily: intertwining tree <=> dual Hamiltonian, and the smallest non-Hamiltonian 3-connected cubic planar graph has 38 vertices, i.e. dual on 2n-4=38 => n=21. Hence every triangulation with n<=20 is an intertwining tree, and the disjunction "bridge-derived OR intertwining" is trivially true below n=21. The 4 Holton-McKay duals are the first non-intertwining triangulations. - Static parity-subgraph invariants (Betti numbers, component counts, cross-edge count, existence of an all-forest partition) do NOT separate bridge-derived from non-bridge-derived -- both classes realize beta=0 partitions and identical ranges. Bridge-derivability is dynamical, not a simple static invariant; no easy obstruction. - Side lemma: every valid parity partition of an n-vertex triangulation has exactly 2n-4 cross edges (intra-edges = n-2). Holds for all n=9 graphs. Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
72 lines
2.9 KiB
Python
72 lines
2.9 KiB
Python
"""Dump candidate invariants for bridge-derived vs non-bridge-derived
|
|
triangulations at small n, to spot a separating (necessary) condition."""
|
|
import sys
|
|
import os
|
|
sys.path.insert(0, '/Users/didericis/Code/math-research/papers/'
|
|
'level_resolutions_of_maximal_planar_graphs/experiments')
|
|
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
|
|
import networkx as nx
|
|
from triangulation_gen import enumerate_all_triangulations
|
|
from exhaustive_bridge import valid_parity_partitions
|
|
from small_n_probe import is_bridge_derived
|
|
|
|
|
|
def per_partition_stats(G):
|
|
"""For each valid partition return dict of invariants."""
|
|
rows = []
|
|
for labels in valid_parity_partitions(G):
|
|
ev = [v for v in G.nodes() if labels[v] == 0]
|
|
od = [v for v in G.nodes() if labels[v] == 1]
|
|
SE, SO = G.subgraph(ev), G.subgraph(od)
|
|
ce = nx.number_connected_components(SE)
|
|
co = nx.number_connected_components(SO)
|
|
be = SE.number_of_edges() - len(ev) + ce
|
|
bo = SO.number_of_edges() - len(od) + co
|
|
rows.append(dict(be=be, bo=bo, ee=SE.number_of_edges(),
|
|
eo=SO.number_of_edges(), ce=ce, co=co,
|
|
ne=len(ev), no=len(od)))
|
|
return rows
|
|
|
|
|
|
def summarize(G):
|
|
rows = per_partition_stats(G)
|
|
tb = [r['be'] + r['bo'] for r in rows]
|
|
cross = [G.number_of_edges() - r['ee'] - r['eo'] for r in rows]
|
|
# does some partition make BOTH parity subgraphs forests (be=bo=0)?
|
|
forests = any(r['be'] == 0 and r['bo'] == 0 for r in rows)
|
|
return dict(min_tb=min(tb), max_tb=max(tb), nparts=len(rows),
|
|
min_cross=min(cross), max_cross=max(cross),
|
|
both_forest=forests)
|
|
|
|
|
|
def main(n):
|
|
tris = enumerate_all_triangulations(n)
|
|
print(f'n={n}: {len(tris)} triangulations', flush=True)
|
|
bd_stats, nb_stats = [], []
|
|
for G in tris:
|
|
s = summarize(G)
|
|
if is_bridge_derived(G):
|
|
bd_stats.append(s)
|
|
else:
|
|
nb_stats.append(s)
|
|
|
|
def col(stats, key):
|
|
return sorted(set(s[key] for s in stats))
|
|
|
|
for key in ['min_tb', 'max_tb', 'min_cross', 'max_cross']:
|
|
print(f' {key:10s} bridge={col(bd_stats,key)} '
|
|
f'NONbridge={col(nb_stats,key)}', flush=True)
|
|
print(f' both_forest exists? bridge={sorted(set(s["both_forest"] for s in bd_stats))}'
|
|
f' NONbridge={sorted(set(s["both_forest"] for s in nb_stats))}', flush=True)
|
|
# separator check: any min_tb value unique to one class?
|
|
bd_min = set(s['min_tb'] for s in bd_stats)
|
|
nb_min = set(s['min_tb'] for s in nb_stats)
|
|
print(f' min_tb only-in-bridge: {bd_min - nb_min}; '
|
|
f'only-in-NONbridge: {nb_min - bd_min}', flush=True)
|
|
print(f' both_forest: bridge {sum(s["both_forest"] for s in bd_stats)}/{len(bd_stats)}, '
|
|
f'NONbridge {sum(s["both_forest"] for s in nb_stats)}/{len(nb_stats)}', flush=True)
|
|
|
|
|
|
if __name__ == '__main__':
|
|
main(int(sys.argv[1]) if len(sys.argv) > 1 else 9)
|