The Cyclic Triangle-Free Process

Abstract

For positive integers s and t, the Ramsey number $$R(s,t)$$ is the smallest positive integer n such that every graph of order n contains either a clique of order s or an independent set of order t. The triangle-free process begins with an empty graph of order n, and iteratively adds edges chosen uniformly at random subject to the constraint that no triangle is formed. It has been an important tool in studying the asymptotic lower bound for $$R(3,t)$$. Cyclic graphs are vertex-transitive. The symmetry of cyclic graphs makes it easier to compute their independent numbers than related general graphs. In this paper, the cyclic triangle-free process is studied. The sizes of the parameter sets and the independence numbers of the graphs obtained by the cyclic triangle-free process are studied. Lower bounds on $$R(3,t)$$ for small t’s are computed, and $$R(3,35)\ge 237$$, $$R(3,36)\ge 244$$, $$R(3,37)\ge 255$$, $$R(3,38)\ge 267$$, etc. are obtained based on the graphs obtained by the cyclic triangle-free process. Finally, some problems on the cyclic triangle-free process and $$R(3,t)$$ are proposed.

1. Introduction

All graphs considered in this paper are finite and undirected graphs. For any positive integer n, the complete graph of order n is denoted by $K_n$, and $K_3$ is also called triangle. An empty graph of order n, denoted by $E_n$, is a graph on n vertices of which the edge set is empty. The independence number of graph G, denoted by $\alpha \left(G\right)$, 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. For a positive integer d, if every vertex in G is adjacent to d vertices, then G is called d-regular.

Suppose that s and t are two positive integers. The Ramsey number $R(s,t)$ is the smallest positive integer n such that every graph of order n contains either an s-clique or a t-independent set. By the well-known Ramsey Theorem [1], we know that, for any positive integers s and t, $R(s,t)$ is finite.

A graph is called an $(s,t)$-graph if it contains neither an s-clique nor a t-independent set. An $(s,t)$-graph of order $R(s,t)-1$ is called an $(s,t)$-Ramsey graph.

Given an integer $n\ge 5$, suppose that $S\subseteq \{1,\cdots ,\lfloor n/2\rfloor \}$. Let G be a graph with the vertex set $V\left(G\right)=\{1,\cdots ,n\}$ and the edge set $E\left(G\right)=\left\{\right(x,y\left)\right|min\left\{\right|x-y|,n-|x-y\left|\right\}\in S\}$. Graph G is called a cyclic graph of order n, denoted by $G_n\left(S\right)$, and S is called the parameter set of $G_n\left(S\right)$.

A vertex-transitive graph is a graph G such that given any two vertices u and v in $V\left(G\right)$, there is some automorphism $f:V\left(G\right)\to V\left(G\right)$ such that $f\left(u\right)=v$. Any cyclic graph is vertex-transitive. In fact, the cyclic graph is a special kind of the Cayley graph, and any Cayley graph is vertex-transitive. Cyclic graphs are symmetric because they are vertex-transitive, and it is easier to compute their independence numbers. In fact, we can compute the independence number of a cyclic graph G by computing the independence number of the subgraph of G induced by the non-neighbors of any vertex in G. Cyclic graphs are often used in studying lower bounds for small Ramsey numbers. On the other hand, it is known that finding the maximum clique is NP-hard even if restricted to cyclic graphs [2]. Thus, it may be difficult to compute the clique number or the independence number of a large cyclic graph.

The triangle-free process begins with $E_n$, an empty graph of order n, and iteratively adds edges chosen uniformly at random subject to the constraint that no triangle is formed. It was used in studying the asymptotic lower bound for $R(3,t)$ in [3,4].

There are other types of random processes similar to the triangle-free process, which have striking applications in extremal graph theory. The H-free process was studied by Bohman and Keevash [5], and in a recent paper [6], the k-matching-free process was considered by Krivelevich, Kwan, Loh and Sudakov.

