I’m moving my “blog” to blogspot. The reasons is that I find editing in WordPress a total pain and a waste of time. The new address is dirkolivertheis.blogspot.com.
I must admit, though, that WordPress looks way cooler. :(
I’m moving my “blog” to blogspot. The reasons is that I find editing in WordPress a total pain and a waste of time. The new address is dirkolivertheis.blogspot.com.
I must admit, though, that WordPress looks way cooler. :(
This post, along with my homepage/blog has moved to dirkolivertheis.blogspot.com
The Boolean rank of a 0/1-matrix M is the smallest number q of 0/1-matrices with rectangular support whose sum in the Boolean semiring (, 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 such that every edge of H is the union of some of the sets . 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.
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 . First, let us make the following trivial observation.
Lemma 0. — the generating number is at most the number of vertices.If we want to prove that is large, then singleton sets work for us: they drive the total number of sets which are needed towards the trivial upper bound . Now let us adapt the concept of generating number to forbid singleton sets.
Definition 1. Denote by the smallest number q of set 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 the hypergraph with vertex set and edge set (this is the hypergraph restricted to the complement of S, we trivially have the following:
Lemma 2. .Now, for a vertex v, denote by H.v the hypergraph with vertex set V(H) and edge set
.
Further, if is an ordering of the vertices of H, we denote by the hypergraph induced by the vertices — 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 be any ordering of the vertices of H. Then .
(As usual, denotes the transversal number.) Again, I leave the proof as an exercise. (Hint: consider the set of all generators which contain the vertex ) Let’s move to an application of Lemma 2.
We would like to determine the generating number 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 .
For the proof, we first note that each of the hypergraphs occurring in Lemma 2 has as its edge set all vertex sets of cardinality between and . Hence, you may check that the transversal number of the hypergraph occurring in Lemma 3 equals , if , and , if . In the first case, the sum in that lemma amounts to
.
The maximum in Lemma 1 thus equals
which proves the theorem.
Corollary 5. For , the generating number of the complete k-uniform hypergraph on n vertices is equal to n.
For k larger than the number in the corollary, the value of is unknown. The following upper bound is proved in arXiv:1111.0444.
Theorem 6. .
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 factor between the bounds in Theorems 5 and 6. For , this factor is needed, since (exercise!) . But but , the gap is a problem.
Problem 7. Determine the value of , when and ! |
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).) |
This post, along with my homepage/blog has moved to dirkolivertheis.blogspot.com
The following is a well-known and easy fact.
Proposition. For every 0/1-matrix M, the number
is equal to the Boolean rank of M.
For a polytope P, let xc(P) denote its extension complexity, i.e., the smallest number of facets of a polytope Q which can be mapped onto P by a projective mapping. Moreover, let S(P) denote the support matrix of the vertex-facet slack matrix of P. The proposition above motivates the following question.
Question 1. Let M be the support matrix of the vertex-facet slack matrix of a polytope. Is it true that the number
is equal to the Boolean rank of M? |
The answer is most probably “no, at least not for all P”. However, let’s look at what we get if we restrict P to a special family of polytopes. My all-time favourite: the Matching polytopes. Here Question 1 gives rise to the following.
Question 2. Is there a polytope which is combinatorially equivalent to the matching polytope and whose extension complexity is ? |
And we might want to relax that further to the following.
Question 3. Is there a polytope which is combinatorially equivalent to the matching polytope and whose extension complexity is polynomial in n? |
We know that the question corresponding to Question 3 for Max-Cut and Traveling Salesman polytopes has a negative answer — but only because the lower bound proof works combinatorially.
In general, it may be a good idea to start by looking at 3-polytopes, because in that case the realization space is comparatively easy. Some other time.