Keywords. Threshold Ramsey multiplicity; Paths; Even cycles; probabilistic method

1 Introduction↩︎

The Ramsey number \(r(H)\) of a graph \(H\) is the minimum positive integer \(n\) such that every red/blue coloring of the edges of the complete graph \(K_n\) on \(n\) vertices contains a monochromatic copy of \(H\). Determining classical Ramsey numbers is a very challenging problem, and the exact value of \(r(H)\) is known only in a few special cases. For example, the Ramsey number of \(K_5\) is still unknown. In fact, even for generalized Ramsey numbers, there are few families of graphs, including paths and cycles, whose Ramsey numbers are determined. Let \(P_t\) and \(C_t\) denote a path and a cycle on \(t\) vertices, respectively. Gerencsér and Gyárfás [1] determined the Ramsey numbers of paths.

For cycles, it is trivial that \(r(C_3)=r(C_4)=6\). The general case for cycles was proved by Faudree and Schelp [2], and independently by Rosta [3].

Apart from trying to determine the Ramsey number of a graph, another interesting problem is to study the Ramsey multiplicity. That is, for a graph \(H\) and an integer \(n\), let \(M(H,n)\) be the minimum number of monochromatic copies of \(H\) in any red/blue edge-coloring of \(K_n\). Equivalently, if a coloring \(\chi\) has \(N_{\mathrm{red}}(H,\chi)\) red copies and \(N_{\mathrm{blue}}(H,\chi)\) blue copies of \(H\), then \[M(H,n)=\min_{\chi}\bigl(N_{\mathrm{red}}(H,\chi)+N_{\mathrm{blue}}(H,\chi)\bigr).\]

In 1962, Erdős [4] conjectured that, for every complete graph \(H\), the quantity \(M(H,n)\) is asymptotically equal to the expected number of monochromatic copies of \(H\) in a uniformly random two-coloring of the edges of \(K_n\). This conjecture was later generalized by Burr and Rosta [5] to all graphs \(H\). It is true for \(K_3\), by a theorem of Goodman [6] that predates Erdős’ conjecture and almost certainly served as one of its motivations. Nevertheless, Thomason [7] proved that the conjecture is already false for \(K_4\). The failure of this natural conjecture has not diminished interest in the problem: the asymptotic behavior of \(M(H,n)\), has been studied extensively; see, for instance, [8]–[14].

By the definition of the Ramsey number, \(M(H,n)=0\) if and only if \(n<r(H)\). It is therefore natural to ask for the value of \(M(H,n)\) at the threshold where it first becomes positive, namely at \(n=r(H)\). We denote this value by \[m(H)=M(H,r(H))\] and refer to it as the threshold Ramsey multiplicity of \(H\).

The threshold Ramsey multiplicity was first studied systematically by Harary and Prins [15]. In general, determining this parameter, or even obtaining a nontrivial lower bound for it, appears to be a very difficult problem. The only family for which \(m(H)\) has been completely determined is stars, as shown by Harary and Prins [15]. In the same paper, Harary and Prins asked for the threshold Ramsey multiplicity of paths and cycles. Rosta and Surányi [16] studied the case of odd cycles, who obtained an exponential lower bound \(m(C_t)\ge 2^{ct}.\) Károlyi and Rosta [17] improved the estimation to \(m(C_t)\ge t^{ct}\), which, as will be seen below, is sharp up to the value of the constant in the exponent. More recently, Conlon, Fox, Sudakov, and Wei [18], [19] proved that there exists an absolute constant \(c>0\) such that \(m(P_t)\ge (ct)^t,\) and an analogous lower bound holds for cycles. They also conjectured exact formulas for sufficiently large \(t\) based on some red/blue edge-colorings of \(K_{r(P_t)}\) and \(K_{r(C_t)}\).

The conjectured values above all come from the same critical split coloring. Let \(\chi(a,b)\) be the coloring of \(K_{a+b}\) obtained by partitioning the vertex set into two parts of sizes \(a\) and \(b\), coloring both parts blue, and coloring all cross-edges red. This coloring is extremal for the Ramsey numbers of paths and cycles, and Conlon, Fox, Sudakov, and Wei conjectured that the corresponding threshold colorings are also extremal for multiplicity.

For \(C_{2t}\), the conjectured coloring is obtained from \(\chi(2t,t-1)\) by changing one edge inside the blue clique of order \(2t\) to red. This creates no red \(C_{2t}\), and the remaining monochromatic cycles are the blue Hamilton cycles in \(K_{2t}\) avoiding that edge, giving \[\frac{(2t-1)!}{2}-(2t-2)! = \frac{2t-3}{2}(2t-2)!.\]

