New Lower Bounds for C4-Free Subgraphs of the Hypercubes Q6, Q7, and Q8: Constructions, Structure, and Computational Method
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918499900719104 |
|---|---|
| author | Minamoto, Minamo |
| author_facet | Minamoto, Minamo |
| contents | We establish new lower bounds ex(Q_7,C_4)>=304 and ex(Q_8,C_4)>=680 for the maximum number of edges in a C_4-free subgraph of the 7- and 8-dimensional hypercubes, and give a modern computational reproduction of 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, 672 for Q_7, 1792 for Q_8). For Q_7 we identify 19866 distinct C_4-free subgraphs on 304 edges; their dimension profiles fall into exactly 20 types. All 19866 solutions share a rigid structural core: degree sequence {4^32,5^96}, spectral radius lambda_1 approximately 4.787, and local maximality. Pairwise Hamming distances range from 36 to 260. Whether these solutions exhaust all 304-edge C_4-free subgraphs of Q_7 remains open. For Q_8 we analyse the local structure of the 680-edge construction: every non-edge of the construction creates at least one C_4, and 1076 independent searches at 681 edges did not achieve zero violations. These observations constitute computational evidence, not a proof, of the conjectured equality ex(Q_8,C_4)=680. The constructions are found by a two-phase simulated annealing algorithm with Aut(Q_n)-based diversification. For Q_6 we provide an ILP-based proof that ex(Q_6,C_4)<=132. Edge lists, ILP files, and source code are publicly available at https://github.com/minamominamoto/c4free-hypercube |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_29127 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | New Lower Bounds for C4-Free Subgraphs of the Hypercubes Q6, Q7, and Q8: Constructions, Structure, and Computational Method Minamoto, Minamo Combinatorics 05C35, 05C62, 05C50 We establish new lower bounds ex(Q_7,C_4)>=304 and ex(Q_8,C_4)>=680 for the maximum number of edges in a C_4-free subgraph of the 7- and 8-dimensional hypercubes, and give a modern computational reproduction of 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, 672 for Q_7, 1792 for Q_8). For Q_7 we identify 19866 distinct C_4-free subgraphs on 304 edges; their dimension profiles fall into exactly 20 types. All 19866 solutions share a rigid structural core: degree sequence {4^32,5^96}, spectral radius lambda_1 approximately 4.787, and local maximality. Pairwise Hamming distances range from 36 to 260. Whether these solutions exhaust all 304-edge C_4-free subgraphs of Q_7 remains open. For Q_8 we analyse the local structure of the 680-edge construction: every non-edge of the construction creates at least one C_4, and 1076 independent searches at 681 edges did not achieve zero violations. These observations constitute computational evidence, not a proof, of the conjectured equality ex(Q_8,C_4)=680. The constructions are found by a two-phase simulated annealing algorithm with Aut(Q_n)-based diversification. For Q_6 we provide an ILP-based proof that ex(Q_6,C_4)<=132. Edge lists, ILP files, and source code are publicly available at https://github.com/minamominamoto/c4free-hypercube |
| title | New Lower Bounds for C4-Free Subgraphs of the Hypercubes Q6, Q7, and Q8: Constructions, Structure, and Computational Method |
| topic | Combinatorics 05C35, 05C62, 05C50 |
| url | https://arxiv.org/abs/2603.29127 |