# Random Cyclic Triangle-Free Graphs of Prime Order

Authors: Yu Jiang; Meilian Liang; Yanmei Teng; Xiaodong Xu
Journal: Journal of Mathematics
 (2021)

---

## Abstract

Cyclic triangle-free process (CTFP) is the cyclic analog of the triangle-free process. It begins with an empty graph of ordern and generates a cyclic graph of order n by iteratively adding parameters, chosen uniformly at random, subject to the constraint that no triangle is formed in the cyclic graph obtained, until no more parameters can be added. The structure of a cyclic triangle-free graph of the prime order is different from that of composite integer order. Cyclic graphs of prime order have better properties than those of composite number order, which enables generating cyclic triangle-free graphs more efficiently. In this paper, a novel approach to generating cyclic triangle-free graphs of prime order is proposed. Based on the cyclic graphs of prime order, obtained by the CTFP and its variant, many new lower bounds on R3,t are computed, including R3,34≥230, R3,35≥242, R3,36≥252, R3,37≥264, R3,38≥272. Our experimental results demonstrate that all those related best known lower bounds, except the bound on R3,34, are improved by 5 or more.


---

## Body

## 1. Introduction

Ramsey theory [1] has played an important branch in combinatorics, which spans numerous diverse areas of mathematics. Many research efforts have been devoted into computing Ramsey numbers and their generalizations [2–5].LetS be a set of integers S⊆1,…,⌊n/2⌋ (n∈ℤ+ and n≥5), a graph with the vertex set V=1,…,n and the edge set E=x,y|minx−y,n−x−y∈S is a cyclic graph of order n, namely GnS. S is the parameter set of GnS. Let s and t be two positive integers, the Ramsey number for s and t, denoted by Rs,t, is the minimum positive integer N such that every graph of order N contains either an s-clique or a t-independent set. There are many results and open problems in Ramsey theory in terms of computing lower bounds for Ramsey numbers (see [6]).The Ramsey numberR3,t is an important topic in Ramsey theory. In [7], Calkin et al. gave theoretical motivation for searching for lower bound for Ramsey numbers based on cyclic graphs of prime order, and provided additional computational evidence that primes tend to perform better than composites. The analysis in [7] does not focus on Ramsey numbers of form R3,t. For Rs,t, in [7] it was shown that standard expected value arguments cannot be used to give bounds on Rs,t that are exponential in mins,t, but in [8] Alon and Orlitsky proved by more sophisticated arguments that random cyclic graphs nonetheless give bounds on Rk,k of order ek.The triangle-free process is an important tool in studying the asymptotic lower bound onR3,t. The triangle-free process was used in studying the asymptotic lower bound for R3,t in [9, 10]. Cyclic triangle-free process (CTFP) is the cyclic analog of the triangle-free process, which is used to generate cyclic graphs of a certain order. To generate a cyclic graph of order n, the process starts with an empty graph of order n and iteratively adding random parameters, chosen uniformly at random, conformed to the constraint that no triangle is formed in the obtained cyclic graph, until no more parameters can be added [11].In our previous work [11], CTFP was applied to study lower bounds on R3,t. Because of the symmetry of cyclic graphs, it is easier to compute the independence numbers of cyclic graphs than those of non-cyclic graphs with the same orders and edge density. In this paper, the previous work is extended by including an approach to generating cyclic triangle-free graphs of prime order. The experimental results demonstrate that generation of cyclic triangle-free graphs is much more efficient compared to the previous work [11].By employing our approach, it is feasible to generate large amount of cyclic triangle-free graphs and improve some previous best known lower bounds onR3,t, including R3,42≥312, R3,44≥320, R3,45≥337, R3,46≥348,R3,47≥360,R3,49≥376 and R3,52≥401.The remaining parts of this paper are organized as follows. In Section2, definitions of Ramsey numbers, as well as some known results on cyclic triangle-free graphs and R3,t, are introduced. The sizes of the parameter sets of cyclic triangle-free graphs of prime order obtained by the CTFP are studied in Section 3. Furthermore, new lower bounds on R3,t for small t are given in Section 4. Section 5 concludes the paper, and discusses a problem on cyclic triangle-free graphs and R3,t.


## 2. Preliminaries

In this section, we firstly introduce some basic concepts and notations used in this paper. Then, some basic known results onR3,t are presented. Finally, cyclic triangle-free process (CTFP) is discussed in details.


### 2.1. Definitions and Notations

