1
$\begingroup$

This note is a continuation of Group graphs and Ramsey theory. Sub-question 1.


Let $\ X\ $ be a group, and let $\ c:\binom X2\to C\ $ be a two-coloring ($r\ $ and $\ g\ $ are the two colors). Together, they form a group graph $\ \Leftarrow:\Rightarrow\ $ for arbitrary edges $\ \alpha\ $ and $\ \gamma\in\binom X2\ $ inequality $\ c(\alpha)\ne c(\gamma)\ $ implies $\ a\cdot d\ne b\cdot c\ $ and $\ a\cdot c\ne b\cdot d\ $ for the endpoints $\ a\ $ and $\ b\ $ of edge $\ \alpha,\ $ and endpoints $\ c\ $ and $\ d\ $ of edge $\ \gamma.$

When this invariance property holds then $\ X\ $ is called a group graph.

Let's consider the following four classes of finite groups:

  • the class $\ \mathbf G\ $ of all groups;
  • the class $\ \mathbf A\ $ of all abelian groups;
  • the class $\ \mathbf C\ $ of all cyclic groups;
  • the class $\ \mathbf B\ $ of all Boolean groups ($\ x^2=1$).

Thus, for the respective variants of the Ramsey numbers we get

$$ R^\mathbf B\ \text{and}\ R^\mathbf C\ \le\ R^\mathbf A \ \le\ R^\mathbf G\ \le\ R^T \le\ R^\Gamma $$

Sub-question 2: Find/compute relations between the classical Ramsey numbers and their variants as listed above.


Addition in $\ \mathbb Z/n:=\{0\ldots n\!-\!1\}\ $ is computed mod $n$. This cyclic group admits a distance function between $\ a\ $ and $\ b\ \in\ \mathbb Z/n\ $ which is the minimum of $\ |a-b|\ $ and $\ n-|a-b|.$ The distances between pairs of different elements are all possible integers between $\ 1\ $ and $\ \lfloor\frac n2\rfloor. $ The examples of critical graphs in $\ R^\mathbf C\ $ are obtained by splitting all these distances into red and green distances so that an edge is painted red (resp. green) when the distance between its endpoints is red (resp. green). The invariance of the metric function implies the group graph condition.

Examples:   (At this time I'll ignore the Boolean class)

  • Case: clique sizes k=m=3. The classical Ramsey number is $\ R_{3\,3}=6.\ $ Group graph $\ \mathbb Z/5,\ $ with the coloring of the length of the edges $\ 1\ $ for red, and $\ 2\ $ for green, provides the critical example free of red and green 3-cliques. Thus, $$ R_{3\,3}^\mathbf C\ =\ R_{3\,3}^\mathbf A \ =\ R_{3\,3}^\mathbf G\ =\ R^T =\ R_{3\,3}^\Gamma\ =\ 6 $$

We can write similar equations in the next two examples.

  • Case: clique sizes: red 3, and green 4. The classical Ramsey number is $\ R_{3\,3}=9.\ $ Group graph $\ \mathbb Z/8,\ $ with the coloring of the length of the edges $\ 1\ $ and $\ 4\ $ for red, and $\ 2\ $ and $\ 3\ $ for green, provides the critical example free of red 3-cliques and green 4-cliques.

  • Case: clique sizes: red 3, and green 5. The classical Ramsey number is $\ R_{3\,5}=14.\ $ Group graph $\ \mathbb Z/13,\ $ with the coloring of the length of the edges $\ 1\ $ and $\ 4\ $ and $\ 6\ $ for red, and $\ 2\ $ and $\ 3\ $ and $\ 5\ $ for green, provides the critical example free of red 3-cliques and green 5-cliques.

The conclusion from the above three examples is:

$$ R_{3\,m}^\mathbf C\ =\ R_{3\,m}^\mathbf A \ =\ R_{3\,m}^\mathbf G\ =\ R^T =\ R_{3\,m}^\Gamma $$ for m=3 and 4 and 5.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.