The largest n such that K_n can be expressed as the union of

[Terrell]

there's a proof provided, but i want to know the intuition as to why it is 2^k.

 

[mfb]

I think there is something missing in the question.

 

[Terrell]

I think there is something missing in the question.

The largest n such that K_n can be expressed as the union of bipartite graph is 2^k where k is the number of bipartite graphs

 

[amilapsn]

Plug in some values,
Draw some examples,
Although it can't be done,
Try to get some counter examples..
And ah ha!
In a moment or two,
You'll get the intuition!

 

[QuantumQuest]

there's a proof provided, but i want to know the intuition as to why it is 2^k.

$K_n$ is a complete graph and the theorem claims that this can be expressed as a union of $k$ bipartite graphs if and only if $n\leq 2^k$.

So, in order to get a more intuitive view, I'd advise to solve for $k$ and see the minimum number of bipartite graphs sufficient to cover $K_n$.
You can take some values for $k$ and see where it goes, doing some required representations along the way. The gist of the theorem is that if the inequality gets violated there can't be a coverage of $K_n$ with $k$ bipartite graphs.

 

[Terrell]

$K_n$ is a complete graph and the theorem claims that this can be expressed as a union of $k$ bipartite graphs if and only if $n\leq 2^k$.

So, in order to get a more intuitive view, I'd advise to solve for $k$ and see the minimum number of bipartite graphs sufficient to cover $K_n$.
You can take some values for $k$ and see where it goes, doing some required representations along the way. The gist of the theorem is that if the inequality gets violated there can't be a coverage of $K_n$ with $k$ bipartite graphs.

i did some calculations but it still just won't sit well with me. i did some research and found that there's 2^k colors since each bipartite graph have 2 colors and there are k such bipartite graphs. after some thinking, it became obvious that the number of vertices should be less than 2^k because each vertex can appear in more than one bipartite graph thus it can have more than 1 color. lastly, for the equality case, there are calculations that did satisfy that ,but i seem to lack the understanding as to why.

 

[Deedlit]

It seems like you've hit the nail on the head: a graph can be represented as a union of k bipartite graphs if and only if it is 2^k-colorable.

For one direction, say a graph is a union of k bipartite graphs. For each bipartite graph we can 2-color it. Then for the original graph, for each vertex we note what color it is in each of the bipartite graphs, and the final color is the ordered k-tuple of binary colors, so that is a 2^k-coloring. Going the other direction, if a graph is 2^k colorable, we can arbitrarily assign each of the 2^k colors to an ordered k-tuple of binary colors. Then we define the ith bipartite graph by saying vertices u and v are connected if and only if they are connected in the original graph and the ith members of their k-tuples are different. So the graph is a union of k bipartite graphs.

I would say the intuition is basically the notion of product coloring; if I can color G with g colors and H with h colors, I can color the union with gh colors by looking at the product coloring. Repeating the process, if G_1, G_2, ..., G_k can be colored with g_1, g_2, ..., g_k colors, then the union of the G_i's can be colored with g_1 g_2 ... g_k colors by taking the product coloring.