New Lower Bounds for C 4 C_{4} -Free Subgraphs of the Hypercubes Q 6 Q_{6} , Q 7 Q_{7} , and Q 8 Q_{8} : Constructions, Structure, and Computational Method
Minamo Minamoto · 2026
Read New Lower Bounds for C 4 C_{4} -Free Subgraphs of the Hypercubes Q 6 Q_{6} , Q 7 Q_{7} , and Q 8 Q_{8} : Constructions, Structure, and Computational Method by Minamo Minamoto (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-29127.txt.
Introduction
Minamoto studies subgraphs of the hypercubes Q6, Q7, and Q8 that avoid four-cycles. He works with odd-square edge sets that meet every four-cycle in one or three edges. He proves the largest sizes are 132, 304, and 682. Machine-checkable certificates back these values. He also sorts 19,866 known 304-edge subgraphs of Q7 into 20 types. They share one structural core and split into 180 symmetry orbits. All certified claims can be rechecked from released code and data.
Catalog record
| CREATOR | Minamo Minamoto |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 13843 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.29127
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
New Lower Bounds for C 4 C_{4} -Free Subgraphs of the Hypercubes Q 6 Q_{6} , Q 7 Q_{7} , and Q 8 Q_{8} : Constructions, Structure, and Computational Method Minamo Minamoto Abstract We establish new lower bounds ex ( Q 7 , C 4 ) ≥ 304 \mathrm{ex}(Q_{7},C_{4})\geq 304 and ex ( Q 8 , C 4 ) ≥ 680 \mathrm{ex}(Q_{8},C_{4})\geq 680 for the maximum number of edges in a C 4 C_{4} -free subgraph of the 7- and 8-dimensional hypercubes, and give a modern computational reproduction of ex ( Q 6 , C 4 ) = 132 \mathrm{ex}(Q_{6},C_{4})=132 . All bounds are witnessed by explicit constructions certified by exhaustive enumeration of all four-cycles (240 for Q 6 Q_{6} , 672 for Q 7 Q_{7} , 1 792 for Q 8 Q_{8} ). For Q 7 Q_{7} we identify 19 866 19\,866 distinct C 4 C_{4} -free subgraphs on 304 edges and classify them into exactly 20 structural types via their dimension profiles . All solutions share a rigid structural core: degree sequence { 4 32 , 5 96 } \{4^{32},5^{96}\} , spectral radius λ 1 ≈ 4.787 \lambda_{1}\approx 4.787 , and local maximality. Pairwise Hamming distances range from 36 to 260. For Q 8 Q_{8} we analyse the 680-edge construction and the 681-edge barrier: every non-edge of the solution creates at least one C 4 C_{4} , and 1 076 independent searches at 681 edges never achieved zero violations. The constructions are found by a two-phase simulated annealing algorithm with Aut ( Q n ) (Q_{n}) -based diversification, described in full detail. For Q 6 Q_{6} we additionally provide an ILP-based proof that ex ( Q 6 , C 4 ) ≤ 132 \mathrm{ex}(Q_{6},C_{4})\leq 132 , reproducing the exact value computationally. Edge lists, ILP files, and source code are publicly available at https://github.com/minamominamoto/c4free-hypercube . MSC 2020: 05C35, 05C62, 05C50. Keywords: hypercube, C_{4} -free, extremal graph theory, simulated annealing, integer linear programming, dimension profile. 1 Introduction The n -dimensional hypercube Q_{n} has vertex set \{0,1\}^{n} , two vertices adjacent iff they differ in exactly one coordinate; it has 2^{n} vertices and n\cdot 2^{n-1} edges. The problem of determining \mathrm{ex}(Q_{n},C_{4})=\max\{|E(G)|:G\subseteq Q_{n},\,G\text{ is }C_{4}\text{-free}\} was raised by Erdős [ 6 ] and remains open in general. The best known asymptotic bounds are \tfrac{1}{2}(n+\sqrt{n})\cdot 2^{n-1}\;\leq\;\mathrm{ex}(Q_{n},C_{4})\;\leq\;0.6032\cdot n\cdot 2^{n-1}, (1) where the lower bound (valid for n=4^{r} ) is due to Brass, Harborth, and Nienborg [ 3 ] , and the upper bound to Baber [ 1 ] via the flag algebra method. Balogh et al. [ 2 ] give 0.6068 via a related method. For general n\geq 9 , the weaker bound \tfrac{1}{2}(n+0.9\sqrt{n})\cdot 2^{n-1} applies [ 3 ] . Exact values have been determined for small n ; Harborth and Nienborg [ 7 ] proved \mathrm{ex}(Q_{6},C_{4})=132 . Our main results are: Theorem 1 . (i) \mathrm{ex}(Q_{7},C_{4})\geq 304 . (ii) \mathrm{ex}(Q_{8},C_{4})\geq 680 . Both bounds are realised by explicit constructions (supplementary files q7_edges_304.jsonl and q8_edges_680.jsonl ). Table 1: Known values and new lower bounds of \mathrm{ex}(Q_{n},C_{4}) . The BHN column gives the Brass–Harborth–Nienborg general estimate. n |E(Q_{n})| \mathrm{ex}(Q_{n},C_{4}) BHN est. Source 4 32 24 \approx 25.6 Chung [ 4 ] 5 80 56 \approx 51.2 Emamy-K et al. [ 5 ] 6 192 132 \approx 96.0 Harborth–Nienborg [ 7 ] (reproduced) 7 448 \geq\mathbf{304} \approx 300.2 This work 8 1024 \geq\mathbf{680} \approx 674.9 This work The paper is organised as follows. Section 2 describes the C_{4} enumeration and verification procedure used throughout. Sections 3 – 4 present the Q_{7} and Q_{8} constructions. Section 5 gives the structural classification of the Q_{7} solutions into 20 types. Section 6 describes the two-phase simulated annealing algorithm. Section 7 reproduces the exact value \mathrm{ex}(Q_{6},C_{4})=132 via ILP. Section 8 lists open problems. 2 C_{4} Enumeration and Verification Lemma 2 ( C_{4} enumeration in Q_{n} ) . Every four-cycle of Q_{n} is uniquely determined by a pair of coordinate directions 0\leq i<j\leq n-1 and a base vertex b\in\{0,1\}^{n} with b_{i}=b_{j}=0 . Its four vertices are b,\quad b\oplus e_{i},\quad b\oplus e_{j},\quad b\oplus e_{i}\oplus e_{j}, and the total number of four-cycles in Q_{n} is \binom{n}{2}\cdot 2^{n-2} . For n=6 : 240 ; for n=7 : 672 ; for n=8 : 1\,792 . Verification algorithm. Given a candidate edge set E\subseteq E(Q_{n}) stored as a hash set, the following procedure performs a complete, deterministic C_{4} -freeness check: for each pair (i,j) with 0\leq i<j\leq n-1 : for each b\in\{0,1\}^{n} with b_{i}=b_{j}=0 : let v_{1}=b,\;v_{2}=b\oplus e_{i},\;v_{3}=b\oplus e_{j},\;v_{4}=b\oplus e_{i}\oplus e_{j} if \{v_{1}v_{2},\,v_{1}v_{3},\,v_{2}v_{4},\,v_{3}v_{4}\}\subseteq E : return violation return c4-free We applied this algorithm to all constructions and all 19\,866 solutions of Q_{7} ; every call returned c4-free . 3 The Q_{7} Construction We constructed a C_{4} -free subgraph of Q_{7} on 304 edges by penalty-based simulated annealing (Section 6 ), then certified it by Lemma 2 ’s algorithm. Proposition 3 . The 304-edge construction has the following properties: (i) Degree sequence: 32 vertices of degree 4 and 96 of degree 5 (degree sum 608=2\cdot 304 ). (ii) Bipartite: \lambda_{1}\approx 4.787 , \lambda_{n}\approx-4.787 , \lambda_{1}+\lambda_{n}=0 to machine precision. (iii) \mathrm{Tr}(A^{4})=5216 , attaining the C_{4} -free trace equality \sum_{i}\deg(i)^{2}+\sum_{uv\in E}(\deg u+\deg v)-2|E| . (iv) Local maximality: every non-edge of Q_{7} creates a C_{4} when added. Through 19\,866 independent runs (Section 5.3 ) we found 19\,866 C_{4} -free subgraphs of Q_{7} on 304 edges with pairwise distinct edge sets (not quotiented by \mathrm{Aut}(Q_{7}) ), all sharing the properties in Proposition 3 . 4 The Q_{8} Construction Simulated annealing produced a C_{4} -free subgraph of Q_{8} on 680 edges, certified by exhaustive enumeration of all 1\,792 four-cycles. Proposition 4 . The 680 -edge C_{4} -free subgraph of Q_{8} has the following properties: (i) Degree sequence \{4^{8},\,5^{160},\,6^{88}\} ; degree sum 1360=2\cdot 680 . (ii) Bipartite, with \lambda_{1}+\lambda_{n}=0 . (iii) Local maximality: every non-edge of Q_{8} creates a C_{4} upon addition. (iv) Edge density 680/1024=66.4\% , compared to 304/448=67.9\% for the Q_{7} construction. Remark 5 . Since 8 is not a power of 4 , the exact BHN formula does not apply for n=8 . The applicable estimate is \tfrac{1}{2}(8+0.9\sqrt{8})\cdot 128\approx 674.9 , which our 680-edge construction surpasses by 5.1 edges. 4.1 The 681-edge barrier For the 680 -edge solution, every non-edge of Q_{8} creates at least one C_{4} upon addition. Among the 344 non-edges: exactly 1 creates exactly 1 new C_{4} ; exactly 1 creates exactly 2 ; the remaining 342 create 3 or more. Over 1\,076 independent simulated-annealing trials targeting 681 edges, the minimum C_{4} violation count observed was 1 (never 0 ). Conjecture 6 . \mathrm{ex}(Q_{8},C_{4})=680 . Table 2 compares the Q_{7} and Q_{8} constructions. Table 2: Structural comparison of the Q_{7} and Q_{8} constructions. Parameter Q_{7} (304 edges) Q_{8} (680 edges) Total edges |E(Q_{n})| 448 1024 Achieved edges 304 680 Edge density 67.9% 66.4% Min degree 4 4 Max degree 5 6 Degree sequence \{4^{32},5^{96}\} \{4^{8},5^{160},6^{88}\} BHN estimate \approx 300.2 \approx 674.9 Improvement +3.8 +5.1 5 Structural Classification of Q_{7} Solutions 5.1 Dimension profiles and the twenty types Definition 7 (Dimension profile) . For G\subseteq Q_{7} , let e_{i}(G)=|\{uv\in E(G):u\oplus v=2^{i}\}| . The dimension profile is the sorted tuple \pi(G)=(e_{\sigma(0)}\geq\cdots\geq e_{\sigma(6)}) . The dimension profile is invariant under coordinate permutations (a subgroup of \mathrm{Aut}(Q_{7})