Hypergraph Examples

Verifying Procedural Minimizers by Mathematica

In our examples, we need to verify that we have the correct value for γ_k := min_{≠f⊥ w{f1,f2,…,fk-1}}D_w(f), and a certain non-zero vector f_k attains the minimum.

The first step is straightforward, and we check that f_k is perpendicular to {f₁,…,f_k-1} in the weighted space, and D_w(f_k) equals γ_k.

The second step is to check that for all ≠f ⊥_w{f₁,f₂,…,f_k-1}, D_w(f) ≥ γ_k. As the numerator in the definition of D_w(f) involves the maximum operator, we use a program to consider all cases of the relative order of the nodes with respect to f.

For each permutation σ : [n] → V , for e ∈ E, we define S_σ(e) := σ(max{i : σ(i) ∈ e}) and I_σ(e) := σ(min{i : σ(i) ∈ e}).

We consider the mathematical program P(σ) := min∑ _e∈Ew_e ⋅ (f(S_σ(e)) - f(I_σ(e)))² - γ_k ⋅∑ _u∈V w_uf(u)² subject to f(σ(n)) ≥ f(σ(n - 1)) ≥ ⋅⋅⋅ f(σ(1)) and ∀i ∈ [k - 1],$\langle$f_i, f$\rangle$ = 0. Since the objective function is a polynomial, and all constraints are linear, the Mathematica function Minimize can solve the program.

Moreover, the following two statements are equivalent.

• For all ≠f ⊥_w{f₁,f₂,…,f_k-1}, D_w(f) ≥ γ_k.
• For all permutations σ, P(σ) ≥ 0.

Hence, to verify the first statement, it suffices to use Mathematica to solve P(σ) for all permutations σ. The test is passed if the total number of violations is zero.

Example 1

Consider the following hypergraph with 5 vertices and 5 hyperedges each with unit weight.

We can verify that different minimizers for γ₂ lead to different values for γ₃.

violation=0;

Fun[list_, mask_] := Module[{ans},
  l = Length[mask];
  max = 0;
  min = l;
  Do[
   max = Max[Extract[Extract[Position[list, Extract[mask, i]], 1], 1], max];
   min = Min[Extract[Extract[Position[list, Extract[mask, i]], 1], 1], min];
   , {i, l}];
  ans = (Extract[list, max] - Extract[list, min])^2
]

constrain = {m1<=m2, m2<=m3, m3<=m4, m4<=m5, m5==1, 5*a+4*b+3*c+2*d+e==0};
var = {a,b,c,d,e};
Do[
  thisObj = Fun[p,{a,b}]+Fun[p,{a,b,c}]+Fun[p,{a,b,c,d}]+Fun[p,{a,b,c,d,e}] - 5/6*(5*a^2+4*b^2+3*c^2+2*d^2+e^2);
  thisConstrain = constrain /. {m1 -> Extract[p, {1}], m2 -> Extract[p, {2}], m3 -> Extract[p, {3}], 
	m4 -> Extract[p, {4}], m5 -> Extract[p, {5}]};
  {opt, assign} = Minimize[thisObj, thisConstrain, var];
  If[opt<0, violation++, ];
  Print["opt=", opt, " perm=", p, " assign=", assign, " obj=", thisObj],
  {p, Permutations[{a,b,c,d,e}]}
]

constrain = {m1<=m2, m2<=m3, m3<=m4, m4<=m5, m5==1, 5*a+4*b+3*c+2*d+e==0, 5*a+4*b+3*c-8*d-4*e==0};
var = {a,b,c,d,e};
Do[
  thisObj = Fun[p,{a,b}]+Fun[p,{a,b,c}]+Fun[p,{a,b,c,d}]+Fun[p,{a,b,c,d,e}] - 113/99*(5*a^2+4*b^2+3*c^2+2*d^2+e^2);
  thisConstrain = constrain /. {m1 -> Extract[p, {1}], m2 -> Extract[p, {2}], m3 -> Extract[p, {3}], 
	m4 -> Extract[p, {4}], m5 -> Extract[p, {5}]};
  {opt, assign}=Minimize[thisObj, thisConstrain, var];
  If[opt<0, violation++, ];
  Print["opt=", opt, " perm=", p, " assign=", assign, " obj=", thisObj],
  {p, Permutations[{a,b,c,d,e}]}
]

