New Ramsey Multiplicity Bounds and Search Heuristics

A subset of vertices in a graph is called homogeneous if it is either a clique, so all pairs of vertices form an edge, or it is an independent set, i.e., no pairs of vertices form an edge. The existence and enumeration of homogeneous subsets is a fundamental, widely-studied topic in combinatorics. Ramsey’s Theorem states that every n-vertex graph contains a homogeneous t-subset, provided that n is large enough compared to t. In 1959, Goodman determined the smallest possible number of homogeneous 3-subsets an n-vertex graph can have for every n and also raised the analogous problem for t-subsets when \(t \ge 4\). A couple of years later, Erdős [19] observed that the number of homogeneous t-subsets can be as small as \(2^{1-{t\atopwithdelims ()2}}\cdot {n\atopwithdelims ()t}\), since this is their expected number in the uniform random graph G(n, 1/2), and hence there must also exist a graph on n vertices with at most that many homogeneous t-subsets. Erdős in fact conjectured that this should be the asymptotic minimum for every \(t\ge 4\). This likely was motivated by the symmetry of the extremal function combined with the role of G(n, 1/2) in providing large graphs without homogeneous t-subsets, and was further supported by the fact that Goodman’s lower bound happens to agree with \(2^{-2}\cdot {n\atopwithdelims ()3}\) asymptotically. Subsequently, several positive results were proved establishing the conjecture for graphs with weaker and weaker pseudorandom conditions [20, 28, 82], yet the general conjecture proved to be difficult to crack already for \(t=4\), a bit of a surprise considering the beauty and relative simplicity of the double-counting arguments for \(t=3\). Thomason [83] soundly rejected the conjecture in 1989 for every \(t\ge 4\), with counterexamples given by sequences of blow-ups of well-designed constant-size graphs. The finite structure ruling these constructions dismissed any heuristic speculation connecting the problem to uniform randomness.

The hunt for the true value of the minimum density of homogeneous t-subsets is still ongoing for every \(t\ge 4\). The determination of this minimum is known as the Ramsey multiplicity problem for cliques and it has received a fair amount of attention [14, 17, 19‐21, 27, 29, 32, 39, 45, 61, 76, 81, 83, 84, 92]. Subsequently the problem was also extended and investigated for arbitrary graphs, hypergraphs, and other discrete structures.

Our first results make progress on the Ramsey multiplicity problem. We denote the number of cliques on t vertices in a graph G by \(k_t(G)\) and let \(k_t(n) = \min \{k_t(G) + k_t({\overline{G}}): |G| = n\}\) be the minimum number of homogeneous t-subsets in an n-vertex graph. The limitexists for every fixed t, as the sequence of minimum proportions \(k_t(n) / {n \atopwithdelims ()t}\) of homogeneous t-subsets is non-decreasing in n.

Trivially \(c_2=1\) and Goodman’s result implies \(c_3= \frac{1}{4}\). For \(t=4\) Thomason [83] showed \(c_4< 0.030304< 0.03125 = 2^{-5}\), hence disproving Erdős’ conjecture. Later Franek and Rödl [29] gave another more straightforward counterexample, with a somewhat larger homogeneous t-subset density. In 1997, Thomason [84] improved the upper bound by \(1.3\cdot 10^{-5}\) to \(c_4 < 0.030291\). Almost thirty years later, Even-Zohar and Linial [21] pushed it further down by another \(0.6\cdot 10^{-5}\) to \(c_4 < 0.030285\). Here we establish the following more substantial improvement.¹

The best known lower bound stands at \(0.0296 < c_4\), and was proved by Grzesik, Lee, Lidický and Volec [39] using flag algebras, so Theorem 1.1 reduces the gap between upper and lower bounds by more than 20%. Perhaps more relevant than the actual values are the methods used to find them. The best of Thomason’s initial constructions [83] were based on the blow-up of a ‘core’ graph on 272 vertices, which were constructed using quadratic forms in an appropriate finite geometric setting. The core graphs of Franek and Rödl [29] were defined on 1024 vertices, over the subsets of a 10-element set using intersection sizes. The improvement of Thomason [84] built on insights from the work of Jagger, Štovíček, and Thomason [45] about the construction in [83], and employed an extensive brute force computer search over XOR products of small graphs to find its core graph on 288 vertices. The improved bound by Even-Zohar and Linial [21] was obtained by identifying a different, iterative blow-up hidden in the construction of Thomason. We will discuss the particularities of the upper bounds and the underlying constructions in more detail in Sect. 3.3.1.

The core graphs of all these constructions happen to be Cayley graphs, yet they were not really sought for as such. For our improvement, we directly construct Cayley graphs via various computer search heuristics which target to find their generating set. A key advantage of this approach is that the size of the search space is only roughly the square root of the size of the produced outcome. Hence our heuristics can efficiently explore and produce relatively large core graphs from the great wealth of good ones among all Cayley graphs over a given group (and not only consider a small portion of them, as before). With our approach, we can find core graph constructions on as few as 192 vertices that improve upon the previous best bound and that can be found with very moderate computational effort. The upper bound for \(c_4\) in Theorem 1.1 is obtained from the sequence of blow-ups of a Cayley graph on 768 vertices, though we also found a construction on 384 vertices that likewise beats 0.03015, hence performing just marginally worse than the construction on 768 vertices.

Much of the effort made by several researchers to optimize Thomason’s approach for \(t = 4\) materialized in improvements for \(t\ge 5\). The best known upper bound for \(t=5\) is \(c_5 < 0.001720\), due to Thomason [84], improving on his bound in [83]. For \(t \in \{6, 7, 8\}\) the best known bounds are given by Deza, Franek, and Liu [17] using the intersection graph idea of [29].

Our method can also be employed to improve the best known upper bound in the \(K_5\)-multiplicity problem. We also complement this with a lower bound using flag algebras.