The parameter set of a $K_3$-free cyclic graph is related to sum-free sets of $\{1,\cdots ,n\}$ or ${\mathbb{Z}}_n$. There are few references on small sum-free sets of $\{1,\cdots ,n\}$ or ${\mathbb{Z}}_n$, and there are some references on large ones. Tuan Tran provided a structural characterization of sum-free subsets of $\{1,\cdots ,n\}$ of density at least $2/5-c$, where c is an absolute positive constant [7]. For ${\mathbb{Z}}_p$ where p is a prime, the well-known Cauchy–Davenport Theorem yields that every sum-free set has size at most $\lfloor \frac{p+1}{3}\rfloor$. S is complete if for every $z\in V\left(G\right)-S$ there exist $x,y\in S$ for which $x+y=z$. Haviv and Levy [8] provided a full characterization of the symmetric complete sum-free subsets of ${\mathbb{Z}}_p$ of size at least $(\frac{1}{3}-c)p$, where p is a prime and c is a positive universal constant.

The remainder of this paper is organized as follows. In Section 2, some basic known results on $R(3,t)$ and the triangle-free process are briefly surveyed. Then, the cyclic triangle-free process is studied in Section 3. The sizes of the parameter sets of graphs obtained by the cyclic triangle-free process are studied in Section 4. Independence numbers of graphs obtained by the cyclic triangle-free process and the lower bound on $R(3,t)$ for small t are studied in Section 5. Some unsolved problems on the cyclic triangle-free process and $R(3,t)$ are discussed in Section 6.

2. Preliminary

Ramsey theory is a generalization of the Drawer principle. The philosophy of Ramsey theory lies in that if a structure is large enough, then there must be a large substructure that is highly ordered.

In Section 2.1, we discuss the Ramsey number $R(s,t)$ briefly.

2.1. The Ramsey Number $R(s,t)$

The Ramsey number $R(s,t)$ is one of the most important and interesting topics in Ramsey theory. The research in Ramsey theory has led to some powerful methods. For instance, the study on the lower bound for $R(k,k)$ led to the probabilistic method, of which the influence is both wide and deep.

Suppose that integers $s,t\ge 2$. It is known that

$R(s,t)\le R(s-1,t)+R(s,t-1).$

In particular,

$R(3,t)\le R(3,t-1)+t.$

In a Dynamic Survey on small Ramsey numbers by Radziszowski [9], many known results on the values and bounds on small Ramsey numbers are surveyed.

In this paper, we focus on the Ramsey number $R(3,t)$. Suppose that $s\ge 4$ and $t\ge 3$. The structure of a $(3,t)$-graph G is often simpler than that of an $(s,t)$-graph, because for any vertex $v\in V\left(G\right)$, the neighbors of v form an independent set.

In the next subsection, we survey some known results on $R(3,t)$ and the triangle-free process.

2.2. $R(3,t)$ and the Triangle-Free Process

The research of $R(3,t)$ has a long history, including the work of Erdős on the lower bound [10], and the work of Ajtai, Komlós and Szemerédi on the upper bound [11]. Spencer wrote an article [12] on the history of $R(3,t)$ until 2009. The best known lower and upper bounds for $R(3,t)$ are

$(\frac{1}{4}+o\left(1\right))\frac{t^2}{logt}\le R(3,t)\le (1+o\left(1\right))\frac{t^2}{logt}.$

The upper bound is implicit in a 1983 paper by Shearer [13]. We know that the following theorem holds [13].

Theorem 1.

Define $f\left(d\right)=(dlogd-d+1)/{(d-1)}^2$, where d is neither 1 nor 0. Let G be a triangle-free graph of order n and average degree d. Then, the independence number $\alpha \left(G\right)\ge f\left(d\right)n$.

The lower bound for $R(3,t)$ cited above was obtained in 2013 by Bohman and Keevash [3], and by Pontiveros, Griffiths and Morris [4] independently and simultaneously. The triangle-free process was used in [3,4]. As pointed out in [3], both proofs exploit self-correction, but are different in some important ways. The lower bound for $R(3,t)$ was proved by proving the following theorem.