All graphs considered in this paper are finite and undirected graphs. The complete graph of ordern (n∈ℤ+) is denoted by Kn. K3 represents a triangle. For a positive integer d, if every vertex in G is adjacent to d vertices, then G is called d-regular. The clique number of graph G, denoted by clG, is the cardinality of the largest clique in G. The independence number of graph G, denoted by αG, is the cardinality of the largest independent set in G. A clique of order k is called a k-clique, and an independent set of order k is called a k-independent set.Lets and t be two positive integers, the Ramsey number Rs,t is the smallest positive integer n such that every graph of order n contains either an s-clique or a t-independent set. In accordance with the well-known Ramsey theorem [12], it is known that Rs,t is finite. An s,t-graph is a graph that contains neither an s-clique nor a t-independent set. Therefore there is an s,t-graph of order Rs,t−1, but there is not an s,t-graph of order Rs,t.The triangle-free process begins withEn, an empty graph of order n, and iteratively adds edges chosen uniformly at random subject to the constraint that no triangle is formed, until no more edge can be added. The triangle-free process ends with a maximal triangle-free graph. The cyclic triangle-free process, i.e., CTFP, begins with En, and generate a cyclic graph of order n by iteratively adding parameters, chosen uniformly at random, subject to the constraint that no triangle is formed in the cyclic graph obtained, until no more parameters can be added.For any real numbera, we use ⌊a⌋ to designate the largest integer that is smaller than or equal to a. Similarly, ⌈a⌉ is used to designate the smallest integer that is larger than or equal to a. Given an integer n≥5, suppose S⊆1,2,…,⌊n/2⌋, and let G be a graph with the vertex set VG=1,…,n and the edge set EG=x,y|minx−y,n−x−y∈S, a graph G is called a cyclic graph of order n, namely GnS. S is called the parameter set of GnS.


### 2.2. Some Basic Known Results onR3,t and the Triangle-Free Process

AlthoughR3,t is simple among Ramsey numbers Rs,t, it can be difficult when t becomes large. The best known asymptotic lower bound on R3,t is R3,t≥1/4+o1t2/logt, obtained by Bohman and Keevash [9] in 2013 and by Pontiveros et al. [10] independently and simultaneously. In 2020, the work of [10] was updated and published as [13]. The triangle-free process was used in both [9, 10]. This asymptotic lower bound on R3,t was obtained by proving the following theorem.Theorem 1 ([9, 10]).
LetG be the maximal triangle-free graph of order n at which the triangle-free process terminates. With high probability, G has independence number at most 1+o12nlogn.The best known asymptotic lower bound onR3,t, given in [9, 10], is far from the best known upper bound 1+o1t2/logt, which was proved by Shearer in [14]. The exact value of R3,t is known only for positive integer t≤9. For larger small positive integer t≤38, the best known lower bound on R3,t was obtained no later than 2017, as described in the survey [15]. Most of these best known lower bounds on small R3,t were obtained by finding cyclic 3,t-graphs. The best known lower bound on R3,t for any integer t∈27,28,…,34 cited in [15] was obtained in [16] based on cyclic triangle-free graphs.In [17], R3,s+t−1≥R3,s+R3,t+s−2 was proved for integers s and t, where 2≤s≤t. The subcase s=2, R3,t+1≥R3,t+3, was proved in [18] in 1989. This bound is weak in general, but it is difficult to be improved.


### 2.3. The Cyclic Triangle-Free Process

Most best known lower bounds on smallR3,t were obtained by cyclic graphs of which the orders are composite integers. Some relevant results can be found in [16, 19, 20]. For prime orders between 120 and 260, there is only one best known lower bound obtained by cyclic graphs of prime order, which is R3,33>223 (i.e., the lower bound on R3,33 is 224) given in [16].There is still no known interesting general lower bound onR3,t given by random cyclic graphs that is better than all linear ones. Thus, it is interesting to know if we can obtain better lower bounds on Ramsey numbers of the form R3,t by computing more triangle-free cyclic graphs generated by the CTFP. In particular, it would be interesting to study lower bounds on R3,t based on cyclic graphs of prime order. The structure of cyclic triangle-free graphs can be quite different between the prime order and the composite integer order cases. For instance, if n is an odd prime, then for any cyclic graph GnS1 and any i∈1,2,…,⌊n/2⌋, there will be a cyclic graph GnS2 that is isomorphic to GnS1 such that 1∈S2.In our previous work, new lower bounds on some small Ramsey numbers of formR3,t, including R3,35≥237, R3,36≥245, R3,37≥255 and R3,38≥267, were obtained in [11] by the CTFP, which improved the best known lower bounds in [15]. More lower bounds were obtained by the CTFP in [11], including R3,41≥291, R3,42≥300, R3,43≥309, R3,44≥316 and R3,48≥362.It is difficult to give interesting lower bounds on smallR3,t by the triangle-free process. For example, we have generated 105 graphs of order 300 by the triangle-free process, and without difficulty, we found that all of them contain 45-independent sets. On the other hand, we have found a cyclic triangle-free graph of order 307 and independence number 40 by the CTFP. More discussions on this would be given in Section 4.In [9, 10], it was proved that with high probability, every vertex of G has degree 1+o11/2nlogn, for the maximal triangle-free graph G of order n at which the triangle-free process terminates. As shown in the computing results in [11], when n is not large, the graphs generated by the CTFP, compared to those generated by the triangle-free process, has more edges and smaller independence numbers with high probability. When n is large, the difference between the numbers of edges in graphs generated by the CTFP, as well as those of edges in graphs generated by the triangle-free process, may become smaller.We focus on improving the best known lower bounds on smallR3,t based on cyclic triangle-free graphs of prime order. In particular, we are interesting in finding triangle-free graphs with small independence numbers. Since the degree of a cyclic triangle-free graph is closely related to its independence number, we study the sizes of parameter sets of cyclic graphs obtained by the CTFP in the next section.


