Ramsey number inequality problem

  • Thread starter Bingk
  • Start date
  • Tags
    Inequality
In summary, the Ramsey number inequality problem is a mathematical problem that aims to find the minimum number of vertices in a graph to guarantee the existence of either a clique or an independent set of a given size. It has wide-ranging applications in various fields and is a difficult problem to solve, with no known formula or algorithm. However, progress has been made in recent years, and it is closely related to other areas of mathematics.
  • #1
Bingk
22
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

FAQ: Ramsey number inequality problem

1. What is the Ramsey number inequality problem?

The Ramsey number inequality problem is a mathematical problem in graph theory, named after mathematician Frank P. Ramsey. It asks for the minimum number of vertices in a graph that guarantees the existence of either a clique (a subgraph where all vertices are connected to each other) or an independent set (a subgraph where no vertices are connected to each other) of a given size. In simple terms, it aims to find the smallest number of people needed at a party to ensure that either there are at least three mutual friends or at least three mutual strangers.

2. Why is the Ramsey number inequality problem important?

The Ramsey number inequality problem has wide-ranging applications in fields such as computer science, sociology, and economics. It helps us understand the structure of complex networks and has practical implications in fields such as social media, communication networks, and search engines. It also has philosophical implications, as it highlights the existence of patterns and order even in seemingly random systems.

3. How is the Ramsey number inequality problem solved?

The Ramsey number inequality problem is a difficult problem to solve, and there is no known formula or algorithm that can be used to find the exact solution for all cases. However, mathematicians have derived various upper and lower bounds for the Ramsey numbers, and there are also many computational methods and heuristics that can be used to find approximate solutions.

4. What is the current status of the Ramsey number inequality problem?

The exact values for most Ramsey numbers are still unknown. However, significant progress has been made in recent years, and the current best-known bounds are constantly being improved. Additionally, researchers continue to explore different approaches and techniques to find better approximations and solutions for this problem.

5. How does the Ramsey number inequality problem relate to other mathematical concepts?

The Ramsey number inequality problem is closely related to other areas of mathematics, including combinatorics, graph theory, and extremal set theory. It also has connections to topics such as Ramsey theory, probabilistic methods, and computational complexity theory. Studying this problem can often lead to new insights and breakthroughs in these fields.

Similar threads

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

Hot Threads

Recent Insights

Back
Top