mies), there are either four mutual friends or four mutual enemies. Show that if

Question

mies), there are either four mutual friends or four mutual enemies. Show that if n is an integer with n 2, then the Ramsey number R(2, n) equals n. (Recall that Ramsey numbers were discussed after Example 13 in Section 6.2.) Show that if m and n are integers with m 2 and n 2, then the Ramsey numbers R(m, n) and R (n, m) are equal, (Recall that Ramsey numbers were discussed after Example 13 in Section 6.2.) Show that there are at least six people in California (population: 37 million) with the same three initials who were horn on the same day of the year (but not necessarily in the same year). Assume that everyone has three initials. Show that if (here are 1 00,000,000 wage earners in the United States who earn less than 1,000,000 dollars (but at least a penny), then there are two who earned exactly

Explanation / Answer

the theorem states that for any given number of coloursc, and any given integersn1,...,nc, there is a number,R(n1, ...,nc), such that if the edges of a complete graph of orderR(n1, ...,nc) are coloured withcdifferent colours, then for someibetween 1 andc, it must contain a complete subgraph of orderniwhose edges are all colouri



Let

v0be a vertex from ak14vertices. The vertices incident tov0arev1,v2,?,v13with edges coloured with either red or blue.

By Pigeonhole principle, there are at least7(kn+1=13,6?2+1=13,6+1=7) edges coloured with either blue or red. Assume it to be coloured with blue. And let these be edges{(v0,v1),(v0,v2),?,(v0,v7)}. If any of the edges betweenv1,v2,?,v7

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.