## 2.1. Definitions and Notations

All graphs considered in this paper are finite and undirected graphs. The complete graph of ordern (n∈ℤ+) is denoted by Kn. K3 represents a triangle. For a positive integer d, if every vertex in G is adjacent to d vertices, then G is called d-regular. The clique number of graph G, denoted by clG, is the cardinality of the largest clique in G. The independence number of graph G, denoted by αG, is the cardinality of the largest independent set in G. A clique of order k is called a k-clique, and an independent set of order k is called a k-independent set.Lets and t be two positive integers, the Ramsey number Rs,t is the smallest positive integer n such that every graph of order n contains either an s-clique or a t-independent set. In accordance with the well-known Ramsey theorem [12], it is known that Rs,t is finite. An s,t-graph is a graph that contains neither an s-clique nor a t-independent set. Therefore there is an s,t-graph of order Rs,t−1, but there is not an s,t-graph of order Rs,t.The triangle-free process begins withEn, an empty graph of order n, and iteratively adds edges chosen uniformly at random subject to the constraint that no triangle is formed, until no more edge can be added. The triangle-free process ends with a maximal triangle-free graph. The cyclic triangle-free process, i.e., CTFP, begins with En, and generate a cyclic graph of order n by iteratively adding parameters, chosen uniformly at random, subject to the constraint that no triangle is formed in the cyclic graph obtained, until no more parameters can be added.For any real numbera, we use ⌊a⌋ to designate the largest integer that is smaller than or equal to a. Similarly, ⌈a⌉ is used to designate the smallest integer that is larger than or equal to a. Given an integer n≥5, suppose S⊆1,2,…,⌊n/2⌋, and let G be a graph with the vertex set VG=1,…,n and the edge set EG=x,y|minx−y,n−x−y∈S, a graph G is called a cyclic graph of order n, namely GnS. S is called the parameter set of GnS.


## 2.2. Some Basic Known Results onR3,t and the Triangle-Free Process

AlthoughR3,t is simple among Ramsey numbers Rs,t, it can be difficult when t becomes large. The best known asymptotic lower bound on R3,t is R3,t≥1/4+o1t2/logt, obtained by Bohman and Keevash [9] in 2013 and by Pontiveros et al. [10] independently and simultaneously. In 2020, the work of [10] was updated and published as [13]. The triangle-free process was used in both [9, 10]. This asymptotic lower bound on R3,t was obtained by proving the following theorem.Theorem 1 ([9, 10]).
LetG be the maximal triangle-free graph of order n at which the triangle-free process terminates. With high probability, G has independence number at most 1+o12nlogn.The best known asymptotic lower bound onR3,t, given in [9, 10], is far from the best known upper bound 1+o1t2/logt, which was proved by Shearer in [14]. The exact value of R3,t is known only for positive integer t≤9. For larger small positive integer t≤38, the best known lower bound on R3,t was obtained no later than 2017, as described in the survey [15]. Most of these best known lower bounds on small R3,t were obtained by finding cyclic 3,t-graphs. The best known lower bound on R3,t for any integer t∈27,28,…,34 cited in [15] was obtained in [16] based on cyclic triangle-free graphs.In [17], R3,s+t−1≥R3,s+R3,t+s−2 was proved for integers s and t, where 2≤s≤t. The subcase s=2, R3,t+1≥R3,t+3, was proved in [18] in 1989. This bound is weak in general, but it is difficult to be improved.


## 2.3. The Cyclic Triangle-Free Process