Theorem 2.

Let G 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+o\left(1\right))\sqrt{2nlogn}$.

In 1995, Kim proved that $R(3,t)\ge c\frac{t^2}{logt}$ [14], which was an important improvement on the lower bound for $R(3,t)$. Kim employed a semi-random construction that is loosely related to the triangle-free process.

Among small Ramsey numbers, the lower bound for $R(3,t)$ has attracted considerable attention, and has been studied by many researchers. The exact values of $R(3,t)$ are known only for positive integer $t\le 9$. For larger small positive integer $t\le 38$, the best known lower bounds for $R(3,t)$ are surveyed in [9]. Most of these best known lower bounds for small $R(3,t)$ were obtained by finding cyclic $(3,t)$-graphs (see [9]). They include $R(3,24)\ge 143$ and $R(3,26)\ge 159$ obtained in [15], and $R(3,22)\ge 131$ and $R(3,25)\ge 154$ obtained in [16]. Furthermore, the best known lower bound on $R(3,t)$ for any integer $t\in \{27,\cdots ,38\}$ was obtained in [17].

For any positive integer $n\le 121$, there are no cyclic $(3,t)$-graphs of order n that can be used to improve the best known lower bound for $R(3,t)$ surveyed in [9] (see [18]).

In [19], a paper titled “An algorithmic framework for obtaining lower bounds for Ramsey numbers“, some results on anti-Ramsey problems or hypergraph problems were obtained. It seems that the methods used cannot be used on classical Ramsey numbers to obtain interesting lower bounds.

In [20], Burr, Erdős, Faudree and Schelp proved that

$R(k,t+1)\ge R(k,t)+2k-3.$

The following inequality is a sub-case of this inequality in [20]:

$R(3,t+1)\ge R(3,t)+3.$

In [21], the following inequality was proved constructively. It is a sub-case of a more general theorem in [21].

Theorem 3.

If s and t are two integers and $2\le s\le t$, then

$R(3,s+t-1)\ge R(3,s)+R(3,t)+s-2.$

By Theorem 3 and related known data on the lower bound for small $R(3,k)$, we can compute the lower bound on $R(3,t)$ for $t>38$. The lower bounds obtained by this method are often weak.

In [22],

$R(3,4k+1)\ge 6R(3,k+1)-5$

was proved constructively. By this inequality and the best known lower bounds $R(3,11)\ge 47$, $R(3,12)\ge 53$ and $R(3,13)\ge 60$, we have $R(3,41)\ge 277,R(3,45)\ge 313$ and $R(3,49)\ge 355$. By $R(3,t+1)\ge R(3,t)+3$, we have $R(3,42)\ge R(3,41)+3\ge 277+3=280$. By Theorem 3, we have $R(3,43)\ge R(3,41)+R(3,3)+3-2\ge 277+7=284$, $R(3,44)\ge R(3,41)+R(3,4)+4-2\ge 277+11=288$ and $R(3,48)\ge R(3,45)+R(3,4)+4-2\ge 313+11=324$.

3. The Cyclic Triangle-Free Process

In this section, we study the cyclic analog of the triangle-free process. Studying the lower bound for small $R(3,t)$ by the cyclic analog of the triangle-free process was suggested in a subsection titled “Problems of algorithms on off-diagonal Ramsey numbers” in [23] by Xu, Liang and Luo. There is no detailed study on the cyclic triangle-free process in [23].

The cyclic triangle-free process begins with an empty graph of order n, 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.

