2
$\begingroup$

Given an undirected graph $G$ with $n$ vertice and $m$ edges, can we construct $p$ complete $k_i$-partite graphs, where $p$ is finite (of course) and each vertex appears at most a constant number of times, satifying " the sum of such $p$ complete $k_i$-partite graphs is $G$ " ? Moreover, such construction can be done in poly-time ?

$\endgroup$
8
$\begingroup$

I think the answer to your first question is "no".

In particular, if you take a random bipartite graph $G=([n],[n],E)$ where $Pr[(i,j)\in E] = 1/2$ for each pair $(i,j)$, the answer is no with probability close to 1.

I am interpreting your first question as follow:

Given any graph $G$, is it always possible to find a collection of subgraphs such that

  • each subgraph is a complete $k$-partite graph for some $k$,
  • each edge in $G$ occurs in at least one of the subgraphs, and
  • each vertex in $G$ occurs in at most a constant number of the subgraphs?

Proof. Fix $n$. Let $G$ be the random graph described above.

Since $G$ is bipartite any complete $k$-partite subgraph has to be bipartite.

First, I claim that with probability $1-o(1)$, every complete bipartite subgraph of $G$ has at most $4n$ edges.

(Here's why. For any pair of subsets $L\subseteq [n]$ and $R\subseteq [n]$ with $|L\times R| \ge 4n$, the probability that the complete bipartite subgraph with edge set $L\times R$ is in $G$ is $2^{-|L\times R|} \le 2^{-4n}$. There are fewer than $2^n\times 2^n = 4^n$ such pairs $L$ and $R$, Thus, by the naive union bound, the probability that any of the corresponding subgraphs is present in $G$ is at most $4^n 2^{-4n} \le 2^{-2n}$.)

Also, with probability $1-o(1)$, the graph $G$ has at least $n^2/4$ edges.

Thus, with probability $1-o(1)$, every complete bipartite subgraph in $G$ has at most $4n$ edges, and $G$ has at least $n^2/4$ edges. Assume this happens.

Now suppose for contradiction that a collection of subgraphs with the desired properties exists. Each of the subgraphs has edge set $L\times R$ for some pair of subsets $L$ and $R$. In $G$, direct all the edges in $L\times R$ from the larger side to the smaller side (to the left if $|L|\le |R|$, and to the right otherwise). Since $|L\times R|\le 4n$, the smaller of $L$ or $R$ must have size at most $2\sqrt n$.

Since each vertex is in $O(1)$ of the subgraphs, each vertex now has $O(\sqrt n)$ edges directed out of it. But all edges are directed one way or the other, so the number of edges in $G$ is at most the number of vertices times the maximum out-degree of any vertex, that is, at most $O(n\sqrt n)$. This contradicts the graph having at least $n^2/4$ edges.

$\endgroup$

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.