Most best known lower bounds on smallR3,t were obtained by cyclic graphs of which the orders are composite integers. Some relevant results can be found in [16, 19, 20]. For prime orders between 120 and 260, there is only one best known lower bound obtained by cyclic graphs of prime order, which is R3,33>223 (i.e., the lower bound on R3,33 is 224) given in [16].There is still no known interesting general lower bound onR3,t given by random cyclic graphs that is better than all linear ones. Thus, it is interesting to know if we can obtain better lower bounds on Ramsey numbers of the form R3,t by computing more triangle-free cyclic graphs generated by the CTFP. In particular, it would be interesting to study lower bounds on R3,t based on cyclic graphs of prime order. The structure of cyclic triangle-free graphs can be quite different between the prime order and the composite integer order cases. For instance, if n is an odd prime, then for any cyclic graph GnS1 and any i∈1,2,…,⌊n/2⌋, there will be a cyclic graph GnS2 that is isomorphic to GnS1 such that 1∈S2.In our previous work, new lower bounds on some small Ramsey numbers of formR3,t, including R3,35≥237, R3,36≥245, R3,37≥255 and R3,38≥267, were obtained in [11] by the CTFP, which improved the best known lower bounds in [15]. More lower bounds were obtained by the CTFP in [11], including R3,41≥291, R3,42≥300, R3,43≥309, R3,44≥316 and R3,48≥362.It is difficult to give interesting lower bounds on smallR3,t by the triangle-free process. For example, we have generated 105 graphs of order 300 by the triangle-free process, and without difficulty, we found that all of them contain 45-independent sets. On the other hand, we have found a cyclic triangle-free graph of order 307 and independence number 40 by the CTFP. More discussions on this would be given in Section 4.In [9, 10], it was proved that with high probability, every vertex of G has degree 1+o11/2nlogn, for the maximal triangle-free graph G of order n at which the triangle-free process terminates. As shown in the computing results in [11], when n is not large, the graphs generated by the CTFP, compared to those generated by the triangle-free process, has more edges and smaller independence numbers with high probability. When n is large, the difference between the numbers of edges in graphs generated by the CTFP, as well as those of edges in graphs generated by the triangle-free process, may become smaller.We focus on improving the best known lower bounds on smallR3,t based on cyclic triangle-free graphs of prime order. In particular, we are interesting in finding triangle-free graphs with small independence numbers. Since the degree of a cyclic triangle-free graph is closely related to its independence number, we study the sizes of parameter sets of cyclic graphs obtained by the CTFP in the next section.


## 3. The Size of Parameter Set of Cyclic Triangle-Free Graphs of Prime Order

Similar to the proof performed on the triangle-free process in [9, 10] (including Theorem 1 in Section 2.1), proving theorems on the CTFP can be difficult. Since cyclic triangle-free graphs are not well understood by now, more details on the structure of those graphs are needed.


### 3.1. Small Parameter Sets of Some Cyclic Triangle-Free Graphs of Prime Orders

As the order of all triangle-free graphs considered are of odd prime orders, the degree equals to the twice of the number of parameters, which is a lower bound on the independence numbers. When generating cyclic triangle-free graphs of prime orders range from 223 to 401, we have found maximal cyclic triangle-free graphs with different parameter sets. Data on sizes of parameter sets are useful in computation experiment design. The sizes of some maximal cyclic triangle-free graphs with small parameter sets are listed in Table1. With only one exception (i.e., 151), the results on prime orders ranging from 127 to 211 are the same to those in [11].Table 1
Sizes of small parameter sets of some cyclic triangle-free graphs with prime orders.
p127131137139149151157163167173α99910101011111112p179181191193197199211223227229α12121313131313141414p233239241251257263269271277281α14141415151515161616p283293307311313317331337347349α16171717171818181919p353359367373379383389397401α191919202020202120


### 3.2. Computing Time Through an Example

The Maximum Independence Number Problem is NP-hard even if restricted to cyclic graphs [21]. It can be difficult to compute the independence number of a large cyclic graph of which the density of edges is low. For instance, it is difficult to compute the independence number of a random cyclic triangle-free graph when the order is larger than 500.Suppose that among all maximal cyclic triangle-free graphs of ordern, the proportion of graphs with independence number smaller than t is x. Suppose that t is not too small such that x>0 holds. If we generate y maximal cyclic triangle-free graphs randomly, then the probability that at least one graph among them has independence number smaller than t is 1−1−xy. When x>0 and y approaches infinite, the probability tends towards 1. When y=⌈1/x⌉ and positive x is very small, the probability is 1−1−xy≈1−1/e, where e is the base of natural logarithm. To find a cyclic triangle-free graph of order n and independence number smaller than t with large probability, sufficient amount of cyclic triangle-free graphs should be generated. Therefore, to enable handling with large amount of graphs, the computation of graphs should be fast enough.For any integern between 121 and 401, generating a cyclic graph of order n by the CTFP costs about one second in average. However, generating a cyclic triangle-free graph G with small parameter set, can spend much more time in average. When the order becomes larger, generating a cyclic graph by the CTFP can take longer time in average. On the other hand, finding a t-independent set in a given cyclic triangle-free graph G can be much easier when t is smaller.We discuss the computing time through an example below. By using CTFP, it is easy to find a cyclic triangle-free graphG of order 313 such that αG=43. However, among 15000 cyclic graphs generated, only one cyclic graph G of order 313 with αG=42 is found. All of the cyclic graphs contain 20 or fewer parameters. For the triangle-free graphs of order 313, whose number of parameters is at most 20, the computation time is about one minute in average. On the other hand, almost for any graph among them, a 42-independent set can be found within one second, and we know that they can not be used to prove R3,42>313.Generating random cyclic triangle-free graphs by the CTFP or similar methods quickly is important in computing new lower bounds on smallR3,t. Our experiment result shows that this is not difficult when the order n is an odd prime.


