## Pages

### Hypergraph problems connected to Boolean rank

The Boolean rank of a 0/1-matrix M is the smallest number q of 0/1-matrices $R_1,\dots,R_q$ with rectangular support whose sum in the Boolean semiring ($1+1=1$, otherwise as usual) equals M. An equivalent graph theoretical parameter is the biclique covering number: Given a bipartite graph G, find the smallest number of bicliques in G (i.e., subgraphs which are complete bipartite graphs), such that each edge of G is contained in at least one of the selected bicliques.
There is a hypergraph (or set system, if you will) parameter which is equivalent to the Boolean rank / biclique covering number. Let H be a hypergraph with vertex set V(H) and (hyper-)edge set E(H). Let us say that a generator of H is a set of vertex sets $W_1,\dots,W_q$ such that every edge of H is the union of some of the sets $W_j$. Let us further agree that the generating number of a hypergraph is the smallest number of sets in a generator.
If somebody knows the proper name for this concept, please let me know!
Biclique covering number and hypergraph generating number are equivalent concepts. Proving this is an easy exercise. (Hint: Hypergraphs and bipartite graphs are equivalent concepts anyway, start from there. Consider only bicliques which are maximal in an appropriate sense.)
This was really easy. But let us make a connection to a more familiar hypergraph concept, namely transversals. It is not surprising that the biclique covering number / hypergraph generating number are transversal numbers of suitably defined hypergraphs. Slightly more sophisticated, though, is the following.

Hypergraph transversals and lower bounds for hypergraph generating number
I will use notation and terminology of the hypergraph generating number, which is more natural in this context.  As usual, we are hunting for lower bounds.  Let us denote the generating number of H by $\gamma(H)$.  First, let us make the following trivial observation.
Lemma 0.  $\gamma(H) \le |H|$ --- the generating number is at most the number of vertices.
If we want to prove that $\gamma(H)$ is large, then singleton sets $W_j$ work for us: they drive the total number of sets which are needed towards the trivial upper bound $|H|$.  Now let us adapt the concept of generating number to forbid singleton sets.
Definition 1.  Denote by $\gamma_2(H)$ the smallest number q of set $W_1,\dots,W_q$ of at least two elements, such that every edge of H is the union of some of these sets.
Obviously, for this number to be finite, we need that H has no singleton edges.  Letting, for a vertex set S denote $H\setminus S$ the hypergraph with vertex set $V(H)\setminus S$ and edge set $\{ e\setminus S \mid e\in E(H)\}$ (this is the hypergraph restricted to the complement of S, we trivially have the following:
Lemma 2.  $\gamma(H) = \min_{S\subset V(H)} \; \bigl( |S| + \gamma_2(H\setminus S) \bigr)$.
Now, for a vertex v, denote by H.v the hypergraph with vertex set V(H) and edge set
$E(H.v) := \bigl\{ e\setminus\{v\} \bigm| e\in E(H), v\in e \bigr\}$.
Further, if $v_1,\dots,v_n$ is an ordering of the vertices of H, we denote by $H_r$ the hypergraph induced by the vertices $v_r,\dots,v_n$ -- i.e., the hypergraph with this vertex set, and with all edges of H which are completely contained in that set.  The following is the connection between generating number and hypergraph transversals.
Lemma 3.  Let $v_1,\dots,v_n$ be any ordering of the vertices of H.  Then  $\gamma_2(H) \ge \sum_{r=1}^n \tau( H_r.v_{r+1})$.
(As usual, $\tau$ denotes the transversal number.)  Again, I leave the proof as an exercise.  (Hint: consider the set of all generators $W_j$ which contain the vertex $v_r$)  Let's move to an application of Lemma 2.

The generating number of complete uniform hypergraphs
We would like to determine the generating number $\gamma_{n,k}$ of the complete k-uniform hypergraph on n vertices.  Here, k may depend on n.  In this paper, we prove the following.
Theorem 4. The generating number of the complete k-uniform hypergraph on n vertices is at least $\min\bigl(n, \; \; (n-k+2)(n-k+1)/2\bigr)$.
For the proof, we first note that each of the hypergraphs $H\setminus S$ occurring in Lemma 2 has as its edge set all vertex sets of cardinality between $k-|S|$ and $k$.  Hence, you may check that the transversal number of the hypergraph $H_r$ occurring in Lemma 3 equals $\max(0, n-r-k+2)$, if $k-|S| \ge 2$, and $\infty$, if $k-|S| \le 1$.  In the first case, the sum in that lemma amounts to
$(n-k+2)(n-k+1)/2$.
The maximum in Lemma 1 thus equals
$\min\Bigl(n, \;\; \min_{s=0,\dots,k-2} \; s + (n-k+2)(n-k+1)/2 \Bigr)$ $= \min\bigl( n, \;\; (n-k+2)(n-k+1)/2 \bigr)$
which proves the theorem.
Corollary 5.  For $k\le n - (\sqrt{8n+1}-3)/2$, the generating number of the complete k-uniform hypergraph on n vertices is equal to n.
For larger than the number in the corollary, the value of $\gamma$ is unknown.  The following upper bound is proved in arXiv:1111.0444.
Theorem 6.  $\gamma_{n,k} \le (n-k+1)^2 \log n$.
The proof uses a simple probabilistic argument, and we omit it here (see Lemma 3.3. in said paper).  What is clear, is that for fast growing k there is a $\log n$ factor between the bounds in Theorems 5 and 6.  For $k = n - O(1)$, this factor is needed, since (exercise!) $\gamma_{n,n-\ell} = \Omega_\ell (\log n)$.  But $n-k \to \infty$ but $n-k = o(\sqrt n)$, the gap is a problem.
 Problem 7.  Determine the value of $\gamma_{n,k}$, when $n-k \to \infty$ and $n-k = o(\sqrt n)$!
The general approach using Lemmas 2 and 3 seems to lend itself to study the generating number of random hypergraphs, too.
 Problem 8.  Determine the generating number of a random k-uniform hypergraph on n vertices! (With, say, edges chosen independently with probability p = p(n).)