FlagSOS.jl

Documentation for FlagSOS.jl, a Julia package for extremal combinatorics based on the flag algebra method and its variants. The package offers various hierarchies to compute lower bounds for problems of the form

\[\begin{aligned} \inf_M\enspace & F(M)\\ \text{s.t. }& G_i(M) \geq 0 \quad\text{ for }i=1,\dots,k,\\ & H_i(M) = 0 \quad\text{ for }i = 1,\dots, \ell, \end{aligned}\]

where $F$, $G_i$, $H_i$ are quantum flags (linear combinations of sub-model density functions), and $M$ is a model of fixed size or a converging sequence in a given theory. The constraints can include labels, but then the entire $S_n$ orbit needs to be included.

Examples

Reference

FlagSOS.FlagSOSModule
module FlagSOS

Module for customizable Flag-Sum of Squares problems: Change the type of Flag-Algebra, e.g. graphs, hypergraphs, permutations, order types. Generate fully symmetry reduced finite n, infinite n, flexible Flag SOS hierarchies.

source
FlagSOS.AbstractFlagModelType
AbstractFlagModel{T<:Flag, N, D}

An abstract Flag-SOS model. T is the Flag-type used internally, i.e. as variables in the SDP obtained at the end. It may be advantageous to use non-induced Flags internally, even when the model is formulated with induced Flags.

N is either :limit, :variable or an Integer. If N == :limit, then we are in the usual case of Flag Algebras, i.e. the case where the number of vertices goes towards infinity (fastest). If N is an integer, then we are in the case of exactly N vertices (slower). If N == :variable, then the model will be parametrized by a variable, i.e. coefficients will be polynomials in N (slowest).

D is the datatype for the coefficients in the final optimization problem.

source
FlagSOS.DirectedGraphType
struct DirectedGraph{allowDigons} <: Flag

A model of a directed graph, given by its adjacency matrix.

source
FlagSOS.EqualityModuleType
EqualityModule{T<:Flag, U<:Flag, N, D} <: AbstractFlagModel{T, N, D}

Implements quadratic modules for equalities. Meant to be used as submodel of a CompositeFlagModel. Multiplies all elements of basis, a vector of all relevant Flags of type U with equality, converts the result to type T, and sets it to zero in the resulting optimization problem.

source
FlagSOS.FlagModelType
FlagModel{T <: Flag, N, D} <: AbstractFlagModel{T, N, D}

A Flag-model with internal Flag type 'T'.

Parameters

  • T: Target Flag type
  • N: Limit parameter, see AbstractFlagModel
  • D: Data type of coefficients of the final optimization problem
source
FlagSOS.GraphType
struct Graph <: Flag

A model of a graph, given by its adjacency matrix.

source
FlagSOS.HarmonicFlagType
HarmonicFlag{T} <: Flag where {T <: Flag}

Turns a given Flag into its harmonic equivalent. E.g. HarmonicFlag{Graph}(P2), where P2 = Graph(Bool[0 0 1; 0 0 1; 1 1 0]) is the path on three vertices, describes the Flag corresponding to the harmonic path density. Only makes sense if there is an equivalent to "edges" in the Flag type T.

source
FlagSOS.InducedFlagType
InducedFlag{T} <: Flag where {T <: Flag}

Turns a given Flag into its induced equivalent. E.g. InducedFlag{Graph}(P2), where P2 = Graph(Bool[0 0 1; 0 0 1; 1 1 0]) is the path on three vertices, describes the Flag corresponding to the induced path density. Only makes sense if there is an equivalent to "edges" in the Flag type T.

source
FlagSOS.LasserreModelType
LasserreModel{T<:Flag, N, D} <: AbstractFlagModel{T, N, D}

A fully symmetry reduced Lasserre-style model.

source
FlagSOS.PartiallyLabeledFlagType
PartiallyLabeledFlag{T} <: Flag where {T<:Flag}

A Flag F where the first n vertices are labeled. May have isolated vertices in the labeled part. Labeling such a Flag canonically cannot swap vertices in the labeled part, meaning the Flags 2-1-o and 1-2-o are different. If swaps there should be allowed, use a ColoredFlag{T} instead.