constrain={m1<=m2, m2<=m3, m3<=m4, m4<=m5, m5==1, 5*a+4*b+3*c+2*d+e==0, 10*a+8*b-9*c-6*d-3*e==0};
var={a,b,c,d,e};
Do[
  thisObj = Fun[p,{a,b}]+Fun[p,{a,b,c}]+Fun[p,{a,b,c,d}]+Fun[p,{a,b,c,d,e}] - 181/165*(5*a^2+4*b^2+3*c^2+2*d^2+e^2);
  thisConstrain = constrain /. {m1 -> Extract[p, {1}], m2 -> Extract[p, {2}], m3 -> Extract[p, {3}], 
	m4 -> Extract[p, {4}], m5 -> Extract[p, {5}]};
  {opt, assign}=Minimize[thisObj, thisConstrain, var];
  If[opt<0, violation++, ];
  Print["opt=", opt, " perm=", p, " assign=", assign, " obj=", thisObj],
  {p, Permutations[{a,b,c,d,e}]}
]

Print["Total number of violations =", violation];

Example 2

Consider the following hypergraph H = (V,E) with V = {a,b,c,d} and E = {e_i : i ∈ [5]}. For i≠3, edge e_i has weight 1, and edge e₃ has weight 2. Observe that every node has weight 3.

We can verify that γ₂ = 2/3 by the following code.

violation = 0;

Fun[list_, mask_] := Module[{ans},
  l = Length[mask];
  max = 0;
  min = l;
  Do[
   max = Max[Extract[Extract[Position[list, Extract[mask, i]], 1], 1], max];
   min = Min[Extract[Extract[Position[list, Extract[mask, i]], 1], 1], min];
   , {i, l}];
  ans = (Extract[list, max] - Extract[list, min])^2
]

obj = 
constrain = {m1<=m2, m2<=m3, m3<=m4, m4==1, a+b+c+d==0};
var = {a,b,c,d};
Do[
  thisObj = Fun[p,{a,b,c}]+(a-b)^2+(b-d)^2+2*(c-d)^2 - (2/3)*3*(a^2+b^2+c^2+d^2);
  thisConstrain = constrain /. {m1 -> Extract[p, {1}], m2 -> Extract[p, {2}], 
      m3 -> Extract[p, {3}], m4 -> Extract[p, {4}]};
  {opt, assign} = Minimize[thisObj, thisConstrain, var];
  If[opt<0, violation++, ];
  Print["opt=", opt, " perm=", p, " assign=", assign, " obj=", thisObj],
  {p, Permutations[{a,b,c,d}]}
]

Print["Total number of violations =", violation];

Example 3

Consider the following hypergraph with 4 vertices and 2 hyperedges each with unit weight.

We can verify the first 3 procedural minimizers.

The following code verifies γ₂ and γ₃.

violation = 0; 

Fun[list_, mask_] := Module[{ans},
  l = Length[mask];
  max = 0;
  min = l;
  Do[
   max = Max[Extract[Extract[Position[list, Extract[mask, i]], 1], 1], max];
   min = Min[Extract[Extract[Position[list, Extract[mask, i]], 1], 1], min];
   , {i, l}];
  ans = (Extract[list, max] - Extract[list, min])^2
]

constrain = {m1<=m2, m2<=m3, m3<=m4, m4==1, a+2*b+c+d==0};
var = {a,b,c,d};
Do[
  thisObj = Fun[p,{b,c,d}]+(a-b)^2 - ((5-Sqrt[5])/4)*(a^2+2*b^2+c^2+d^2);
  thisConstrain = constrain /. {m1 -> Extract[p , {1}], m2 -> Extract[p, {2}], 
	m3 -> Extract[p, {3}], m4 -> Extract[p, {4}]};
  {opt, assign} = Minimize[thisObj, thisConstrain, var];
  If[opt<0, violation++, ];
  Print["opt=", opt, " perm=", p, " assign=", assign, " obj=", thisObj],
  {p, Permutations[{a,b,c,d}]}
]

constrain = {m1<=m2, m2<=m3, m3<=m4, m4==1, a+2*b+c+d==0, (Sqrt[5]-1)*a+2*(3-Sqrt[5])/2*b-c-d==0};
var = {a,b,c,d};
Do[
  thisObj = Fun[p,{b,c,d}]+(a-b)^2 - ((11+Sqrt[5])/8)*(a^2+2*b^2+c^2+d^2);
  thisConstrain = constrain /. {m1 -> Extract[p , {1}], m2 -> Extract[p, {2}], 
	m3 -> Extract[p, {3}], m4 -> Extract[p, {4}]};
  {opt, assign} = Minimize[thisObj, thisConstrain, var];
  If[opt<0, violation++, ];
  Print["opt=", opt, " perm=", p, " assign=", assign, " obj=", thisObj],
  {p, Permutations[{a,b,c,d}]}
]

Print["Total number of violations =", violation];