flag-algebra
A generic implementation of flag algebras.
Flag algebras is a framework used to produce computer-assisted proofs of some inequalities in combinatorics, relying on Semi-Definite Programming.
Example
// Proving that in any graph, at least 1/4 of the triples
// are triangles or independent sets.
extern crate flag_algebra;
use *;
use Graph;
Features
This library can currently do the following.
- Generate list of flags from scratch.
- Generate flag algebra operators and memoize them in files.
- Compute in the flag algebra (multiplication, unlabeling) and add user-defined vectors.
- Define, manipulate or amplify flag inequalities (for instance by multiplying an inequality by all flags).
- Write problem in .spda format or directly run the CSDP solver.
- Automatically eliminate unnecessary constraints (in a naive way).
- It is generic: defining new specific class/subclass of flags boils down to implementing a Rust Trait.
- Output flags, problems or certificates as html pages in (hopefully) human-readable format (provided that it has a reasonnable size).
Supported flags
This library is generic. To use a kind combinatorial objects as flags (e.g. graphs), it suffices to implement the Flag trait for the corresponding Rust datatype.
Currently, Flag is implemented for Graphs, Digraphs and edge-colored graphs with some fixed number of colors.
Beside implementing directly Flag for your own types, two mechanisms help
to define flag classes based on an existing flag class F
.
- The Colored structure for defining vertex-colored flags.
If
N
is an integer identifier,Colored<F, N>
is the type for flags of typeF
where the vertices are further colored inN
different colors.Colored<F, N>
automatically implementFlag
whenF
does. - The Subclass structure and the SubFlag for classes that are subsets of already defined classes. This is usefull for instance for computing in triangle-free graphs flag algebra without considering other graphs.
License: GPL-3.0