Dirk Oliver Theis

Good bye!

In Zzzz on August 5, 2013 at 14:17

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. :(

Hypergraph problems connected to Boolean rank

In Matrix Theory, Problems, Research on July 31, 2013 at 10:44

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 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).)

Best combinatorial bound for extension complexity

In Matrix Theory, Problems, Research on July 29, 2013 at 17:51

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

\min \{ \mbox{rk}_+(A) \mid \mbox{supportmatrix}(A) = M \}

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

\min \{ \mbox{xc}(P) \mid S(P) = M \}

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 O(n^4)?

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.

Follow

Get every new post delivered to your Inbox.