1
$\begingroup$

Why is $R^{(3)}(s,t)=\max\{s,t\}$,if $\min\{s,t\}=3$

Did I understand something wrong ?

If a graph has $|S|$ vertices, we let $\binom{|S|}{3}$ the set of all subsets of $3$ elements of $S$.

Then we give every such 3-tuple a color.

And $R^{(3)}(s,t)$ is the number $n$ s.t. every coloring of 3-tuples $\binom{n}{3}$, using $2$ colors, say red and blue, gives either a red-homogeneous set of size $s$ or blue homogeneous set of size $t$.

for example red-homogeneous set $S'$ means that, every $3$-tuple formed by the elements of $S'$ receives the color red.

So in our case if $\min\{s,t\}\overset{\text{wlog}} =s=3$, then does this not mean that, we need an $n$ such that every coloring of the $3$-tuples of this set of size $n$ in red and blue has

  • either a subset of $s=3$ elements s.t. every $3$-tuple in it is red, or

  • a subset of $t$ elements s.t. every $3$-tuple in it is blue

don't we have $R^{(3)}(s,t)=R^{(3)}(t,s)$? Then we would only need $3$ elements, am I wrong?

EDIT: My Question is from the script below on page $70$, last paragraph before Theorem $12.4$

script

$\endgroup$
3
  • 1
    $\begingroup$ Please, give at least a thorough reference where we can find information about Ramsey numbers, that are not of daily use for most of us. $\endgroup$
    – Jean Marie
    Commented Jun 2, 2017 at 18:20
  • $\begingroup$ Where you wrote $\binom{|S|}3$ I think you meant $\binom S3.$ Outside of that, everythink you write seems OK, up to the point where you say "Then we wouild only need $3$ elements." Why do you think you would only need $3$ elements?? $\endgroup$
    – bof
    Commented Jun 3, 2017 at 2:09
  • $\begingroup$ Yes, it's symmetric. $R^{(3)}(3,t)=t$ for all $t\ge3,$ and $R^{(3)}(s,3)=s$ for all $s\ge3,$ and because of the symmetry it's enough to prove just one of those two statements, they are equivalent. So what? $\endgroup$
    – bof
    Commented Jun 3, 2017 at 2:11

1 Answer 1

Reset to default
2
$\begingroup$

You have set without loss of generality $s=3$, but this doesn't mean that $t=3$ (which is I think what you are confusing in the last line of your question). Up to the last line though, you are correct; find an $n$ such that any red/blue-coloring of the 3-tuples on $n$ vertices contains either a subset of 3 vertices with every 3-tuple red, or a subset of $t \geq 3$ vertices with every 3-tuple blue.

To help you along, assume you can't satisfy the first of the two conditions. What value of $n$ do you need to satisfy the second?

$\endgroup$
2
  • $\begingroup$ I was thinking how the first condition cannot be satisfied if you already have $3$ elements. Since every $3$-tuple gets a color, assume in this case it gets blue, but using the symmetry of the relation (in the last line) we can swap colors, and done. Or does the symmetry only holds for $2$-tuples ? $\endgroup$
    – pigeon whole
    Commented Jun 2, 2017 at 21:07
  • 1
    $\begingroup$ Once you have said "without loss of generality" you have broken the symmetry, and can no longer argue with this nonexistent symmetry. $\endgroup$
    – Bob Krueger
    Commented Jun 3, 2017 at 21:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .