## flag-algebra

An implementation of Razborov’s flag algebras

### 11 releases

 new 0.1.11 Oct 26, 2020 Oct 12, 2020 Dec 4, 2019 Nov 20, 2019 Jan 24, 2019

#51 in Math

225KB
6K SLoC

# 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 flag_algebra::*;
use flag_algebra::flags::Graph;

pub fn main() {
// Work on the graphs of size 3.
let basis = Basis::new(3);

// Define useful flags.
let k3 = flag(&Graph::new(3, &[(0, 1), (1, 2), (2, 0)])); // Triangle
let e3 = flag(&Graph::new(3, &[])); // Independent set of size 3

// Definition of the optimization problem.
let pb = Problem::<i64, _> {
// Constraints
ineqs: vec![total_sum_is_one(basis), flags_are_nonnegative(basis)],
// Use all relevant Cauchy-Schwarz inequalities.
cs: basis.all_cs(),
// Minimize density of triangle plus density of independent of size 3.
obj: k3 + e3,
};

// Write the correspondind SDP program in "goodman.sdpa".
// This program can then be solved by CSDP. The answer would be 0.25.
pb.write_sdpa("goodman").unwrap();
}
``````

## 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 type `F` where the vertices are further colored in `N` different colors. `Colored<F, N>` automatically implement `Flag` when `F` 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.