ABSTRACT
It is known that the complete multigraph λKn cannot be edge-partitioned into fewer than n-1 bicliques (complete bipartite subgraphs). We conjecture that for each given λ, this lower bound is attained for all sufficiently large n. For some parameter pairs (λ,n), exact partitions (that is, partitions by exactly n-1 bicliques) are related to other combinatorial structures such as balanced weighing matrices and affine designs. Exact partitions for larger n are obtained from these by a simple recursion; this settles the conjecture for infinitely many λ, including all λ ≤ 18. Exact partitions in which the bicliques are all isomorphic are also examined. This leads us to consider balanced bipartite designs and a bipartite analogue of difference sets.
