Graham And Pollock (1971)

Notation: $[n] = \{1, 2, \ldots, n \}$

Main Result#

The result is due to R. L. Graham and H. O. Pollak, “On the Addressing Problem for Loop Switching” (1971).

For $n = 4$, we get this picture. Note that each sub-graph is bi-partite, and complete. No edge is re-used. So we have decomposed $K_4$ into edge-disjoint bi-partite cliques.

The general algorithm is the following, for all $i \in [n]$,

$$A_i = \{i\} \qquad B_i = \{i+1, \ldots, n\}$$ Starting at $i=1$, incrementally remove all edges incident on vertices in $A_i$ from $K_n$ and add them to $A_i \cup B_i$. Then continue the process from what is left in the edge set.

Proof: Let $t \in \Naturals$ denote the minimum number of cliques. Let $\vec{x}:= (x_1, \dots, x_n)$ denote variables corresponding to each vertex of $K_n$. Define equations

$$ \begin{align*} S(\vec{x}) &:= \sum_{1 \leq i < j \leq n} x_i x_j \\[10pt] T(\vec{x}) &:= \sum_{i \in [n]} x_i^2 \\ \end{align*} $$

It is algebraic fact that for all $\vec{x} \in \mathbb{R}^n$ $$ \begin{align} T(x) = \Big(\sum_{i \in [n]} x_i\Big)^2 - 2S(\vec{x}) \tag{a}\label{eq:main} \\[10pt] \end{align} $$

Now if we assume $t = n-2$ we will show there exits an $\vec{z} \in \mathbb{R}^n$ such that the above equation does not hold, but that is impossible, so $t > n-2$.

Assume $t = n-2$. For each $i \in [n-2]$, let $A_i$ and $B_i$ denote the left and right vertices of the $i$’th bipartite clique. As the cliques are edge-disjoint, we have

$$ S(x) := \sum_{k=1}^t \left(\sum_{i \in A_k}x_i\right)\left(\sum_{j \in B_k}x_j\right) := \sum_{k=1}^t R_k(\vec{x}) L_k(\vec{x}) $$

Define constraints $$ \begin{align*} L_0(\vec{x} &:= \sum_{i \in [n]} x_i = 0 \\[10pt] L_k(\vec{x})&:= \left(\sum_{i \in [n]}\mathbb{1}\left[x_i \in A_k\right]\right) = 0 \quad \forall k \in [n-2]\
\end{align*} $$

This is actually giving us a system of $n-1$ equations in $n$ variables (an under determined system).

Let $M$ denote the above matrix. As we have an under-determined system, we has a solution $\vec{z} \neq \vec{0}$ such that $M\vec{z} = 0$ (coz the kernel of $M$ cannot be empty).

Now use $\vec{z}$ in Equation $\eqref{eq:main}$. The RHS is zero. The LHS cannot be zero. Impossible. So $t = n -2$ not possible.