### 3.3. A Method on Generating Random Cyclic Triangle-Free Graphs of Prime Order

Suppose thatp is an odd prime and p>120. Let G1=GpS1 (S1>10) be a cyclic triangle-free graph, S0=a,a+1,…,b and a=⌈p/3⌉ and b=p−1/2, GpS0 is a triangle-free graph.Based on the data on graphs generated by the CTFP, we found that among cyclic graphsG=GpS of order p generated that have x parameters, the number of parameters in S∩S0 equals to ⌊x/3⌋ or ⌊x/3⌋+1 with high probability. This can be proved via Theorem 2.Theorem 2.
Suppose thatp is a prime and p>120, and let G1=GpS1 be a cyclic triangle-free graph, where S1=k>10. Let S0=a,a+1,…,b, where a=⌈p/3⌉ and b=p−1/2, there is a parameter set S such that G=GpS is isomorphic to G1, and S∩S0≥⌊S1/3⌋.Proof.
LetT=S∪i|p−i∈S and xmodp denote y∈0,1,…,p−1 such that y≡xmodp, i.e., y−x=cp (c is an integer). Let Ti=ijmodpj∈T, and Si=Ti∩1,2,…,p−1/2 for any i∈1,2,…,p−1, T1=T and Ti=2k for any i∈1,2,…,p−1. For any i∈1,2,…,p−1, GpSi is isomorphic to GpS1. For any i∈T, if j runs over 1,2,…,p−1, then ijmodp runs over 1,2,…,p−1 as well. Therefore, for any i∈1,2,…,p−1, there are 2k sets among T1,T2,…,Tp−1 that contain i. According to the Drawer principle, there is i0 such that Ti0∩S0≥⌊S1/3⌋. Let S be Si0, we can conclude that S∩S0≥⌊S1/3⌋.
We can also prove thatS∩S0≥⌊S1/3⌋ in Theorem 2, with similar proof. By the method based on Theorem 2, however, we can generate cyclic triangle-free graphs more similar to those generated by the CTFP at the distribution of parameters.
The CTFP generatesGpSi and GpS in Theorem 2 with the same probability for any i∈1,…,p−1. Based on a result given by Muzychuk on isomorphic cyclic graphs [22], all cyclic graphs isomorphic to GpS can be obtained in the same manner when the order is an odd prime.
Based on Theorem2, a novel approach similar to the CTFP can be devised, which can generate cyclic graphs of prime order more effectively. We choose ⌊x/3⌋ integers in S0 randomly, and generate a cyclic graph of order p by iteratively adding parameters. Firstly, we add parameters chosen uniformly in 1,…,a−1 at random and subject to the constraint that no triangle is formed in the cyclic graph obtained, until no more parameter in 1,2,…,a−1 can be added. Then, we iteratively add parameters that are chosen uniformly in a,a+1,…,b at random and conformed to the constraint that no triangle is formed in the cyclic graph obtained, until there is no such parameter that is different from those ⌊x/3⌋ integers chosen in S0 earlier.
This method is similar to the CTFP. Together with other improvement, the new method can generate cyclic triangle-free graphs more quickly than the CTFP. Among cyclic graphs of orderp that have x parameters generated using this method, in many cases, the number of parameters in S∩S0 equals to ⌊x/3⌋ or ⌊x/3⌋+1.
If we generate 100 cyclic triangle-free graphs of order 313 by this method, of which the number of parameters is at most 20, then the computation spends about 28 seconds in average. This allows to generate more graphs. We have generated more than105 graphs of order 313 whose the number of parameters is at most 20, and found a triangle-free graph of order 313 and independence number 41. We have also generated many cyclic triangle-free graphs of order 317, of which the number of parameters is at most 20, and found a triangle-free graph of order 317 and independence number 41.
From computing results obtained by the new method, we can see that, in studying lower bounds onR3,t, the new method can achieve results similar to that derived by the CTFP more efficiently.


## 3.1. Small Parameter Sets of Some Cyclic Triangle-Free Graphs of Prime Orders

