Skip to main content

Code for computer aided proof of tangencies problem

This web-page provides the source code of the programs needed to perfom the computations reported in the paper 'Packing Twelve Spherical Caps to Maximize Tangencies' by L. Harris, M. Taylor, F. Theil and A. Tarasov.

1) Use the plantri to generate the list of all spherical graphs with 12 or less vertices and at least 24 edges. The program can be downloaded at http://cs.anu.edu.au/~bdm/plantri. The command is plantri n -c2 -p -v -e24: -h >graphs, where n is the number of vertices. The size of the file 'graphs' is 16gb if n=12.

2) Download the files maxdegreefilter.c, rigidgraphfilter.c and simplexalgorithm.c by right-clicking the links and choosing 'Save link as' or 'Save target as', depending on your browser.

3) Compile the programs with the commands 'gcc maxdegreefilter.c -o maxdegreefilter', 'gcc -fopenmp simplexalgorithm.c -o simplexalgorithm', 'gcc -lm -fopenmp rigidgraphfilter.c -o rigidgraphfilter'

4) Generate the list of graphs with maximum vertex degree 5 using the command 'maxdegreefilter <graphs >graphs1'.

5) Eliminate the graphs for which no solution of the linear inequalities (8)-(17) exists by invoking the command 'simplexalgorithm <graphs1 >graphs2'. This elimination step leavs 67 graphs if n=12 and 0 if n<12.

6) Eliminate those graphs which are partially rigid and cannot be contact graphs by invoking the command 'rigidgraphfilter <graphs1 >graphs2. Only the cuboctahedron and the twisted cubeoctahedron survive.