Known asymptotic lower bounds for the Ramsey number $R(3,t)$ were based on non-constructive methods which cannot be used to study $R(3,t)$ for small t’s. For small t’s, in most cases, the best known lower bound for $R(3,t)$ was obtained based on a $K_3$-free cyclic graph. Most of those cyclic graphs were obtained by searching in the following way. Given integers $n>10$ and $t>3$, we can generate $K_3$-free cyclic graphs of order n by generating their parameter sets lexicographically. We can search for $(3,t)$-graphs among cyclic graphs generated. If we find one, then we obtain that $R(3,t)\ge n+1$. We may also choose some parameter sets of $K_3$-free cyclic graphs of order n, and generate more $K_3$-free cyclic graphs lexicographically from each parameter set chosen, respectively. Most best known lower bounds on $R(3,t)$ were obtained this way. Such a method works well in studying lower bounds on $R(3,t)$ in small cases. However, it may lead to locally optimal solutions, in particular in the cases when n is much larger than 200. The cyclic triangle-free process may work better in these cases.

The cyclic triangle-free process, the cyclic analog of the triangle-free process, is interesting in its own right. It is a natural idea that it may work better than the triangle-free process in giving lower bounds for small $R(3,t)$.

In [3,4], the following theorem on the triangle-free process was proved.

Theorem 4.

Let G be the maximal triangle-free graph of order n at which the triangle-free process terminates. With high probability, every vertex of G has degree $(1+o\left(1\right))\sqrt{(1/2)nlogn}.$

For small cases, the lower bounds for $R(3,t)$ based on the triangle-free process are much smaller than the best known ones. We have done some computation on the independence numbers of some graphs obtained by the triangle-free process. For example, the independence numbers of 100 graphs of order 200 obtained by the triangle-free process range from 36 to 40. We have found a graph of order 200 with independence number 31 by the cyclic triangle-free process. Note that the best known lower bound for $R(3,32)$ is 217.

Since the degree of a cyclic $K_3$-free graph is closely related to its independence number, we study the sizes of parameter sets of cyclic graphs obtained by the cyclic triangle-free process in the next section.

4. The Sizes of Parameter Sets of Cyclic Graphs Obtained by the Cyclic Triangle-Free Process

The degrees and the independence numbers of cyclic graphs of order n generated by the cyclic triangle-free process may have a large range when the order is not large, say, between 100 and 400. For instance, we have generated 100 graphs of order 240 by the cyclic triangle-free process. Among these graphs, the one with the maximum degree is 120-regular and the one with the minimum degree is 34-regular. The independence numbers of these cyclic graphs range from 36 to 120. On the other hand, the independence numbers of the 100 graphs of order 240 that we generated by the triangle-free process range from 41 to 43.

If n is between 400 and 500, then the computing results show us that the degrees of the graphs obtained by the cyclic triangle-free process often vary more widely than those of the graphs obtained by the triangle-free process. However, we have done only a little computation on the independence numbers of these graphs because it is much more difficult than in smaller cases.

In the first subsection of this section, we consider the sizes of parameter sets of cyclic graphs obtained by the cyclic triangle-free process in large cases, and contrast the results with those obtained by the triangle-free process.

4.1. Computation on the Sizes of Parameter Sets of Cyclic Graphs in Large Cases

In this subsection, let us survey more computing results on the degrees of graphs obtained by the cyclic triangle-free process in larger cases as follows.

We have generated 100 graphs of order 1000 by the cyclic triangle-free process, and the degrees of graphs range from 84 to 140. We have also generated 100 graphs of order 1000 by the triangle-free process. The maximum of the averaging degrees of these graphs is 71.216 and the minimum of the averaging degrees of these graphs is 70.728. The maximum degrees range from 78 to 84, and the minimum degrees range from 58 to 63. By these data on graphs of order 1000, we can see that the number of edges in a graph obtained by the cyclic triangle-free process, is with high probability larger than the number of edges in a graph obtained by the triangle-free process. On the other hand, $\lfloor \sqrt{(1/2)nlogn}\rfloor$ in Theorem 4 equals 58 when $n=1000$.

