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

  • Context: Graduate 
  • Thread starter Thread starter MathematicalPhysicist
  • Start date Start date
Click For Summary

Discussion Overview

The discussion revolves around proving the Ramsey number theorem, specifically the inequality R(s,t) ≤ χ(G) for a graph G. Participants explore the relationship between edge colorings and vertex colorings in the context of Ramsey theory, focusing on the conditions under which certain complete subgraphs appear in colored graphs.

Discussion Character

  • Exploratory
  • Mathematical reasoning

Main Points Raised

  • One participant presents a question about proving the inequality R(s,t) ≤ χ(G) and suggests that showing a specific combinatorial inequality could lead to a solution.
  • Another participant mentions that proving the combinatorial inequality would allow them to conclude the proof using a known result by Szkres-Erdos.
  • A third participant describes a method involving vertex colorings of G and edge colorings of a complete graph K_n, arguing that the presence of certain colorings implies a relationship between χ(G) and R(s,t).
  • One participant expresses relief that the problem seems easier than initially thought after receiving feedback.

Areas of Agreement / Disagreement

The discussion does not appear to reach a consensus, as participants are exploring different approaches and proofs without confirming a definitive solution to the problem.

Contextual Notes

Participants reference specific combinatorial inequalities and theorems, but the discussion does not resolve the mathematical steps or assumptions necessary for the proofs presented.

Who May Find This Useful

Readers interested in Ramsey theory, graph theory, and combinatorial mathematics may find the discussion relevant.

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 [tex]K_s[/tex] or blue copy of [tex]K_t[/tex]. show that [tex]R(s,t)\le\chi(G)[/tex], where R(s,t) is ramsey number and [tex]\chi(G)[/tex] is vertex colouring minimum number of G.

Now I thought of proving that [tex](1)\binom{s+t-2}{t-1}\le\chi(G)=\chi'(L(G))[/tex]
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); [tex]\chi'(L(G))[/tex] 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.
 

Similar threads

Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
Replies
3
Views
4K
  • · Replies 21 ·
Replies
21
Views
2K
  • · Replies 0 ·
Replies
0
Views
1K
  • · Replies 2 ·
Replies
2
Views
3K
Replies
2
Views
3K
  • · Replies 0 ·
Replies
0
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 2 ·
Replies
2
Views
4K