= Balancing a multipartite edge-triangle objective
{title2=$F=\sum_{i<j}a_ia_j-c\sum_{i<j<k}a_ia_ja_k$}
With two part sizes of fixed sum and all other sizes fixed, this objective has form constant plus $(1-cB)a_ia_j$, where $B$ is the sum of the other sizes. A nonpositive coefficient permits merging the pair, while a positive coefficient favours balancing it. Choose an optimum with fewest nonzero parts: all remaining coefficients are positive, and the integer sizes differ by at most one. For real sizes they are exactly equal. This explains extremizers among <Turan graphs>.
Back to article page