We have generated 100 graphs of every order n among $2000,3000$, 4000, 5000, $6000,7000$, and 8000 by the cyclic triangle-free process, and the smallest degrees that we have generated are 132, 166, 200, 224, 250, 276 and 294, respectively. Note that $\lfloor \sqrt{(1/2)nlogn}\rfloor$ equals 87, 109, 128, 145, 161, 176 and 189 for $n=2000,3000,4000,5000$, $6000,7000$, and 8000, respectively. As we can see, the degrees are larger than $\lfloor \sqrt{(1/2)nlogn}\rfloor$ in these cases. On the other hand, the largest degrees that we have generated are 198, 218, 256, 283, 314, 320 and 330 for $n=2000,3000,4000,5000$, $6000,7000$, and 8000, respectively.

4.2. A Simple Lower Bound on the Sizes of Parameter Sets

Suppose that G is a $K_3$-free graph obtained by the cyclic triangle-free process. Let its parameter set be $S=\{s_1,\cdots ,s_r\}$ and $n=\left|V\right(G\left)\right|\ge 10$. Since G is a maximum cyclic $K_3$-free graph, r cannot be very small if n is not small.

In fact, for any $s_i\in S$, $s_i$ itself, $2s_i$ and $t_i$ are forbidden, where $t_i$ is $\frac{1}{2}{s}_i$ for even $s_i$ and odd n, $t_i$ is either $\frac{1}{2}{s}_i$ or $\frac{1}{2}(n-s_i)$ for even $s_i$ and even n, and $t_i=\frac{1}{2}(n-s_i)$ for odd $s_i$ and odd n. Furthermore, for any different i and j among $\{1,\cdots ,r\}$, $s_i-s_j$ and $s_i+s_j$ are forbidden. Since G is a maximum cyclic $K_3$-free graph, we can see that $2C_r^2+4r\ge \lfloor \frac{n}{2}\rfloor$ if n is even. By $2C_r^2=r^2-r$ we have $r^2+3r\ge \lfloor \frac{n}{2}\rfloor$, where $C_r^2$ is the combinatorial number that denotes the number of different ways to choose two objects among r ones. We can see that, if n is odd, then $r^2+2r\ge \lfloor \frac{n}{2}\rfloor$.

Theorem 5.

Suppose that n is an integer and $n\ge 10$, and G is any graph of order n that is obtained by the cyclic triangle-free process. Let its parameter set be $S=\{s_1,\cdots ,s_r\}$. Then, $r^2+2r\ge \lfloor \frac{n}{2}\rfloor$ if n is odd, and $r^2+3r\ge \lfloor \frac{n}{2}\rfloor$ if n is even.

This theorem may be weak. For instance, the smallest parameter set that we have found of the cyclic graph of order 200 obtained by the cyclic triangle-free process, has 13 parameters. However, by Theorem 5, we can only prove that $r\ge 9$.

4.3. More Computation on the Sizes of Parameter Sets of Cyclic Graphs

In Table 1, we list the averages of the sizes of the parameter sets of 100 cyclic $K_3$-free graphs of given orders that were generated by the cyclic triangle-free process.

We deal with orders such as 122, 197, 236, etc., since we wish to find graphs of these orders with small independence numbers, so as to improve the best known lower bounds for related $R(3,t)$.

We have done some computation to search cyclic graphs with small parameter sets by the cyclic triangle-free process. In the following Table 2, we list the parameter sets of the $K_3$-free graphs with the smallest sizes of parameter sets in 100 cyclic graphs obtained by the cyclic triangle-free process for each order from 101 to 220. We have not done more computation to determine the minimum sizes, because it is of little use in improving the best known lower bound for small $R(3,t)$.

We have generated some cyclic graphs by the cyclic triangle-free process. In Table 3, we list the parameter sets of some cyclic graphs with fewest parameters among these graphs.

Note that the independence numbers of most graphs in Table 3 are large.

5. Independence Numbers and Lower Bounds for Small $R(3,t)$

By Theorems 2 and 4, we know that if G is obtained by the triangle-free process and $\left|V\right(G\left)\right|$ is large enough, then $\alpha \left(G\right)$ may be much larger than the maximum degree of G. Now, let us consider related facts on the graphs obtained by the cyclic triangle-free process.

