Thep-intersection number of a complete bipartite graph and orthogonal double coverings of a clique

Thep-intersection graph of a collection of finite sets {S_i}_i=1ⁿ is the graph with vertices 1, ...,n such thati, j are adjacent if and only if |S_iS_j|p. Thep-intersection number of a graphG, herein denoted _p(G), is the minimum size of a setU such thatG is thep-intersection graph of subsets ofU. IfG is the complete bipartite graphK_n,n andp2, then _p(K_{n, n})(n²+(2p–1)n)/p. Whenp=2, equality holds if and only ifK_n has anorthogonal double covering, which is a collection ofn subgraphs ofK_n, each withn–1 edges and maximum degree 2, such that each pair of subgraphs shares exactly one edge. By construction,K_n has a simple explicit orthogonal double covering whenn is congruent modulo 12 to one of {1, 2, 5, 7, 10, 11}.Research supported in part by ONR Grant N00014-5K0570.