Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube

József Balogh, Ping Hu, Bernard Lidický, Hong Liu

This page is containing computer assisted parts of the paper titled Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube.

You can download the technical things as

• only sources (can generate everything)
• including outputs (no need to compile anything)

• Source codes of two programs cubes_1.cpp and cubes_2.cpp doing the same thing
• 99 4-cycle-free spanning subgraphs of 3 dimensional hypercube (graphs_1_C4-free.txt, graphs_2_C4-free.txt)
• 116 6-cycle-free spanning subgraphs of 3 dimensional hypercube (graphs_1_C6-free.txt, graphs_2_C6-free.txt)
• semidefinite program for 4-cycle-free graphs (sdp_1_C4_input.txt, sdp_2_C4_input.txt)
• semidefinite program for 6-cycle-free graphs (sdp_1_C6_input.txt, sdp_2_C6_input.txt)
• outputs of CSDP solver (sdp_X_CY_solution.txt)
• matlab fix for results ( *.m)
• Makefile for convenience

The semidefinite program is in SDPA format.

The spanning subgraphs of Q₃ are given as {0,1}¹² characteristic vectors of 12 edges ordered in the lexicographic order.

Notes:

• Numbers in SDP are multiplied by 48 as the resulting program is easier to solve then. Also the solution of SDP has to be divided by -48 to get the desired density. Matlab code takes care of this.