For an integer n much larger than 400, the degrees of the graphs obtained by the cyclic triangle-free process do not vary as much as in the small cases. However, it is difficult to compute the exact value of the independence number when its order is much larger than 400, and we are not sure how much the independence numbers of these graphs vary. We conjecture that their independence numbers do not vary much.

Suppose that n is an integer that is not small. Although any edge-maximal $K_3$-free graph of order n can be generated by the triangle-free process with a positive probability, the probability to generate one with a very small independence number may be very small. Maybe the cyclic triangle-free process works better than the triangle-free process in improving lower bounds on $R(3,t)$. For integers n between 120 and 200, the cyclic triangle-free process does not improve the known results from the study of cyclic graphs. However, for integers n larger than 230, the computational results that we have obtained imply that the cyclic triangle-free process is a powerful tool to obtain good lower bounds for $R(3,t)$. However, for cases with n between 200 and 230, it is not clear whether additional computation using the cyclic triangle-free process will improve the best known lower bounds on $R(3,t)$ or not.

Furthermore, it is much easier to compute the independence number of a $K_3$-free graph of order n obtained by the cyclic triangle-free process, than that of a graph of order n obtained by the triangle-free process. If we can compute the independence numbers of graphs obtained by the cyclic triangle-free process more quickly, maybe we can obtain interesting results on the lower bound for $R(3,t)$ in larger cases.

We are interested in improving the best known lower bounds for small $R(3,t)$. Hence, we are more interested in finding $K_3$-free graphs of given orders with small independence numbers. Let us consider an example. Observe that, if we wish to obtain a graph G of order 268 with independence number $\alpha \left(G\right)\le 37$, then we need not compute the exact value of $\alpha \left(G\right)$ for each graph generated by the cyclic triangle-free process. Instead, we should check whether $V\left(G\right)$ contains a 38-independent set. Performing this check takes only a few seconds, rather than the few minutes needed to compute $\alpha \left(G\right)$ exactly. If $V\left(G\right)$ contains a 38-independent set, then we should consider other graphs. Otherwise, we should compute the exact value of $\alpha \left(G\right)$.

We list the independence numbers of some graphs obtained by the cyclic triangle-free process in Table 4.

The parameter sets of the $K_3$-free cyclic graphs obtained by the cyclic triangle-free process used in the following are listed in Table 4.

Observe that we have found a $K_3$-free cyclic graph of order 243 with independence number 35 by the cyclic triangle-free process. Therefore, $R(3,36)\ge 244$. Hence, by Theorem 3, $R(3,37)\ge R(3,36)+3\ge 244+3=247.$ On the other hand, we have obtained a better result that $R(3,37)\ge 255$ based on a graph of order 254 with independence number 36 obtained by the cyclic triangle-free process. Therefore, we have improved the best known lower bounds $R(3,36)\ge 241$ and $R(3,37)\ge 246$, respectively.

We have also obtained $R(3,35)\ge 237$ and $R(3,38)\ge 267$, which improve the best known lower bounds $R(3,35)\ge 236$ and $R(3,38)\ge 259$, respectively.

Furthermore, we have obtained $R(3,41)\ge 291$, $R(3,42)\ge 300$, $R(3,43)\ge 309$, $R(3,44)\ge 316$ and $R(3,48)\ge 362$. They improve related results in Section 2, respectively.

We list these new lower bounds for Ramsey numbers obtained above in the following theorem.

Theorem 6.

$R(3,35)\ge 237$, $R(3,36)\ge 244$, $R(3,37)\ge 255$, $R(3,38)\ge 267$, $R(3,41)\ge 291$, $R(3,42)\ge 300$, $R(3,43)\ge 309$, $R(3,44)\ge 316$ and $R(3,48)\ge 362$ can be obtained by $K_3$-free cyclic graphs.

6. Conclusions and Problems

In this paper, we have studied the cyclic triangle-free process, and analyzed the parameter sets and independence numbers of the $K_3$-free cyclic graphs obtained by it. We have studied the lower bound for small $R(3,t)$ based on the cyclic triangle-free process, and improved the best known lower bound for $R(3,t)$ based on some graphs obtained by the cyclic triangle-free process.

It seems that the cyclic triangle-free process is not a very powerful tool to find good constructions for $R(3,t)$ through computation in the case when t is small and there aren’t many constructions. For instance, there is a cyclic $K_3$-free graph on 228 vertices of independence number 33. However, we did not find one by generating 50 maximal cyclic $K_3$-free graphs on 228 vertices with fewer than 16 parameters. On the other hand, for t that is not very small, the earlier works on the lower bound for $R(3,t)$ based on cyclic $K_3$-free graphs are not efficient in finding good parameter sets. Hence, the cyclic triangle-free process may be used as a good tool in studying the lower bound for $R(3,t)$ for large t.

It may be interesting to consider a similar Cayley type triangle-free process based on other finite groups instead of cyclic groups. It is also interesting to know if the cyclic triangle-free process can be used in studying the lower bound for the multicolor Ramsey number $R_m\left(3\right)$. The reader can find results related to $R_m\left(3\right)$ in [24,25,26,27]. We will study these problems in the future.

Let us finish this paper by proposing the following problems on the cyclic triangle-free process and $R(3,t)$. They are interesting for us and may be very difficult. More unsolved problems on Ramsey numbers can be found in [23].

Problem 1.

Let G be the maximal triangle-free graph at which the cyclic triangle-free process terminates. Does $\alpha \left(G\right)\le (1+o\left(1\right))\sqrt{2nlogn}$ hold with high probability?

Problem 2.

Let G be the cyclic triangle-free graph of order n with smallest independence number. Let $t=\alpha \left(G\right)$. Does ${lim}_{n\to \infty }\frac{n}{R(3,t+1)}=1$?

If ${lim}_{n\to \infty }\frac{n}{R(3,t+1)}=1$ in Problem 2 holds, then we can conclude that some $K_3$-free cyclic graphs can be used to give a good asymptotical lower bound for $R(3,t)$.

In [3], Bohman and Keevash conjectured that the upper bound on the independence number in Theorem 2 is asymptotically best possible. We list it as Problem 3 as follows. In fact, Bohman and Keevash [3] were tempted to believe that $R(3,t)\sim t^2/(4logt)$.

Problem 3.

Let G be the maximal triangle-free graph of order n at which the triangle-free process terminates. Does $\alpha \left(G\right)\sim (1+o\left(1\right))\sqrt{2nlogn}$ hold with high probability?

Problem 3 may be very difficult. Computation on small cases will not help with establishing an asymptotic bound for $\alpha \left(G\right)$. We have no idea in which direction to conjecture.

We may also consider related problems on the cyclic triangle-free process similar to Problem 3. Solving such a problem related to Problem 3 means that we can obtain a lower bound on $R(3,t)$ that matches the best one by cyclic graphs. This makes it interesting for us. It may be more difficult, and we have no powerful tools to use on it. Perhaps the cyclic triangle-free process can work as well as the triangle-free process when n tends to infinity.

Author Contributions

Conceptualization, M.L. and X.X.; Formal analysis, Y.T. and X.X.; Methodology, Y.J. and X.X.; Software, Y.J. and M.L.; Writing—original draft, Y.J. and X.X.; and Writing—review and editing, M.L. and Y.T.

Funding

This research was funded by the National Natural Science Foundation of China (grant number 11361008).

Acknowledgments

The authors thank the reviewers and Rujie Zhu for their valuable and insightful comments and suggestions.

Conflicts of Interest

The authors declare no conflict of interest.

Tables

Table 1

The averages of the sizes of 100 parameter sets of given orders.

Order	Average	Range	Order	Average	Range
122	14.33	11–31	290	25.44	20–49
197	18.95	15–33	299	25.57	19–45
200	19.44	15–32	308	26.02	21–42
236	21.45	17–35	315	26.09	20–46
240	21.86	17–60	361	27.62	23–47
243	22.05	17–40	400	30.13	22–47
254	22.51	18–48	500	34.81	29–54
266	23.75	19–40	1000	51.80	43–70

