We consider the problem of computing the second elementary symmetric
polynomial S(2,n)(X) using depth-three arithmetic circuits of the form:
Sum of Products of Linear forms. We consider this problem over several
fields and determine *exactly* the number of multiplication gates
required. The lower bounds are proved for inhomogeneous circuits where
the linear forms are allowed to have constant terms; the upper bounds
are proved in the homogeneous model. For reals and rationals the
number of multiplication gates required is exactly n-1; in most other
cases, it is ceil(n/2).
This problem is related to the Graham-Pollack theorem in algebraic
graph theory. In particular, our results answer the following question
of Babai and Frankl: what is the minimum number of complete bipartite
graphs required to cover each edge of a complete graph an odd number
of times? We show that for infinitely many n, the answer is
ceil(n/2).