Proving Ramsey Number Theorem: R(s,t) ≤ χ(G) for Graph G

  • Thread starter Thread starter MathematicalPhysicist
  • Start date Start date
MathematicalPhysicist
Science Advisor
Gold Member
Messages
4,662
Reaction score
372
I have this next question which I am trying to resolve.
Let G=(V,E) be some graph (usually in this context threre aren't loops nor directed edges),assume that every red-blue colouring of the edges of G contains a red copy of K_s or blue copy of K_t. show that R(s,t)\le\chi(G), where R(s,t) is ramsey number and \chi(G) is vertex colouring minimum number of G.

Now I thought of proving that (1)\binom{s+t-2}{t-1}\le\chi(G)=\chi'(L(G))
where L(G) is the graph in which you identify each edge of G as a vertex and each vertex in G which is common with two edges in G as an edge in L(G); \chi'(L(G)) is the edges colouring index of L(G).
How do I show (1), I am not sure?
 
Physics news on Phys.org
I forgot to say that if I prove (1), then by Szkres-Erdos I am done.
 
Consider a vertex colouring of G with n=Chi(G) colours and take any red-blue edge colouring of K_n. If an edge in G has end-vertices coloured i and j, colour it the same as the edge ij in K_n. G must contain either blue K_s or red K_t with distinctly coloured vertices and hence K_n must contain either a blue K_s or red K_t, so Chi(G)>=R(s,t).
 
Thanks.

Easy than I thought it would be.
 
Namaste & G'day Postulate: A strongly-knit team wins on average over a less knit one Fundamentals: - Two teams face off with 4 players each - A polo team consists of players that each have assigned to them a measure of their ability (called a "Handicap" - 10 is highest, -2 lowest) I attempted to measure close-knitness of a team in terms of standard deviation (SD) of handicaps of the players. Failure: It turns out that, more often than, a team with a higher SD wins. In my language, that...
Hi all, I've been a roulette player for more than 10 years (although I took time off here and there) and it's only now that I'm trying to understand the physics of the game. Basically my strategy in roulette is to divide the wheel roughly into two halves (let's call them A and B). My theory is that in roulette there will invariably be variance. In other words, if A comes up 5 times in a row, B will be due to come up soon. However I have been proven wrong many times, and I have seen some...
Back
Top