Constrained example: Caccetta Haeggkvist conjecture
The maximum minimum outdegree of a directed graph (without digons) without directed triangles is conjectured to be $\frac{1}{3}$:
\[\begin{aligned} \frac{1}{3}=\max_{G \text{ directed graph}} &r\\ \text{s.t.}\enspace & G \text{ has no directed triangles},\\ & \text{the relative outdegree of every vertex is at least }r. \end{aligned}\]
Here we compute an upper bound using a basic application of flag algebras. A more advanced application of the method lead to current best bound.
using FlagSOS
Setting up the model
We work with directed graphs without digons.
const Digraph = DirectedGraph{false}
DirectedGraph{false}
We define the relevant graphs using their adjacency matrices.
directedEdge = Digraph(Bool[0 1; 0 0]) # o -> o
directedTriangle = Digraph(Bool[0 1 0; 0 0 1; 1 0 0]) # x -> o -> o -> x
DirectedGraph{false}(Bool[0 1 0; 0 0 1; 1 0 0])
We start with an empty FlagModel
of type DirectedGraph
, where we forbid the directed triangle:
m = FlagModel{Digraph}()
addForbiddenFlag!(m, directedTriangle)
Set{DirectedGraph{false}} with 1 element:
DirectedGraph{false}(Bool[0 0 1; 1 0 0; 0 1 0])
Choosing a relaxation
Now we need to choose a hierarchy. One option is the Lasserre hierarchy, which we can attach to the model using addLasserreBlock!
.
addLasserreBlock!(m, 4);
This results in a semidefinite programming problem with block sizes
modelSize(m)
12₁11₁8₂6₁5₁3₁2₁1₄
We obtain an equivalent formulation of the conjecture the following way: We remove additional outgoing edges, until every vertex has relative outdegree exactly r. Then r is exactly the edge density of the digraph, i.e. we want to maximize the density of directedEdge
. This we can do by minimizing its negative
m.objective = -1 * directedEdge
-1 DirectedGraph{false}(Bool[0 1; 0 0])
We add the constraint that every vertex has relative outdegree identical to the (directed) edge density of the graph.
const lDigraph = PartiallyLabeledFlag{Digraph}
e1 = lDigraph(Bool[0 1; 0 0]; n=1) # 1 -> o
eL = lDigraph(Bool[0 1; 0 0]; n=0) # o -> o
qm2 = FlagSOS.addEquality!(m, e1 - eL, 4);
Finally, we compute the coefficients of the SDP.
computeSDP!(m)
2-element Vector{Nothing}:
nothing
nothing
Solving the SDP
We solve the relaxation using Hypatia.
using Hypatia, JuMP
jm = buildJuMPModel(m)
set_optimizer(jm.model, Hypatia.Optimizer)
optimize!(jm.model)
termination_status(jm.model)
OPTIMAL::TerminationStatusCode = 1
objective_value(jm.model)
0.500000007545878
This page was generated using Literate.jl.