For \(P_{2t+1}\), the coloring \(\chi(2t,t)\) contains no blue \(P_{2t+1}\), and every red copy must alternate between the two parts. Hence the number of red copies is \[\frac{t!}{2}(2t)_{t+1} = \frac{t}{2}(2t)!,\] where \((m)_n=m(m-1)\cdots (m-n+1)\) for integers \(m\ge n\ge 1\).

For \(P_{2t}\), the coloring \(\chi(2t,t-1)\) contains no red \(P_{2t}\), so all monochromatic copies come from the blue clique of order \(2t\), giving \((2t)!/2.\)

The weakness of these split colorings is that they leave too many highly symmetric monochromatic structures. For even cycles, almost all Hamilton cycles of a \(2t\)-vertex clique remain blue. For odd paths, the complete bipartite red structure creates many alternating paths. For even paths, the blue clique of size \(2t\) creates many paths.

Our constructions follow the same Ramsey‑critical split idea, but we modify the part that creates too many monochromatic copies. We keep the global split structure, but add a local restriction that forces any remaining copy to pass through a controlled set of edges.

For even cycles, the blue clique has size \(2t-1\), so it is one vertex short of containing a blue \(C_{2t}\). Any blue cycle must enter the red clique of size \(t\) through sparse random blue portal edges, while red cycles are forced to alternate through the red clique and are reduced by the corresponding missing red edges.

For odd paths, the blue clique has size \(2t\), so every blue \(P_{2t+1}\) must use vertices outside the clique. These outside vertices, which forms a red clique of size \(t\), can be inserted only through sparse blue support sets. In the red graph, the same support sets become forbidden adjacencies, deleting many alternating red paths.

For even paths, a random sparse interface is less effective because the endpoints of a path create additional configurations. Instead, we use a deterministic local defect. Starting from the critical split coloring, we do not add the last vertex as a full member of the large blue clique. Rather, we delete a small blue star from that clique. This destroys many blue Hamilton paths, while the new red paths created by the defect all pass through one common center and remain controllable.

Our main results are the following.

By the three theorems above, Conjectures 1 and 2 are false. Moreover, Theorems 3 and 4 show the true values of \(m(C_{2t})\) and \(m(P_{2t+1})\) are much less than the conjectured ones. Although the exact values are still unknown, the combinatorial and local random construction method applied in this paper may shed some light on the determination of threshold Ramsey multiplicity of paths and cycles.

The detailed proofs of Theorems 3, 4, and 5 will be presented in Sections 2, 3, and 4, respectively, and we divide each of the proofs into the following three parts: a red/blue edge-coloring construction, a count of monochromatic cycles/paths in the given coloring, and the asymptotic ratio between the resulting upper bound and the conjectured value of Conlon, Fox, Sudakov, and Wei.

2 Proof of Theorem 3↩︎

2.1 The random-portal coloring for even cycles↩︎

By Theorem 2, \(r(C_{2t})=3t-1\). We introduce a local random construction for a red/blue edge-coloring of the complete graph \(K_{3t-1}\). Fix integers \(t\ge 1\) and \(q\) with \(1\le q\le t-2\). The value of \(q\) will be chosen later. Let \[V(K_{3t-1})=A\cup B,\,\, |A|=t,\,\,~\text{and}~|B|=2t-1,\] where \(A\) and \(B\) are pairwise disjoint. For each vertex \(b\in B\), choose a \(q\)-element subset \(M_b\subseteq A.\) We call \(M_b\) the set of blue portals from \(b\) into \(A\). The edge-coloring of \(K_{3t}\) is defined as follows:

• all edges inside \(A\) are red;

• all edges inside \(B\) are blue;

• for \(a\in A\) and \(b\in B\), the edge \(ab\) is blue if and only if \(a\in M_b\); otherwise \(ab\) is red.

The described red/blue coloring of \(K_n\) is illustrated in Figure 1.

The construction will be used probabilistically. For each \(b\in B\), choose \(M_b\) independently and uniformly from all \(q\)-subsets of \(A\). We determine the expected number of monochromatic \(C_{2t}\)’s. If this expectation is at most \(\mathbb{E}\), then at least one deterministic choice of the sets \(M_b\) gives at most \(\mathbb{E}\) monochromatic even cycles.

2.2 Counting monochromatic even cycles↩︎