Our improved upper bound is based on the sequence of blow-ups of a Cayley graph on 192 vertices, just like Thomason’s. We will go more into about our bounds and how they were found in Sect. 3.

A related question, likewise raised by Erdős [19], concerns the minimum number \(k'_{s,t}(n) = \min \{ k_s({\overline{G}}): |G| = n, k_t(G) = 0 \}\) of independent sets of size s in a graph of order n with clique number bounded by \(t-1\). The associated limit, whose existence again follows by monotonicity [62], is defined asNote that obviously \(g_{t,t} \ge c_t\) for any \(t \ge 2\). We trivially have \(g_{s,2} = 1\) and the fact that \(g_{2,t} = 1/(t-1)\) is established by Turán’s theorem [85]. Erdős [19] asked if the upper bound given by the Turán graphs \(T_{t-1}(n)\) as \(n \rightarrow \infty \) is also tight in general, that is if \(g_{s,t} = (t-1)^{1-s}\). This holds for \(s = t = 3\), as an easy consequence of the previously mentioned result of Goodman [36] and the value of \(k'_{3,3}(n)\) was settled precisely by Lorden [55]. Nikiforov [62] however showed that the Turán graph upper bound can be sharp only for a finite number of pairs \(s, t \ge 3\). Das et al. [15] and Pikhurko and Vaughan [66] established tight values when one of the parameters is three and the other at most seven. In particular this confirmed Erdős’ intuition for \(g_{3, t}\) when \(4 \le t \le 7\) and disproved it for \(g_{s, 3}\) when \(4 \le s \le 7\). They also determine the unique extremal constructions in these cases. Moreover, Pikhurko and Vaughan [66] found a construction based on non-balanced blow-ups of a (3, 4)-Ramsey graph of order 8 bounding \(g_{4,4}\) away from the value given by \(T_3(n)\) that is conjectured to be tight. Here we present the first tight value for \(g_{s,t}\) when \(s,t \ge 4\). Furthermore, we show that any graph that comes close to the optimum of \(g_{4,5}\) must be close to a balanced blow-up of \(C_{R(3,5)}\), the unique (3, 5)-Ramsey graph of order 13, i.e., the Cayley graph on \({\mathbb {Z}}_{13}\) whose edge relations are given by the cubic-non-residues.

The upper bound is given by the sequence of balanced blow-ups of \(C_{R(3,5)}\), the lower bound matching that construction was established using the flag algebra approach. The notion of perfect stability was introduced by Pikhurko, Sliačan, and Tyros [65] and strengthens the standard notion of stability. We will formally state it in Definition 4.8 in Sect. 4.2. For the details of the proofs see proofs see Sect. 4.

The fact that Ramsey graphs are a good source of constructions for this problem was previously already noted by Nikiforov [62] and Das et al. [15]. We found several more such graphs whose sequence of (sometimes non-balanced) blow-ups give good upper bounds for additional values of \(g_{s,t}\), but were unable to establish matching lower bounds. The most reasonable open conjecture out of all studied values seems to be that \(g_{5,5} = 61 \cdot 13^{-4}\), where the upper bound also comes from \(C_{R(3,5)}\). We list all other bounds in Sect. 3.3. We also remark that more general bounds for \(g_{s,t}\) were given by Nikiforov [62] and Sawin [76], who studied the close connection to (multicolor) Ramsey numbers.

There is a stark contrast between the difficulty of counting homogeneous triples and counting homogeneous 4-subsets. This is demonstrated by the relatively straightforward proof of \(c_3=1/4\) and the slow progress towards determining the value of \(c_4\). To get a grip on the latter, we propose to investigate the question when we count \(K_4\) only in the graph and triangles in the complement. This problem proves to be more manageable, as we can not only derive an exact solution but also demonstrate the stability of a unique construction on 27 vertices.

Formally, for arbitrary \(s,t\ge 3\), we propose to study the following off-diagonal version of the Ramsey multiplicity parameter:Observe that clearly \(c_{t,t}=c_t\) as well as \(c_{s,t} \le \min \{ g_{s,t}, g_{t,s} \}\). From a result of Reiher [69] it follows that \(c_{2,t} = g_{2,t}\) for every \(t \ge 3\). Here we establish the first exact results when \(t> s\ge 3\).

Note that \(c_{s,t} < g_{s,t}\) for each of these values of s and t. The upper bound for \(c_{3,4}\) is uniquely given by the sequence of balanced blow-ups of the Schläfli graph. The upper bound for \(c_{3,5}\) is more easily described as an upper bound of \(c_{5,3}\), in which case it is given by the sequence of balanced blow-ups of the complement of the Schläfli graph. The upper bound for \(c_{4,5}\) is given by the sequence of blow-ups of a vertex-transitive graph on 128 vertices. Lower bounds are again established using the flag algebra approach. The proof of stability largely follows the template laid out by Pikhurko et al. [65], but also requires additional ideas.

A central question in the symmetric Ramsey multiplicity problem is whether a tight upper bound can be achieved through the sequence of (possibly weighted or iterated) blow-ups of a finite-sized graph. For \(c_3\), this is true, with Goodman’s bound reached by, among others, the blow-ups of \(K_2\). However, for \(c_4\), the question remains open. Theorem 1.4, which states the extremality and stability of blow-ups of a single finite graph (on 27 vertices) for the \(c_{3,4}\) problem, may suggest the existence of such a finite graph for \(c_4\). Our results for \(c_4\) however suggest that any such finite construction might be of considerable size.

There is no specific reason for our choice to weight the contributions from both terms equally in \(c_{s,t}\). Other choices, such as the weighting given by linearly connecting the points indicated by \(g_{s,t}\) and \(g_{t,s}\), would also be reasonable. In fact, the previously introduced problems are part of a broader question aiming to understand which pairs of clique and independent set densities can be realized as the limit of some sequence of graphs. We introduce this problem and our results in the next section.

