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.

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.

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.

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

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.

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

A fully symmetry reduced Lasserre-style model.

FlagSOS.PartiallyColoredFlagType
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.

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.

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.

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
FlagSOS.QuantumFlagType
mutable struct QuantumFlag{F<:Flag, T}

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

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.

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

Scalar multiplication of a linear combinations of Flags.

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.

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.

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

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

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.

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.

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

Adds two linear combinations of Flags.

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

Adds a flag to a linear combination of flags.

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

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

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

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

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

Inverts the sign of a linear combinations of Flags.

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

Subtracts two linear combinations of Flags.

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

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

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

The empty Flag of the same type as F.

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

The empty Flag of type T.

Base.sizeMethod
size(F::QuantumFlag)

The maximum size of the Flags in 'F'.

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

The size (number of vertices) of F.

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.

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.

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.

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.

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

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.

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

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.

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.

FlagSOS.glueMethod
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.

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.

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

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

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.

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

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.

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.

FlagSOS.isolatedVerticesMethod
isolatedVertices(F::PartiallyColoredFlag)::BitVector

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

FlagSOS.isolatedVerticesMethod
isolatedVertices(F::PartiallyLabeledFlag)::BitVector

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

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

Returns the indicator vector of isolated vertices of F.

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

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

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.

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.

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.

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

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

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

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

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.

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

Permutes the vertices of F according to the permutation p.

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.

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

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

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.

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

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