Results 1 to 4 of 4

Thread: graph proofs

  1. #1
    Member
    Joined
    Apr 2008
    Posts
    204

    graph proofs

    (i) prove that $\displaystyle r(a, b, 2) = r(a, b)$
    (ii) prove that $\displaystyle 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 $\displaystyle r(3, 3, 3) \leq 17$
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,743
    Thanks
    2814
    Awards
    1
    Quote Originally Posted by wik_chick88 View Post
    (i) prove that $\displaystyle r(a, b, 2) = r(a, b)$
    (ii) prove that $\displaystyle 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 $\displaystyle 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...

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

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

    Note $\displaystyle G \cup \overline{G} = K_{p}$ so we may restate the definition as: $\displaystyle r(m, n)$ is the least positive integer $\displaystyle p$ such that if we 2-colour the edges of $\displaystyle K_{p}$ then either we have a mono-chromatic $\displaystyle K_{m}$ or a mono-chromatic $\displaystyle 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 $\displaystyle 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 $\displaystyle K_2$. If there's no blue edge then whole G is coloured with white and red, so it contains white $\displaystyle K_a$ or red $\displaystyle K_b$. We conclude that $\displaystyle r(a,b,2) \leq r(a,b)$.
    On the other hand, let H be a complete graph on $\displaystyle r(a,b,2)$ vertices. If we colour it with white and red only, it has to contain white $\displaystyle K_a$ or red $\displaystyle K_b$. So $\displaystyle r(a,b) \leq r(a,b,2)$.

    (ii) Let $\displaystyle n = r(a-1,b,c) + r(a,b-1,c) + r(a,b,c-1) - 1$ and assume the edges of $\displaystyle K_n$ are coloured white, red and blue. Arbitrarily pick one vertex $\displaystyle v$ and consider its $\displaystyle n-1$ edges. We have: The number of white edges incident to $\displaystyle v$ is greater or equal to $\displaystyle r(a-1,b,c)$ OR the number of red edges incident to $\displaystyle v$ is greater or equal to $\displaystyle r(a,b-1,c)$ OR the number of blue edges incident to $\displaystyle v$ is greater or equal to $\displaystyle 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 $\displaystyle v$ is less or equal to $\displaystyle r(a-1,b,c)-1$ AND the number of red edges incident to $\displaystyle v$ is less or equal to $\displaystyle r(a,b-1,c)-1$ AND the number of blue edges incident to $\displaystyle v$ is less or equal to $\displaystyle r(a,b,c-1)-1$. Which would imply: $\displaystyle n-1 =$ (the number of white edges incident to $\displaystyle v$) + (the number of red edges incident to $\displaystyle v$) + (the number of blue edges incident to $\displaystyle v$) $\displaystyle \leq$
    $\displaystyle \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 $\displaystyle v$ is greater or equal to $\displaystyle r(a-1,b,c)$,
    2) the number of red edges incident to $\displaystyle v$ is greater or equal to $\displaystyle r(a,b-1,c)$,
    3) the number of blue edges incident to $\displaystyle v$ is greater or equal to $\displaystyle r(a,b,c-1)$.

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

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


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

    $\displaystyle 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: Sep 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: Jun 8th 2009, 05:17 AM
  4. Replies: 0
    Last Post: Apr 26th 2009, 09:24 AM
  5. Replies: 3
    Last Post: Oct 6th 2007, 02:01 PM

Search Tags


/mathhelpforum @mathhelpforum