For convenience, we define \[T_t^{C}:=\frac{(2t-1)!}{2}.\] This is the number of Hamilton cycles in the complete graph \(K_{2t}\). Indeed, there are \((2t)!\) linear orderings of the vertices, and each undirected Hamilton cycle is counted \(2t\) times by choosing a starting point and twice more by choosing a direction. Hence the number is \[\frac{(2t)!}{2\cdot 2t}=\frac{(2t-1)!}{2}.\]

2.2.1 The expected number of red cycles↩︎

2.2.2 The expected number of blue cycles↩︎

We now estimate the sum in Claim 3. We shall use only two standard facts about the modified Bessel function. The modified Bessel function of the first kind of order one is defined by the absolutely convergent power series \[I_1(x) = \sum_{m=0}^{\infty} \frac{1}{m!(m+1)!} \left(\frac{x}{2}\right)^{2m+1}.\] See, for example, the NIST Handbook of Mathematical Functions [20]. We shall also use the standard large-argument asymptotic formula \[\label{eq:bessel-asymp} I_1(x)=\frac{e^x}{\sqrt{2\pi x}}\left(1+O\left(\frac{1}{x}\right)\right),\qquad x\to\infty.\tag{1}\] for positive real \(x\). This is the case \(\nu=1\) of the usual asymptotic expansion for the modified Bessel function \(I_\nu(x)\); see again [20].

2.3 Asymptotic ratio to the conjectured value↩︎

By Claims 2 and 4, the expected total number of monochromatic copies of \(C_{2t}\) is at most \[T_t^{C}\exp\left(-2q+O\left(\frac{q^2}{t}\right)\right)+T_t^{C}\,t^{-1}\exp(2\sqrt2 q+o(q)).\] Choose \[\gamma=\frac{1}{1+\sqrt2}~\text{and}~ q=\left\lfloor\frac{\gamma}{2}\log t\right\rfloor.\] Then as \(t\to\infty\), we have \(q\to\infty\) and \(q^2/t=o(1)\).

We now estimate the two terms separately. The red term is \[\exp\left(-2q+O\left(\frac{q^2}{t}\right)\right)=t^{-\gamma+o(1)}.\] For the blue term, we deduce \[t^{-1}\exp(2\sqrt2 q+o(q))=t^{-1+\sqrt2\gamma+o(1)}.\] Since \[-1+\sqrt2\gamma=-1+\frac{\sqrt2}{1+\sqrt2}=-\frac{1}{1+\sqrt2}=-\gamma,\] the blue term is also \(t^{-\gamma+o(1)}\). Combining the two terms, it follows that \[\mathbb{E}\bigl(N_{\mathrm{red}}(C_{2t})+N_{\mathrm{blue}}(C_{2t})\bigr) \le t^{-\gamma+o(1)}T_t^{C}.\] By the probabilistic method, there exists a deterministic choice of the sets \(M_b\) for which the actual number of monochromatic \(C_{2t}\)’s is at most this expectation. Therefore \[m(C_{2t})\le t^{-\gamma+o(1)}T_t^{C} =t^{-\gamma+o(1)}\frac{(2t-1)!}{2}.\] This proves Theorem 3.

Finally, the conjectured value in Conjecture 1 satisfies \[\frac{2t-3}{2}(2t-2)!=\frac{2t-3}{2t-1}\cdot \frac{(2t-1)!}{2}=(1+o(1))\frac{(2t-1)!}{2}.\] Hence our construction gives a polynomial improvement over the conjectured value.

3 Proof of Theorem 4↩︎

3.1 The random-support coloring for odd paths↩︎

We now give an analogous local random construction for odd paths. Fix integers \(t\ge 1\) and \(q\) with \(1\le q\le 2t\). Since \(r(P_{2t+1})=3t\) by Theorem 1, the red-blue coloring is taken on the complete graph \(K_{3t}\). Let \[V(K_{3t})=U\cup V,\,\, |U|=2t,\,~\text{and}~|V|=t\] where \(U\) and \(V\) are pairwise disjoint. For each vertex \(v\in V\), choose a \(q\)-element subset \(M_v\subseteq U.\) We call \(M_v\) the set of blue supports of \(v\) in \(U\). The edge-coloring of \(K_{3t}\) is defined as follows:

• all edges inside \(U\) are blue;

• all edges inside \(V\) are red;

• for \(u\in U\) and \(v\in V\), the edge \(uv\) is blue if and only if \(u\in M_v\); otherwise \(uv\) is red.

