A crown graph is a complete bipartite graph from which a perfect matching has been removed.

The bipartite dimension of a graph is the minimum number of complete bipartite subgraphs needed to cover all the edges of the graph.

The bipartite dimension of a crown graph with $2n$ vertices is

$\sigma(n)=\min\left\{k \hspace{0.2cm} |\hspace{0.2cm} n\leq\begin{pmatrix}k\\\lfloor k/2\rfloor\end{pmatrix}\right\}$.

This formula is described here.

My question is: how can we derive such a formula?

My actual problem is to compute the bipartite dimension of the following graph where the blue edges are removed from the crown graph. It means two perfect matchings have been removed from a complete bipartite graph.

enter image description here

Thanks for any advice!

  • 1
    $\begingroup$ What's a crown graph? What's "bipartite dimension"? (Wikipedia is anunrelaible guide to standard notation.) $\endgroup$ – Chris Godsil Jan 11 '16 at 13:06
  • $\begingroup$ @ChrisGodsil I made some edits. $\endgroup$ – user85022 Jan 11 '16 at 14:45
  • $\begingroup$ In general, which two matchings have been removed? A cycle? The covers constructed for a complete graph minus a cycle also work. mathoverflow.net/questions/227918/… $\endgroup$ – Douglas Zare Jan 11 '16 at 16:05
  • $\begingroup$ @DouglasZare Yes, I suppose that in order to obtain the matrix described in mathoverflow.net/questions/227918/…, we have to remove two perfect matchings in cycle. I am trying to see if we can adapt the quantity $\sigma(n)$ to answer the question. $\endgroup$ – user85022 Jan 11 '16 at 16:30

Let $C(n,n)$ be a crown graph with $2n$ vertices. It has two parts $X$ and $\tilde{X}$, $|X|=\tilde{X}=n$, for each $x\in X$ there exists unique $\tilde{x}\in \tilde{X}$ such that $x$ and $\tilde{x}$ are not joined.

Let $C(n,n)$ be covered by complete bipartite subgraphs $G_1,\dots G_k$. For each vertex $x\in X$ denote by $M(x)$ the set of $i$ such that $x\in G_i$. Note that edge $(x,\tilde{y})$may belong to $G_i$ if and only if $x\in G_i$, $y\notin G_i$, i.e., $i\in M(x)\setminus M(y)$. Hence the problem reduces to Sperner's lemma on the existence of $n$ subsets of $k$-set such that none of them is contained in another. It is well-known that they exist if and only if $n\leqslant \binom{k}{[k/2]}$.

  • $\begingroup$ What I don't get in your argument is why if we have $M(x) \subset M(y)$ then we have the edge between $x$ and copy of $y$ not covered? And what do you mean by "copy of $y$"? Thanks! $\endgroup$ – user85022 Jan 11 '16 at 14:40
  • 1
    $\begingroup$ Each vertex $x$ in the first part has its copy $\tilde{x}$ in the second part, which is the only vertex in the second part not joined with $x$. If $(x,\tilde{y})$ is an edge of $G_i$, then vertices $x, \tilde{y}$ belong to $G_i$, hence $y$ does not, i.e., $i\in M(x)\setminus M(y)$. $\endgroup$ – Fedor Petrov Jan 11 '16 at 15:40
  • 1
    $\begingroup$ If there exist no edge between $x$ and $\tilde{y}$, we should not cover it. Hence instead Sperner's condition $M(x)\setminus M(y)\ne \emptyset$ for all $x\ne y$ we get it not for all pairs. On the other hand, we can not in general $M(x)$ with all $\tilde{y}$, $y\notin M(x)$. Well, this is just another question. $\endgroup$ – Fedor Petrov Jan 11 '16 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.