Theorem 2: a tree meeting exactly one endpoint of gives EC&R assignments of class for every partition of its nodes
ProvedNetBilinear.theorem_2Let be a finite network without self-loops, with tail and head of each arc (parallel arcs allowed, no connectivity assumed), and let be its undirected variant. Let be a tree in with node set , let be an arc incident to exactly one node of , and let be a partition of (, ; either part may be empty).
Then:
- if , then is an EC&R assignment for class-;
- if , then is an EC&R assignment for class-;
- if , then is an EC&R assignment for class-;
- if , then is an EC&R assignment for class-.
Here is an EC&R assignment for : the rows in are multiplied by , those in by , the base equality by , with some nonnegative weights for which (C1) at least bilinear terms are canceled and (C2) every used constraint has a canceled term.
Together with Proposition 2 of the paper (every non-trivial facet comes from such a tree), this gives a graphical description of all EC&R assignments for one variable: trees of the network that contain exactly one end of the base arc generate the cutting planes of the convex hull of the bilinear set.
Formalization Note The network is Network V A with tail, head and loopless; is the SimpleGraph G.underlying, and the tree is a subgraph T with T.verts = Ĩ whose induced graph is a tree. Rows of the augmented incidence matrix are pairs with ; rowsWith s X is .
Differences from the source:
- reading: a network G = (V,A) (self-loops not mentioned) → Network has the field loopless: no arc is a self-loop; reason: a node-arc incidence matrix (p.4) has no self-loop column; for a loop l at a node v ∈ Ĩ, l is incident to exactly one node and h(l) ∈ Ĩ, but y₁x_l occurs only in the base equality and never cancels, so (C2) fails
- encoding: T̄ a tree in the (multi)graph Ḡ with node set Ĩ → a subgraph T of the SimpleGraph G.underlying with T.verts = Ĩ and T.coe.IsTree; reason: a tree on Ĩ exists in the multigraph Ḡ iff one exists in its simple collapse; same instances
- encoding: l is incident to exactly one node of T̄ → Xor (t(l) ∈ Ĩ) (h(l) ∈ Ĩ); reason: equivalent since t(l) ≠ h(l)
- encoding: EC&R assignment [I₁,…,I_m, Ī | J, J̄] (p.3) → the reduced m = 1 form [I₁, Ī] (J = J̄ = ∅), rows V × Sign, weights γ, θ ≥ 0; reason: Remark 1 (p.5) reduces the m = 1 assignment to [I₁, Ī], the form Theorem 2 writes; (C1), (C2) are those of p.3 with J = J̄ = ∅
- reading: a bilinear term is canceled "(i.e., their coefficient becomes zero)" → the term is created (nonzero contribution) by some used constraint and its aggregated coefficient is 0; reason: (C2) speaks of terms "created" and then "canceled"; counting terms that never appear would make (C1) hold for free
import Mathlib import Definitions.Def_NetBilinear_Network import Definitions.Def_NetBilinear_IsECRAssignmentOne import Definitions.Def_NetBilinear_Network_IsECRAssignment
namespace NetBilinear
/-- **Theorem 2: every tree meeting exactly one endpoint of `l` gives EC&R assignments of class
`l±` for every partition of its nodes.**
Khademnia & Davarnia, *Convexification of Bilinear Terms over Network Polytopes*,
arXiv:2302.14151v2, Theorem 2, p.7: "Consider set S1 with Ξ that represents the network
polytope corresponding to the network G = (V,A). Let T̄ be a tree in Ḡ with the node set Ĩ ⊆ V,
and let l ∈ A be an arc that is incident to exactly one node of T̄. Then, for any partition Ĩ1
and Ĩ2 of Ĩ (i.e., Ĩ1 ∩ Ĩ2 = ∅ and Ĩ1 ∪ Ĩ2 = Ĩ), we have that
(i) if h(l) ∈ Ĩ, then [{i+}i∈Ĩ1, {i−}i∈Ĩ2] is an EC&R assignment for class-l+,
(ii) if h(l) ∈ Ĩ, then [{i−}i∈Ĩ1, {i+}i∈Ĩ2] is an EC&R assignment for class-l−,
(iii) if t(l) ∈ Ĩ, then [{i−}i∈Ĩ1, {i+}i∈Ĩ2] is an EC&R assignment for class-l+,
(iv) if t(l) ∈ Ĩ, then [{i+}i∈Ĩ1, {i−}i∈Ĩ2] is an EC&R assignment for class-l−."
Hypotheses (those of Theorem 2, p.7): `G` is a finite network without self-loops, `T` is a
tree in `Ḡ` (a subgraph of `G.underlying` whose induced graph `T.coe` is a tree) with node set
`Ĩ = Itil`, the arc `l` is incident to exactly one node of `T` (`Xor`), and `(Ĩ₁, Ĩ₂) =
(I1, I2)` is a partition of `Ĩ` (either part may be empty).
**Formalization Note.** "EC&R assignment" is the reduced `m = 1` form `[I₁, Ī]` of Remark 1
(p.5), `Network.IsECRAssignment`: disjoint row sets with some nonnegative weights satisfying
(C1) and (C2). The first slot `I₁` (rows multiplied by `y₁`) and the second `Ī` (rows
multiplied by `1 − y₁`) are `rowsWith s X`, the rows `i^s`, `i ∈ X`. The network has no
self-loops (field `loopless`): for a loop `l` at a node of `Ĩ` the statement is false. -/
theorem theorem_2 {V A : Type*} [Fintype V] [DecidableEq V] [Fintype A] [DecidableEq A]
(G : Network V A) (Itil : Finset V) (T : G.underlying.Subgraph)
(hT : T.verts = (Itil : Set V)) (hTree : T.coe.IsTree) (l : A)
(hl : Xor (G.tail l ∈ Itil) (G.head l ∈ Itil))
(I1 I2 : Finset V) (hdisj : Disjoint I1 I2) (hunion : I1 ∪ I2 = Itil) :
(G.head l ∈ Itil →
G.IsECRAssignment l .pos (rowsWith .pos I1) (rowsWith .neg I2)) ∧
(G.head l ∈ Itil →
G.IsECRAssignment l .neg (rowsWith .neg I1) (rowsWith .pos I2)) ∧
(G.tail l ∈ Itil →
G.IsECRAssignment l .pos (rowsWith .neg I1) (rowsWith .pos I2)) ∧
(G.tail l ∈ Itil →
G.IsECRAssignment l .neg (rowsWith .pos I1) (rowsWith .neg I2)) := by sorry
end NetBilinear
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.