The situation is presented in Figure 2. Similarly, the construction will be used probabilistically. For each \(v\in V\), choose \(M_v\) independently and uniformly from all \(q\)-subsets of \(U\).

3.2 Counting monochromatic odd paths↩︎

Let \[T_t^{P}:=\frac{t}{2}(2t)!.\] This is the number of alternating \(P_{2t+1}\)’s in the complete bipartite graph \(K_{2t,t}\).

3.2.1 The expected number of red paths↩︎

3.2.2 The expected number of blue paths↩︎

In the blue graph, \(U\) is a blue clique and \(V\) is blue-independent. Since \(|U|=2t\), every blue \(P_{2t+1}\) must use at least one vertex of \(V\).

Suppose a blue \(P_{2t+1}\) uses exactly \(s\) vertices of \(V\), where \(1\le s\le t\). Then it uses \(2t+1-s\) vertices of \(U\). We first order the chosen vertices of \(U\) and then insert the \(s\) vertices of \(V\) into the gaps. Let \(j\) be the number of inserted vertices of \(V\) which lie at the two endpoints of the path. Thus \(j=0,1,2\) and \(j\le s\).

For fixed \(s\) and \(j\), we have the following facts:

• the \(s\) vertices of \(V\) can be chosen and ordered in \((t)_{s}\) ways;

• the \(2t+1-s\) vertices of \(U\) can be chosen and ordered in \((2t)_{2t+1-s}\) ways;

• there are \(\binom{2}{j}\binom{2t-s}{s-j}\) ways to choose the endpoint and internal gaps;

• a vertex of \(V\) placed at an endpoint requires one blue support edge, with probability \[\alpha_q=\frac{\binom{q}{1}}{\binom{2t}{1}}=\frac{q}{2t};\]

• a vertex of \(V\) placed internally requires two blue support edges, with probability \[\beta_q=\frac{\binom{q}{2}}{\binom{2t}{2}}=\frac{q(q-1)}{2t(2t-1)}.\]

Dividing by \(2\) for reversing the path gives the following exact expectation.

We now estimate the normalized blue expectation. If \(q=O(\log t)\), then \[\beta_q=\frac{q(q-1)}{2t(2t-1)}\le (1+o(1))\frac{q^2}{4t^2}.\] We split the sum according to the value of \(j\).

3.3 Asymptotic ratio to the conjectured value↩︎

The proof follows the same reasoning as in Theorem 3. By Claims 6 and 8, the expected total number of monochromatic copies of \(P_{2t+1}\) is at most \[T_t^{P}\exp\left(-q+O\left(\frac{q^2}{t}\right)\right)+T_t^{P}t^{-1}\exp(\sqrt2 q+o(q)).\] We choose the parameters as below: \[\gamma=\frac{1}{1+\sqrt2} ~~\text{and}~~q=\left\lfloor \gamma\log t\right\rfloor.\] Then \(q\to\infty\) and \(q^2/t=o(1)\). The red term and blue term are \[\exp\left(-q+O\left(\frac{q^2}{t}\right)\right)=t^{-\gamma+o(1)}\] and \[t^{-1}\exp(\sqrt2 q+o(q))=t^{-1+\sqrt2\gamma+o(1)},\] respectively. Since \(-1+\sqrt2\gamma=-\gamma\), we deduce \[\mathbb{E}\bigl(N_{\mathrm{red}}(P_{2t+1})+N_{\mathrm{blue}}(P_{2t+1})\bigr)\le t^{-\gamma+o(1)}T_t^{P}.\] It implies that \[m(P_{2t+1})\le t^{-\gamma+o(1)}T_t^{P}=t^{-\gamma+o(1)}\frac{t}{2}(2t)!.\] The proof of Theorem 4 complete.

4 Proof of Theorem 5↩︎

4.1 A red/blue edge-coloring construction for even paths↩︎

In this subsection, we first introduce a red/blue edge-coloring of the complete graph \(K_n\). Let \[V(K_n)=S\cup R\cup B\cup\{x\} \text{ and } A=S\cup R,\] where \(S,R,B\) and \(\{x\}\) are pairwise disjoint. The edge-coloring of \(K_n\) is defined as follows:

• all edges inside \(A\) are blue;

• all edges inside \(B\) are blue;

• all edges between \(A\) and \(B\) are red;

• all edges between \(x\) and \(B\) are red;

• all edges between \(x\) and \(S\) are blue;

• all edges between \(x\) and \(R\) are red.

