Ramsey number inequality problem

  • Thread starter Thread starter Bingk
  • Start date Start date
  • Tags Tags
    Inequality
Click For Summary
SUMMARY

The Ramsey number inequality R(p,q) ≤ (p+q-2 choose p-1) is established as a key result in combinatorial mathematics. The discussion emphasizes the use of induction on the inequality R(p,q) ≤ R(p-1,q) + R(p,q-1) to prove this result. Initial validation for the base case of p=q=1 is confirmed, but participants express challenges in deriving the combination from the induction hypothesis. The link provided leads to additional resources for further understanding.

PREREQUISITES
  • Understanding of Ramsey theory and its applications.
  • Familiarity with mathematical induction techniques.
  • Knowledge of combinatorial notation, specifically binomial coefficients.
  • Basic concepts of graph theory related to Ramsey numbers.
NEXT STEPS
  • Study the principles of mathematical induction in combinatorial proofs.
  • Explore advanced topics in Ramsey theory, focusing on R(p,q) properties.
  • Learn about binomial coefficients and their applications in combinatorial mathematics.
  • Review graph theory fundamentals to understand the implications of Ramsey numbers.
USEFUL FOR

Mathematicians, students of combinatorics, and anyone interested in advanced graph theory and Ramsey theory applications.

Bingk
Messages
22
Reaction score
0
Prove that
[itex]R(p,q) \leq \left(\stackrel{p+q-2}{p-1}\right)[/itex]
where [itex]p[/itex] and [itex]q[/itex] are positive integers

I'm supposed to use induction on the inequality [itex]R(p,q) \leq R(p-1,q) + R(p,q-1)[/itex], but I'm having difficulty there.

How do I go about doing this? I can show it's true for [itex]p=q=1[/itex].
But, I can't see how I get the combination in the first inequality from an induction on the second inequality (which doesn't contain a combination) ...
 
Physics news on Phys.org

Similar threads

Inner Product, Triangle and Cauchy Schwarz Inequalities
  • · Replies 5 ·
Replies
5
Views
4K
Direct Proof that every zero of p(T) is an eigenvalue of T
  • · Replies 24 ·
Replies
24
Views
4K
Verify Green's Formula for a Simple DE
  • · Replies 1 ·
Replies
1
Views
1K
True or false questions about Divergence and Curl
  • · Replies 1 ·
Replies
1
Views
1K
Proof that e is irrational using Taylor series
  • · Replies 2 ·
Replies
2
Views
3K
Does this series converge uniformly?
  • · Replies 7 ·
Replies
7
Views
2K
Triangle Inequality: use to prove convergence
  • · Replies 9 ·
Replies
9
Views
3K
Congruence and Primes: Proving the Order of an Integer Modulo a Prime
  • · Replies 4 ·
Replies
4
Views
2K
Markov's Inequality for Geometric Distribution.
  • · Replies 2 ·
Replies
2
Views
4K
Can Discrete Logarithms Be Added in Modular Arithmetic?
  • · Replies 16 ·
Replies
16
Views
2K