Outline. We first explore the broader question of realizable pairs of clique and independent set densities and their relation to earlier introduced parameters in Sect. 2. Next, we describe the constructions for upper bounds and their discovery methods in Sect. 3. We then outline Razborov’s flag algebra approach and its application for stability results in Sect. 4. Finally, we discuss related problems and recent learning-based optimization heuristics in Sect. 5.

Lemma 3.2 motivates considering the discrete optimization problemwhere we are minimizing a cost \(c: \{0, 1\}^N \rightarrow {\mathbb {R}}\) over a discrete search space consisting of binary vectors \(\{0, 1\}^N\) for some \(N \in {\mathbb {N}}\). In particular, we considered encoding both simple graphs as well as Cayley graphs through binary vectors, though many other combinatorial structures can expressed this way, see for example the recent work of Wagner [90].

The graph search space. When constructing arbitrary graphs on n vertices, a state \(\textbf{s}\in \{0,1\}^N\) represents the edges of that graph, so that we have \(N = {n \atopwithdelims ()2}\). We associate with each edge an entry \(s_i\) in \(\textbf{s}\) that indicates whether the edge is in the graph or not. Denoting the constructed graph by \(C = C(\textbf{s})\), the cost function is simply given bywhere \(\lambda = 1\) in the case of \(c_{s,t}\), except when searching for particular improvements on the bounds on \(c_{s,t}(x)\), and \(\lambda \gg 1\) in the case of \(g_{s,t}\) to act as a Lagrangian multiplier to ensure that the constraint \(k_t(C[m]) = 0\) is fulfilled. This cost function is easily calculated through Lemma 3.2.

The Cayley graph search space. The effectiveness of any search method will primarily be governed by the number N of variables used to construct the graph. However, at least for the motivating \(K_4\)-Ramsey multiplicity problem, we found that the quality of a construction was strongly dependent on its number of vertices n. Since in the general graph space \(N={n\atopwithdelims ()2}\) is quadratic in n, searching for constructions becomes intractable when the number of vertices reaches the fourties. In order to access graphs beyond that, we explored the family of Cayley graphs, for which more efficient description is available.

Given a group \(\textbf{G}\) and a set \(S \subseteq \textbf{G}\setminus \{1\}\) satisfying \(S = S^{-1}\), the corresponding Cayley graph \(C=C(\textbf{G}, S)\) has vertex set \(\textbf{G}\) and two vertices \(g_1, g_2\) are connected by an edge if \(g_1 s = g_2\) for some \(s \in S\). A state \(\textbf{s}\in \{0,1\}^N\) represents the generating set \(\bigcup _{\textbf{s}_A=1} A\) where each subset \(A=\{g, g^{-1}\}\) for \(g\in \textbf{G}\) corresponds to an entry \(\textbf{s}_{A}\) in \(\textbf{s}\). Denoting the Cayley graph constructed this way by \(C = C(\textbf{s})\), the relevant cost function is again given by Eq. (5).

The number N of variables needed to encode a Cayley graph is between \(|\textbf{G}|/2\) and \(|\textbf{G}| - 1\). This is only linear in the number of vertices, which allows us to search for graphs an order of magnitude larger. Additionally, Cayley graphs form a substantial subset of vertex-transitive graphs [40, 41], making them a highly relevant source of constructions. Both circumstantial evidence and the following lemma, stating that in an optimal construction, the number of \(K_4\) and \(\overline{K_4}\) at each vertex is asymptotically the same, support this relevance. Given a graph G and set of vertices \(S \subseteq V(G)\), let \(k_t(G, S)\) denote the number of cliques of size t in G containing all vertices of S. The proof is based on that of [3, Proposition 8].

Since the early 80s, many heuristic methods have been suggested for solving NP-hard optimization problems, particularly for combinatorial problems with discrete search spaces. We focus on two well-established methods that gained traction in the search for Ramsey numbers [22, 23, 59] and provide an accessible introduction to both, complementing a recent growing interest in computational means in Extremal Combinatorics [51, 71, 90, 91]. Although heuristics inherently lacking global optimality guarantees, matching flag algebra lower bounds and stability results can, in this particular case, establish the optimality and uniqueness of heuristic solutions. For more information on the subject of heuristic search methods, we refer the interested reader to the handbook of Gendreau and Potvin [31]. We also discuss the efficacy of a more recent Machine Learning-based approach compared to these methods in Sect. 5.3.

Simulated Annealing. Simulated Annealing (SA) is a probabilistic technique that can be interpreted as a modified local search. It accepts worse states according to a probabilistic acceptance criterion, which is modified over time to reject worse states and avoid getting trapped in local minima. SA was originally proposed by Kirkpatrick, Gelatt and Vecchi [49], and its impact has been significant; in 2014, the original paper was listed as one of the 100 most cited scientific papers of all time [86]. Algorithm 1 describes the algorithm in pseudocode.

