Flagmatic

This post is copied from the Centre for Discrete Mathematics site.


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.

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in software and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s