As the order of all triangle-free graphs considered are of odd prime orders, the degree equals to the twice of the number of parameters, which is a lower bound on the independence numbers. When generating cyclic triangle-free graphs of prime orders range from 223 to 401, we have found maximal cyclic triangle-free graphs with different parameter sets. Data on sizes of parameter sets are useful in computation experiment design. The sizes of some maximal cyclic triangle-free graphs with small parameter sets are listed in Table1. With only one exception (i.e., 151), the results on prime orders ranging from 127 to 211 are the same to those in [11].Table 1
Sizes of small parameter sets of some cyclic triangle-free graphs with prime orders.
p127131137139149151157163167173α99910101011111112p179181191193197199211223227229α12121313131313141414p233239241251257263269271277281α14141415151515161616p283293307311313317331337347349α16171717171818181919p353359367373379383389397401α191919202020202120


## 3.2. Computing Time Through an Example

The Maximum Independence Number Problem is NP-hard even if restricted to cyclic graphs [21]. It can be difficult to compute the independence number of a large cyclic graph of which the density of edges is low. For instance, it is difficult to compute the independence number of a random cyclic triangle-free graph when the order is larger than 500.Suppose that among all maximal cyclic triangle-free graphs of ordern, the proportion of graphs with independence number smaller than t is x. Suppose that t is not too small such that x>0 holds. If we generate y maximal cyclic triangle-free graphs randomly, then the probability that at least one graph among them has independence number smaller than t is 1−1−xy. When x>0 and y approaches infinite, the probability tends towards 1. When y=⌈1/x⌉ and positive x is very small, the probability is 1−1−xy≈1−1/e, where e is the base of natural logarithm. To find a cyclic triangle-free graph of order n and independence number smaller than t with large probability, sufficient amount of cyclic triangle-free graphs should be generated. Therefore, to enable handling with large amount of graphs, the computation of graphs should be fast enough.For any integern between 121 and 401, generating a cyclic graph of order n by the CTFP costs about one second in average. However, generating a cyclic triangle-free graph G with small parameter set, can spend much more time in average. When the order becomes larger, generating a cyclic graph by the CTFP can take longer time in average. On the other hand, finding a t-independent set in a given cyclic triangle-free graph G can be much easier when t is smaller.We discuss the computing time through an example below. By using CTFP, it is easy to find a cyclic triangle-free graphG of order 313 such that αG=43. However, among 15000 cyclic graphs generated, only one cyclic graph G of order 313 with αG=42 is found. All of the cyclic graphs contain 20 or fewer parameters. For the triangle-free graphs of order 313, whose number of parameters is at most 20, the computation time is about one minute in average. On the other hand, almost for any graph among them, a 42-independent set can be found within one second, and we know that they can not be used to prove R3,42>313.Generating random cyclic triangle-free graphs by the CTFP or similar methods quickly is important in computing new lower bounds on smallR3,t. Our experiment result shows that this is not difficult when the order n is an odd prime.


## 3.3. A Method on Generating Random Cyclic Triangle-Free Graphs of Prime Order

