We are very happy to announce that Emil Vaughan’s Flagmatic program is available and is supported by the Centre for Discrete Mathematics.
The program computes exact values of Turán densities of hypergraphs, especially ordinary graphs, directed graphs, and 3-uniform hypergraphs, using Razborov’s flag algebra calculus. The exact values are confirmed by certificates, which enable independent verification of the result. A long list of results which have been obtained using the program is available from the old website, and will be migrated to the new site shortly.
Razborov’s method uses semidefinite programming, and Flagmatic makes use of the semidefinite program solver CSDP. Version 1 of the program is stand-alone; version 2 (available shortly) will be a Sage package.
The Turán density of a set of (hyper)graphs is the limit of edge densities of (hyper)graphs containing no copies of the given (hyper)graphs. The most ancient case is Mantel’s Theorem: the Turán density of a triangle is 1/2, since a graph with no triangle has at most about half as many edges as the complete graph. The Turán density is often but not always rational. The program can also compute induced subgraph densities. It is a tool of great potential value in extremal graph and hypergraph theory.