Equivalently, the red graph consists of the complete bipartite graph between \(A\cup\{x\}\) and \(B\), together with the red star from \(x\) to \(R\); the blue graph consists of the complete graphs \(K_{|A|}\) on \(A\) and \(K_{|B|}\) on \(B\), together with the blue star from \(x\) to \(S\). The construction is shown in Figure 3.

4.2 Counting monochromatic even paths↩︎

By Theorem 1, \(r(P_{2t})=2t-1+t=3t-1\). Given an integer \(\alpha\) (the exact value of \(\alpha\) will be specified later), consider the edge-coloring of \(K_{3t-1}\) given in Subsection 4.1 with \[|S|=2t-1-\alpha,\,\,|R|=\alpha, \text{ and } |B|=t-1.\] Clearly, \[|A|=|S|+|R|=2t-1 \text{ and } |A\cup\{x\}|=2t.\]

Combining Claims 9 and 10, we conclude that the number of monochromatic copies of \(P_{2t}\) in this red/blue coloring of the complete graph is \[\left(2t-1-\alpha+\binom{2t-1-\alpha}{2}+\alpha t+\binom{\alpha}{2}\right)(2t-2)!=(\alpha^2-t \alpha+2t^2-t)(2t-2)!.\] It is minimized by choosing \(\alpha=\lfloor t/2\rfloor\), which therefore yields the best possible bound \[m(P_{2t}) \le\frac{(2t)!}{2}-\left\lfloor \frac{t^2}{4}\right\rfloor(2t-2)!.\]

4.3 Asymptotic ratio to the conjectured value↩︎

Since \[m(P_{2t}) \leq\frac{(2t)!}{2}-\left\lfloor \frac{t^2}{4}\right\rfloor(2t-2)!\] and \[\frac{\left\lfloor t^2/4\right\rfloor}{t(2t-1)}=\frac{1}{8}+o(1),\] we obtain \[m(P_{2t}) \leq \left(\frac{7}{8}+o(1) \right)\frac{(2t)!}{2}.\] The proof is complete.

5 Concluding Remarks↩︎

The two constructions about \(m(C_{2t})\) and \(m(P_{2t+1})\) are both local random constructions, but the local random sets play slightly different roles.

For even cycles, the set \(A\) is a red core of size \(t\), while \(B\) is a blue reservoir of size \(2t-1\). Since \(B\) is one vertex short of containing \(C_{2t}\) by itself, every blue \(C_{2t}\) must enter \(A\) through portal edges. On the other hand, every red \(C_{2t}\) is forced to use all of \(A\) and alternate with \(t\) vertices of \(B\). The random portal sets therefore reduce the red cycles multiplicatively, while the sparsity of the portals controls the blue cycles.

For odd paths, the set \(U\) is a blue clique of size \(2t\), while \(V\) is a red clique of size \(t\). Every red \(P_{2t+1}\) is forced to alternate through all vertices of \(V\), so the random supports remove a multiplicative proportion of red paths. A blue \(P_{2t+1}\) must insert at least one vertex of \(V\) into the blue clique \(U\), and each insertion requires one or two support edges.

The exponents in Theorems 3 and 4 arise from balancing the two contributions. In the even-cycle case, the red contribution is essentially \(\exp(-2q)\) and the blue contribution is essentially \(t^{-1}\exp(2\sqrt2q)\). In the odd-path case, the red contribution is essentially \(\exp(-q)\) and the blue contribution is essentially \(t^{-1}\exp(\sqrt2q)\). Both balances lead to the same final exponent \[\gamma=\frac{1}{1+\sqrt2}.\]

The constructions only give upper bounds. We cannot prove that these bounds are best possible. It would be interesting to determine the true order of \(m(C_{2t})\) and \(m(P_{2t+1})\), or even to decide whether these local random models are optimal within suitable restricted classes of colorings.

We once tried to apply the local random construction to find a red/blue edge-coloring of \(K_{3t-1}\) for \(P_{2t}\), the expected number of monochromatic copies of \(P_{2t}\) turned out to be even larger than the conjectured value. We do not know if the upper bound obtained in Theorem 5 is near the value of \(m(P_{2t})\). So, it is of interesting to determine the true order of \(m(P_{2t})\) and corresponding optimal red/blue edge-colorings.

Acknowledgement↩︎

This research is supported by National Key R&D Program of China under grant number 2024YFA1013900 and NSFC under grant number 12471327.

Declaration↩︎

\(\boldsymbol{Conflict~of~interest}\) The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper. \(\boldsymbol{Data~availability}\) No data was used for the research described in the article.

References↩︎