Table 2

Sizes of small parameter sets of $K_3$-free cyclic graphs of given orders.

101	102	103	104	105	106	107	108	109	110
8	8	8	8	8	8	9	8	9	9
111	112	113	114	115	116	117	118	119	120
8	8	8	8	9	8	8	9	8	9
121–138	139–150	151–172	173–187	188–220	/	/	/	/	/
9	10	11	12	13	/	/	/	/	/

Table 3

Some cyclic graphs obtained by the cyclic triangle-free process with few parameters.

Order	Size	Parameter Set
197	13	4, 14, 17, 30, 35, 53, 54, 59, 77, 78, 87, 97, 98
200	13	14, 20, 45, 57, 67, 69, 70, 80, 82, 91, 92, 97, 99
236	14	2, 11, 24, 28, 51, 61, 69, 76, 81, 90, 103, 107, 110, 113
243	14	18, 20, 21, 24, 43, 47, 50, 52, 56, 59, 101, 105, 113, 116
254	15	11, 17, 31, 59, 67, 72, 74, 86, 92, 93, 100, 116, 119, 122, 125
266	15	3, 8, 19, 34, 47, 48, 54, 63, 69, 84, 89, 99, 112, 122, 124
290	17	12, 22, 32, 33, 56, 63, 71, 73, 79, 81, 82, 84, 86, 92, 100, 107, 121
299	18	12, 16, 19, 37, 45, 76, 81, 83, 89, 94, 96, 98, 119, 123, 130, 144, 145, 148
308	18	8, 9, 14, 26, 31, 37, 42, 43, 47, 49, 64, 67, 87, 108, 112, 127, 142, 146
315	18	26, 54, 74, 79, 89, 104, 119, 120, 127, 131, 135, 136, 138, 144, 149, 150, 155, 156
361	20	3, 9, 13, 17, 23, 24, 28, 29, 82, 83, 101, 102, 103, 141, 145, 151, 152, 153, 163, 171
400	21	18, 21, 24, 35, 37, 49, 52, 62, 64, 100, 108, 110, 115, 119, 130, 141, 142, 186, 189, 198, 199

Table 4

Independence numbers of some graphs obtained by the cyclic triangle-free process.

Order	$\mathit{\alpha }\left(\mathit{G}\right)$	Parameter Set
200	31	5, 13, 19, 20, 23, 35, 47, 49, 50, 59, 61, 76, 83, 86, 93
236	34	19, 40, 43, 49, 57, 61, 65, 67, 72, 75, 77, 78, 88, 90, 95, 111, 113
243	35	26, 37, 42, 43, 47, 50, 71, 78, 88, 96, 102, 107, 109, 111, 116, 117, 119
254	36	6, 9, 20, 21, 31, 47, 54, 57, 70, 82, 87, 89, 99, 112, 116, 123, 126
266	37	3, 11, 12, 28, 30, 32, 45, 51, 65, 67, 72, 82, 89, 98, 106, 108, 125, 131
290	40	6, 9, 26, 30, 34, 41, 42, 44, 46, 54, 57, 59, 61, 104, 117, 133, 135, 136, 137
299	41	11, 17, 18, 20, 23, 26, 51, 53, 61, 65, 66, 67, 75, 94, 96, 97, 100, 110, 125, 129
308	42	4, 9, 15, 20, 22, 28, 51, 62, 63, 76, 101, 103, 108, 109, 115, 120, 132, 134, 150, 153
315	43	1, 7, 9, 17, 29, 41, 45, 47, 53, 65, 73, 78, 84, 89, 104, 116, 128, 139, 141, 144, 155
361	47	3, 27, 36, 41, 64, 74, 84, 89, 95, 96, 112, 118, 127, 129, 134, 140, 142, 144, 146, 152, 162, 164, 166