Odd covers of graphs

Abstract

Given a finite simple graph G $G$, an odd cover of G $G$ is a collection of complete bipartite graphs, or bicliques, in which each edge of G $G$ appears in an odd number of bicliques, and each nonedge of G $G$ appears in an even number of bicliques. We denote the minimum cardinality of an odd cover of G $G$ by b2(G) ${b}_{2}(G)$ and prove that b2(G) ${b}_{2}(G)$ is bounded below by half of the rank over F2 ${{\mathbb{F}}}_{2}$ of the adjacency matrix of G $G$. We show that this lower bound is tight in the case when G $G$ is a bipartite graph and almost tight when G $G$ is an odd cycle. However, we also present an infinite family of graphs which shows that this lower bound can be arbitrarily far away from b2(G) ${b}_{2}(G)$. Babai and Frankl proposed the "odd cover problem," which in our language is equivalent to determining b2(Kn) ${b}_{2}({K}_{n})$. In this paper, we determine that b2(Kn) ${b}_{2}({K}_{n})$ is n/2 $n\unicode{x02215}2$ when 8 divide n $8| n$ and is (n+1)/2 $(n+1)\unicode{x02215}2$ when n $n$ is equivalent to 1 or -1 $-1$ modulo 8.