source
FlagSOS.PredicateType
abstract type Predicate

A way to describe one predicate value in a Flag. For example, it may describe a single edge of a Graph, or a single label of a PartiallyLabeledFlag.

source
FlagSOS.QuadraticModuleType
QuadraticModule{T <: Flag, U <: Flag, B <: AbstractFlagModel{U, N, D}, N, D} <: AbstractFlagModel{T, N, D}

Implements quadractic modules for inequalities. Meant to be used as a submodel of a FlagModel. Multiplies all elements of the baseModel with the inequality and then transforms them to type T (e.g. by unlabeling). The inequality f >= 0 is given in form of a QuantumFlag{U} describing f. If both inequalities f >= 0 and -f >= 0 appear in the problem it is equivalent, but much more efficient, to use an EqualityModule instead.

Parameters

  • T: Target Flag type
  • U: Flag type of the inequality, and the target type of the base model
  • B: Type of the base model
  • N: Limit parameter, see AbstractFlagModel
  • D: Data type of coefficients of the final optimization problem
source
FlagSOS.QuantumFlagType
mutable struct QuantumFlag{F<:Flag, T<:Real}

A linear combination of Flags of type F with coefficients of type T.

source
FlagSOS.RazborovModelType
RazborovModel{T<:Flag, N, D} <: AbstractFlagModel{T, N, D}

A (not fully symmetry reduced) Razborov-style model. If T is an InducedFlag, the hierarchy is the same as the one implemented in Flagmatic. If T is not induced, then a Moebius-transform is applied only on the labeled vertices. The resulting hierarchy is then a basis-transformation of the usual hierarchy, and returns the same bounds, but expressed in non-induced flags.

source
Base.:*Method
:*(F::QuantumFlag{T,R}, G::QuantumFlag{T, R}) where {T <: Flag, R<:Real}

The gluing operation of type T extended to linear combinations of Flags.

source
Base.:*Method
:*(G::QuantumFlag{T, R},F::T) where {T <: Flag, R<:Real}

The gluing operation of type T extended to linear combinations of Flags.

source
Base.:*Method
:*(c::R, G::QuantumFlag{T, R}) where {T <: Flag, R<:Real}

Scalar multiplication of a linear combinations of Flags.

source
Base.:*Method
:*(c::R, G::T) where {T <: Flag, R<:Real}

Scalar multiplication of Flags. Returns a 'QuantumFlag{T, R}'.

source
Base.:*Method
:*(F::T, G::QuantumFlag{T, R}) where {T <: Flag, R<:Real}

The gluing operation of type T extended to linear combinations of Flags.

source
Base.:*Method
:*(F::T, G::T) where {T<:Flag}

The gluing operation of type T. Should, for example, glue unlabeled vertices to distinct vertices in the result. Default implementation glues the Flags on fully distinct vertices.

source
Base.:+Method
:+(F::QuantumFlag{T,R}, G::QuantumFlag{T, R}) where {T <: Flag, R<:Real}

Adds two linear combinations of Flags.

source
Base.:+Method
:+(F::T, G::QuantumFlag{T, R}) where {T <: Flag, R<:Real}

Adds a flag to a linear combination of flags.

source
Base.:+Method
:+(F::T, G::T) where {T <: Flag}

Adds two Flags. Returns a 'QuantumFlag{T, Int}'.

source
Base.:-Method
:-(G::T) where {T <: Flag}

Scalar multiplication of Flags. Returns a 'QuantumFlag{T, Int}'.

source
Base.:-Method
:-(F::QuantumFlag{T,R}) where {T <: Flag, R<:Real}

Inverts the sign of a linear combinations of Flags.

source
Base.:-Method
:-(F::QuantumFlag{T,R}, G::QuantumFlag{T, R}) where {T <: Flag, R<:Real}

Subtracts two linear combinations of Flags.

source
Base.:-Method
:-(F::T, G::T) where {T <: Flag}

Subtracts two Flags. Returns a 'QuantumFlag{T, Int}'.

source
Base.oneMethod
one(F::T)::T where {T <: Flag}

The empty Flag of the same type as F.

