Odd Covers of Complete Graphs and Hypergraphs

The `odd cover number' of a complete graph is the smallest size of a family of complete bipartite graphs that covers each edge an odd number of times. For n odd, Buchanan, Clifton, Culver, Nie, O'Neill, Rombach and Yin showed that the odd cover number of Kₙ is equal to (n+1) /2 or (n+3) /2, and they conjectured that it is always (n+1) /2. We prove this conjecture. For n even, Babai and Frankl showed that the odd cover number of Kₙ is always at least n/2, and the above authors and Radhakrishnan, Sen and Vishwanathan gave some values of n for which equality holds. We give some new examples. Our constructions arise from some very symmetric constructions for the corresponding problem for complete hypergraphs. Thus the odd cover number of the complete 3-graph Kₙ^ (3) is the smallest number of complete 3-partite 3-graphs such that each 3-set is in an odd number of them. We show that the odd cover number of Kₙ^ (3) is exactly n/2 for even n, and we show that for odd n it is (n-1) /2 for infinitely many values of n. We also show that for r=3 and r=4 the odd cover number of Kₙ^ (r) is strictly less than the partition number, answering a question of Buchanan, Clifton, Culver, Nie, O'Neill, Rombach and Yin for those values of r.