C4-Free Subgraphs of Hypercubes Q6, Q7, Q8: Odd Squares and Computational Structure

Overview

This research investigates C₄-free subgraphs within the hypercubes Q₆, Q₇, and Q₈. The primary focus is on determining the maximum size of an odd-square edge set, defined as a set of edges that intersects every 4-cycle of Q_n in precisely one or three edges. The study establishes specific values for this maximum size, denoted as g(n), for n=6, 7, and 8, and provides machine-verifiable certificates for these findings. These results contribute to the understanding of graph theory problems related to C₄-free subgraphs and connect to concepts from statistical physics, particularly fully-frustrated models.

Research Context

The concept of odd-square edge sets and their maximum sizes (g(n)) is directly relevant to determining ex(Q_n,C₄), which represents the maximum number of edges in a C₄-free subgraph of Q_n. The study proves that g(6)=132, g(7)=304, and g(8)=682. Consequently, these values are presented as ex(Q₇,C₄)=304 and ex(Q₈,C₄)=682. For Q₆, the value ex(Q₆,C₄)=132 is stated to rest on Harborth-Nienborg's upper bound, which is not independently verified in this work, although the g(6)=132 odd-square result is self-contained.

Within the statistical-physics literature, these values have historical context. The fully-frustrated-hypercube correspondence indicates that field identity and optimal values for these systems trace back to Derrida, Pomeau, Toulouse, and Vannimenus (1979), who constructed ground states for D=7. The attainment for D=8 was reported by Marinari, Parisi, and Ritort (1995). Laplante et al. are noted to have addressed the graph-theoretic formulation directly. A specific question left open by Derrida, Pomeau, Toulouse, and Vannimenus (1979) regarding the realisability of optimal n=6 field distributions is also addressed.

Approach

The core contribution of this study includes a concise, self-contained proof for the determined optimal values of g(n). This proof utilizes a mod-8 refinement of the classical two-point inequality. The research also generates explicit machine-verifiable certificates for the calculated g(n) values. For the n=6 case, the study provides an exhaustive decision regarding the realisability of the optimal field distributions. It was determined that exactly one of the three optimal distributions is realisable.

Independent of the odd-square maximum size computations, the research classifies 19,866 previously released 304-edge C₄-free subgraphs of Q₇. Among these, 389 are identified as odd-square subgraphs. This classification involves grouping them into 20 distinct dimension-profile types. The common structural core of these subgraphs is established, characterized by a degree sequence of {4³², 5⁹⁶}. Furthermore, these subgraphs are decomposed into 180 Aut(Q₇)-orbits, which collectively contain 34,227,200 labeled solutions. The question of whether these represent all orbits of 304-edge solutions remains open.

Findings

• The maximum size of an odd-square edge set for hypercubes Q₆, Q₇, and Q₈ is g(6)=132, g(7)=304, and g(8)=682, respectively.
• These values imply ex(Q₇,C₄)=304 and ex(Q₈,C₄)=682.
• Explicit machine-verifiable certificates are provided for these g(n) values.
• A short, self-contained proof for the optima leverages a mod-8 refinement of the classical two-point inequality.
• For n=6, exactly one of the three optimal field distributions from Derrida, Pomeau, Toulouse, and Vannimenus (1979) is realisable.
• 19,866 previously released 304-edge C₄-free subgraphs of Q₇ were classified into 20 dimension-profile types.
• 389 of these 304-edge subgraphs of Q₇ are odd-square.
• The common structural core of these classified subgraphs of Q₇ possesses a degree sequence of {4³², 5⁹⁶}.
• These subgraphs decompose into 180 Aut(Q₇)-orbits, containing 34,227,200 labeled solutions.

Why This Matters

The established g(n) values directly determine extremal graph properties (ex(Q_n,C₄)) for hypercubes, a fundamental problem in extremal graph theory. By providing explicit machine-verifiable certificates and a self-contained proof method, the research enhances the rigor and reproducibility of these complex graph-theoretic results. The resolution of a long-standing question regarding the realisability of optimal n=6 field distributions from the 1979 work of Derrida, Pomeau, Toulouse, and Vannimenus clarifies aspects of fully-frustrated models in statistical physics. The comprehensive classification of C₄-free subgraphs of Q₇ provides a detailed structural understanding of these specific graph configurations, which could inform further research into graph properties and symmetries.

Potential Applications

All certified or deterministic claims made in this study are re-checkable using the released code and data. Imported results are explicitly marked. The repository containing edge lists and code (https://github.com/minamominamoto/c4free-hypercube) includes SHA-256 manifests for verification.

Key Limitations Mentioned by Researchers

The ex(Q₆,C₄)=132 result relies on Harborth-Nienborg's upper bound and is not independently verified within this study, though the g(6)=132 odd-square finding is self-contained. It remains an open question whether the identified 180 Aut(Q₇)-orbits constitute all orbits of 304-edge solutions for C₄-free subgraphs of Q₇.