### 11 releases

new 0.1.11 | Oct 26, 2020 |
---|---|

0.1.10 | Oct 12, 2020 |

0.1.6 | Dec 4, 2019 |

0.1.5 | Nov 20, 2019 |

0.1.3 | Jan 24, 2019 |

#**51** in Math

**46** downloads per month

**GPL-3.0**license

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

is an integer identifier,`N`

is the type for flags of type`Colored``<`F, N`>`

where the vertices are further colored in`F`

different colors.`N`

automatically implement`Colored``<`F, N`>`

when`Flag`

does.`F` - 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

#### Dependencies

~48MB

~671K SLoC