# 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.

It is also possible to download programs needed to perform the calculation from arXiv, however the arXiv version does not contain files that are generated during the calculation.

Dependencies

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)