source
Base.oneMethod
one(F::Type{T})::T where {T <: Flag}

The empty Flag of type T.

source
Base.sizeMethod
size(F::QuantumFlag)

The maximum size of the Flags in 'F'.

source
Base.sizeMethod
size(F::T)::Int where {T<:Flag}

The size (number of vertices) of F.

source
FlagSOS.addLasserreBlock!Method

addLasserreBlock!(m::FlagModel{T,N,D}, maxEdges::Int; maxVertices = maxEdges * maxPredicateArguments(T)) where {T<:Flag,N,D}

Adds a symmetry reduced Lasserre block of internal flag type 'T' to 'm' and returns it. All flags with up to 'floor(maxEdges/2)' edges (resp. true predicates) with optionally at most 'floor(maxVertices/2)' vertices are added as generators of the block. The resulting hierarchy contains flags with at most 'maxEdges' edges and 'maxVertices' vertices.

source
FlagSOS.addLasserreBlock!Method

addLasserreBlock!(m::FlagModel{T,N,D}) where {T<:Flag,N,D}

Adds an empty Lasserre block of internal flag type 'T' to 'm' and returns it. One should then use 'addFlag' to add generators to the block.

source
FlagSOS.addPredicatesMethod
addPredicates(::T, ::U, ::Vararg{U} where {T<:Flag,U<:Predicate}

Creates a copy of F, and adds all predicates with the given values to the copy. May change the order of vertices of F, if necessary (E.g. in the case of PartiallyLabeledFlag). The predicates are given as a Vector of Vectors of Predicate-value pairs, sorted by type in a way that addPredicates understands.

source
FlagSOS.addRazborovBlock!Method

addLasserreBlock!(m::FlagModel{T,N,D}, maxEdges::Int; maxVertices = maxEdges * maxPredicateArguments(T)) where {T<:Flag,N,D}

Adds a symmetry reduced Lasserre block of internal flag type 'T' to 'm' and returns it. All flags with up to 'floor(maxEdges/2)' edges (resp. true predicates) with optionally at most 'floor(maxVertices/2)' vertices are added as generators of the block. The resulting hierarchy contains flags with at most 'maxEdges' edges and 'maxVertices' vertices.

source
FlagSOS.allowMultiEdgesMethod
allowMultiEdges(::T) where {T<:Flag}

Can edges be added multiple times? More generally, can we repeatedly add to the same predicate value?

For most combinatoric models this should return false.

source
FlagSOS.autMethod
aut(F::T)::NamedTuple{(:gen, :size),Tuple{Vector{Vector{Int64}},Int64}} where {T<:Flag}

The automorphisms of F. Returns a named tuple with fields

  • gen::Vector{Vector{Int}}: Vector of permutations generating all automorphisms.
  • size::Int: The size of the automorphism group of F.
source
FlagSOS.countEdgesMethod
countEdges(F::T)::Vector{Int} where {T<:Flag}

Returns the Vector of numbers of set predicates in the Flag F for each Predicate type. For Graphs, this is the Vector with one element, the number of edges in the graph. Used when generating all Flags up to isomorphism of a given type to specify an upper bound on the number of set predicates.

source
FlagSOS.distinguishMethod

distinguish(F::T, v::Int, W::BitVector)::UInt where {T<:Flag}

Given a Flag F, a vertex v and a subset of vertices indicated by W, distinguish v by analyzing it's relationship to the vertices W. This may, for example, be the number of edges between v and the cell W, or the number of triangles with v and one/two vertices of W. The type of result does not matter, as it does get hashed after.

source
FlagSOS.findUnknownPredicatesMethod
findUnknownPredicates(F::T, fixed::Vector{Vector{Int}})

Given a Flag T, as well as subsets of vertices such that predicates (e.g. edges) are fixed if all arguments are within one of these sets. One should return a Predicate for each predicate and each combination of arguments, such that not all arguments are contained in one of the fixed subsets. The function returns a Vector of Vectors of Predicates, such that should return a Vector of Vectors of Predicates addPredicates can understand it.

This is then used to determine the glued Flag in induced settings. For example, gluing the partially labelled edge 1-o to itself, would call

findUnknownPredicates(Graph(Bool[0 1 1; 1 0 0; 1 0 0]), [[1,2],[1,3]])

The only unclear predicate here is the edge [2,3], i.e. this function should return

[[EdgePredicate(2,3)]]
source
FlagSOS.generateAllMethod
generateAll(::Type{F}, maxVertices::Int, maxPredicates::Vector{Int}; withProperty = (F::T) -> true) where {F}

Generates all Flags of type F with up to maxVertices vertices and up to maxPredicates non-zero predicate values. 'maxPredicates' is a vector, for the case that there are multiple predicates. If a function withProperty:F->{true, false} is given, keeps adding edges to flags as long as the property holds.

source
FlagSOS.glueMethod
glue(F::HarmonicFlag{T}, G::HarmonicFlag{T}, p::Vector{Int})

Glues together the two harmonic Flags F and G, after applying the permutation p to the vertices of F. p may be a permutation involving more than size(F) vertices. Since these Flags describe harmonic densities, the result is another flag of type F, where double edges cancelled out.

source
FlagSOS.glueMethod
glue(F::InducedFlag{T}, G::InducedFlag{T}, p::Vector{Int})

Glues together the two induced Flags F and G, after applying the permutation p to the vertices of F. p may be a permutation involving more than size(F) vertices. Since these Flags describe induced densities, the result is a linear combination of every possible combination of "unknown" edges between the added vertices from eachothers perspectives (or equivalent). If the common part is different, they are orthogonal to each other and thus return an empty Vector.

source
FlagSOS.glueMethod
glue(F::PartiallyLabeledFlag{T}, G::PartiallyLabeledFlag{T}, p::Vector{Int})

Glues together the two partially labeled Flags F and G, after applying the permutation p to the vertices of F. p may be a permutation involving more than size(F) vertices, but should send the labeled part of F to the labeled part of G, without permuting indices there.

source
FlagSOS.glueMethod
glue(F::T, G::T, p::Vector{Int})::U where {T<:Flag, U<:Flag}

Glues together the two Flags F and G, after applying the permutation p to the vertices of F. p may be a permutation involving more than size(F) vertices, in which case the result should have at least maximum(p) vertices. Optionally specifices a different output Flag type, for cases where the internal Flag type differs and there are performance advantages (such as the case of internal non-induced Graphs and the gluing of two induced Graphs).

source
FlagSOS.glueMethod
glue(Fs::Vararg{T}) where {T<:Flag}

Glues Flags together "on top of each other". Optionally specifices the output Flag type, for cases where a different type may improve performance (E.g. non-induced Flag as target for the gluing of two induced Flags). The default implementation only uses the custom type for the final gluing.

glue(F, G, H)

is equivalent to

glue(F, glue(G, H, 1:size(G)), 1:size(F))
source
FlagSOS.glueFiniteMethod
glueFinite(N, F::T, G::T, p::AbstractVector{Int}; labelFlags = true) where {T<:Flag}

Glues together the flags F and G, after applying the permutation p to the vertices of F. This variant of glue is for optimizing over finite objects, given by N which should be one of the options :limit, :variable or an integer. The operation assumes the k vertices that are sent on top of each other by p correspond to labels, and assumes that the other vertices are unlabeled, i.e. get sent to all N-k other vertices.

source
FlagSOS.isAllowedMethod
isAllowed(F::T) where {T<:Flag}

Sometimes one may want to create a flag-algebra with inherently forbidden flags, instead of attaching it to a model. Then one should implement (or locally overwrite) this function.

source
FlagSOS.isAllowedMethod
isAllowed(F::T, e::P) where {T<:Flag, P<:Predicate}

Sometimes one may want to create a flag-algebra with inherently forbidden flags, instead of attaching it to a model. This function should return true iff the predicate P can be set to true (i.e. the edge P can be added).

source
FlagSOS.isSymMethod
isSym(F::T, v1::Int, v2::Int)::Bool where {T<:Flag}

Returns true if the permutation which swaps the vertices v1 and v2 is an automorphism of F.

source
FlagSOS.isVariableVertexMethod
isVariableVertex(F::T, v::Int) where {T<:Flag}

Returns true if vertex v is one of the "variable vertices", i.e. vertices of which the number goes towards infinity. Per default, it always returns true. But, for example, for partially labeled Flags, it only returns true if the vertex is unlabeled.

source
FlagSOS.labelCanonicallyMethod
labelCanonically(F::T)::T where {T <: Flag}

Labels F canonically. If two Flags are isomorphic, this function should return the same Flag.

source
FlagSOS.labelCanonicallyMethod
labelCanonically(F::QuantumFlag{T,R})::QuantumFlag{T,R} where {T <: Flag, R <: Real}

Labels F canonically. If two Flags are isomorphic, this function should return the same Flag.

source
FlagSOS.labelCanonicallyMethod
labelCanonically(Fs::Vector{T})::Vector{T} where {T <: Flag}

Labels all Flags in Fs canonically. If two Flags are isomorphic, this function should return the same Flag.

source
FlagSOS.maxPredicateArgumentsMethod
maxPredicateArguments(::Type{T}) where {T<:Flag}

Maximum number of arguments of a predicate in the theory 'T'. For instance, this is '2' for graphs, as the only predicate, the edge predicate, takes two arguments.

source
FlagSOS.moebiusMethod
moebius(F::EdgeMarkedFlag{T}) where {T<:Flag}

Computes the moebius transform of an edge-marked flag on the marked edges.

source
FlagSOS.moebiusMethod
moebius(F::T, verts = 1:size(F)) where {T<:Flag}

Computes the moebius transform of a flag on the vertices 'verts'

source
FlagSOS.overlapsFunction
overlaps(lambda, mu [, total = pN, limit::Bool = false, fixedN = false])

Calculate the different ways two partitions can overlap, with multiplicities. Lambda is considered fixed, mu changes. Adds a biggest dynamic part by (lambda,n-sum(lambda)). Result is array of pairs, first is multiplicity depending on n, second is matrix. Rows are lambda i (last is dynamic sized), columns are mu i (last is dynamic sized)

To get the total amount of combinations (i.e. lambda can move around, too), multiply all multiplicities with numSplits(lambda). We have overlaps(lambda,mu) * numsplits(lambda) == overlaps(mu,lambda) * numSplits(mu).

Examples

julia> overlaps([1],[2])
2-element Array{Any,1}:
 (1//2*n^2-3//2*n+1//1, [0 2; 1 0])
 (n-1//1, [1 1; 0 0])

Corresponds to the two ways the partitions (1,n-1) and (2,n-2) can overlap. The first element is the overlap, where the 2-part of mu lies in the n-1 part of lambda, with multiplicity n-1 choose 2. The second is the one where 1 element of the 2-part of mu lies in the 1-part of lambda, with multiplicity n-1 choose 1.

source
FlagSOS.permuteMethod
permute(F::T, p::AbstractVector{Int})::T where {T<:Flag}

Permutes the vertices of F according to the permutation p.

source
FlagSOS.possibleValuesMethod
possibleValues(::Type{P}) where {P<:Predicate}

Returns the possible non-zero (!) values of a predicate of type P. Usually just [true], but for example directed graphs (without possiblity of a bi-directional edge) may have predicate values 0, 1 and -1.

source
FlagSOS.subFlagMethod
subFlag(F::T, vertices::AbstractVector{Int})::T where {T<:Flag}

Returns the sub-Flag indexed by vertices, which is a subset of 1:size(F).

source
FlagSOS.subFlagMethod
subFlag(F::T, vertices::BitVector)::T where {T<:Flag}

Returns the sub-Flag given by the indicator vector vertices, which is a BitVector of length size(F). If not extended, it calls subFlag(F, findall(vertices)).

source
FlagSOS.vertexColorMethod
vertexColor(::T, ::Int) where {T<:Flag}

Returns the color of vertices in colored Flags. The default is the case of a vertex-transitive Flags-type, where all vertices have color 1.

source
FlagSOS.zetaMethod
zeta(F::T, verts = 1:size(F)) where {T<:Flag}

Computes the zeta transform of a flag on the vertices 'verts'

source