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.

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.

struct DirectedGraph{allowDigons} <: Flag

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

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.

abstract type Flag

An abstract Flag.

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

struct Graph <: Flag

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

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.

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.

LasserreModel{T<:Flag, N, D} <: AbstractFlagModel{T, N, D}

A fully symmetry reduced Lasserre-style model.

PartiallyColoredFlag{T} <: Flag where {T<:Flag}

A Flag F where (some of) the n vertices are colored. May have isolated vertices. Assumes vertices are ordered by color, with uncolored vertices at the end. Labeling such a Flag canonically cannot swap vertices with different colors, meaning the Flags 2-1-o and 1-2-o are different. If swaps there should be allowed, use a ColoredFlag{T} instead.

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.

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.

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

mutable struct QuantumFlag{F<:Flag, T}

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

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.

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

Scalar multiplication of a linear combinations of Flags.

:*(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.

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

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

:*(c::R, G::T) where {T <: Flag, R<:Real}

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

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

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

:*(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.

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

Adds two linear combinations of Flags.

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

Adds a flag to a linear combination of flags.

:+(F::T, G::T) where {T <: Flag}

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

:-(G::T) where {T <: Flag}

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

:-(F::QuantumFlag{T,R}) where {T <: Flag, R<:Real}

Inverts the sign of a linear combinations of Flags.

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

Subtracts two linear combinations of Flags.

:-(F::T, G::T) where {T <: Flag}

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

one(F::T)::T where {T <: Flag}

The empty Flag of the same type as F.

one(F::Type{T})::T where {T <: Flag}

The empty Flag of type T.

size(F::QuantumFlag)

The maximum size of the Flags in 'F'.

size(F::T)::Int where {T<:Flag}

The size (number of vertices) of F.

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.

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.

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.

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.

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.

Returns (Variables, Constraints)

countEdges(F::QuantumFlag)

The maximum number of edges of the flags in 'F'.

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.

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.

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)]]

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.

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.

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.

glue(F::PartiallyColoredFlag{T}, G::PartiallyColoredFlag{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 vertices with the same colors to vertices with the same colors.

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.

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).

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))

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.

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.

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).

isIsomorphic(F::T, G::T) where {T<:Flag}

Checks if two flags are isomorphic.

isSubFlag(F::T, G::T) where {T<:Flag}

Checks if 'F' appears as sub-flag of 'G'.

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.

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.

isolatedVertices(F::PartiallyColoredFlag)::BitVector

Returns the isolated, and un-labeled vertices of F.

isolatedVertices(F::PartiallyLabeledFlag)::BitVector

Returns the isolated, and un-labeled vertices of F.

isolatedVertices(F::T)::Vector{Int} where{T<:Flag}

Returns the indicator vector of isolated vertices of F.

labelCanonically(F::T)::T where {T <: Flag}

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

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.

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.

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.

moebius(F::EdgeMarkedFlag{T}) where {T<:Flag}

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

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

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

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.

permute(F::T, p::AbstractVector{Int})::T where {T<:Flag}

Permutes the vertices of F according to the permutation p.

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.

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).

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)).

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.

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

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