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!

Homework Help: Ramsey Theory

  1. Jun 1, 2012 #1
    errrr, THEOREM >.< ... oops ....

    1. The problem statement, all variables and given/known data
    Prove that when edges of a complete heptagon are colored with two different colors, there will be at least three pure triangles.

    2. Relevant equations

    3. The attempt at a solution
    i can do two pure triangles, but not three :cry:
    pick a vertex v. It has 6 edges incident to it, at least 3 of which are the same color.
    1. Suppose 3 of these edges, connecting to vertices r, s and t, are blue. If any of the edges (r, s), (r, t), (s, t) are also blue then we have an entirely blue triangle. If not, then those three edges are all red and we have an entirely red triangle. Same goes for the other 3 edges incident to v, say red, that are connected to other 3 vertices, say a, b, c. Therefore we have 2 pure triangles.
    2. Suppose at least 4 edges connecting v to r, s, t, u are blue. Then the least amount of pure triangles connecting r,s,t,u is 0 when the internal diagonals are blue and the outside square is red. But since we have two blue diagonals, each connected to v by two blue edges, we have 2 pure triangles.

    now any ideas as far as how to get the third? :confused:
  2. jcsd
  3. Jun 1, 2012 #2
    i've been fiddling with the picture in photoshop XD cuz i'm a visual learner XD
    and i kinda see what's going on, just not sure how to put it into words, or if i'm even on the right track or if i'm over complicating this X.X

    but if there are at least 4 edges incident to v s.t. we have at most 2 pure triangles (if we connect the other two red vertices with the same color line, we're done, otherwise...), then the outsides edges r-s-t-u are all red, which means if they make up the bases of some triangles, the other two edges for each of those triangles must be different colors (since we want to try to avoid having 3 pure triangles, but seeing if we'll be forced to)
    2.JPG 3.JPG

    since we have to alternate colors, they eventually create another triangle ... so i'm convinced of that now ... just dunno how to show it properly :\

    i can also kinda see how we're forced to have the third pure triangle when we have 3 red and 3 blue edges coming out of v, but again, not sure how to put it into math form XD
    Last edited: Jun 2, 2012
  4. Jun 2, 2012 #3
    No one? XD well at least I dun feel so bad now XD
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook