| Summary: | For positive integers <i>s</i> and <i>t</i>, the Ramsey number <inline-formula> <math display="inline"> <semantics> <mrow> <mi>R</mi> <mo>(</mo> <mi>s</mi> <mo>,</mo> <mi>t</mi> <mo>)</mo> </mrow> </semantics> </math> </inline-formula> is the smallest positive integer <i>n</i> such that every graph of order <i>n</i> contains either a clique of order <i>s</i> or an independent set of order <i>t</i>. The triangle-free process begins with an empty graph of order <i>n</i>, 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 <inline-formula> <math display="inline"> <semantics> <mrow> <mi>R</mi> <mo>(</mo> <mn>3</mn> <mo>,</mo> <mi>t</mi> <mo>)</mo> </mrow> </semantics> </math> </inline-formula>. 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 <inline-formula> <math display="inline"> <semantics> <mrow> <mi>R</mi> <mo>(</mo> <mn>3</mn> <mo>,</mo> <mi>t</mi> <mo>)</mo> </mrow> </semantics> </math> </inline-formula> for small <i>t</i>’s are computed, and <inline-formula> <math display="inline"> <semantics> <mrow> <mi>R</mi> <mo>(</mo> <mn>3</mn> <mo>,</mo> <mn>35</mn> <mo>)</mo> <mo>≥</mo> <mn>237</mn> </mrow> </semantics> </math> </inline-formula>, <inline-formula> <math display="inline"> <semantics> <mrow> <mi>R</mi> <mo>(</mo> <mn>3</mn> <mo>,</mo> <mn>36</mn> <mo>)</mo> <mo>≥</mo> <mn>244</mn> </mrow> </semantics> </math> </inline-formula>, <inline-formula> <math display="inline"> <semantics> <mrow> <mi>R</mi> <mo>(</mo> <mn>3</mn> <mo>,</mo> <mn>37</mn> <mo>)</mo> <mo>≥</mo> <mn>255</mn> </mrow> </semantics> </math> </inline-formula>, <inline-formula> <math display="inline"> <semantics> <mrow> <mi>R</mi> <mo>(</mo> <mn>3</mn> <mo>,</mo> <mn>38</mn> <mo>)</mo> <mo>≥</mo> <mn>267</mn> </mrow> </semantics> </math> </inline-formula>, etc. are obtained based on the graphs obtained by the cyclic triangle-free process. Finally, some problems on the cyclic triangle-free process and <inline-formula> <math display="inline"> <semantics> <mrow> <mi>R</mi> <mo>(</mo> <mn>3</mn> <mo>,</mo> <mi>t</mi> <mo>)</mo> </mrow> </semantics> </math> </inline-formula> are proposed.
|
|---|