### 14 releases

0.2.1 | Jun 27, 2023 |
---|---|

0.2.0 | Jun 18, 2023 |

0.1.12 | Apr 25, 2021 |

0.1.11 | Oct 26, 2020 |

0.1.3 | Jan 24, 2019 |

#**99** in Math

**589** downloads per month

**GPL-3.0**license

230KB

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.
`use` `flag_algebra``::``*``;`
`use` `flag_algebra``::``flags``::`Graph`;`
`//` 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, Oriented graphs, Directed graphs 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. See the documentation page of [SubFlag] for more details.

## Expressing elements of a flag algebra

See [Type], [Basis] and [QFlag].

The

structure identifies a
"type" σ in the sense of flag algebras (i.e. a completely labeled flag)
is represented by an object.
The `Type <F:Flag>`

`Basis``<`F`:`Flag`>`

structure corresponds to a couple (n, σ)
and identifies the set of σ-flags of size n.
The structure `QFlag`

License: GPL-3.0

#### Dependencies

~**67MB**

~877K SLoC