Abstract:We study C_4-free subgraphs of the hypercubes Q_6, Q_7 and Q_8. Writing g(n) for the maximum size of an odd-square edge set -- meeting every 4-cycle of Q_n in exactly one or three edges -- we prove g(6)=132, g(7)=304, g(8)=682, with explicit machine-verifiable certificates, giving ex(Q_7,C_4)>=304 and ex(Q_8,C_4)>=682. Under the standard fully-frustrated-hypercube correspondence, these values are already implicit in the statistical-physics literature: the field identity and its optimal values go back to Derrida, Pomeau, Toulouse and Vannimenus (1979), who construct ground states for D<=7; the D=8 attainment was reported by Marinari, Parisi and Ritort (1995); Laplante et al. treat the graph-theoretic formulation directly. Our contribution is accordingly narrow: a short self-contained proof of the optima via a mod-8 refinement of the classical two-point inequality, the certificates themselves, and an exhaustive decision of the realisability of the optimal n=6 field distributions, settling a question DPTV left open in 1979: exactly one of the three optimal distributions is realisable.
Independently, we classify the 19,866 previously released 304-edge C_4-free subgraphs of Q_7 (389 of them odd-square) into 20 dimension-profile types, establish their common structural core (degree sequence {4^32,5^96}), and decompose them into 180 Aut(Q_7)-orbits containing 34,227,200 labelled solutions; whether these are all orbits of 304-edge solutions is open. For Q_6, ex(Q_6,C_4)=132 rests on Harborth-Nienborg's upper bound, not independently verified here; the odd-square g(6)=132 is self-contained. All certified or deterministic claims are re-checkable from the released code and data; imported results are marked as such, and the repository carries SHA-256 manifests. Edge lists and code: this https URL
From: Minamo Minamoto [view email]
[v1]
Tue, 31 Mar 2026 01:22:53 UTC (5 KB)
[v2]
Wed, 1 Apr 2026 22:39:59 UTC (7 KB)
[v3]
Mon, 11 May 2026 01:07:21 UTC (7 KB)
[v4]
Wed, 13 May 2026 16:30:03 UTC (7 KB)
[v5]
Fri, 28 Aug 2026 01:03:22 UTC (75 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。