1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Apr 26, 2017 #1
    there's a proof provided, but i want to know the intuition as to why it is 2^k.
     
  2. jcsd
  3. Apr 26, 2017 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    I think there is something missing in the question.
     
  4. Apr 26, 2017 #3
    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
     
  5. Apr 26, 2017 #4
    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!
     
  6. Apr 26, 2017 #5

    QuantumQuest

    User Avatar
    Gold Member

    ##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.
     
  7. Apr 26, 2017 #6
    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.
     
  8. Apr 29, 2017 #7
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: The largest n such that K_n can be expressed as the union of
Loading...