To more precisely describe the algorithm, let \({\mathcal {N}}: \{0,1\}^N \rightarrow {\mathcal {P}}(\{0,1\}^N)\) denote some notion of neighborhoods of the states. We restricted ourselves to considering states as neighboring if their Hamming distance is 1. The algorithm starts with a random state \(\textbf{s}_0\) and executes a fixed number of iterations I, where in each iteration \(1 \le i \le I\) we pick a candidate state \(\textbf{s}_c\) uniformly at random from \({\mathcal {N}}(\textbf{s}_{i-1})\) and accept it based on the probabilistic Metropolis’ criterion [60]. See also Dueck and Scheuer [18] for a variant that avoids the probabilistic nature of SA. The temperature sequence \((t_i)_{1 \le i \le I}\) typically converges to 0, and SA functions more like a local search as it does. There are many details when implementing SA, and the presentation here should not be considered authoritative. Due to the relatively cheap computation of \(c(\textbf{s}')\) for any \(\textbf{s}' \in {\mathcal {N}}(\textbf{s})\), we implemented a variant of SA that avoids rejecting states by directly sampling candidates from an appropriate distribution dictated by Metropolis’ criterion, as previously suggested by Greene and Supowit [38].

Tabu Search. Tabu Search, an even simpler search heuristic than SA, was suggested by Glover [33‐35]. Like SA, it can be viewed as a modified local search aimed at avoiding local optima and cycles. We start with a randomly initialized state \(\textbf{s}_0\) and require a notion of neighborhood \({\mathcal {N}}: \{0,1\}^N \rightarrow {\mathcal {P}}(\{0,1\}^N)\). We execute I iterations, where in each iteration \(1 \le i \le I\), we pick the neighboring state \(\textbf{s}\in {\mathcal {N}}(\textbf{s}_{i-1})\) with the lowest associated cost and that has not been visited recently, regardless of whether it improves upon \(c(\textbf{s}_{i-1})\). Algorithm 2 contains the pseudo-code for Tabu Search.

There are many degrees of freedom when implementing this algorithm. One modification we made was to the history implementation: instead of storing a history of the last \(\ell \) states and excluding those from the update, we store a list of the last \(\ell \) modified bits and exclude any state that differs from the current one in one of those bits. This slightly increases the number of excluded states but drastically reduces the computational and implementation effort required to determine which states to exclude.

It is crucial to have an efficient implementation of the cost function c for both methods, particularly since they are often run in parallel for various initial states. In our application, we precomputed the relevant indices for all cliques, considering multiplicity, and stored the results in a matrix format. This approach allowed us to evaluate c using only elementary matrix operations on a GPU, substantially improving efficiency when assessing multiple states in parallel.

We implemented all search methods in Python and Pytorch and logged the results using Weights & Biases [7]. We relied on the GAP [30] component in SageMath and in particular the Small Groups library for Cayley graph constructions. We will represent graphs using their graph6 representation, a 6-bit encoding of the upper triangle of the graph adjacency matrix. This representation can be most easily decoded using SageMath and a formal description is available at .​ Graph descriptions too large to be included in this paper are available at .​ We also provide a survey of the derivation of previous constructions and describe the process we used to obtain our bounds for additional context.

Suppose we have a (possibly empty) family \({\mathcal {X}}\) of forbidden graphs. Let \({\mathcal {G}}_n = {\mathcal {G}}_n({\mathcal {X}})\) denote set of all graphs up to isomorphism of some given order n not containing any graph in \({\mathcal {X}}\) as an induced subgraph and write \({\mathcal {G}}= {\mathcal {G}}({\mathcal {X}}) = \bigcup _{n \in {\mathbb {N}}} {\mathcal {G}}_n ({\mathcal {X}})\). For two graphs G and H we let \(d_H(G)\) denote the induced subgraph density of H in G, that is the probability that |V(H)| vertices chosen uniformly at random in G induce a copy of H. Consider a graph parameter \(\lambda : {\mathcal {G}}\rightarrow {\mathbb {R}}\) for which there exists some \(n_0 \in {\mathbb {N}}\) such that \(\lambda \) satisfies the averaging equalityfor any \(n \ge n_0\) and \(G \in {\mathcal {G}}\) of order at least n. We note that the results in this paper are limited to families of forbidden graphs \({\mathcal {X}}= \emptyset \) and \({\mathcal {X}}= \{K_t\}\) as well as the graph parameter \(\lambda (G) = d_{K_s}({\overline{G}}) + d_{K_t}(G)\), which clearly satisfies Eq. (6) with \(n_0 = \max \{s,t\}\).

For any infinite subset \({\mathcal {H}}\subseteq {\mathcal {G}}\), we writewhere for notational convenience \(\lambda (n, {\mathcal {H}}) = \infty \) when \({\mathcal {H}}\cap {\mathcal {G}}_n = \emptyset \). We are of course primarily interested in studying \(\lambda ({\mathcal {G}})\), though we keep the notation general, as we will need it when establishing stability. Note that a trivial lower bound that follows from Eq. (6) is \(\lambda ({\mathcal {G}}) \ge \lambda (m, {\mathcal {G}})\) for any arbitrary \(m \ge n_0\).

The goal of the flag algebra approach is to establish the existence of coefficents \(a_H \in {\mathbb {R}}\) for some fixed \(m \in {\mathbb {N}}\) satisfying the inequalityfor any G of order at least m, as this implies the, hopefully improved, lower bound ofIn order to establish the type of coefficients commonly achieved through the solution of an SDP, we will need some additional notation. Note that the term strong (graph) homomorphism between two (potentially looped) graphs \(G_1\) and \(G_2\) refers to any map \(\psi : V(G_1) \rightarrow V(G_2)\) satisfying \(\{v_1, v_2\} \in E(G_1)\) if and only if \(\{\psi (v_1), \psi (v_2)\} \in E(G_2)\).

We will denote the set of all \(\tau \)-flags of order \(l \ge v\) by \({\mathcal {F}}_{\tau }^{l}\). Let \(F, F' \in {\mathcal {F}}_{\tau }^{l}\) be two \(\tau \)-flags of same order and \(H \in {\mathcal {G}}\) an arbitrary graph of order at least \(2l - v\). Let \(\theta :[v] \hookrightarrow V(H)\) be an arbitrary injective map implying a partial labelling of H (but not necessarily turning \((H, \theta )\) into a \(\tau \)-flag) and write \(d^{\theta }_F(H)\) for the probability that \(l-v\) vertices selected uniformly at random in \(V(H) \setminus \theta ([v])\) together with the vertices labelled by \(\theta \) induce a flag isomorphic to F. Obviously this value is 0 whenever \((H, \theta )\) is not a \(\tau \)-flag. We will write \(d_F(H) = {\mathbb {E}}_{\theta } \, d^{\theta }_F(H)\) for the flag density, where we are taking the uniform distribution over all possible injective maps \(\theta \). We will likewise write \(d^{\theta }_{F, F'}(H)\) for the probability that a subset \(S_1\) of \(V(H) \setminus \theta ([v])\) of size \(l-v\) chosen uniformly at random together with the vertices labelled through \(\theta \) is isomorphic to F and that another subset \(S_2\) of \(V(H) \setminus \big ( \theta ([v]) \cup S_1 \big )\) of size \(l-v\) chosen uniformly at random together with the vertices labelled through \(\theta \) is isomorphic to \(F'\). We will write \(d_{F,F'}(H) = {\mathbb {E}}_{\theta } \, d^{\theta }_{F, F'}(H)\) for the flag pair density.

We note that Eq. (6) holds for the flag pair density when \(m \ge 2l-v\), that isfor arbitrary \(G \in {\mathcal {G}}\). We also note that \(d_F^{\theta }(G) \, d_{F'}^{\theta }(G) = d_{F, F'}^{\theta }(G) + O(1/n)\) and henceUsing this notation, we can now state the heart of the SDP-based flag algebra approach.

This proposition motivates the following SDP formulation: given two symmetric matrices A and B of equal size, we will use the inner product \(\langle A,B \rangle = \text {tr}(A^T B)\). Write \(D^{(i)}(H)\) for the symmetric matrix of size \(|{\mathcal {F}}_{\tau _i}^{l_i}| \times |{\mathcal {F}}_{\tau _i}^{l_i}|\) for \(1 \le i \le r\) whose entries are given by \(d_{F,F'}(H)\) when using flags \(F \in {\mathcal {F}}_{\tau _i}^{l_i}\) as indices. Write \(D_H\) for the symmetric block diagonal matrix with the integer 1 as its first and \(D^{(i)}(H)\) as the following blocks for \(1 \le i \le r\). Finally, let C denote the matrix of equal size to \(D_H\) with all-zero entries except for the first, which is 1. We are now interested in solvingFinding a positive semi-definite matrices X that solves this SDP is equivalent to finding \({\mathcal {Q}}^{(i)}\) that maximize the right hand side of Eq. (11). Of course, most actual solvers will take advantage of the block-diagonal structure that we may assume for X given the problem formulation, rather than optimizing over the whole space of positive semi-definite matrices.

After finding matching upper and lower bounds, it is natural to ask whether the construction is unique and stability holds, i.e., if anything that comes close to the optimal value must be close to the extremal construction. Statements like this can usually be derived by extracting additional information from a flag algebra based proof and appealing to the Induced Removal Lemma of Alon et al. [1]. Pikhurko et al. [65] formalized this process, establishing sufficient criteria for various stability forms. We will present this succinctly while highlighting two improvements: introducing and strengthening the notion of reconstructors to derive stability from smaller Flag-Algebra-based proofs, and formalizing an argument for establishing the optimal weighting of a blow-up. Let us start by establishing some additional notions relating to Theorem 4.2.

A graph that is not sharp asymptotically does not appear as a subgraph in any extremal sequence, see for example Lemma 4.1 in [66] for a proof of this statement.

Sharp graphs therefore usually give a good indication of which graphs can occur as subgraphs in an extremal sequence and have in the past been used to find novel constructions.

If a certificate \((m, (\tau _i), ({\mathcal {Q}}^{(i)}) )\) is sufficiently large in relation to our believed extremal construction C, say \(m \ge |V(C)| + 1\), and stability is believed to hold, then establishing it is often a reasonably straight-forward matter of verifying that the only sharp graphs are those that occur with positive density in the blow-up sequence of C and then invoking the Induced Removal Lemma. This is often far beyond the realm of being computationally feasible, so we need a way to establish the structure of a construction C using only graphs of order m, where m is preferably as small as possible. This was already done implicitly in [66] and the same ideas can also be found in [65], where some sufficient requirements are part of the general criteria stated there. We find it helpful though to state the exact requirements separately from the statements used to establish the stability result, as this is the place were the most can be achieved using ad-hoc arguments invoking the structure of C. This motivates the following definition.

Let us introduce some additional notions. For a given graph C, we say that a graph T uniquely embeds into C if there exists a strong homomorphism \(\psi : V(T) \rightarrow V(C)\) and \(\psi \) is unique up to automorphism, that is for any additional strong homomorphism \(\psi ': V(T) \rightarrow V(C)\) there must exist \(\varphi _T \in \text {Aut}(T)\) and \(\varphi _C \in \text {Aut}(C)\) such that \(\varphi _C \circ \psi ' \circ \varphi _T \equiv \psi \). For a set of vertices \(X \subseteq V(C)\), we write \(N_{C,X}(v) = N_C(v) \cap X\) for the neighborhood of any \(v \in V(C)\) in X. We let \(\sim _X\) denote the equivalence relationship induced in V(C) by \(N_{C,X}\) and \([v]_X\) the equivalence class containing \(v \in V(C)\). We say X defines unique neighborhoods in C if \([v]_X = \{v\}\) for all \(v \in V(C)\).

It is easy to see that a graph C is an \(\ell \)-reconstructor of itself if \(|V(C)| \le \ell -1\). More commonly though, the following lemma is used, which is also implicit in Theorem 4.1 in [65].

A more technical but stronger condition was previously already implicitly formulated in [66] to establish stability of the Clebsch graph for \(g_{6,3}\) using a certificate with \(m = 7\). Here we further strengthen it in the form of the following lemma.

Having established how to find reconstructors, let us now formally introduce the relevant notion of stability and how to establish it using a reconstructor. Letdenote the set of all blow-ups of C and assume that we have established that \(\lambda ({\mathcal {G}}) = \lambda ({\mathcal {B}}(C))\).

Perfect stability strengthens the standard notion of stability, where one requires that for every \(\varepsilon > 0\) there exists \(\delta > 0\) such that \(\lambda (G) \le \lambda ({\mathcal {G}}) + \delta \) and \(n \ge 1/\delta \) implies that one has to change at most \(\varepsilon n^2\) edges to obtain a graph in \({\mathcal {B}}(C)\). Clearly perfect stability also implies that any \(G \in {\mathcal {G}}_n\) with \(n \ge n_0\) satisfying \(\lambda (G) = \lambda (n, {\mathcal {G}})\) is a blow-up of C.

Theorem 4.9 in combination with Lemma 4.7 allows us to establish our stability results. However, this only implies that extremal constructions must be some blow-up of a given graph C of order n. One can go further though and establish that a particular weighting of the blow-up must be optimal. For both of our applications, that weighting will be the balanced one. For any vector of weights \(\textbf{w}\in {\mathbb {S}}_n\), where \({\mathbb {S}}_n\) is the n-dimensional probability simplex, we defineas the set of all blow-ups of C where the parts are weighted according to \(\textbf{w}\) where \(w_i\) denotes the i-th entry of \(\textbf{w}\).

While theoretically the problem of establishing \(\mathop {\mathrm {arg\,min}}\limits _{\textbf{w}\in {\mathbb {S}}_n} \lambda ({\mathcal {B}}_{\textbf{w}}(C))\) could be stated as a polynomial minimization problem over \(n-1\) variables, the usual approach relies on studying if any of the matrices \({\mathcal {Q}}^i\) have unique zero eigenvectors and then invoking the subsequent proposition to relate them to graph densities, assuming the associated types \(\tau _i\) are present in C and fulfill certain properties. We will need the following result, c.f. Lemma 3.4 in [65]. Before stating it, assume some \(1 \le i \le r\) and \(\psi : [v_i] \hookrightarrow V(C)\) us given, where \(v_i\) is the order of \(\tau _i\), such that \((C, \psi )\) is a \(\tau _i\)-flag and \(w_j \ne 0\) for all \(j \in \psi ([v_i])\). Let \(\delta ^{\psi }_{F}(C, \textbf{w})\) now denote the probability that \(l_i - v_i\) vertices chosen not-necessarily-injectively and at random according to \(\textbf{w}\) in \(V(C) \setminus \psi ([v_i])\) together with the vertices labelled by \(\psi \) induce a flag isomorphic to F. Note that this generalizes the previous definition of \(d^{\psi }_{F}(C)\), where the vertices were selected uniformly at random.

Using this, one can formulate some sufficient criteria to establish the uniqueness of a given optimal weighting. The following is a generalization of Lemma 6.2 in [65] that is based on ideas previously used in [66].

flagmatic, developed by Emil Vaughan and hosted on , calculates graph densities and passes SDP formulations to solvers like CSDP [9] and SDPA [93]. In order to obtain rigorous mathematical proofs, the floating point-based solutions from the SDPs need to be rounded to (fractional) values while ensuring the matrices remain positive semi-definite. flagmatic handles this rounding process and produces verifiable certificates for the proofs, allowing anyone with access to the software to verify the results independently. The certificates for our lower bounds can be found at .​ We do not supply certificates of stability and symmetry from [65], as they are incompatible with our ad-hoc arguments in Lemma 4.7 and Theorem 4.9. Below we describe some specifics regarding the bounds for each problem.

Bounds and stability for \(c_{s,t}\). For the lower bounds of \(c_{3,4}\) and \(c_{3,5}\), we used \(m = 6\) and were able to reduce the number of types to 4 for each problem. The certificates for these proofs are contained in the files c_34.json and c_35.json.

In order to derive stability for \(c_{3,4}\), we also obtained a certificate for \(m = 7\) and verified that all sharp graphs are those with a strong homomorphism into the Schläfli graph. The certificate for this proof is contained in the file c_34_7.json. Perfect stability now follows from Theorem 4.9 using the uniquely embeddable subgraph T of \(C_{S}\) consisting of two triangles joined by an edge. The fact that T is a 7-reconstructor of the Schläfli graph follows by computationally verifying the requirements of Lemma 4.7. The certificate for the proof that \(\lambda ({\mathcal {G}}(\{T\}) > \lambda ({\mathcal {G}})\) is contained in the file c_34_reconstructor.json. The fact that the balanced blow-up of the Schläfli graph is the unique optimal weighting follows by applying Theorem 4.11. Here let the Schläfli graph be as ordered in the graph6 representation stated in Sect. 3.3 with vertices labelled \(1, \ldots , 27\) and use \(X_1 = \{1, 2, 4, 6, 7\}\), \(X_2 = \{1, 2, 12, 13, 14\}\) and \(X_3 = \{1, 2, 4, 6, 12\}\). The certificate for the proof that \(\lambda ({\mathcal {G}}(C_S[X_1])) > \lambda ({\mathcal {G}})\) is contained in the file c_34_symmetry.json.

Regarding the non-differentiability of \(c_{3,4}(x)\) at \(x = 41\cdot 3^{-6}\), we considered a differently weighted version of Eq. (1). For \(w_s, w_t \ge 0\) satisfying \(w_s + w_t = 2\), letand note that clearly \(c_{s,t} = c^{(1,1)}_{s,t}\). We used flagmatic to establish a lower bound for \(c^{(1-\epsilon ,1+\epsilon )}_{3,4}\) that matches the upper bound given by the Schläfli graph when \(\epsilon = 10^{-4}\), implying the non-differentiability of \(c_{3,4}(x)\) at that point. The certificate for this proof is contained in the file c_34_epsilon.json and uses \(m=6\) as well as the same types as the proof of \(c_{3,4}\).

For the lower bounds of \(c_5\) and \(c_{4,5}\), we used \(m = 8\) and the values obtained after rounding are reasonably close to those indicated by the SDP solver. The certificates for these proofs are contained in the files c_5.json and c_45.json.

Bounds and stability for \(g_{s,t}\). For \(g_{4,5}\), we used \(m = 7\) and also used the full 38 types to establish this bound as the rounding failed when attempting to reduce the number of types involved. In general, this problem seemed more demanding and for example required the double precision solver. The certificate for the proof is contained in the file g_45.json. We can also easily derive perfect stability from this certificate by verifying that all sharp graphs are those with a strong homomorphism into \(C_{R(3,5)}\) and noting that the graph T of order 5 obtained by joining two triangles at a vertex is a 7-reconstructor of \(C_{R(3,5)}\) by Lemma 4.6. The certificate for the proof that \(\lambda ({\mathcal {G}}(\{K_5, K_4^+\}) > \lambda ({\mathcal {G}}(\{K_5\})\) is contained in the file g_45_reconstructor.json. The fact that the balanced blow-up of \(C_{R(3,5)}\) is the unique optimal weighting also easily follows by applying Theorem 4.11 with T as \(C[X_1]\) and \(k=1\) after verifying that the associated matrix \({\mathcal {Q}}\) indeed has co-rank 1.

All of the reported lower bounds for \(g_{s,t}\) when \((s,t) \ne (4,5)\) were obtained using \(m = 8\). The certificates for these proofs are contained in the files g_st.json.

The crucial question regarding the Ramsey multiplicity of \(K_4\) is whether it whether there exists a graph whose blow-up sequence determines its value. Our answer to the \(c_{3,4}\) and \(c_{3,5}\) problem supports this possibility for \(c_4\). Our efforts for Theorem 1.1 however show that this construction could be unexpectedly complex.

In any case, the deeper understanding of the generating sets of our Cayley graphs on 192, 384, and 768 vertices, to the extent that they can be generalized, for arbitrary large k, to (semi-)direct products of the 3-element cyclic group \({\mathbb {Z}}_3\) with k copies of \({\mathbb {Z}}_2\), would be extremely interesting. Besides that they would of course improve the upper bound on \(c_4\), more importantly they might shed light on how to count cliques in blow-ups of certain Cayley graphs. This could also lead to identifying the right choice of generating sets and help in constructing new Cayley graph sequences that improve the value of \(c_t\) for \(t\ge 5\). This would be particularly desirable, since the best known general upper bound for the Ramsey multiplicity problem still comes from the original construction of Thomason [83], the analysis of which was improved by Jagger, Štovíček, and Thomason [45] to \(c_t < 0.835 \cdot 2^{1-{t\atopwithdelims ()2}}\) for \(t \ge 7\) via a direct counting of the homogeneous sets in the blow-up with Fourier analytic methods.

For large t Rödl conjectured (cf. [27]) that \(c_t 2^{{t\atopwithdelims ()2}} \rightarrow 0\), possibly even exponentially fast. Yet, no t is known where the value of the quotient is less than 1/2. The best known general lower bound is due to Conlon [14] who showed that \(c_t \ge C^{-t^2 (1+o(1))}\) where \(C \approx 2.18\). Conlon comments, that his proof is the Ramsey multiplicity analogue of the Erdős-Szekeres proof for the symmetric Ramsey number. Hence it seems plausible that the approach of the recent improvements of Campos, Griffiths, Morris, and Sahasrabudhe [12] on the upper bound of the symmetric Ramsey number could be adapted to improve Conlon’s constant C, though likely not to the best possible \(\sqrt{2}\).

Additionally, we explored graphs with small clique densities of order s and given independent set densities of order t. It is a tantalizing open problem to determine, or just obtain a better idea about the lower bounding curve \(c_{3,4}(x)\) of the region of realizable \(K_3\)- and \({\bar{K}}_4\)-density pairs in graphs. Given the results in Fig. 2, even formulating a conjecture seems challenging. The properties of the curve, such as the number of non-differentiable points, what constructions they would be determined by, and convexity or concavity, remain unclear. The argument of Bollobás [8] giving a piece-wise linear lower bound for \(c_{2,t}(x)\) does not seem to generalize easily.

Nikiforov [62] established that \(g_{s,t} = (t-1)^{1-s}\) holds only for a finite number of pairs \(s,t \ge 3\), that is for all but a finite number of such pairs the construction given by Turán graphs is not optimal. Das et al. [15] established that equality does not hold for \(s > 3\) and arbitrary t as well as for \(t \ge 2074\) when \(s = 3\). The results of Pikhurko and Vaughan [66] establish that equality holds when \(s = 3\) and \(t \le 7\). The following proposition shows that there must exist a smallest \(7 < t_0 \le 2074\) such that \(g_{3,t} = 1/(t-1)^2\) for \(t < t_0\) and \(g_{3,t} < 1/(t-1)^2\) for \(t \ge t_0\). It would be interesting to precisely determine this value and to therefore determine all pairs of s, t for which Erdős’ original intuition about the Turán graph holds true.

Recent interest has emerged in using Machine Learning approaches to tackle combinatorial optimization problems. Specifically, Wagner [91] proposed finding constructions in Extremal Combinatorics by framing the underlying optimization problems within a Reinforcement Learning context, an idea similar to the ‘active learning’ approach suggested earlier by Bello et al. [6]. In the context of round-based games and Reinforcement Learning, states are constructed bit-by-bit, using a Neural Network to decide for each bit whether it should be 1 or 0 based on previous decisions. After sampling several discrete states through this procedure, the Neural Network’s parameters are updated to produce states closer to the best ones sampled. The update procedure in [91] employs the Cross-Entropy (CE) method by Rubinstein [72, 73].

We experimented a fair amount with Reinforcement Learning-based methods, including different network architectures and learning methods from the ones suggested in [91], but found their performance inferior to both SA and Tabu Search (TS) in terms of solution quality and computation time for medium and large-sized problems:While the values above do no constitute fully rigorous and definitive benchmarking of the three methods, they do reflect a fair amount of (hyper)parameter tuning as well as our anecdotal experience for these particular problems. We find it notable that for the problems studied here Tabu Search, with its straightforward idea and implementation, emerged as perhaps the most preferable method, fairly reliably finding good solutions in a short amount of time while requiring essentially zero tuning.

The idea of pretraining-free learning-based meta-heuristics using neural networks has a long history [42, 80], but seems to so far not yet outperform simple baselines. There is a fair amount of ongoing research focused on improving optimization methods by training their behavior on dedicated training datasets, which are hoped to reflect real-world applications prior to the actual usage of these methods. However, this approach strongly differs from our use case, where we are predominantly interested in solving singular, difficult problems rather than a large pool of small or moderately-sized ones. It should be further noted that an RL-based approach is inherently wasteful in our particular context, that is for attacking simple black-box discrete optimization problems given by Eq. (4); it models a distribution over the states \(\{0,1\}^N\) through N consecutive evaluations of a neural network. This round-based approach is artificially imposed, since, unlike with playing chess or Go, we do not have any opponent’s choices to respond to and our distribution will ultimately collapse to a single state. This effectively means that rather than trying to find (an approximation of) a strategy, i.e., a still very large sub-tree of the full game tree, we are merely looking for a single path from the root to a leaf.

Before it was disproved, the conjecture of Erdős mentioned in the introduction was generalised to arbitrary graphs by Burr and Rosta [10]. For graphs H and G we let t(H, G) be the number of copies of H in G andWe note that \(c_t = c(K_t)\) and while Burr and Rosta conjectured that the minimum is always attained by the random graph, we say that a graph H is common if \(c(H) = 2^{1-|E(H)|}\) and uncommon otherwise. A triangle is common by Goodman’s result and Thomason’s [83] result implies that \(K_t\) is uncommon for \(t \ge 4\). Since then large families of common and uncommon graphs have been found and for an overview we refer to the recent paper of Grzesik, Lee, Lidicky, and Volec [39] and the references therein. Only recently the first uncommon graphs H were found, for which c(H) is known [26]. Also an off-diagonal variant of common and uncommon pairs of graphs was studied by Behague, Morrison, and Noel [4, 5]. Lower bounds for common graphs are usually obtained through the flag algebra approach and upper bounds rely on constructions that beat \(2^{1-|E(H)|}\). There is also an interesting connection to the famous and still open conjecture of Sidorenko [78], which implies that every bipartite graph is common.

Similar problems to the ones considered in this paper have been studied in Additive Combinatorics, where one is interested in minimizing the number of monochromatic solutions to some system of linear equations in a coloring of the integers \([n] = \{1, \ldots , n\}\), the cyclic group \({\mathbb {Z}}_n\) or the repeated product of a fixed small finite field \({\mathbb {F}}_q^n\). Graham, Rödl and Ruciński [37] asked this question regarding Schur triples in two-colorings of [n], which was independently resolved by Datskovsky [16], Robertson and Zeilberger [70], and Schoen [77], who showed that the true answer lies far below the number expected in a random coloring. In contrast to this, Cameron, Cilleruelo and Serra [11] showed that in finite groups the number of monochromatic solutions to any equation in an odd number of variables, which includes Schur triples, is minimized by the random coloring. Wolf [92] as well as Lu and Peng [57] studied the question of how many 4-term arithmetic progressions a two-coloring of \({\mathbb {Z}}_n\) can contain. Interestingly, the upper bounds given for this type of problem likewise consist of a type of ‘blow-up’ of a finite construction, indicating that the methods used here are also applicable in this context. In fact, denoting the minimum fraction of monochromatic k-term arithmetic progressions in a 2-coloring of \({\mathbb {Z}}_n\) by \(m_k({\mathbb {Z}}_n)\), it is easy to derive the following lemma from their work (see the proof of Lemma 4.1 and Theorem 1.5 in [57]).

Lu and Peng [57] found a construction for \(k=4\) with \(n=11\) and \(\ell =1\) giving \(\liminf m_4({\mathbb {Z}}_n) \le 1/12\). Using Tabu Search we found the following partial colorings of \({\mathbb {Z}}_{44}\)and of \({\mathbb {Z}}_{226}\)that together with Lemma 5.2 establish \(\liminf _{n \rightarrow \infty } m_5({\mathbb {Z}}_n) \le 1/48\) as well as \(\liminf _{n \rightarrow \infty } m_6({\mathbb {Z}}_n) \le 1/228\) with the former improving upon a bound found by Lu and Peng [57], who also conjectured their construction for \(k=4\) to be tight. We believe that our constructions for \(k=5, 6\) provide tight bounds as well.

Lastly, we note that Saad and Wolf [75] also initiated a more systematic study of the question when the answer is given by random colorings, with recent results by Fox, Pham and Zhao [25], Kamčev, Liebenau and Morrison [46, 47] as well as Versteegen [88, 89]. Rué and the third author also recently extended the flag algebra framework to additive problems in vector spaces over finite fields [74].

Note. Recently McKay [58] experimented with various local search strategies in order to further improve the upper bound on \(c_4\). Starting from our best Cayley graph on 768 vertices, his search iteratively switches the edge/non-edge status of certain pairs of vertices. The most successful attempt created a graph with value \(10486266368/768^4=0.0301422734319\), which is an improvement over Theorem 1.1 of the order \(10^{-6}\). McKay’s graph has 768 vertices, 148724 edges, 536 vertices of degree 387, 232 vertices of degree 388, and, unlike our construction, has a trivial automorphism group.