I understand why R(3,3) is equal to 6 since we have a clique of 3 in a graph of 6 vertices. What I don't understand is that by definition of Ramsay number it says that for a R(r,s) we have to find a clique of either 3 or 4 in size. In this case, we can find a clique of 3 in a graph of 6 nodes unconditionally. Could someone explain to this hopeless student why R(3,4) = 9?
$\begingroup$
$\endgroup$
2
-
7$\begingroup$ You are misunderstanding the definition of R(r,s). The definition of R(3,4) is that for any coloring of edges of a complete on this many vertices with red and blue, we will have either a red clique on 3 vertices or a blue clique on 4 vertices. The reason this needn't be the same as R(3,3) is that the colored graph may contain a blue clique on 3 vertices, but no red clique on 3 vertices, or blue clique on 4 vertices. Indeed, it might be instructive for you to find such a coloring of a complete graph on 6 vertices. $\endgroup$– WojowuDec 25, 2020 at 19:49
-
$\begingroup$ I don't really understand since it is possible to find a clique of 4 nodes on K_6 where as you say it isn't possible which makes me slightly confused. $\endgroup$– a_confused_studentDec 25, 2020 at 20:02
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
For $R(3,4)$ you must find either a clique of size $3$ or an independent set of size $4$. The graph
* * *
| | |
* * *
on $6$ vertices has neither a clique of size $3$ nor an independent set of size $4$. Every set of $3$ vertices contains two that are not adjacent, and every set of $4$ vertices contains two that are adjacent.
answered Dec 25, 2020 at 19:51
-
$\begingroup$ so from what i understand R(r,s) means that if there is an r clique there must therefore be an independent set of size s? $\endgroup$ Dec 25, 2020 at 20:03
-
2$\begingroup$ @a_confused_student: No, $R(r,s)$ is the smallest $n$ such that every graph on $n$ vertices has either an $r$-clique or an independent set of size $s$ (or both). $\endgroup$ Dec 25, 2020 at 20:20
-
$\begingroup$ but in the example given we have an independent set of size 3 and so for R(3,4) we can say that for n= 6 we satisfy the definition you gave. I'm really sorry for giving so much trouble i'm really confused with all these definitions haha $\endgroup$ Dec 25, 2020 at 20:49
-
$\begingroup$ @a_confused_student: No, it does not satisfy that definition. It does not have a $3$-clique, and it does not have an independent set of size $4$. You cannot interchange the two numbers. $\endgroup$ Dec 25, 2020 at 20:56