Suppose thatp is an odd prime and p>120. Let G1=GpS1 (S1>10) be a cyclic triangle-free graph, S0=a,a+1,…,b and a=⌈p/3⌉ and b=p−1/2, GpS0 is a triangle-free graph.Based on the data on graphs generated by the CTFP, we found that among cyclic graphsG=GpS of order p generated that have x parameters, the number of parameters in S∩S0 equals to ⌊x/3⌋ or ⌊x/3⌋+1 with high probability. This can be proved via Theorem 2.Theorem 2.
Suppose thatp is a prime and p>120, and let G1=GpS1 be a cyclic triangle-free graph, where S1=k>10. Let S0=a,a+1,…,b, where a=⌈p/3⌉ and b=p−1/2, there is a parameter set S such that G=GpS is isomorphic to G1, and S∩S0≥⌊S1/3⌋.Proof.
LetT=S∪i|p−i∈S and xmodp denote y∈0,1,…,p−1 such that y≡xmodp, i.e., y−x=cp (c is an integer). Let Ti=ijmodpj∈T, and Si=Ti∩1,2,…,p−1/2 for any i∈1,2,…,p−1, T1=T and Ti=2k for any i∈1,2,…,p−1. For any i∈1,2,…,p−1, GpSi is isomorphic to GpS1. For any i∈T, if j runs over 1,2,…,p−1, then ijmodp runs over 1,2,…,p−1 as well. Therefore, for any i∈1,2,…,p−1, there are 2k sets among T1,T2,…,Tp−1 that contain i. According to the Drawer principle, there is i0 such that Ti0∩S0≥⌊S1/3⌋. Let S be Si0, we can conclude that S∩S0≥⌊S1/3⌋.
We can also prove thatS∩S0≥⌊S1/3⌋ in Theorem 2, with similar proof. By the method based on Theorem 2, however, we can generate cyclic triangle-free graphs more similar to those generated by the CTFP at the distribution of parameters.
The CTFP generatesGpSi and GpS in Theorem 2 with the same probability for any i∈1,…,p−1. Based on a result given by Muzychuk on isomorphic cyclic graphs [22], all cyclic graphs isomorphic to GpS can be obtained in the same manner when the order is an odd prime.
Based on Theorem2, a novel approach similar to the CTFP can be devised, which can generate cyclic graphs of prime order more effectively. We choose ⌊x/3⌋ integers in S0 randomly, and generate a cyclic graph of order p by iteratively adding parameters. Firstly, we add parameters chosen uniformly in 1,…,a−1 at random and subject to the constraint that no triangle is formed in the cyclic graph obtained, until no more parameter in 1,2,…,a−1 can be added. Then, we iteratively add parameters that are chosen uniformly in a,a+1,…,b at random and conformed to the constraint that no triangle is formed in the cyclic graph obtained, until there is no such parameter that is different from those ⌊x/3⌋ integers chosen in S0 earlier.
This method is similar to the CTFP. Together with other improvement, the new method can generate cyclic triangle-free graphs more quickly than the CTFP. Among cyclic graphs of orderp that have x parameters generated using this method, in many cases, the number of parameters in S∩S0 equals to ⌊x/3⌋ or ⌊x/3⌋+1.
If we generate 100 cyclic triangle-free graphs of order 313 by this method, of which the number of parameters is at most 20, then the computation spends about 28 seconds in average. This allows to generate more graphs. We have generated more than105 graphs of order 313 whose the number of parameters is at most 20, and found a triangle-free graph of order 313 and independence number 41. We have also generated many cyclic triangle-free graphs of order 317, of which the number of parameters is at most 20, and found a triangle-free graph of order 317 and independence number 41.
From computing results obtained by the new method, we can see that, in studying lower bounds onR3,t, the new method can achieve results similar to that derived by the CTFP more efficiently.


## 4. New Lower Bounds on SmallR3,t

