Results 1 to 4 of 4

Math Help - graph proofs

  1. #1
    Member
    Joined
    Apr 2008
    Posts
    204

    graph proofs

    (i) prove that r(a, b, 2) = r(a, b)
    (ii) prove that r(a, b, c) \leq r(a - 1, b, c) + r(a, b - 1, c) + r(a, b, c - 1) - 1
    (iii) use parts (i) and (ii) to show that r(3, 3, 3) \leq 17
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,657
    Thanks
    1607
    Awards
    1
    Quote Originally Posted by wik_chick88 View Post
    (i) prove that r(a, b, 2) = r(a, b)
    (ii) prove that r(a, b, c) \leq r(a - 1, b, c) + r(a, b - 1, c) + r(a, b, c - 1) - 1
    (iii) use parts (i) and (ii) to show that r(3, 3, 3) \leq 17
    We do not know that notation.
    Anytime you post a question be sure that you define the uncommon terms.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Apr 2008
    Posts
    204
    sorry...

    r(m, n) denotes a Ramsey number. It is the least positive integer p such that for any graph G on p vertices:

    either G contains a copy of K_{m},
    or else \overline{G} contains a copy of K_{n}.

    Note G \cup \overline{G} = K_{p} so we may restate the definition as: r(m, n) is the least positive integer p such that if we 2-colour the edges of K_{p} then either we have a mono-chromatic K_{m} or a mono-chromatic K_{n}.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Aug 2009
    Posts
    125
    Hi there
    (i) Let G be a complete graph on  r(a,b) vertices and let G be coloured with white, red and blue. If there is at least one edge coloured with blue then this edge is a blue K_2. If there's no blue edge then whole G is coloured with white and red, so it contains white K_a or red K_b. We conclude that r(a,b,2) \leq r(a,b).
    On the other hand, let H be a complete graph on r(a,b,2) vertices. If we colour it with white and red only, it has to contain white K_a or red K_b. So r(a,b) \leq r(a,b,2).

    (ii) Let n =  r(a-1,b,c) + r(a,b-1,c) + r(a,b,c-1)  - 1 and assume the edges of K_n are coloured white, red and blue. Arbitrarily pick one vertex v and consider its n-1 edges. We have: The number of white edges incident to v is greater or equal to r(a-1,b,c) OR the number of red edges incident to v is greater or equal to r(a,b-1,c) OR the number of blue edges incident to v is greater or equal to r(a,b,c-1). Can you see why?
    Spoiler:

    wait for it...
    Spoiler:

    The reason is that otherwise we'd have: The number of white edges incident to v is less or equal to r(a-1,b,c)-1 AND the number of red edges incident to v is less or equal to r(a,b-1,c)-1 AND the number of blue edges incident to v is less or equal to r(a,b,c-1)-1. Which would imply: n-1 = (the number of white edges incident to v) + (the number of red edges incident to v) + (the number of blue edges incident to v) \leq
    \leq r(a-1,b,c)-1 + r(a,b-1,c)-1 + r(a,b,c-1)-1 = n-2, a contradiction.


    So we distinguish three cases:

    1) the number of white edges incident to v is greater or equal to r(a-1,b,c),
    2) the number of red edges incident to v is greater or equal to r(a,b-1,c),
    3) the number of blue edges incident to v is greater or equal to r(a,b,c-1).

    In case 1) we can choose exactly  r(a-1,b,c) vertices connected to v by a white edge. These chosen vertices induce complete subgraph. This subgraph contains a white K_{a-1} or a red K_b or a blue K_c (because it has  r(a-1,b,c) vertices). In the first case, vertex v with this white K_{a-1} forms a white K_a.

    Cases 2) and 3) are treated analogously, we always find a white subgraph K_a or a red subgraph K_b or a blue subgraph K_c of the graph K_n. This means that we've proved that r(a,b,c) \leq n.


    (iii) You surely heard of r(3,3) = 6, so now when we know (i) and (ii) it is easy to proove (iii). Can you finish it?
    Spoiler:

    r(3,3,3) \leq r(2,3,3)+r(3,2,3)+r(3,3,2)-1 = r(3,3)+r(3,3)+r(3,3)-1 = 17
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  2. Graph connectivity proofs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 12th 2010, 12:11 PM
  3. Graph Proofs- Isomorphic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 8th 2009, 05:17 AM
  4. Replies: 0
    Last Post: April 26th 2009, 09:24 AM
  5. Replies: 3
    Last Post: October 6th 2007, 02:01 PM

Search Tags


/mathhelpforum @mathhelpforum