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.

### Like this:

Like Loading...

*Related*

## About Peter Cameron

I count all the things that need to be counted.