Take the Ramsey numberR3,37 as an example, the lower bound R3,37≥255 was obtained in [11]. If we can improve it into R3,37≥258 based on a cyclic triangle-free graph G of order 257, then G has at most 18 parameters. It is easy to find a large independent set in some cases, in which the neighborhood of a vertex is a 36-independent set contained in a larger independent set. Hence αG>36 in these cases, and graphs obtained can not be used in improving R3,37≥255.This method is powerful in computing graphs when the orders of cyclic graphs are large. Although useful, this method is less important in improving the efficiency as the method on generating random cyclic triangle-free graphs, as discussed in the last section.We have conducted much computation to improve the best known lower bound onR3,t, based on graphs of prime order p, generated by the CTFP and the new method described in the last section. For each prime p that ranges from 127 to 401, we have generated more than 10000 cyclic graphs of order p, of which the amount of parameters is small enough to enable improving the best known lower bound on R3,t.In [11], a question was proposed for cases n between 200 and 230, i.e., whether additional computation using the CTFP can improve the best known lower bounds on R3,t. We have carried out much computation for any prime p among 211,223,227,229, and have found a cyclic triangle-free graph of order 229 and independence number 33. Therefore R3,34≥230, which improves the previous best known lower bound on R3,34 by 1.Table2 presents a list of the smallest independence numbers of generated graphs of order p. In most cases, the results were obtained based on graphs generated by the CTFP, and in some cases were obtained based on graphs generated by the new method presented in the last section. Some results of small prime orders were known before, including R3,24>139, R3,25>149, R3,26>157, R3,27>163, R3,28>167, R3,29>179 and R3,29>181. Although improving lower bounds on R3,t in Table 2 can be difficult, by the new method on generating random cyclic triangle-free graphs, obtaining the same lower bounds on R3,t is easier.Table 2
Small independence numbers of some cyclic triangle-free graphs of given prime orders.
p127131137139149151157163167173α22222323242525262727p179181191193197199211223227229α28282929303031323333p233239241251257263269271277281α34343435363637373838p283293307311313317331337347349α38394041414142434444p353359367373379383389397401α444546464647484848We have also generated more than105 graphs of order 197 of which the number of parameters is at most 14 by the new method, and the independence numbers are all larger than 29. Note that R3,30≥195 is the best known lower bound on R3,30 given in [16]. We have not found a cyclic triangle-free graph of order 389 and independence number 47, among the 105 generated graphs whose the number of parameters is at most 23, generated using the new method.Some new lower bounds onR3,t, obtained based on the results in Table 2, are listed in Theorem 3.Theorem 3.
R3,34≥230, R3,35≥242, R3,36≥252, R3,37≥264, R3,38≥272, R3,39≥284, R3,40≥294, R3,41≥308, R3,42≥318, R3,43≥332, R3,44≥338, R3,45≥354, R3,46≥360, R3,47≥380, R3,48≥384 and R3,49≥402 can be obtained by cyclic triangle-free graphs.Compared to the results given in [11], except the first one (i.e., R3,34), all the best known lower bound are improved by 5 or more. We list the parameter sets and independence numbers of some graphs obtained by the CTFP or the similar method in Table 3, based on which the result in Theorem 3 is obtained.Table 3
Parameter sets of some graphs obtained by the CTFP.
OrderαGParameter set229333, 31, 40, 41, 49, 50, 51, 58, 63, 67, 73, 79, 84, 86, 88, 97241346, 10, 11, 31, 43, 44, 45, 58, 70, 72, 73, 91, 93, 100, 108, 109, 112251351, 3, 8, 17, 19, 21, 26, 33, 58, 60, 64, 70, 80, 95, 104, 108, 119263363, 5, 7, 11, 20, 33, 39, 49, 57, 58, 67, 81, 89, 102, 108, 110, 118, 131271378, 29, 36, 39, 48, 54, 63, 66, 79, 80, 81, 86, 97, 98, 101, 103, 123283382, 3, 7, 16, 17, 21, 27, 31, 36, 56, 60, 68, 86, 97, 109, 110, 119, 123, 132293395, 12, 18, 35, 43, 46, 49, 50, 56, 72, 82, 83, 103, 110, 114, 116, 124,135, 1433074024, 31, 32, 43, 49, 54, 59, 65, 69, 70, 72, 99, 105, 106, 107, 111, 116,120, 125, 145317412, 20, 33, 42, 43, 59, 64, 70, 73, 80, 83, 87, 88, 98, 119, 124, 127, 133,138, 1453314210, 13, 17, 22, 24, 42, 49, 50, 57, 61, 69, 75, 80, 95, 115, 142, 146, 148, 151, 153, 1623374331, 32, 36, 52, 57, 59, 66, 74, 76, 94, 100, 115, 117, 119, 121, 127, 129, 138,141, 145, 162353442, 3, 15, 32, 39, 52, 53, 63, 72, 79, 80, 86, 97, 117, 123, 130, 134, 141, 153,154, 163, 174359459, 10, 12, 13, 27, 50, 52, 74, 75, 80, 82, 98, 103, 106, 117, 123, 131, 145, 151,152, 159, 170379466, 9, 14, 19, 30, 35, 42, 64, 67, 68, 69, 71, 95, 108, 112, 115, 146, 148, 151, 158,171, 174, 187383478, 14, 18, 39, 41, 42, 61, 70, 74, 76, 91, 97, 98, 107, 110, 126, 141, 142, 153, 157,162, 164, 1904014811, 18, 25, 34, 42, 55, 56, 79, 85, 91, 114, 117, 124, 126, 129, 130, 131, 150, 162, 174,177, 178, 194, 200For the cases in Table3 where the order p>300, the lower bound is better when the independence number is even. The reason is given below: if the expected independence number α is even, we can generate cyclic triangle-free graphs of which the number of parameters is no larger than α/2 quickly, which allows to deal with many graphs; if more random cyclic triangle-free graphs are generated, we can improve some best known lower bounds of form R3,α+1>p in which cases the expected independence number α is odd.


## 5. Conclusion and Discussions

In this paper, we have improved the best known lower bound forR3,t based on some cyclic graphs of prime order obtained by the CTFP or a similar method. For t that is not small, the works on the lower bound for R3,t. based on cyclic triangle-free graphs earlier than [11] were not efficient in finding good parameter sets. The CTFP can be used as a good tool in studying the lower bound on R3,t for large t.We propose a problem on cyclic triangle-free graphs of prime orders.Problem 1.
Suppose thatn is an integer and n≥10. Let fn be the minimum among the independence numbers of all cyclic triangle-free graphs of order n. Is there an integer n0≥120 such that for any pair primes p1 and p2, fp1≥fp2 when p1>p2>n0?We propose this problem based on the data in Table2. For instance, we know that f311≤41 and f313≤41, while whether f313≥f311 is unknown. Note that in this paper we have obtained lower bounds on R3,t by computing small upper bounds for fn.For a positive integern≤121, there is no cyclic 3,t-graphs of order n that can be used to improve the best known lower bound on R3,t given in [15] (see [23]). It is likely that for any integer n between 121 and 200, there is not a cyclic triangle-free graph that can be used to improve the best known lower bound on R3,t.



---

*Source: 5595919-2021-08-09.xml*