On the crossing numbers of complete graphs

József Balogh, Bernard Lidický, Gelasio Salazar

This page contains computer assisted parts of the paper On the crossing numbers of complete graphs.

A preliminary version of the paper can be downloaded here or from arXiv.

Here, you can download the technical things as one archive

• hill_computations.zip (zip, around 0.5MB)
• hill_computations_2.zip (zip, around 200MB, includes some generated files)
• hill3.tar.gz (tar.gz, around 285MB, includes all generated files and some transcripts of execution)

Dependencies

• Some C++ compiler
• Sage
• CSDP

Description of the content

• Makefile.include ... Common part of Makefile for all calculations.
• flag.cpp ... C++ program that calculates coefficients in the semidefinite program
• rounding_Integer.sage ... Sage script to perform approximate rounding of solutions of semidefinite program by CSDP.
• */run.sh ... script to perform the entire calculation (uncomment sections as needed)
• */Makefile ... for compilation of flag.cpp
• */F_rotationsystem*__objective.txt ... $N_4$, the rotations on 4 vertices without crossing, with different scale
• */SDP_n*.dat-s ... semidefinite program for calculating upper bound for $\phi(N_4)$ (generated file)
• */SDP_n*.dat-s.result ... Solution to the semidefinite program using CSDP (generated file)
• */SDP_n*.pkl ... Rounded matrices from CSDP (generated file - the actual certificates of a proof)
• rotation_systems/F_rotationsystem__n5_unlabeled.txt ... $\mathcal{E}_1,\ldots,\mathcal{E}_5$ rotations on up to 5 vertices
• rotation_systems/F_rotationsystem__n7_labeled.txt ... Labeled flags $F_1,\ldots,F_8$ (generated file)
• rotation_systems/F_rotationsystem__n7_unlabeled.txt ... $\mathcal{E}_1,\ldots,\mathcal{E}_7$ rotations on up to 7 vertices (generated file)
• rotation_systems_convex/F_rotationsystem__n5_unlabeled.txt ... $\mathcal{C}_1,\ldots,\mathcal{C}_5$ convex rotations on up to 5 vertices
• rotation_systems_convex/F_rotationsystem__n8_labeled.txt ... Labeled flags $F_1,\ldots,F_5$ (generated file)
• rotation_systems_convex/F_rotationsystem__n8_unlabeled.txt ... $\mathcal{C}_1,\ldots,\mathcal{C}_8$ convex rotations on up to 8 vertices
• rotation_systems_blind/* ... Not used in the paper, included for curious readers
• rotation_systems_blind/F_rotationsystemblind__n5_unlabeled.txt ... $\mathcal{M}_1,\ldots,\mathcal{M}_5$ rotations on up to 5 vertices
• rotation_systems_blind/F_rotationsystemblind__n7_labeled.txt ... possible labeled flags for calculation. (generated file)
• rotation_systems_blind/F_rotationsystemblind__n7_unlabeled.txt ... $\mathcal{M}_1,\ldots,\mathcal{M}_7$ rotations on up to 7 vertices (generated file)
• rotation_systems_convex_blind/* ... Not used in the paper, included for curious readers
• rotation_systems_convex_blind/F_rotationsystemblind__n5_unlabeled.txt ... convex rotations on up to 5 vertices from $\mathcal{M}_1,\ldots,\mathcal{M}_5$
• rotation_systems_convex_blind/F_rotationsystemblind__n8_labeled.txt ... possible labeled flags for calculation. (generated file)
• rotation_systems_convex_blind/F_rotationsystemblind__n8_unlabeled.txt ... convex rotations on up to 8 vertices from $\mathcal{M}_1,\ldots,\mathcal{M}_8$ (generated file)