Almost balanced ordered biclique covering of graphs

Abstract

Let $f(n,k)$ be the minimum size of a collection of bicliques such that (i) every edge of the complete graph $K_n$ is covered by at least one and at most $k$ bicliques in the collection, and (ii) for each edge $\{u,v\}$, the number of bicliques in which $u$ appears in the first class and $v$ in the second class differs by at most one from the number of bicliques in which $u$ appears in the second class and $v$ in the first class. For $k=1$, $f(n,k)$ reduces to the biclique partition number of $K_n$, and the Graham-Pollak theorem gives $f(n,1)=n-1$. For $k=2$, $f(n,k)$ is the ordered biclique partition number of $K_n$, for which it is known that $c_1{n}^{1/2}\le f(n,2)\le c_2{n}^{1/2+o(1)}$ for some positive constants $c_1$ and $c_2$. In this note, we give almost tight bounds for $f(n,k)$ for fixed $k\ge 2$: \[ (1+o(1))c_1(k)\cdot n^{\frac{1}{\lceil k/2\rceil+1}} \le f(n,k) \le (1+o(1))c_2(k)\cdot n^{\frac{1}{\lfloor k/2\rfloor+1}+o(1)}, \] where $c_1(k)$ and $c_2(k)$ are positive constants.

9 pages