## ON A PROBLEM OF RAMSEY THEORY

Frasser C.E.

Ph.D. in Engineering Sciences, Odessa National Polytechnic University, Ukraine

## Abstract

In 1955, Greenwood and Gleason showed that the Ramsey number R (3, 3, 3) = 17 by constructing an edge-chromatic graph on 16 vertices in three colors with no triangles. Their technique employed finite fields. This same result was obtained later by using another technique. In this article, we examine the complete graph on 17 vertices, 𝐾17 , which can be represented as a regular polygon of 17 sides with all its diagonals. We color each edge of 𝐾17 with one of the three colors, blue, red or yellow.  The  graph  thus  obtained  is  called complete  trichromatic  graph 𝐾 17 (3) (the  superscript determines the number of colors). A triangle contained in graph 𝐾 17 (3) with edges colored with one and only one color is called monochromatic . It has been shown that for any coloring of the 𝐾 17 (3) edges, 𝐾 17 (3) contains at least one monochromatic triangle. This article examines the problem of determining the minimum number of monochromatic triangles with the same color contained in 𝐾 17 (3) .

Keywords: Ramsey theory, graph construction, monochromatic triangles, 𝐾 17 (3) .

In order to solve the aforementioned problem, construct first the graph 𝐾 16 (3) that does not contain monochromatic triangles. An example of the construction of such a graph was described for the first time in the classic research article authored by Greenwood and Gleason [2].

Let's designate the vertices of 𝐾16 with the letters O , 𝐴𝑖 , 𝐵𝑖 , 𝐶𝑖 , i = 1,…,5 (Fig.1). Let's color the  edges 𝑂𝐴1 ,…, 𝑂𝐴5 ;    𝑂𝐵 1 ,…, 𝑂𝐵5 ;    𝑂𝐶 1 ,…, 𝑂𝐶 5 with  the  colors  blue,  red  and  yellow, respectively. Let's color subgraphs 𝐾  with vertices 𝐴 5 𝑖 , 𝐵𝑖 , 𝐶𝑖 , i = 1,…,5 with the colors red and yellow, yellow and blue, blue and red. Now, let's color the edges between 𝐴𝑖 and 𝐵𝑗 , 𝐵𝑖 and 𝐶 𝑗 , 𝐶𝑖 and 𝐴𝑗 ; i , j =  1,…,5, using the convenient color so that no monochromatic triangles are formed. Such a coloring of edges 𝐴𝑖 𝐵𝑗 , i , j = 1,…,5 is obtained by joining the left and right parts of Fig. 1 so that the cylinder (Fig. 2 (a), (b)) is formed.

Using the cyclic permutation of the colors

$$b l u e \to r e d \to y e l l o w$$

we obtain the corresponding colorings for the edges 𝐵𝑖 𝐶 𝑗 , 𝐶𝑖 𝐴𝑗 , that is, if 𝐴1𝐵2 is red, then 𝐵1𝐶2 is yellow and 𝐶1𝐴2 is blue. Such a coloring guarantees the absence of monochromatic triangles with vertex O and with vertices 𝐴𝑖 and 𝐵𝑗 , 𝐵𝑖 and 𝐶 𝑗 , 𝐶𝑖 and 𝐴𝑗 ; i , j = 1,...,5.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00815v1-figure-b60c6283-a68d-41de-b396-b67cd9369054.jpg)

;

It  only  remains  to  check  that  there  are  no  monochromatic  triangles  of  the  form 𝐴𝑖 𝐵 𝐶 𝑗 𝑘 i , j , k = 1,…,5. It is easy to convince yourself of it by checking directly. Therefore, the constructed graph 𝐾 16 (3) does not contain monochromatic triangles.

We now need to show that there exists graph 𝐾 17 (3) , which contains exactly 5 monochromatic triangles of only one color. To this purpose, it should result from the graph of Fig. 3 two subgraphs 𝐾 16 (3) with  no  monochromatic triangles, in which the colors of the blue, red, and yellow edges coincide. That is only possible if when deleting vertex O (including the corresponding incident edges) from each of the two subgraphs 𝐾 16 (3) of the graph in Fig. 3, we obtain identical subgraphs 𝐾 15 (3) . As a result, we get graph 𝐾 17 (3) without one of its edges, in which there is no monochromatic triangles. Adding the missing edge and coloring it blue, red or yellow, we obtain graph 𝐾 17 (3) with five  triangles  colored  blue,  red  or  yellow,  respectively.  This  elegant  construction  is  due  to mathematician A.D. Glukhov (Kiev, Ukraine), whose description is based on the results obtained by C.B. Beliy [1]. The original proof, omitted in this article, belongs to C.B. Beliy.

## References

- 1. C.B. Beliy, Matematika Segodnya'89 (Magazine), Issue No. 5, (1989), 29. [In Russian]
- 2. R.E. Greenwood,  A.M.  Gleason,  Combinatorial  Relations  and  Chromatic  Graphs, Canadian J. Math , 7 (1955), 1-7.
Carlos E. Frasser
On a Problem of Ramsey Theory
In 1955, Greenwood and Gleason showed that the Ramsey number R(3, 3, 3) = 17
by constructing an edge-chromatic graph on 16 vertices in three colors with no
triangles. Their technique employed finite fields. This same result was
obtained later by using another technique. In this article, we examine the
complete graph on 17 vertices, K17, which can be represented as a regular
polygon of 17 sides with all its diagonals. We color each edge of K17 with one
of the three colors, blue, red or yellow. The graph thus obtained is called
complete trichromatic graph K17^(3) (the superscript determines the number of
colors). A triangle contained in graph K17^(3) with edges colored with one and
only one color is called monochromatic. It has been shown that for any coloring
of the K17^(3) edges, K17^(3) contains at least one monochromatic triangle.
This article examines the problem of determining the minimum number of
monochromatic triangles with the same color contained in K17^(3).