Abstract

The Ramsey multiplicity problem asks for the minimum asymptotic density of monochromatic labelled copies of a graph \(H\) in a red/blue colouring of the edges of \(K_n\). We introduce an off-diagonal generalization in which the goal is to minimize a certain weighted sum of the densities of red copies of one graph and blue copies of another. We build up various properties of this new notion, including a useful “dual formulation,” and use these results to solve the problem for several pairs of graphs.

1 Introduction↩︎

The Ramsey number of a pair \((H_1,H_2)\) of graphs, denoted by \(r(H_1,H_2)\), is the minimum integer \(N\) such that every colouring of the edges of the complete graph \(K_N\) with red and blue contains a red copy of \(H_1\) or a blue copy of \(H_2\). The existence of \(r(H_1,H_2)\) is implied by a famous theorem of Ramsey from 1929 [1]. Determining exact values of Ramsey numbers, even for small graphs, is notoriously difficult; e.g. \(r(K_5,K_5)\) is still unknown. For a list of bounds on small Ramsey numbers, see [2] and, for a survey of asymptotic results, see [3].

A natural quantitative extension of this problem is to ask, given \(N\gg r(H_1,H_2)\), at least how many red copies of \(H_1\) and blue copies of \(H_2\) must appear in a red/blue colouring of the edges of \(K_N\)? To make this question meaningful, we must explain how “copies” are counted, and specify the relative weighting on copies of \(H_1\) or \(H_2\). A homomorphism from a graph \(H\) to a graph \(G\) is a map \(f:V(H)\to V(G)\) such that \(f(u)f(v)\) is an edge of \(G\) whenever \(uv\) is an edge of \(H\). Let \(\hom(H,G)\) be the number of homomorphisms from \(H\) to \(G\). The homomorphism density \(t(H,G)\) of \(H\) in \(G\) is the probability that a random function from \(V(H)\) to \(V(G)\) is a homomorphism; that is, \[t(H,G):=\frac{\hom(H,G)}{v(G)^{v(H)}}\] where \(v(F):=|V(F)|\) for every graph \(F\). Since there are only \(O\left(v(G)^{v(H)-1}\right)\) non-injective functions from \(V(H)\) to \(V(G)\), the homomorphism density is a good proxy for the number of labelled copies of \(H\) in \(G\) when \(G\) is a large dense graph. The Ramsey multiplicity constant (see, e.g., [4]–[7]) of \(H\) is defined as follows: \[c(H) := \liminf_{n\to\infty}\left[t(H,G_n)+ t(H,\overline{G_n})\right]\] where \(G_1,G_2,\dots\) is a sequence containing every finite graph exactly once. By thinking of the edges of \(G_n\) and \(\overline{G_n}\) as being red and blue, respectively, we can view \(c(H)\) as the limit as \(n\) tends to infinity of the minimum proportion of monochromatic labelled copies of \(H\) over all red/blue colourings of the edges of \(K_n\); it is a nice exercise to show that the limit exists.

Computing \(c(H)\) is a difficult problem in general. For example, despite receiving a fair amount of attention [6], [8]–[13], the value of \(c(K_4)\) is still unknown. A graph \(H\) is said to be common if \(c(H)=2^{1-e(H)}\), where \(e(H):=|E(H)|\). In other words, \(H\) is common if its Ramsey multiplicity constant is achieved by a sequence of uniformly random colourings. There are now many families of graphs that are known to be common [6], [12]–[22], but the problem of classifying such graphs is wide open. Very recently, Fox and Wigderson [7] determined \(c(H)\) for a wide range of uncommon graphs \(H\); prior to this result, there were no uncommon graphs \(H\) for which \(c(H)\) was known.

In this paper, we investigate an “off-diagonal” extension of Ramsey multiplicity problems to pairs \((H_1,H_2)\) of graphs. Roughly speaking, the goal is to minimize a weighted sum of the homomorphism densities of \(H_1\) and \(H_2\) in a large graph \(G\) and its complement, respectively. The weighting will be chosen in such a way that this minimum density is as large as possible (see Definition 1). This choice is motivated by a desire to establish a “balance” between red copies of \(H_1\) and blue copies of \(H_2\); a nice consequence of this choice is a natural dual formulation of the problem, which we shall discuss in Section 3.

Definition 1. Given graphs \(H_1\) and \(H_2\) and \(\lambda\in [0,2]\), define the \(\lambda\)-Ramsey multiplicity constant of \((H_1,H_2)\) to be \[c_\lambda(H_1,H_2):=\liminf_{n\to\infty}\left[\lambda \cdot t(H_1,G_n)+ (2-\lambda)\cdot t(H_2,\overline{G_n})\right]\] where \(G_1,G_2,\dots\) is a sequence containing every finite graph exactly once.³

Remark 1. Clearly, \(c_\lambda(H_1,H_2)=c_{2-\lambda}(H_2,H_1)\) for any graphs \(H_1,H_2\) and \(\lambda\in[0,2]\).

Remark 1. By definition, \(c(H)=c_1(H,H)\) for any graph \(H\).

Note that \(0\leq t(H,G)\leq1\) for every pair of graphs \(H\) and \(G\); thus, the following statement holds trivially.

Observation 1. \(0\leq c_\lambda(H_1,H_2)\leq2\) for any two graphs \(H_1\) and \(H_2\) and \(\lambda\in[0,2]\).

Definition 1, specialized to the case that \(H_1\) and \(H_2\) are complete graphs, appeared in a recent paper of Parczyk, Pokutta, Spiegel and Szabó [9]. The results of [9] include the following: \[c_1(K_3,K_4)=\frac{689}{3^8}\text{ and }c_1(K_3,K_5)=\frac{24011}{3^{12}}.\] In both of these cases, the tight examples are colourings based on blow-ups of the \(27\)-vertex Schläfli graph or its complement. Also, in [9], they mention that the tight colouring for \(c_1(K_3,K_4)\) also provides a tight bound on \(c_{1-\epsilon}(K_3,K_4)\) for \(\epsilon=10^{-4}\).

Outside of a few inherently natural choices for \(\lambda\) (e.g. \(\lambda=1\)), it can be hard to argue that any particular \(\lambda\) provides the “correct” weighting on copies of \(H_1\) and \(H_2\). The following definition is an attempt to find a “natural” choice of \(\lambda\) by taking the supremum of \(c_\lambda(H_1,H_2)\) over all possible \(\lambda\). This new notion is the central focus of this paper.

Definition 1. Given graphs \(H_1\) and \(H_2\), define the balanced Ramsey multiplicity constant of \((H_1,H_2)\) to be \[c(H_1,H_2):=\sup_{\lambda\in[0,2]}c_\lambda(H_1,H_2).\]

The following is a simple consequence of Remark 1.

Fact 1. For any graphs \(H_1\) and \(H_2\), \(c(H_1, H_2) = c(H_2, H_1)\).

In this paper, we aim to establish some basic properties of the balanced Ramsey multiplicity constant, elucidate connections between it and well-studied problems in extremal graph theory and exactly determine \(c(H_1,H_2)\) for several explicit pairs of graphs. The following theorem says that balanced Ramsey multiplicity generalizes usual Ramsey multiplicity, just as one would hope.

Theorem 1. For any graph \(H\), \[c(H,H)=c(H).\]

A well-known conjecture of Sidorenko [23], now known to be equivalent to an earlier conjecture of Erdős and Simonovits [24], says that, if \(H\) is bipartite, then \(t(H,G)\geq t(K_2,G)^{e(H)}\) for every graph \(G\). A graph \(H\) with this property is said to be Sidorenko. For background on Sidorenko’s Conjecture, see the recent paper [25] and the references therein. We prove the following theorem, which determines the balanced Ramsey multiplicity constant of every pair of Sidorenko graphs. This will be derived as a corollary of a more general result (Theorem 1), stated and proven in Section 4. A graph \(H\) is said to be empty if its edge set is empty.

Theorem 1. Let \(H_1\) and \(H_2\) be non-empty graphs and let \(p\in(0,1)\) be such that \(p^{e(H_1)}=(1-p)^{e(H_2)}\). If \(H_1\) and \(H_2\) are Sidorenko, then \[c(H_1,H_2)=2\cdot p^{e(H_1)}=2\cdot (1-p)^{e(H_2)}.\]

In other words, Theorem 1 says that, if \(H_1\) and \(H_2\) are Sidorenko, then the optimal construction for \(c(H_1,H_2)\) is to colour each edge of \(K_n\) red with probability \(p\) and blue with probability \(1-p\), independently of all other edges, where \(p\) is chosen so that \(p^{e(H_1)}=(1-p)^{e(H_2)}\). The next theorem shows that random colourings can also be optimal when one of the graphs is not bipartite (and therefore not Sidorenko). For \(k\geq3\), let \(C_k\) denote the cycle of length \(k\). The banner graph \(B\) is the graph obtained from \(C_4\) by adding a pendant edge. See Figure 1.

Theorem 1. \(c(C_5,B)=c_{1}(C_5,B)=1/16\).

In contrast, the next two results concern situations in which the optimal colourings are highly structured.

Theorem 1. \(c(K_3,C_5)=c_{10/17}(K_3,C_5)=3/34\).

Let \(D\) be the graph obtained from \(K_4\) by deleting an edge, which is referred to as the diamond graph. Let \(M\) be the graph obtained from two disjoint triangles by adding one edge; we call \(M\) the moth graph.⁴ See Figure 1.

Theorem 1. \(c(D,M)=c_{5/6}(D,M)=1/36\).

Figure 1: The cycle C_5, the banner graph B, the diamond graph D and the moth graph M. — Figure 1: The cycle \(C_5\), the banner graph \(B\), the diamond graph \(D\) and the moth graph \(M\).

It is interesting to observe differences between the tight examples for Theorems 1 and 1. To prove the upper bound \(c_\lambda(K_3,C_5)\leq 3/34\), we use two different constructions of colourings to cover different ranges of \(\lambda\). In contrast, there is a single colouring which proves \(c_\lambda(D,M)\leq 1/36\) for all \(\lambda\in[0,2]\) simultaneously; see Section 4 for details.

In Section 2, we translate the key definitions in this paper into the language of graph limits and build up a few preliminary observations. In Section 3, we obtain an equivalent “dual formulation” of the problem of computing \(c(H_1,H_2)\) based on finding certificates in the form of two graph limit objects representing red/blue colourings of \(E(K_n)\) for large \(n\) with certain special properties; see Theorem 1. In Section 4, we use this dual formulation to prove Theorems 1 and 1 as well as all of the upper bounds in Theorems 1–1. In Section 5, we use flag algebras to prove the lower bounds in Theorems 1–1. Some of the calculations needed to verify these proofs will be included in an ancillary file with a later arxiv preprint of the paper. We conclude the paper in Section 6 by discussing several open problems.

2 Graph Limits↩︎

Many asymptotic notions in extremal graph theory can be elegantly formulated in terms of graph limits. Here, we will introduce only the aspects of graph limit theory that we require in this paper; for a comprehensive treatment of the subject, see [26].

A bounded measurable function \(U:[0,1]^2\to \mathbb{R}\) such that \(U(x,y)=U(y,x)\) for all \((x,y)\in [0,1]^2\) is called a kernel. A kernel \(W\) such that \(0\leq W\leq 1\) is a graphon. The set of all graphons is denoted by \(\mathcal{W}_0\). One way to think of a graphon is as an analytic extension of the concept of the adjacency matrix of a graph. In particular, if \(G\) is a graph with vertices \(v_1,\dots,v_n\), then we obtain a graphon \(W_G\) associated to \(G\) by dividing \([0,1]\) into \(n\) intervals \(I_1,\dots,I_n\) of measure \(1/n\) and setting \(W_G=1\) on the set \(\bigcup_{v_iv_j\in E(G)}\left(I_i\times I_j\right)\) and \(W_G=0\) elsewhere. Likewise, a kernel generalizes the concept of an edge-weighted graph. Because of these analogies, we often refer to an element \(x\in[0,1]\) as a vertex of a kernel \(U\).

The homomorphism density of a graph \(H\) in a kernel \(U\) is defined by \[t(H,U):=\int_{[0,1]^{V(H)}}\prod_{uv\in E(H)}U(x_u,x_v)\prod _{v\in V(H)}dx_v.\] It is easily observed that \(t(H,G)=t(H,W_G)\) for every graph \(G\), where \(W_G\) is a graphon associated to \(G\) defined in the previous paragraph. Therefore, the notion of homomorphism density for kernels generalizes homomorphism density for graphs. Next, we introduce a standard notion of convergence for dense graphs, which is often referred to as “left-convergence” in the graph limits literature.

Definition 1. Say that a sequence \((W_n)_{n=1}^\infty\) of graphons converges to a graphon \(W\) if \(\lim_{n\to\infty} t(H,W_n)=t(H,W)\) for every graph \(H\). A sequence \((G_n)_{n=1}^\infty\) of graphs is said to converge to a graphon \(W\) if \((W_{G_n})_{n=1}^\infty\) converges to \(W\).

The following “compactness” result is vitally important to the study of graph limits and extremal graph theory. For instance, it is a close relative of the powerful Szemerédi Regularity Lemma; see [27].

Theorem 1 (Lovász and Szegedy [28]). For any sequence \((W_n)_{n=1}^\infty\) of graphons, there is a subsequence \((W_{n_k})_{k=1}^\infty\) and a graphon \(W\) such that \((W_{n_k})_{k=1}^\infty\) converges to \(W\).

The next result tells us that graphons corresponding to finite graphs are “dense” in \(\mathcal{W}_0\).

Theorem 1 (See [26]). For every graphon \(W\) there is a sequence \((G_n)_{n=1}^\infty\) of finite graphs such that \(v(G_n)\to\infty\) and \((G_n)_{n=1}^\infty\) converges to \(W\).

We state another easy consequence of standard results in graph limit theory.

Lemma 1 (See, e.g., [26]). If \((G_n)_{n=1}^\infty\) is a sequence of graphs which converges to a graphon \(W\) such that \(v(G_n)\to\infty\), then \((\overline{G_n})_{n=1}^\infty\) converges to \(1-W\).

Our next goal is to rephrase the definitions from the introduction in terms of graph limits and to use this perspective to derive some basic properties. We start with the following alternative definition of \(c_\lambda(H_1,H_2)\).

Lemma 1. For any graphs \(H_1\) and \(H_2\) and any \(\lambda\in [0,2]\), \[c_\lambda(H_1,H_2)=\min_{W\in\mathcal{W}_0}\left[\lambda\cdot t(H_1,W) + (2-\lambda)\cdot t(H_2,1-W)\right].\]

Proof. By definition of \(c_\lambda(H_1,H_2)\), there exists a sequence \((G_n)_{n=1}^\infty\) of graphs such that \(v(G_n)\to\infty\) and \[\lim_{n\to\infty} [\lambda\cdot t(H_1,G_n) + (2-\lambda)\cdot t(H_2,\overline{G_n})]=c_\lambda(H_1,H_2).\] By Theorem 1, there is a subsequence \((G_{n_k})_{k=1}^\infty\) and a graphon \(W\) such that \((G_{n_k})_{k=1}^\infty\) converges to \(W\). By Lemma 1, \(\overline{G_{n_k}}\) converges to \(1-W\). Therefore, \[c_\lambda(H_1,H_2)=\lim_{n\to\infty} [\lambda\cdot t(H_1,G_n) + (2-\lambda)\cdot t(H_2,\overline{G_n})]\] \[= \lim_{k\to\infty} [\lambda\cdot t(H_1,G_{n_k}) + (2-\lambda)\cdot t(H_2,\overline{G_{n_k}})] = \lambda \cdot t(H_1,W)+(2-\lambda)\cdot t(H_2,1-W).\] So, there exists a graphon \(W\) such that \[\lambda \cdot t(H_1,W)+(2-\lambda)\cdot t(H_2,1-W)=c_\lambda(H_1,H_2).\] All that remains is to show that there cannot exist a graphon \(W'\) such that \[\lambda \cdot t(H_1,W')+(2-\lambda)\cdot t(H_2,1-W')<c_\lambda(H_1,H_2).\] To see this, we use Theorem 1. That is, if such a \(W'\) existed, then we could take \(G_1',G_2',\dots\) to be a sequence of graphs of increasing orders which converges to \(W'\). By Lemma 1, the sequence of complements of these graphs converges to \(1-W'\). However, then we would have \[\lim_{n\to\infty} [\lambda\cdot t(H_1,G_n') + (2-\lambda)\cdot t(H_2,\overline{G_n'})] = \lambda \cdot t(H_1,W')+(2-\lambda)\cdot t(H_2,1-W')<c_\lambda(H_1,H_2)\] which contradicts the definition of \(c_\lambda(H_1,H_2)\) and completes the proof. ◻

The previous lemma suggests the following definition.

Definition 1. Let \(H_1\) and \(H_2\) be graphs and \(\lambda\in [0,2]\). We say that a graphon \(W\) is \(\lambda\)-optimal for \((H_1,H_2)\) if \[\lambda\cdot t(H_1,W) + (2-\lambda)\cdot t(H_2,1-W) = c_\lambda(H_1,H_2).\]

Next, we show that \(c_\lambda(H_1,H_2)\) is continuous when viewed as a function of \(\lambda\).

Lemma 1. For any two graphs \(H_1\) and \(H_2\), \(c_\lambda(H_1,H_2)\) is a continuous function of \(\lambda\).

Proof. Suppose, to the contrary, that there exists \(\lambda,\lambda_1,\lambda_2,\ldots\in [0,2]\) and \(\varepsilon>0\) such that \((\lambda_n)_{n=1}^\infty\) converges to \(\lambda\) and \(|c_{\lambda_n}(H_1,H_2)-c_\lambda(H_1,H_2)|\geq \varepsilon\) for all \(n\geq1\). By Lemma 1, for each \(n\geq1\) we can let \(W_n\) be a \(\lambda_n\)-optimal graphon. By Theorem 1, there is a subsequence \((W_{n_k})_{k=1}^\infty\) and a graphon \(W\) such that \((W_{n_k})_{k=1}^\infty\) converges to \(W\). By Observation 1 and compactness of \([0,2]\), we can additionally assume that \(\lim_{k\to\infty}c_{\lambda_{n_k}}(H_1,H_2)\) exists. Since \(W_{n_k}\) is \(\lambda_{n_k}\)-optimal, we have that \[\label{eq:clambda1} \begin{gather} \lim_{k\to\infty} c_{\lambda_{n_k}}(H_1,H_2) = \lim_{k\to\infty} \lambda_{n_k}t(H_1,W_{n_k})+(2-\lambda_{n_k})t(H_2,1-W_{n_k})\\= \lambda\cdot t(H_1,W) + (2-\lambda)t(H_1,1-W)\geq c_\lambda(H_1,H_2)\end{gather}\tag{1}\] where the last inequality holds due to Lemma 1.

Now, by Lemma 1, we can let \(W'\) be a \(\lambda\)-optimal graphon. Applying Lemma 1 again, we see that \[c_{\lambda_{n_k}}(H_1,H_2)\leq \lambda_{n_k}\cdot t(H_1,W')+(2-\lambda_{n_k})\cdot t(H_2,1-W')\] for all \(k\geq1\). So, \[\label{eq:clambda2} \begin{gather} \lim_{k\to\infty}c_{\lambda_{n_k}}(H_1,H_2)\leq \lim_{k\to\infty}\left(\lambda_{n_k}\cdot t(H_1,W')+(2-\lambda_{n_k})\cdot t(H_2,1-W')\right)\\ =\lambda\cdot t(H_1,W')+(2-\lambda)\cdot t(H_2,1-W') = c_\lambda(H_1,H_2). \end{gather}\tag{2}\] Putting 1 and 2 together, we get that \[\lim_{k\to\infty}c_{\lambda_{n_k}}(H_1,H_2) = c_\lambda(H_1,H_2).\] However, this contradicts the assumption that \(|c_{\lambda_n}(H_1,H_2)-c_\lambda(H_1,H_2)|\geq \varepsilon\) for all \(n\geq1\) and completes the proof. ◻

Thus, by Lemma 1 and the Extreme Value Theorem, we get that the supremum in Definition 1 can be replaced by a maximum.

Corollary 1. For any graphs \(H_1\) and \(H_2\), \[c(H_1,H_2)=\max_{\lambda\in[0,2]}c_\lambda(H_1,H_2).\]

Next, we derive a lower bound on \(c_\lambda(H_1,H_2)\) via a standard double-counting argument.

Lemma 1. For any non-empty graphs \(H_1\) and \(H_2\) and \(\lambda\in[0,2]\), \[c_\lambda(H_1,H_2)\geq \frac{\min\{\lambda,2-\lambda\}\cdot(r(H_1,H_2)-\max\{v(H_1),v(H_2)\})!}{r(H_1,H_2)!}.\]

Proof. Let \(G_1,G_2,\dots\) be a sequence of graphs such that \(v(G_n)\to\infty\). By definition of \(r(H_1,H)\), for every set \(S\subseteq V(G_n)\) of cardinality \(r(H_1,H_2)\), either the subgraph of \(G_n\) induced by \(S\), denoted \(G_n[S]\), contains a labelled copy of \(H_1\) or \(\overline{G_n}[S]\) contains a labelled copy of \(H_2\). Letting \(N_{n,1}\) be the number of such sets \(S\) containing a copy of \(H_1\) in \(G_n[S]\) and \(N_{n,2}\) be the number containing a copy of \(H_2\) in \(\overline{G_n}[S]\), we have that \[\label{eq:overcount}N_{n,1} + N_{n,2}\geq \binom{v(G_n)}{r(H_1,H_2)}.\tag{3}\] The quantity \(N_{n,r}\) counts every (unlabelled) copy of \(H_1\) in \(G_n\) at most \(\binom{v(G_n)-v(H_1)}{r(H_1,H_2)-v(H_1)}\) times. Thus, the total number of copies of \(H_1\) in \(G_n\) is at least \[\frac{N_{n,1}}{\binom{v(G_n)-v(H_1)}{r(H_1,H_2)-v(H_1)}}\geq\frac{N_{n,1}(r(H_1,H_2)-v(H_1))!}{v(G_n)^{r(H_1,H_2)-v(H_1)}}\] and, likewise, the total number of copies of \(H_2\) in \(\overline{G_n}\) is at least \[\frac{N_{n,2}}{\binom{v(G_n)-v(H_2)}{r(H_1,H_2)-v(H_2)}}\geq \frac{N_{n,2}(r(H_1,H_2)-v(H_2))!}{v(G_n)^{r(H_1,H_2)-v(H_2)}}.\] Thus, letting \(h=\max\{v(H_1),v(H_2)\}\) and \(\ell:=\min\{\lambda,2-\lambda\}\), we get \[\lambda\cdot t(H_1,G_n) + (2-\lambda)\cdot t(H_2,\overline{G_n})\] \[\geq \frac{\lambda\cdot N_{n,1}\cdot(r(H_1,H_2)-v(H_1))! + (2-\lambda)\cdot N_{n,2}\cdot(r(H_1,H_2)-v(H_2))!}{v(G_n)^{r(H_1,H_2)}}\] \[\geq \frac{\ell\cdot \left(N_{n,1}+N_{n,2}\right)\cdot (r(H_1,H_2)-h)! }{v(G_n)^{r(H_1,H_2)}}\] By 3 , we can bound this quantity below by \[\frac{\ell\cdot \binom{v(G_n)}{r(H_1,H_2)}(r(H_1,H_2)-h)!}{v(G_n)^{r(H_1,H_2)}}.\] The limit of this expression as \(v(G_n)\) tends to infinity is \(\frac{\ell\cdot (r(H_1,H_2)-h)!}{r(H_1,H_2)!}\). Thus, \[c_\lambda(H_1,H_2)\geq\frac{\ell\cdot(r(H_1,H_2)-h)!}{r(H_1,H_2)!}.\] ◻

The following proposition is useful for ruling out the “extreme points” \(\lambda=0\) and \(\lambda=2\) when computing \(c(H_1,H_2)\).

Proposition 1. Let \(H_1\) and \(H_2\) be graphs. Then \(c(H_1,H_2)=c_0(H_1,H_2)\) if and only if \(H_2\) is empty.

Proof. If \(H_2\) is empty, then \(t(H_2,1-W)=1\) for every graphon \(W\). Thus, \[c(H_1,H_2)\geq c_0(H_1,H_2)=2\cdot \min_{W\in\mathcal{W}_0}t(H_2,1-W) = 2.\] Also, \(c(H_1,H_2)\leq 2\) by Observation 1. Thus, \(c(H_1,H_2)=c_0(H_1,H_2)=2\) if \(H_2\) is empty.

On the other hand, if \(H_2\) is not empty, then, by taking \(W:=1\), we see that \[c_0(H_1,H_2)\leq 2\cdot t(H_2,1-W) = 0.\] However, by Lemma 1, we have \(c(H_1,H_2)\geq c_1(H_1,H_2)>0\). Thus, \(c(H_1,H_2)\neq c_0(H_1,H_2)\) and the result follows. ◻

3 A Dual Perspective↩︎

By Corollary 1, \(c(H_1,H_2)\) is the maximum over all \(\lambda\) of \(c_\lambda(H_1,H_2)\). Our goal in this section is to show how computing \(c(H_1,H_2)\) can be equivalently phrased as a minimization problem over pairs of graphons representing edge colourings of cliques. The key definition and theorem of this section are as follows.

Definition 1. Let \(H_1\) and \(H_2\) be graphs and let \(\alpha\in\mathbb{R}\). Say that a pair \((W_1,W_2)\) is an \(\alpha\)-certificate for \((H_1,H_2)\) if there exists \(\lambda\in[0,2]\) such that the following four bounds hold:

\(\lambda\cdot t(H_1,W_1) + (2-\lambda)\cdot t(H_2,1-W_1) \leq \alpha\),
\(\lambda\cdot t(H_1,W_2) + (2-\lambda)\cdot t(H_2,1-W_2) \leq \alpha\),
\(t(H_1,W_1)\geq t(H_2,1-W_1)\) and
\(t(H_1,W_2)\leq t(H_2,1-W_2)\).

Theorem 1. Let \(H_1\) and \(H_2\) be non-empty graphs. Then \(c(H_1,H_2)\) is equal to the minimum over all \(\alpha\) for which there exists an \(\alpha\)-certificate for \((H_1,H_2)\).

Proof. First, we show that, if there exists an \(\alpha\)-certificate \((W_1,W_2)\) for \((H_1,H_2)\), then \(c(H_1,H_2)\leq \alpha\). Let \(\lambda\in [0,2]\) so that [eq:ralpha] and [eq:balpha] both hold and let \(\gamma\in[0,2]\). First, if \(\gamma\in [0,\lambda]\), then \[c_\gamma(H_1,H_2) \leq \gamma\cdot t(H_1,W_1) + (2-\gamma)\cdot t(H_2,1-W_1)\] \[=\lambda\cdot t(H_1,W_1) + (2-\lambda)\cdot t(H_2,1-W_1) + (\gamma-\lambda)\cdot \left(t(H_1,W_1) -t(H_2,1-W_1)\right)\] which is at most \(\alpha\) by [eq:ralpha], [eq:rbigger] and the fact that \(\gamma\leq \lambda\). The case \(\gamma\in[\lambda,2]\) is analogous, but with \(W_2\) in the place of \(W_1\).

Now, we let \(\alpha:=c(H_1,H_2)\) and show that there exists an \(\alpha\)-certificate for \((H_1,H_2)\). By Corollary 1, we can choose \(\lambda\in[0,2]\) so that \(c_\lambda(H_1,H_2)=c(H_1,H_2)\). By Proposition 1, Remark 1, Fact 1 and that \(H_1\) and \(H_2\) are non-empty, we can assume that \(\lambda\in (0,2)\). Now, let \(\lambda_n\) be a sequence in \((0,2)\) which converges to \(\lambda\) from the right. For each \(n\), by Lemma 1, we can let \(W_{2,n}\) be a graphon such that \[\lambda_n\cdot t(H_1,W_{2,n}) + (2-\lambda_n)\cdot t(H_2,1-W_{2,n})=c_{\lambda_n}(H_1,H_2).\] Note that \[c_{\lambda}(H_1, H_2) \leq \lambda\cdot t(H_1,W_{2,n}) + (2-\lambda)\cdot t(H_2,1-W_{2,n})\] \[=\lambda_n\cdot t(H_1,W_{2,n}) + (2-\lambda_n)\cdot t(H_2,1-W_{2,n}) + (\lambda-\lambda_n)(t(H_1,W_{2,n}) - t(H_2,1-W_{2,n}))\] \[=c_{\lambda_n}(H_1,H_2) + (\lambda-\lambda_n)(t(H_1,W_{2,n}) - t(H_2,1-W_{2,n}))\] \[\leq c_\lambda(H_1,H_2)+ (\lambda-\lambda_n)(t(H_1,W_{2,n}) - t(H_2,1-W_{2,n})),\] where in the last line we used that \(c_{\lambda_n}(H_1, H_2) \leq c(H_1, H_2) = c_{\lambda}(H_1, H_2)\). Therefore, by definition of \(c_\lambda(H_1,H_2)\) and the fact that \(\lambda_n>\lambda\), we must have that \(t(H_2,1-W_{2,n})\geq t(H_1,W_{2,n})\). By Theorem 1, we can take a subsequence \((W_{2,n_k})_{k=1}^\infty\) of \((W_{2,n})_{n=1}^\infty\) that converges to a graphon \(W_{2}\). By Lemma 1, we have \[\lambda\cdot t(H_1,W_2)+(2-\lambda)\cdot t(H_2,1-W_2) = \lim_{k\to\infty}c_{\lambda_{n_k}}(H_1,H_2) = c_\lambda(H_1,H_2).\] Since \(t(H_2,1-W_{2,n})\geq t(H_1,W_{2,n})\) for all \(n\), we must have \(t(H_2,1-W_{2})\geq t(H_1,W_{2})\), and so [eq:bbigger] holds. The construction of \(W_1\) is similar, except that we take \((\lambda_n)_{n=1}^\infty\) to be a sequence converging to \(\lambda\) from the left. ◻

In light of Theorem 1, we make the following definition.

Definition 1. If \((W_1,W_2)\) is a \(c(H_1,H_2)\)-certificate for a pair \((H_1,H_2)\) of graphs, then we say that \((W_1,W_2)\) is an optimal certificate for \((H_1,H_2)\).

4 Applying Duality↩︎

Our next goal is to provide several applications of Theorem 1. We start with a proof of Theorem 1.

Proof of Theorem 1. First, by definition of \(c(H,H)\) and Remark 1, we have \[c(H,H)\geq c_1(H,H)=c(H).\] So, all that remains is to prove \(c(H,H)\leq c(H)\). By Lemma 1 and Remark 1, we can let \(W\) be a graphon such that \[t(H,W) + t(H,1-W) = c_1(H,H)=c(H).\] Without loss of generality, \(t(H,W)\geq t(H,1-W)\). Thus, the pair \((W,1-W)\) is a \(c(H)\)-certificate for \((H,H)\) and so we are done by Theorem 1. ◻

We now prove a general upper bound on \(c(H_1,H_2)\) coming from random colourings in which each edge is red with density \(p\) and blue with density \(1-p\) and characterize the case of equality. The characterization involves the following off-diagonal generalization of the notion of common graphs introduced recently in [29].

Definition 1. For \(p\in (0,1)\), a pair \((H_1,H_2)\) of graphs is said to be \((p,1-p)\)-common if the following inequality holds for every graphon \(W\): \[\frac{t(H_1,W)}{e(H_1) p^{e(H_1)-1}} + \frac{t(H_2,1-W)}{e(H_2) (1-p)^{e(H_2)-1}}\geq \frac{p}{e(H_1)}+\frac{1-p}{e(H_2)}.\]

Theorem 1. Let \(H_1\) and \(H_2\) be non-empty graphs and let \(p\in(0,1)\) such that \(p^{e(H_1)}=(1-p)^{e(H_2)}\). Then \[c(H_1,H_2)\leq 2\cdot p^{e(H_1)}=2\cdot(1-p)^{e(H_2)}\] with equality if and only if \((H_1,H_2)\) is \((p,1-p)\)-common.

Proof. Let \(H_1\) and \(H_2\) be arbitrary non-empty graphs. For the upper bound, we show that the pair \((W_1,W_2)\) where \(W_1=W_2=p\) is a \(2p^{e(H_1)}\)-certificate for \((H_1,H_2)\) and apply Theorem 1. Since \(p^{e(H_1)}=(1-p)^{e(H_2)}\), we have \[t(H_1,W_1)=t(H_1,W_2)=p^{e(H_1)}=(1-p)^{e(H_2)}=t(H_2,1-W_1)=t(H_2,1-W_2)\] and so [eq:rbigger] and [eq:bbigger] both hold. Using the fact that \(p^{e(H_1)}=(1-p)^{e(H_2)}\) again, for any \(\lambda\in[0,2]\), we have \[\lambda\cdot t(H_1,W_1) + (2-\lambda)\cdot t(H_2,1-W_1)\] \[=\lambda\cdot t(H_1,W_2) + (2-\lambda)\cdot t(H_2,1-W_2)= \lambda\cdot p^{e(H_1)}+ (2-\lambda)(1-p)^{e(H_2)} = 2\cdot p^{e(H_1)}\] and so [eq:ralpha] and [eq:balpha] hold for \(\alpha=2p^{e(H_1)}\). Thus, \((W_1,W_2)\) is a \(2p^{e(H_1)}\)-certificate for \((H_1, H_2)\) and we are done with the upper bound.

What remains is to characterize the case of equality. Define \[\label{eq:commonlambda}\lambda_0 :=2\left( \frac{e(H_2)(1-p)^{e(H_2)-1}}{e(H_1)p^{e(H_1)-1} + e(H_2)(1-p)^{e(H_2)-1}}\right)\tag{4}\] and \[\label{eq:commonsigma}\sigma_0 := \frac{1}{2}\left(\frac{e(H_1)p^{e(H_1)-1} + e(H_2)(1-p)^{e(H_2)-1}}{\left(e(H_1)p^{e(H_1)-1}\right)\cdot\left(e(H_2)(1-p)^{e(H_2)-1}\right)}\right).\tag{5}\] Note that \[\label{eq:lambdasigma1}\sigma_0\cdot\lambda_0 = \frac{1}{e(H_1)p^{e(H_1)-1}}\tag{6}\] and \[\label{eq:lambdasigma2}\sigma_0\cdot(2-\lambda_0) = \frac{1}{e(H_2)(1-p)^{e(H_2)-1}}.\tag{7}\] Therefore, \((H_1,H_2)\) is \((p,1-p)\)-common if and only if \[\sigma_0\cdot\lambda_0\cdot t(H_1,W) + \sigma_0\cdot(2-\lambda_0)\cdot t(H_2,1-W)\geq \frac{p}{e(H_1)}+\frac{1-p}{e(H_2)}\] or, equivalently, \[\lambda_0\cdot t(H_1,W) + (2-\lambda_0)\cdot t(H_2,1-W)\geq \frac{1}{\sigma_0}\left(\frac{p}{e(H_1)}+\frac{1-p}{e(H_2)}\right)\] for every graphon \(W\). Now, observe that \[\frac{1}{\sigma_0}\left(\frac{p}{e(H_1)}+\frac{1-p}{e(H_2)}\right) = \frac{2e(H_1)p^{e(H_1)-1}e(H_2)(1-p)^{e(H_2)-1}}{e(H_1)p^{e(H_1)-1} + e(H_2)(1-p)^{e(H_2)-1}}\left(\frac{p}{e(H_1)}+\frac{1-p}{e(H_2)}\right)\] \[= \frac{2e(H_1)p^{e(H_1)-1}e(H_2)(1-p)^{e(H_2)-1}}{e(H_1)p^{e(H_1)-1} + e(H_2)(1-p)^{e(H_2)-1}}\left(\frac{e(H_2)p+e(H_1)(1-p)}{e(H_1)e(H_2)}\right)\] \[= \frac{2e(H_2)p^{e(H_1)}(1-p)^{e(H_2)-1}+2e(H_1)p^{e(H_1)-1}(1-p)^{e(H_2)}}{e(H_1)p^{e(H_1)-1} + e(H_2)(1-p)^{e(H_2)-1}}\] which, since \((1-p)^{e(H_2)}=p^{e(H_1)}\), is equal to \(2\cdot p^{e(H_1)}\). So, \((H_1,H_2)\) is \((p,1-p)\)-common if and only if \[\lambda_0\cdot t(H_1,W) + (2-\lambda_0)\cdot t(H_2,1-W)\geq2\cdot p^{e(H_1)}\] for every graphon \(W\). In particular, if \((H_1,H_2)\) is \((p,1-p)\)-common, then \[c(H_1,H_2)\geq c_{\lambda_0}(H_1,H_2)\geq 2\cdot p^{e(H_1)}\] which proves one direction of the characterization.

Now, suppose that \((H_1,H_2)\) is not \((p,1-p)\)-common. Our goal is to find an \(\alpha\)-certificate for \((H_1,H_2)\) with \(\alpha<2\cdot p^{e(H_1)}\), from which the result will follow by Theorem 1. To this end, using the characterization of the case that \((H_1,H_2)\) is \((p,1-p)\)-common from the previous paragraph, let \(W_1\) be a graphon such that \[\lambda_0\cdot t(H_1,W_1) + (2-\lambda_0)\cdot t(H_2,1-W_1)< 2\cdot p^{e(H_1)}.\] Without loss of generality, \(t(H_1,W_1)\geq t(H_2,1-W_1)\). Choose \(\gamma\) to be slightly larger than \(\lambda_0\) so that the following inequality is still satisfied \[\gamma\cdot t(H_1,W_1) + (2-\gamma)\cdot t(H_2,1-W_1)< 2\cdot p^{e(H_1)}.\] Set \(\alpha_1:=\gamma\cdot t(H_1,W_1) + (2-\gamma)\cdot t(H_2,1-W_1)\). For \(x\in \mathbb{R}\), let \[f(x):=\sigma_0\gamma \cdot (p+x)^{e(H_1)} + \sigma_0(2-\gamma)\cdot (1-p-x)^{e(H_2)}.\] Then \[\frac{df}{dx}(0)=\sigma_0\gamma e(H_1) p^{e(H_1)-1} - \sigma_0(2-\gamma) e(H_2)(1-p)^{e(H_2)-1}\] which, by 6 , 7 and the fact that \(\gamma>\lambda_0\), is positive. So, by taking \(\varepsilon>0\) sufficiently small and using that \(p^{e(H_1)} = (1-p)^{e(H_2)}\), we can ensure that \(p-\varepsilon>0\) and \[\gamma \cdot (p-\varepsilon)^{e(H_1)} + (2-\gamma)\cdot (1-p+\varepsilon)^{e(H_2)} < 2p^{e(H_1)}.\] We define \(W_2:=p-\varepsilon\) and set \(\alpha_2:=\gamma \cdot (p-\varepsilon)^{e(H_1)} + (2-\gamma)\cdot (1-p+\varepsilon)^{e(H_2)}\). Note that, by definition of \(p\), we must have \((p-\varepsilon)^{e(H_1)}<(1-p+\varepsilon)^{e(H_2)}\). Thus, we conclude that \(c(H_1,H_2)\leq \min\{\alpha_1,\alpha_2\}<2p^{e(H_1)}\) by Theorem 1. ◻

Theorem 1 is now a consequence of Theorem 1 and the following statement, which recently appeared in [29].

Theorem 1. If \(H_1\) and \(H_2\) are Sidorenko, then \((H_1,H_2)\) is \((p,1-p)\)-common for all \(p\in (0,1)\).

Proof. Let \(H_1\) and \(H_2\) be Sidorenko, let \(p\in (0,1)\) and let \(W\) be a graphon. Define \(x:=t(K_2,W)-p\). Then \[\frac{t(H_1,W)}{e(H_1)p^{e(H_1)-1}}+\frac{t(H_2,1-W)}{e(H_2)(1-p)^{e(H_2)-1}}\geq\frac{(p+x)^{e(H_1)}}{e(H_1)p^{e(H_1)-1}}+\frac{(1-p-x)^{e(H_2)}}{e(H_2)(1-p)^{e(H_2)-1}}\] \[=\frac{p^{e(H_1)}(1+xp^{-1})^{e(H_1)}}{e(H_1)p^{e(H_1)-1}}+\frac{(1-p)^{e(H_2)}(1-x(1-p)^{-1})^{e(H_2)}}{e(H_2)(1-p)^{e(H_2)-1}}\] \[=\frac{p(1+xp^{-1})^{e(H_1)}}{e(H_1)}+\frac{(1-p)(1-x(1-p)^{-1})^{e(H_2)}}{e(H_2)}.\] Using Bernoulli’s Inequality (i.e. the fact that \((1+y)^r\geq 1+ry\) for all \(r\geq 1\) and \(y\geq-1\)) on each term of the above expression and cancelling yields \(\frac{p}{e(H_1)}+\frac{1-p}{e(H_2)}\), as desired. ◻

Proof of Theorem 1. Let \(H_1\) and \(H_2\) be non-empty Sidorenko graphs and let \(p\in (0,1)\) such that \(p^{e(H_1)}=(1-p)^{e(H_2)}\). By Theorem 1, \((H_1,H_2)\) is \((p,1-p)\)-common. Thus, the result follows by Theorem 1. ◻

We now turn our attention to the upper bounds in Theorems 1–1. The upper bound in Theorem 1 follows easily from Theorem 1.

Proposition 1. \(c(C_5,B)\leq 1/16\).

Proof. The graphs \(C_5\) and \(B\) both have five edges; thus, \(p^{e(C_5)}=(1-p)^{e(B)}\) if and only if \(p=1/2\). So, by Theorem 1, \(c(C_5,B)\leq 2(1/2)^5=1/16\). ◻

Next, we prove the upper bounds in Theorems 1 and 1. In each case, the proof will simply boil down to exhibiting an \(\alpha\)-certificate \((W_1,W_2)\) for an appropriate choice of \(\alpha\), verifying that it satisfies the properties outlined in Definition 1 and concluding with an application of Theorem 1. After giving the examples, we will include some further discussion to provide insight into how we found them.

Proposition 1. \(c(K_3,C_5)\leq 3/34\).

Proof. Define \(\alpha=3/34\) and \(\lambda=10/17\). Our goal is to find an \(\alpha\)-certificate \((W_1,W_2)\) for \((K_3,C_5)\). Let \(W_2=W_{K_2}\). We have \(t(K_3,W_2)=0\) and \(t(C_5,1-W_2)=(1/2)^4\). Therefore, [eq:bbigger] holds. Also, \[\lambda\cdot t(K_3,W_2) + (2-\lambda)\cdot t(C_5,1-W_2)=(10/17)\cdot 0 + (24/17)\cdot(1/16) = 3/34\] and so [eq:balpha] holds.

Now, let \(W_1=W_{\overline{C_6}}\). A standard fact from algebraic graph theory is that, if \(G\) is an \(n\)-vertex graph and \(\lambda_1,\dots,\lambda_n\) are the eigenvalues of its adjacency matrix, then \[t(C_k,G)=\sum_{i=1}^n\left(\frac{\lambda_i}{n}\right)^k\] for any \(k\geq3\); see, e.g., [26]. The eigenvalues of the adjacency matrix of \(\overline{C_6}\) are \(3,-2,-2,1,0,0\). Therefore, \[t(K_3,W_1)=(3/6)^3 + (-2/6)^3 + (-2/6)^3+(1/6)^3 = 1/18.\] Similarly, \[t(C_5,1-W_1)=(3/6)^5 + (2/6)^5 + (2/6)^5+(-1/6)^5 = 17/432.\] This is because the matrix obtained from subtracting the adjacency matrix of \(\overline{C_6}\) from the \(6\times 6\) all-ones matrix has eigenvalues \(3,2,2,-1,0,0\). Note that \(1/18>17/432\) and so [eq:rbigger] holds. Also, \[\lambda\cdot (1/18) + (2-\lambda)\cdot (17/432) = (10/17)\cdot (1/18)+(24/17)\cdot(17/432)=3/34.\] So, [eq:ralpha] holds as well. The proposition now follows from Theorem 1. ◻

It is worth noting that the two tight colourings described in the proof of Proposition 1 seem to be far from the only such colourings. For example, if \(H\) is the \(8\)-vertex graph obtained from \(\overline{C_6}\) by duplicating two adjacent vertices that are not in a common triangle, then \((10/17)t(K_3,W_H) + (24/17)t(C_5,1-W_H)=3/34\) as well; see Figure 2.

Figure 2: The graph \overline{C_6} used in the proof of Proposition 1 and another tight example H. — Figure 2: The graph \(\overline{C_6}\) used in the proof of Proposition 1 and another tight example \(H\).

Next, we consider \(D\) and \(M\). In our analysis, the following result, often referred to as Goodman’s Formula [14], will be valuable. For \(k\geq1\), let \(P_k\) denote the path with \(k\) vertices.

Theorem 1 (Goodman’s Formula [14]). For any graphon \(W\), \(t(K_3,W)+t(K_3,1-W)\) is equal to \[t(K_2,W)^3+t(K_2,1-W)^3+\frac{3}{2}\left(t(P_3,W)+t(P_3,1-W)-t(K_2,W)^2-t(K_2,1-W)^2\right).\]

Proposition 1. \(c(D,M)\leq 1/36\).

Proof. Define \(\alpha=1/36\). Let \(K\) be the tensor product of \(K_3\) and \(K_4\); that is, \(K\) has \(12\) vertices labelled \(u_{i,j}\) for \(1\leq i\leq 3\) and \(1\leq j\leq 4\) where \(u_{i,j}\) is adjacent to \(u_{i',j'}\) if and only if \(i\neq i'\) and \(j\neq j'\); see Figure 3. We show that \((W_K,W_K)\) is an \(\alpha\)-certificate for \((D,M)\).

First, we compute \(t(D,K)=t(D,W_K)\). Consider the edge \(u_{1,1}u_{2,2}\). If \(u_{i,j}\) is a common neighbour of \(u_{1,1}\) and \(u_{2,2}\), then \(i\) must be \(3\) and \(j\) must be \(3\) or \(4\). Thus, there are precisely two such common neighbours. Let \(x\) and \(y\) be the two vertices of degree \(3\) in \(D\). The number of homomorphisms from \(D\) to \(K\) such that \(f(x)=u_{1,1}\) and \(f(y)=u_{2,2}\) is precisely the number of ways to choose an ordered pair of common neighbours of these two vertices with replacement; thus, it is \(2^2=4\). Since the automorphism group of \(K\) acts transitively on pairs of adjacent vertices, we get that \[t(D,K) = \frac{\hom(D,K)}{12^4} = \frac{2\cdot |E(K)|\cdot 4}{12^4} = \frac{6\cdot 12\cdot 4}{12^4}=\frac{1}{72}.\]

Now, let us compute \(t(M,1-W_K)\). Since \(K\) is \(6\)-regular, we get that \[t(K_2,W_K)=t(K_2,1-W_K)=1/2\] and \[t(P_3,W_K)=t(P_3,1-W_K)=1/4.\] Therefore, by Goodman’s Formula, \(t(K_3,1-W_K) = 1/4 - t(K_3,W_K)\). Using the observations from the previous paragraph, we get that \(t(K_3,W_K)=\frac{6\cdot 12\cdot 2}{12^3}=\frac{1}{12}\). Therefore, \(t(K_3,1-W_K)=1/6\). Finally, since \(K\) is vertex-transitive and \(M\) consists of two triangles and a \(K_2\) glued together on single vertices, we have \[t(M,1-W_K) = t(K_3,1-W_K)\cdot t(K_2,1-W_K)\cdot t(K_3,1-W_K)=1/72.\] Thus, if \(W_1=W_2=W_K\), then \((W_1,W_2)\) satisfies all of the conditions of Definition 1 (for any \(\lambda\in [0,2]\)) and so we are done. ◻

Figure 3: The graph K used in the proof of Proposition 1. — Figure 3: The graph \(K\) used in the proof of Proposition 1.

Let us now speak about how we found the constructions in the previous two propositions. In both cases, the first step was to apply the flag algebra method to obtain a lower bound on \(c(H_1,H_2)\). An introduction to this approach will be given in the next section but, for now, let us just say that this involved solving, by computer, a certain semidefinite program aimed at maximizing a variable, say \(t\), which provides a lower bound on \(c(H_1,H_2)\). At first glance, one may wonder about how to choose the right value of \(\lambda\) to enter into this optimization problem. However, as it turns out, one can formulate the semidefinite program so that \(\lambda\) is one of the variables, and the computer aims to maximize, over all choices of \(\lambda\), a variable \(t\) satisfying \(t\leq c_\lambda(H_1,H_2)\). That is, the output of the optimization problem not only gives us a lower bound on the balanced Ramsey multiplicity constant, but it also points us toward what the SDP solver “believes” to be the best possible \(\lambda\).

After obtaining a candidate for \(\lambda\) and a lower bound of the form \(c_\lambda(H_1,H_2)\geq \alpha\) from flag algebras, where \(\alpha\) is the optimal value of \(t\), we started to search for an \(\alpha\)-certificate to get the matching upper bound. For the pair \((K_3,C_5)\), the certificate used in Proposition 1 is very simple; it is just a pair of graphons corresponding to two graphs on \(2\) and \(6\) vertices, respectively. The first graphon was easy to guess and the second was found quickly via an exhaustive computer search through all graphs on small numbers of vertices.

For the pair \((D,M)\), the search for the certificate went somewhat differently. By analyzing the dual of the semidefinite program in the flag algebra calculation, we were able to determine various constraints that a graphon in a \(1/36\)-certificate is likely to satisfy; e.g., we found values of the homomorphism densities of \(K_2\), \(K_3\), etc in a theoretical tight example. Moreover, the dual of the SDP suggested that the tight construction should be rather symmetric; e.g. each vertex should have the same degree, be contained in the same number of triangles, etc. By analyzing the dual further and doing a bit of numerological guesswork, we felt that there was a good chance that the optimal certificate involved a graphon corresponding to a graph on 12 vertices. However, all of these observations needed to be taken with a grain of salt due to the fact that an optimal certificate may have involved a pair of graphons \(W_1\) and \(W_2\) which may have different subgraph densities.

Given these insights, we ran a heuristic search on the set of \(6\)-regular graphs on \(12\) vertices in an attempt to find such a certificate. The heuristic search started with a random such graph \(G\) generated via the configuration model and applied random “switchings;” i.e. replacing edges \(u_1v_1\) and \(u_2v_2\) with \(u_1v_2\) and \(u_2v_1\) for four vertices \(u_1,u_2,v_1,v_2\) such that the edges \(u_1v_1\) and \(u_2v_2\) are currently present in \(G\) and \(u_1v_2\) and \(u_2v_1\) are not. If the switching decreased the objective function \((5/6)t(D,W_G)+(7/6)t(M,1-W_G)\), then we keep it; if not, then we undo it. The search concluded with the construction in Proposition 1 rather quickly. It seems that the fact that the optimal certificate consists of only a single graphon in this case was very lucky, and it made it much easier to use information from the dual of the SDP to find it.

5 Flag Algebra Lower Bounds↩︎

In this section, we apply the flag algebra method of Razborov [30] to complete the proofs of Theorems 1–1. Let us begin by stating the key definitions and lemmas that we will need. All of the lemmas stated here are very standard; proofs of these statements, or statements very similar to them, can be found in, e.g., [26], [30]. See [29] for a gentle introduction to the method which contains proofs of similar statements in a more restricted setting.

Definition 1. The induced homomorphism density of a graph \(J\) in a graphon \(W\) is \[t_{\mathop{\mathrm{ind}}}(J,W):=\int_{[0,1]^{V(J)}}\prod_{uv\in E(J)}W(x_u,x_v)\prod_{uv\in E(\overline{J})}(1-W(x_u,x_v))\prod_{v\in V(J)}dx_v.\]

Definition 1. For a graph \(J\) and a graphon \(W\), define \(d(J,W):=\frac{v(J)!}{\mathop{\mathrm{aut}}(J)}\cdot t_{\mathop{\mathrm{ind}}}(J,W)\), where \(\mathop{\mathrm{aut}}(J)\) is the number of automorphisms of \(J\).

Lemma 1. For any positive integer \(\ell\) and graphon \(W\), \[\sum_{J:v(J)=\ell}d(J,W)=1\] where the sum is over all graphs \(J\) on \(\ell\) vertices up to isomorphism.

Definition 1. Given graphs \(H\) and \(J\) with \(v(H)\leq v(J)\), the injective homomorphism density of \(H\) in \(J\), denoted \(t_{\mathop{\mathrm{inj}}}(H,J)\), is the probability that a random injective function from \(V(H)\) to \(V(J)\) is a homomorphism.

Lemma 1. For any graph \(H\), integer \(\ell\geq v(H)\) and graphon \(W\), \[t(H,W)=\sum_{J: v(J)=\ell}t_{\mathop{\mathrm{inj}}}(H,J)\cdot d(J,W)\] where the sum is over all graphs \(J\) on \(\ell\) vertices up to isomorphism.

Definition 1. Let \(F\) be a graph on vertex set \([k]:=\{1,\dots,k\}\) and \(0\leq r\leq k\). Given a graphon \(W\), define \(t_{\mathop{\mathrm{ind}},r}(F,W):[0,1]^{r}\to [0,1]\) by \[t_{\mathop{\mathrm{ind}},r}(F,W)(x_1,\dots,x_r)=\int_{[0,1]^{k-r}}\prod_{ij\in E(F)}W(x_i,x_j)\prod_{ij\in E(\overline{F})}(1-W(x_i,x_j))\prod_{i=r+1}^kdx_i.\]

Definition 1. Given graphs \(F_1,\dots,F_t\) on vertex set \([k]\), an integer \(0\leq r\leq k\) and a graph \(F\) on vertex set \([r]\), we say that \(F_1,\dots,F_t\) are \(F\)-compatible if the subgraph of \(F_i\) induced by \([r]\) is equal to \(F\) for all \(1\leq i\leq t\). Less precisely, we say that \(F_1,\dots,F_t\) are \(r\)-compatible if they are \(F\)-compatible for some graph \(F\) on vertex set \([r]\).

Definition 1. Let \(F\) be a graph on \([r]\) and let \(F_1\) and \(F_2\) be \(F\)-compatible graphs on \([k]\). Define \(t_{\mathop{\mathrm{ind}},r}(F_1\cdot F_2,W)(x_{1},\dots,x_r)\) to be equal to \[\begin{cases}\displaystyle\frac{t_{\mathop{\mathrm{ind}},r}(F_1,W)(x_{1},\dots,x_r)\cdot t_{\mathop{\mathrm{ind}},r}(F_2,W)(x_{1},\dots,x_r)}{t_{\mathop{\mathrm{ind}}}(F,W)(x_1,\dots,x_r)} &\text{if } t_{\mathop{\mathrm{ind}}}(F,W)(x_1,\dots,x_r)\neq 0,\\ \displaystyle0 &\text{otherwise}.\end{cases}\]

Lemma 1. Let \(F\) be a graph on \([r]\), let \(F_1\) and \(F_2\) be \(F\)-compatible graphs on \([k]\) and let \(\ell\geq2k-r\). Then there exist constants \(a_r(F_1,F_2;J)\) for each graph \(J\) such that \(v(J)=\ell\) such that \[\int_{[0,1]^r}t_{\mathop{\mathrm{ind}},r}(F_1\cdot F_2,W)(x_1,\dots,x_r)dx_1\cdots dx_r=\sum_{J:v(J)=\ell}a_r(F_1,F_2;J)\cdot d(J,W)\] for every graphon \(W\), where the sum on the right side is over all graphs \(J\) on \(\ell\) vertices up to isomorphism.

Let us illustrate the way in which one can compute the coefficients \(a_r(F_1,F_2;J)\) in the previous lemma with an example. Let \(F_1=F_2\) be the complete graph on \([3]\) and let \(r=1\). Then, after a slight change of variables, we can write \(\int_0^1t_{\mathop{\mathrm{ind}},1}(F_1\cdot F_2,W)(x_1)dx_1\) as \[\int_{[0,1]^5}\prod_{\substack{i,j\in\{1,2,3\}\\i\neq j}}W(x_i,x_j)\prod_{\substack{i,j\in\{1,4,5\}\\i\neq j}}W(x_i,x_j)dx_1\cdots dx_5\] \[=\int_{[0,1]^5}\prod_{\substack{i,j\in\{1,2,3\}\\i\neq j}}W(x_i,x_j)\prod_{\substack{i,j\in\{1,4,5\}\\i\neq j}}W(x_i,x_j)\prod_{\substack{i\in\{2,3\}\\ j\in \{4,5\}}}(W(x_i,x_j)+(1-W(x_i,x_j)))dx_1\cdots dx_5.\] If we expand the third product inside the integral and collect terms, we get \[\label{eq:tindJ}t_{\mathop{\mathrm{ind}}}(J_1,W)+4t_{\mathop{\mathrm{ind}}}(J_2,W)+2t_{\mathop{\mathrm{ind}}}(J_3,W)+4t_{\mathop{\mathrm{ind}}}(J_4,W)+4t_{\mathop{\mathrm{ind}}}(J_5,W)+t_{\mathop{\mathrm{ind}}}(J_6,W)\tag{8}\] where \(J_1,\dots,J_6\) are the following graphs: \[\begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=vertex] (1) at (90:1.00) {}; \node [style=vertex] (2) at (30:0.75) {}; \node [style=vertex] (3) at (330:0.75) {}; \node [style=vertex] (4) at (150:0.75) {}; \node [style=vertex] (5) at (210:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw (1.center) to (3.center); \draw (2.center) to (3.center); \draw (1.center) to (4.center); \draw (1.center) to (5.center); \draw (4.center) to (5.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=vertex] (1) at (90:1.00) {}; \node [style=vertex] (2) at (30:0.75) {}; \node [style=vertex] (3) at (330:0.75) {}; \node [style=vertex] (4) at (150:0.75) {}; \node [style=vertex] (5) at (210:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw (1.center) to (3.center); \draw (2.center) to (3.center); \draw (1.center) to (4.center); \draw (1.center) to (5.center); \draw (4.center) to (5.center); \draw (2.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=vertex] (1) at (90:1.00) {}; \node [style=vertex] (2) at (30:0.75) {}; \node [style=vertex] (3) at (330:0.75) {}; \node [style=vertex] (4) at (150:0.75) {}; \node [style=vertex] (5) at (210:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw (1.center) to (3.center); \draw (2.center) to (3.center); \draw (1.center) to (4.center); \draw (1.center) to (5.center); \draw (4.center) to (5.center); \draw (2.center) to (4.center); \draw (3.center) to (5.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=vertex] (1) at (90:1.00) {}; \node [style=vertex] (2) at (30:0.75) {}; \node [style=vertex] (3) at (330:0.75) {}; \node [style=vertex] (4) at (150:0.75) {}; \node [style=vertex] (5) at (210:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw (1.center) to (3.center); \draw (2.center) to (3.center); \draw (1.center) to (4.center); \draw (1.center) to (5.center); \draw (4.center) to (5.center); \draw (2.center) to (4.center); \draw (2.center) to (5.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=vertex] (1) at (90:1.00) {}; \node [style=vertex] (2) at (30:0.75) {}; \node [style=vertex] (3) at (330:0.75) {}; \node [style=vertex] (4) at (150:0.75) {}; \node [style=vertex] (5) at (210:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw (1.center) to (3.center); \draw (2.center) to (3.center); \draw (1.center) to (4.center); \draw (1.center) to (5.center); \draw (4.center) to (5.center); \draw (2.center) to (4.center); \draw (2.center) to (5.center); \draw (3.center) to (5.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=vertex] (1) at (90:1.00) {}; \node [style=vertex] (2) at (30:0.75) {}; \node [style=vertex] (3) at (330:0.75) {}; \node [style=vertex] (4) at (150:0.75) {}; \node [style=vertex] (5) at (210:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw (1.center) to (3.center); \draw (2.center) to (3.center); \draw (1.center) to (4.center); \draw (1.center) to (5.center); \draw (4.center) to (5.center); \draw (2.center) to (4.center); \draw (2.center) to (5.center); \draw (3.center) to (4.center); \draw (3.center) to (5.center); \end{pgfonlayer} \end{tikzpicture}.\] Then, by definition of \(d(J,W)\), 8 can be rewritten as \[\frac{8}{120}d(J_1,W) + 4\cdot\frac{2}{120}d(J_2,W)+2\cdot\frac{8}{120}d(J_3,W)+ 4\cdot\frac{4}{120}d(J_4,W)+4\cdot\frac{12}{120}d(J_5,6)+\frac{120}{120}d(J_6,W).\] Therefore, we have, e.g., \(a_1(F_1,F_2;K_5)=a_1(F_1,F_2;J_6)=1\) and \(a_1(F_1,F_2;\overline{K_5})=0\). This illustrates the way in which the coefficients in Lemma 1 are computed for \(\ell=2k-r\). The following lemma allows us to transfer the statement of Lemma 1 from \(\ell=2k-r\) to larger values of \(\ell\).

Definition 1. Given graphs \(F\) and \(J\) with \(v(F)\leq v(J)\), let \(d(F,J)\) be the probability that a random subset of \(V(J)\) of cardinality \(v(F)\) induces a subgraph of \(J\) isomorphic to \(F\).

Lemma 1. For any graph \(F\), integer \(\ell\geq v(F)\) and graphon \(W\), \[d(F,W)=\sum_{J: v(J)=\ell}d(F,J)d(J,W)\] where the sum is over all graphs \(J\) on \(\ell\) vertices up to isomorphism.

Recall that a \(t\times t\) matrix \(A\) is positive semi-definite (PSD) if it is real-valued and symmetric and all of its eigenvalues are non-negative. Equivalently, \(A\) is PSD if \[\sum_{i=1}^t\sum_{j=1}^tA(i,j)x_ix_j\geq0\] for any \(x_1,\dots,x_t\in\mathbb{R}\), where \(A(i,j)\) denotes the entry on the \(i\)th row and \(j\)th column of \(A\). Using the lemmas presented in this section, together with the second definition of PSD matrices, we derive the following lemma which is key to the main proofs in this section.

Lemma 1. Let \(H_1\) and \(H_2\) be graphs, let \(\lambda\in [0,2]\) and let \(\ell\geq\max\{v(H_1),v(H_2)\}\). Let \(m,r_1,\dots,r_m,k_1,\dots,k_m,t_1,\dots,t_m\) be positive integers and let \(F^1,\dots,F^m\) be graphs. For \(1\leq q\leq m\), suppose that \(2k_q-r_q\leq\ell\) and \(V(F^q)=[r_q]\), let \(F^q_1,\dots,F^q_{t_q}\) be \(F^q\)-compatible graphs on vertex set \([k_q]\) and let \(A_q\) be a \(t_q\times t_q\) PSD matrix. Then \(c_\lambda(H_1,H_2)\) is at least \[\min_{J: v(J)=\ell}\left\{\lambda\cdot t_{\mathop{\mathrm{inj}}}(H_1,J)+(2-\lambda)\cdot t_{\mathop{\mathrm{inj}}}(H_2,\overline{J})-\sum_{q=1}^m\sum_{i=1}^{t_q}\sum_{j=1}^{t_q}A_q(i,j)a_{r_q}(F^q_i\cdot F^q_j;J)\right\}\] where the minimum is over all graphs \(J\) on \(\ell\) vertices up to isomorphism.

Proof. By Lemma 1, we can let \(W\) be a graphon such that \(\lambda\cdot t_{\mathop{\mathrm{inj}}}(H_1,W)+(2-\lambda)\cdot t_{\mathop{\mathrm{inj}}}(H_2,1-W)=c_\lambda(H_1,H_2)\). By Lemma 1, \[\label{eq:tinjJ} \begin{gather} c_\lambda(H_1,H_2)=\lambda\cdot t_{\mathop{\mathrm{inj}}}(H_1,W)+(2-\lambda)\cdot t_{\mathop{\mathrm{inj}}}(H_2,1-W)\\=\sum_{J:v(J)=\ell}\left(\lambda \cdot t_{\mathop{\mathrm{inj}}}(H_1,J)+(2-\lambda)\cdot t_{\mathop{\mathrm{inj}}}(H_2,\overline{J})\right)\cdot d(J,W). \end{gather}\tag{9}\] Now, by Lemma 1 and Fubini’s Theorem, we can write \[\sum_{q=1}^m\sum_{i=1}^{t_q}\sum_{j=1}^{t_q}A_q(i,j)a_{r_q}(F^q_i\cdot F^q_j;J)d(J,W)\] \[=\sum_{q=1}^m\int_{[0,1]^r}\sum_{i=1}^{t_q}\sum_{j=1}^{t_q}A_q(i,j)t_{\mathop{\mathrm{ind}},r_q}(F^q_i\cdot F^q_j,W)(x_1,\dots,x_r)dx_1\cdots dx_r.\] Now, for fixed \(1\leq q\leq m\), by definition of \(t_{\mathop{\mathrm{ind}},r_1}(F^q_i\cdot F^q_j,W)(x_1,\dots,x_r)\), for each choice of \((x_1,\dots,x_r)\in [0,1]^r\), we have that \(\sum_{i=1}^{t_q}\sum_{j=1}^{t_q}A_q(i,j)t_{\mathop{\mathrm{ind}},r_q}(F^q_i\cdot F^q_j,W)(x_1,\dots,x_r)\) is equal to zero if \(t_{\mathop{\mathrm{ind}}}(F^q,W)(x_1,\dots,x_r)=0\) and, otherwise, is equal to \[\sum_{i=1}^{t_q}\sum_{j=1}^{t_q}\frac{A_q(i,j)t_{\mathop{\mathrm{ind}},r_q}(F_i^q,W)(x_1,\dots,x_r)\cdot t_{\mathop{\mathrm{ind}},r_q}(F_j^q,W)(x_1,\dots,x_r)}{t_{\mathop{\mathrm{ind}}}(F^q,W)}\] which is non-negative because \(A_q\) is PSD. Thus, \[\sum_{q=1}^m\sum_{i=1}^{t_q}\sum_{j=1}^{t_q}A_q(i,j)a_{r_q}(F^q_i\cdot F^q_j;J)d(J,W)\geq0.\] Combining this with 9 , we see that \(c_\lambda(H_1,H_2)\) is at least \[\sum_{J:v(J)=\ell}\left(\lambda\cdot t_{\mathop{\mathrm{inj}}}(H_1,J)+(2-\lambda)\cdot t_{\mathop{\mathrm{inj}}}(H_2,\overline{J})-\sum_{q=1}^m\sum_{i=1}^{t_q}\sum_{j=1}^{t_q}A_q(i,j)a_{r_q}(F^q_i\cdot F^q_j;J)\right)d(J,W)\] which, since the quantities \(d(J,W)\) are non-negative and sum to one by Lemma 1, implies the conclusion of the lemma. ◻

The lower bounds in Theorems 1–1 are all proven using Lemma 1. We present these proofs in order of increasing complexity. The easiest one is Theorem 1.

Proof of Theorem 1. The upper bound was proven in Proposition 1. We apply Lemma 1 to show that \(c_{10/17}(K_3,C_5)\geq 3/34\). In this application of Lemma 1, we set \(\ell=5\), \(m=r_1=1\), \(k_1=3\) and \(t_1=6\). Let \(F^1\) be the unique \(1\)-vertex graph and let \(F^1_1,\dots,F^1_6\) be as follows: \[\begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (270:0.75) {}; \node [style=vertex] (2) at (150:0.75) {}; \node [style=vertex] (3) at (30:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (270:0.75) {}; \node [style=vertex] (2) at (150:0.75) {}; \node [style=vertex] (3) at (30:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw (1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (270:0.75) {}; \node [style=vertex] (2) at (150:0.75) {}; \node [style=vertex] (3) at (30:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw (1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (270:0.75) {}; \node [style=vertex] (2) at (150:0.75) {}; \node [style=vertex] (3) at (30:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw (2.center) to (3.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (270:0.75) {}; \node [style=vertex] (2) at (150:0.75) {}; \node [style=vertex] (3) at (30:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw (1.center) to (3.center); \draw (2.center) to (3.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (270:0.75) {}; \node [style=vertex] (2) at (150:0.75) {}; \node [style=vertex] (3) at (30:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw (1.center) to (3.center); \draw (2.center) to (3.center); \end{pgfonlayer} \end{tikzpicture}\] In each of the above diagrams, the square vertex is labelled \(1\) and the round vertices are labelled \(2\) and \(3\) from left to right. Define \[A_1:=\frac{15}{34}\begin{bmatrix} 3 & 3 & 0 & -2 & -3 & -1\\ 3 & 8 & 5 & -6 & -8 & -2\\ 0 & 5 & 5 & -4 & -5 & -1\\ -2 & -6 & -4 & 5 & 6 & 1\\ -3 & -8 & -5 & 6 & 8 & 2\\ -1 & -2 & -1 & 1 & 2 & 1 \end{bmatrix}.\] The matrix \(A_1\) is positive semidefinite; the non-zero eigenvalues of \((34/15)\cdot A_1\) are approximately 25.36, 3.76 and 0.88. There are 34 graphs of order 5, up to isomorphism. For every such graph \(J\), it holds that \[(10/17)\cdot t_{\mathop{\mathrm{inj}}}(K_3,J) + (24/17)\cdot t_{\mathop{\mathrm{inj}}}(C_5,\overline{J})-\sum_{i=1}^{6}\sum_{j=1}^{6}A_1(i,j)a_1(F^1_{i},F^1_{j}; J)\geq 3/34.\] The full list of calculations needed to verify this for all graphs \(J\) on 5 vertices are tedious and will be included in an ancillary file with a later arxiv preprint of this paper. We include two sample calculations to illustrate how they work in principle.

First, consider \(J=K_5\). In this case, \(a_1(F^1_{i},F^1_{j}; K_5)\) is equal to \(0\) unless \(i=j=6\), in which case it is equal to \(1\). Also, clearly, \(t_{\mathop{\mathrm{inj}}}(K_3,K_5)=1\) and \(t_{\mathop{\mathrm{inj}}}(C_5,\overline{K_5})=0\). Therefore, \[(10/17)\cdot t_{\mathop{\mathrm{inj}}}(K_3,K_5) + (24/17)\cdot t_{\mathop{\mathrm{inj}}}(C_5,\overline{K_5})-\sum_{i=1}^{6}\sum_{j=1}^{6}A_1(i,j)a_1(F^1_{i},F^1_{j}; K_5)\] \[= (10/17) - 1\cdot A_1(6,6) = 5/34.\] For a slightly more involved example, let \(J=K_{1,4}\). Then one can check that \[a_1(F^1_{3},F^1_{3}; K_{1,4})=1/5,\] \[a_1(F^1_{1},F^1_{5}; K_{1,4})=a_1(F^1_{5},F^1_{1}; K_{1,4})=1/5\] and \(a_1(F^1_{i},F^1_{j}; K_{1,4})=0\) for all other \(i\) and \(j\). Also, \(t_{\mathop{\mathrm{inj}}}(K_3,K_{1,4})=t_{\mathop{\mathrm{inj}}}(C_5,\overline{K_{1,4}}) = 0\). Therefore, \[(10/17)\cdot t_{\mathop{\mathrm{inj}}}(K_3,K_{1,4}) + (24/17)\cdot t_{\mathop{\mathrm{inj}}}(C_5,\overline{K_{1,4}})-\sum_{i=1}^{6}\sum_{j=1}^{6}A_1(i,j)\cdot a_1(F^1_{i},F^1_{j}; K_{1,4})\] \[= -(1/5)\cdot A_1(3,3)-(1/5)\cdot A_1(1,5)-(1/5)\cdot A_1(5,1) = 3/34.\] ◻

Next, we show that \(c_1(C_5,B)\geq1/16\) which, by Theorem 1 and the fact that \(e(C_5)=e(B)\), is equivalent to the statement that \((C_5,B)\) is \((1/2,1/2)\)-common.

Proof of Theorem 1. The upper bound follows from Proposition 1. To prove the lower bound, we apply Lemma 1 with \(\ell=5\), \(m=4\), \(r_1=r_2=r_3=r_4=3\) and \(k_1=k_2=k_3=k_4=4\) and \(t_1=t_2=t_3=t_4=8\). We define graphs \(F^q_{i}\) for \(1\leq q\leq 4\) and \(1\leq i\leq 8\) as in the pictures below, where the eight graphs corresponding to \(q=1\) are listed first, followed by the eight graphs for \(q=2\), and so on. In these depictions, the square vertices are labelled \(1,2,3\) from left to right and the round vertex is labelled \(4\). \[\begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](0.center) to (1.center); \draw [style=dashededge](2.center) to (1.center); \draw [style=dashededge](0.center) to (2.center); \draw [style=dashededge](3.center) to (0.center); \draw [style=dashededge](3.center) to (1.center); \draw [style=dashededge](3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](0.center) to (1.center); \draw [style=dashededge](2.center) to (1.center); \draw [style=dashededge](0.center) to (2.center); \draw [style=dashededge](3.center) to (0.center); \draw [style=dashededge](3.center) to (1.center); \draw (3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](0.center) to (1.center); \draw [style=dashededge](2.center) to (1.center); \draw [style=dashededge](0.center) to (2.center); \draw [style=dashededge](3.center) to (0.center); \draw (3.center) to (1.center); \draw [style=dashededge](3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](0.center) to (1.center); \draw [style=dashededge](2.center) to (1.center); \draw [style=dashededge](0.center) to (2.center); \draw [style=dashededge](3.center) to (0.center); \draw (3.center) to (1.center); \draw (3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](0.center) to (1.center); \draw [style=dashededge](2.center) to (1.center); \draw [style=dashededge](0.center) to (2.center); \draw (3.center) to (0.center); \draw [style=dashededge](3.center) to (1.center); \draw [style=dashededge](3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](0.center) to (1.center); \draw [style=dashededge](2.center) to (1.center); \draw [style=dashededge](0.center) to (2.center); \draw (3.center) to (0.center); \draw [style=dashededge](3.center) to (1.center); \draw (3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](0.center) to (1.center); \draw [style=dashededge](2.center) to (1.center); \draw [style=dashededge](0.center) to (2.center); \draw (3.center) to (0.center); \draw (3.center) to (1.center); \draw [style=dashededge](3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](0.center) to (1.center); \draw [style=dashededge](2.center) to (1.center); \draw [style=dashededge](0.center) to (2.center); \draw (3.center) to (0.center); \draw (3.center) to (1.center); \draw (3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}.\] \[\begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (0.center) to (1.center); \draw [style=dashededge](2.center) to (1.center); \draw [style=dashededge](0.center) to (2.center); \draw [style=dashededge](3.center) to (0.center); \draw [style=dashededge](3.center) to (1.center); \draw [style=dashededge](3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (0.center) to (1.center); \draw [style=dashededge](2.center) to (1.center); \draw [style=dashededge](0.center) to (2.center); \draw [style=dashededge](3.center) to (0.center); \draw [style=dashededge](3.center) to (1.center); \draw (3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (0.center) to (1.center); \draw [style=dashededge](2.center) to (1.center); \draw [style=dashededge](0.center) to (2.center); \draw [style=dashededge](3.center) to (0.center); \draw (3.center) to (1.center); \draw [style=dashededge](3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (0.center) to (1.center); \draw [style=dashededge](2.center) to (1.center); \draw [style=dashededge](0.center) to (2.center); \draw [style=dashededge](3.center) to (0.center); \draw (3.center) to (1.center); \draw (3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (0.center) to (1.center); \draw [style=dashededge](2.center) to (1.center); \draw [style=dashededge](0.center) to (2.center); \draw (3.center) to (0.center); \draw [style=dashededge](3.center) to (1.center); \draw [style=dashededge](3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (0.center) to (1.center); \draw [style=dashededge](2.center) to (1.center); \draw [style=dashededge](0.center) to (2.center); \draw (3.center) to (0.center); \draw [style=dashededge](3.center) to (1.center); \draw (3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (0.center) to (1.center); \draw [style=dashededge](2.center) to (1.center); \draw [style=dashededge](0.center) to (2.center); \draw (3.center) to (0.center); \draw (3.center) to (1.center); \draw [style=dashededge](3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (0.center) to (1.center); \draw [style=dashededge](2.center) to (1.center); \draw [style=dashededge](0.center) to (2.center); \draw (3.center) to (0.center); \draw (3.center) to (1.center); \draw (3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}.\] \[\begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (0.center) to (1.center); \draw [style=dashededge](2.center) to (1.center); \draw (0.center) to (2.center); \draw [style=dashededge](3.center) to (0.center); \draw [style=dashededge](3.center) to (1.center); \draw [style=dashededge](3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (0.center) to (1.center); \draw [style=dashededge](2.center) to (1.center); \draw (0.center) to (2.center); \draw [style=dashededge](3.center) to (0.center); \draw [style=dashededge](3.center) to (1.center); \draw (3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (0.center) to (1.center); \draw [style=dashededge](2.center) to (1.center); \draw (0.center) to (2.center); \draw [style=dashededge](3.center) to (0.center); \draw (3.center) to (1.center); \draw [style=dashededge](3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (0.center) to (1.center); \draw [style=dashededge](2.center) to (1.center); \draw (0.center) to (2.center); \draw [style=dashededge](3.center) to (0.center); \draw (3.center) to (1.center); \draw (3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (0.center) to (1.center); \draw [style=dashededge](2.center) to (1.center); \draw (0.center) to (2.center); \draw (3.center) to (0.center); \draw [style=dashededge](3.center) to (1.center); \draw [style=dashededge](3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (0.center) to (1.center); \draw [style=dashededge](2.center) to (1.center); \draw (0.center) to (2.center); \draw (3.center) to (0.center); \draw [style=dashededge](3.center) to (1.center); \draw (3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (0.center) to (1.center); \draw [style=dashededge](2.center) to (1.center); \draw (0.center) to (2.center); \draw (3.center) to (0.center); \draw (3.center) to (1.center); \draw [style=dashededge](3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (0.center) to (1.center); \draw [style=dashededge](2.center) to (1.center); \draw (0.center) to (2.center); \draw (3.center) to (0.center); \draw (3.center) to (1.center); \draw (3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}.\] \[\begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (0.center) to (1.center); \draw (2.center) to (1.center); \draw (0.center) to (2.center); \draw [style=dashededge](3.center) to (0.center); \draw [style=dashededge](3.center) to (1.center); \draw [style=dashededge](3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (0.center) to (1.center); \draw (2.center) to (1.center); \draw (0.center) to (2.center); \draw [style=dashededge](3.center) to (0.center); \draw [style=dashededge](3.center) to (1.center); \draw (3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (0.center) to (1.center); \draw (2.center) to (1.center); \draw (0.center) to (2.center); \draw [style=dashededge](3.center) to (0.center); \draw (3.center) to (1.center); \draw [style=dashededge](3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (0.center) to (1.center); \draw (2.center) to (1.center); \draw (0.center) to (2.center); \draw [style=dashededge](3.center) to (0.center); \draw (3.center) to (1.center); \draw (3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (0.center) to (1.center); \draw (2.center) to (1.center); \draw (0.center) to (2.center); \draw (3.center) to (0.center); \draw [style=dashededge](3.center) to (1.center); \draw [style=dashededge](3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (0.center) to (1.center); \draw (2.center) to (1.center); \draw (0.center) to (2.center); \draw (3.center) to (0.center); \draw [style=dashededge](3.center) to (1.center); \draw (3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (0.center) to (1.center); \draw (2.center) to (1.center); \draw (0.center) to (2.center); \draw (3.center) to (0.center); \draw (3.center) to (1.center); \draw [style=dashededge](3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (2) at (330:1) {}; \node [style=root] (1) at (90:1) {}; \node [style=root] (0) at (210:1) {}; \node [style=vertex] (3) at (0,0) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (0.center) to (1.center); \draw (2.center) to (1.center); \draw (0.center) to (2.center); \draw (3.center) to (0.center); \draw (3.center) to (1.center); \draw (3.center) to (2.center); \end{pgfonlayer} \end{tikzpicture}.\] Consider the following four \(8\times 8\) matrices: \[A_1:=\frac{1}{192}\begin{bmatrix} 180 &60 &60 &-60 &60 &-60 &-60 &-180\\ 60 &64 &-2 &-5 &-2 &-5 &-50 &-60\\ 60 &-2 &64 &-5 &-2 &-50 &-5 &-60\\ -60 &-5 &-5 &100 &-50 &-20 &-20 &60\\ 60 &-2 &-2 &-50 &64 &-5 &-5 &-60\\ -60 &-5 &-50 &-20 &-5 &100 &-20 &60\\ -60 &-50 &-5 &-20 &-5 &-20 &100 &60\\ -180 &-60 &-60 &60 &-60 &60 &60 &180 \end{bmatrix}\] \[A_2:=\frac{1}{192}\begin{bmatrix} 300 &150 &75 &-75 &75 &-75 &-150 &-300\\ 150 &192 &-21 &0 &-21 &0 &-150 &-150\\ 75 &-21 &96 &-15 &0 &-60 &0 &-75\\ -75 &0 &-15 &120 &-60 &30 &-75 &75\\ 75 &-21 &0 &-60 &96 &-15 &0 &-75\\ -75 &0 &-60 &30 &-15 &120 &-75 &75\\ -150 &-150 &0 &-75 &0 &-75 &300 &150\\ -300 &-150 &-75 &75 &-75 &75 &150 &300 \end{bmatrix}\] \[A_3:=\frac{1}{192}\begin{bmatrix} 300 &30 &30 &-240 &240 &-30 &-30 &-300\\ 30 &66 &-6 &30 &-30 &-30 &-30 &-30\\ 30 &-6 &66 &30 &-30 &-30 &-30 &-30\\ -240 &30 &30 &300 &-300 &-30 &-30 &240\\ 240 &-30 &-30 &-300 &300 &30 &30 &-240\\ -30 &-30 &-30 &-30 &30 &90 &-30 &30\\ -30 &-30 &-30 &-30 &30 &-30 &90 &30\\ -300 &-30 &-30 &240 &-240 &30 &30 &300 \end{bmatrix}\] \[A_4:=\frac{1}{192}\begin{bmatrix} 180 &60 &60 &-60 &60 &-60 &-60 &-180\\ 60 &60 &0 &0 &0 &0 &-60 &-60\\ 60 &0 &60 &0 &0 &-60 &0 &-60\\ -60 &0 &0 &60 &-60 &0 &0 &60\\ 60 &0 &0 &-60 &60 &0 &0 &-60\\ -60 &0 &-60 &0 &0 &60 &0 &60\\ -60 &-60 &0 &0 &0 &0 &60 &60\\ -180 &-60 &-60 &60 &-60 &60 &60 &180 \end{bmatrix}\] The matrices \(A_1,A_2,A_3\) and \(A_4\) are positive semi-definite. For each graph \(J\) of order five, we have \[t_{\mathop{\mathrm{inj}}}(C_5,J) + t_{\mathop{\mathrm{inj}}}(B,\overline{J})-\sum_{q=1}^4\sum_{i=1}^{8}\sum_{j=1}^{8}A_q(i,j)a_q(F^q_{i},F^q_{j}; J)=1/16.\] The full list of calculations required to verify this for all graphs \(J\) on five vertices will be included in an ancillary file with a later arxiv preprint of the paper. ◻

Finally, we prove Theorem 1. This proof follows the same principles of the other two in this section, but the details are much more complicated.

Proof of Theorem 1. The upper bound was proven in Proposition 1. We prove the lower bound \(c_{5/6}(D,M)\geq 1/36\) by applying Lemma 1 with \(\ell=6\), \(m=5\), \(r_1=3\), \(r_2=2\), \(r_3=r_4=r_5=4\), \(k_1=k_2=4\), \(k_3=k_4=k_5=5\), \(t_1=8\), \(t_2=20\) and \(t_3=t_4=t_5=16\). Let \(F^1_1,\dots,F^1_8\) be as in the proof of Theorem 1. Define \(F^2_1,\dots,F^2_{20}\) to be the following graphs where the square vertices are labelled \(1\) and \(2\) from left to right and the round vertices are labelled \(3\) and \(4\) from left to right: \[\begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (225:0.75) {}; \node [style=root] (2) at (315:0.75) {}; \node [style=vertex] (3) at (45:0.75) {}; \node [style=vertex] (4) at (135:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](2.center) to (4.center); \draw [style=dashededge](3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (225:0.75) {}; \node [style=root] (2) at (315:0.75) {}; \node [style=vertex] (3) at (45:0.75) {}; \node [style=vertex] (4) at (135:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw (1.center) to (4.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](2.center) to (4.center); \draw [style=dashededge](3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (225:0.75) {}; \node [style=root] (2) at (315:0.75) {}; \node [style=vertex] (3) at (45:0.75) {}; \node [style=vertex] (4) at (135:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw (1.center) to (3.center); \draw (1.center) to (4.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](2.center) to (4.center); \draw [style=dashededge](3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (225:0.75) {}; \node [style=root] (2) at (315:0.75) {}; \node [style=vertex] (3) at (45:0.75) {}; \node [style=vertex] (4) at (135:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw (1.center) to (4.center); \draw (2.center) to (3.center); \draw [style=dashededge](2.center) to (4.center); \draw [style=dashededge](3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (225:0.75) {}; \node [style=root] (2) at (315:0.75) {}; \node [style=vertex] (3) at (45:0.75) {}; \node [style=vertex] (4) at (135:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw [style=dashededge](2.center) to (3.center); \draw (2.center) to (4.center); \draw [style=dashededge](3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (225:0.75) {}; \node [style=root] (2) at (315:0.75) {}; \node [style=vertex] (3) at (45:0.75) {}; \node [style=vertex] (4) at (135:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw (2.center) to (3.center); \draw (2.center) to (4.center); \draw [style=dashededge](3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (225:0.75) {}; \node [style=root] (2) at (315:0.75) {}; \node [style=vertex] (3) at (45:0.75) {}; \node [style=vertex] (4) at (135:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw (1.center) to (4.center); \draw [style=dashededge](2.center) to (3.center); \draw (2.center) to (4.center); \draw [style=dashededge](3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (225:0.75) {}; \node [style=root] (2) at (315:0.75) {}; \node [style=vertex] (3) at (45:0.75) {}; \node [style=vertex] (4) at (135:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw (1.center) to (3.center); \draw (1.center) to (4.center); \draw [style=dashededge](2.center) to (3.center); \draw (2.center) to (4.center); \draw [style=dashededge](3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (225:0.75) {}; \node [style=root] (2) at (315:0.75) {}; \node [style=vertex] (3) at (45:0.75) {}; \node [style=vertex] (4) at (135:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw (1.center) to (4.center); \draw (2.center) to (3.center); \draw (2.center) to (4.center); \draw [style=dashededge](3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (225:0.75) {}; \node [style=root] (2) at (315:0.75) {}; \node [style=vertex] (3) at (45:0.75) {}; \node [style=vertex] (4) at (135:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw (1.center) to (3.center); \draw (1.center) to (4.center); \draw (2.center) to (3.center); \draw (2.center) to (4.center); \draw [style=dashededge](3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\] \[\begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (225:0.75) {}; \node [style=root] (2) at (315:0.75) {}; \node [style=vertex] (3) at (45:0.75) {}; \node [style=vertex] (4) at (135:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](2.center) to (4.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (225:0.75) {}; \node [style=root] (2) at (315:0.75) {}; \node [style=vertex] (3) at (45:0.75) {}; \node [style=vertex] (4) at (135:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw (1.center) to (4.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](2.center) to (4.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (225:0.75) {}; \node [style=root] (2) at (315:0.75) {}; \node [style=vertex] (3) at (45:0.75) {}; \node [style=vertex] (4) at (135:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw (1.center) to (3.center); \draw (1.center) to (4.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](2.center) to (4.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (225:0.75) {}; \node [style=root] (2) at (315:0.75) {}; \node [style=vertex] (3) at (45:0.75) {}; \node [style=vertex] (4) at (135:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw (1.center) to (4.center); \draw (2.center) to (3.center); \draw [style=dashededge](2.center) to (4.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (225:0.75) {}; \node [style=root] (2) at (315:0.75) {}; \node [style=vertex] (3) at (45:0.75) {}; \node [style=vertex] (4) at (135:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw [style=dashededge](2.center) to (3.center); \draw (2.center) to (4.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (225:0.75) {}; \node [style=root] (2) at (315:0.75) {}; \node [style=vertex] (3) at (45:0.75) {}; \node [style=vertex] (4) at (135:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw (2.center) to (3.center); \draw (2.center) to (4.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (225:0.75) {}; \node [style=root] (2) at (315:0.75) {}; \node [style=vertex] (3) at (45:0.75) {}; \node [style=vertex] (4) at (135:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw (1.center) to (4.center); \draw [style=dashededge](2.center) to (3.center); \draw (2.center) to (4.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (225:0.75) {}; \node [style=root] (2) at (315:0.75) {}; \node [style=vertex] (3) at (45:0.75) {}; \node [style=vertex] (4) at (135:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw (1.center) to (3.center); \draw (1.center) to (4.center); \draw [style=dashededge](2.center) to (3.center); \draw (2.center) to (4.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (225:0.75) {}; \node [style=root] (2) at (315:0.75) {}; \node [style=vertex] (3) at (45:0.75) {}; \node [style=vertex] (4) at (135:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw (1.center) to (4.center); \draw (2.center) to (3.center); \draw (2.center) to (4.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (225:0.75) {}; \node [style=root] (2) at (315:0.75) {}; \node [style=vertex] (3) at (45:0.75) {}; \node [style=vertex] (4) at (135:0.75) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw (1.center) to (2.center); \draw (1.center) to (3.center); \draw (1.center) to (4.center); \draw (2.center) to (3.center); \draw (2.center) to (4.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\] Next, we define \(F^q_i\) for \(3\leq q\leq 5\) and \(1\leq i\leq 16\) as follows, where the graphs \(F^1_1,\dots,F^1_{16}\) are listed first, followed by \(F^2_1,\dots,F^2_{16}\) and then \(F^3_1,\dots,F^3_{16}\). Square vertices are labelled \(1,2,3\) and \(4\) from left to right and round vertices are labelled \(5\). \[\begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw [style=dashededge](1.center) to (5.center); \draw [style=dashededge](4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw [style=dashededge] (2.center) to (5.center); \draw [style=dashededge](3.center) to (5.center); \draw [style=dashededge] (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw (1.center) to (5.center); \draw [style=dashededge](4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw [style=dashededge] (2.center) to (5.center); \draw [style=dashededge](3.center) to (5.center); \draw [style=dashededge] (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw [style=dashededge](1.center) to (5.center); \draw [style=dashededge](4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw (2.center) to (5.center); \draw [style=dashededge](3.center) to (5.center); \draw [style=dashededge] (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw (1.center) to (5.center); \draw [style=dashededge](4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw (2.center) to (5.center); \draw [style=dashededge](3.center) to (5.center); \draw [style=dashededge] (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw [style=dashededge](1.center) to (5.center); \draw [style=dashededge](4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw [style=dashededge](2.center) to (5.center); \draw (3.center) to (5.center); \draw [style=dashededge] (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw (1.center) to (5.center); \draw [style=dashededge](4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw [style=dashededge](2.center) to (5.center); \draw (3.center) to (5.center); \draw [style=dashededge] (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw [style=dashededge](1.center) to (5.center); \draw [style=dashededge](4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw (2.center) to (5.center); \draw (3.center) to (5.center); \draw [style=dashededge] (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw (1.center) to (5.center); \draw [style=dashededge](4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw (2.center) to (5.center); \draw (3.center) to (5.center); \draw [style=dashededge] (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\] \[\begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw [style=dashededge](1.center) to (5.center); \draw (4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw [style=dashededge](2.center) to (5.center); \draw [style=dashededge](3.center) to (5.center); \draw [style=dashededge] (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw (1.center) to (5.center); \draw (4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw [style=dashededge](2.center) to (5.center); \draw [style=dashededge](3.center) to (5.center); \draw [style=dashededge] (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw [style=dashededge](1.center) to (5.center); \draw (4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw (2.center) to (5.center); \draw [style=dashededge](3.center) to (5.center); \draw [style=dashededge] (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw (1.center) to (5.center); \draw (4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw (2.center) to (5.center); \draw [style=dashededge](3.center) to (5.center); \draw [style=dashededge] (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw [style=dashededge](1.center) to (5.center); \draw (4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw [style=dashededge](2.center) to (5.center); \draw (3.center) to (5.center); \draw [style=dashededge] (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw (1.center) to (5.center); \draw (4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw [style=dashededge](2.center) to (5.center); \draw (3.center) to (5.center); \draw [style=dashededge] (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw [style=dashededge](1.center) to (5.center); \draw (4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw (2.center) to (5.center); \draw (3.center) to (5.center); \draw [style=dashededge] (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw (1.center) to (5.center); \draw (4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw (2.center) to (5.center); \draw (3.center) to (5.center); \draw [style=dashededge] (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\] \[\begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw (2.center) to (3.center); \draw (1.center) to (4.center); \draw [style=dashededge](1.center) to (5.center); \draw [style=dashededge](4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw [style=dashededge](2.center) to (5.center); \draw [style=dashededge](3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw (2.center) to (3.center); \draw (1.center) to (4.center); \draw (1.center) to (5.center); \draw [style=dashededge](4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw [style=dashededge](2.center) to (5.center); \draw [style=dashededge](3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw (2.center) to (3.center); \draw (1.center) to (4.center); \draw [style=dashededge](1.center) to (5.center); \draw [style=dashededge](4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw (2.center) to (5.center); \draw [style=dashededge](3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw (2.center) to (3.center); \draw (1.center) to (4.center); \draw (1.center) to (5.center); \draw [style=dashededge](4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw (2.center) to (5.center); \draw [style=dashededge](3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw (2.center) to (3.center); \draw (1.center) to (4.center); \draw [style=dashededge](1.center) to (5.center); \draw [style=dashededge](4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw [style=dashededge](2.center) to (5.center); \draw (3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw (2.center) to (3.center); \draw (1.center) to (4.center); \draw (1.center) to (5.center); \draw [style=dashededge](4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw [style=dashededge](2.center) to (5.center); \draw (3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw (2.center) to (3.center); \draw (1.center) to (4.center); \draw [style=dashededge](1.center) to (5.center); \draw [style=dashededge](4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw (2.center) to (5.center); \draw (3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw (2.center) to (3.center); \draw (1.center) to (4.center); \draw (1.center) to (5.center); \draw [style=dashededge](4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw (2.center) to (5.center); \draw (3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\] \[\begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw (2.center) to (3.center); \draw (1.center) to (4.center); \draw [style=dashededge](1.center) to (5.center); \draw (4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw [style=dashededge](2.center) to (5.center); \draw [style=dashededge](3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw (2.center) to (3.center); \draw (1.center) to (4.center); \draw (1.center) to (5.center); \draw (4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw [style=dashededge](2.center) to (5.center); \draw [style=dashededge](3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw (2.center) to (3.center); \draw (1.center) to (4.center); \draw [style=dashededge](1.center) to (5.center); \draw (4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw (2.center) to (5.center); \draw [style=dashededge](3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw (2.center) to (3.center); \draw (1.center) to (4.center); \draw (1.center) to (5.center); \draw (4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw (2.center) to (5.center); \draw [style=dashededge](3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw (2.center) to (3.center); \draw (1.center) to (4.center); \draw [style=dashededge](1.center) to (5.center); \draw (4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw [style=dashededge](2.center) to (5.center); \draw (3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw (2.center) to (3.center); \draw (1.center) to (4.center); \draw (1.center) to (5.center); \draw (4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw [style=dashededge](2.center) to (5.center); \draw (3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw (2.center) to (3.center); \draw (1.center) to (4.center); \draw [style=dashededge](1.center) to (5.center); \draw (4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw (2.center) to (5.center); \draw (3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw (2.center) to (3.center); \draw (1.center) to (4.center); \draw (1.center) to (5.center); \draw (4.center) to (5.center); \draw [style=dashededge](2.center) to (4.center); \draw (2.center) to (5.center); \draw (3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\] \[\begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw [style=dashededge](1.center) to (5.center); \draw [style=dashededge](4.center) to (5.center); \draw (2.center) to (4.center); \draw [style=dashededge](2.center) to (5.center); \draw [style=dashededge](3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw (1.center) to (5.center); \draw [style=dashededge](4.center) to (5.center); \draw (2.center) to (4.center); \draw [style=dashededge](2.center) to (5.center); \draw [style=dashededge](3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw [style=dashededge](1.center) to (5.center); \draw [style=dashededge](4.center) to (5.center); \draw (2.center) to (4.center); \draw (2.center) to (5.center); \draw [style=dashededge](3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw (1.center) to (5.center); \draw [style=dashededge](4.center) to (5.center); \draw (2.center) to (4.center); \draw (2.center) to (5.center); \draw [style=dashededge](3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw [style=dashededge](1.center) to (5.center); \draw [style=dashededge](4.center) to (5.center); \draw (2.center) to (4.center); \draw [style=dashededge](2.center) to (5.center); \draw (3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw (1.center) to (5.center); \draw [style=dashededge](4.center) to (5.center); \draw (2.center) to (4.center); \draw [style=dashededge](2.center) to (5.center); \draw (3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw [style=dashededge](1.center) to (5.center); \draw [style=dashededge](4.center) to (5.center); \draw (2.center) to (4.center); \draw (2.center) to (5.center); \draw (3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw (1.center) to (5.center); \draw [style=dashededge](4.center) to (5.center); \draw (2.center) to (4.center); \draw (2.center) to (5.center); \draw (3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\] \[\begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw [style=dashededge](1.center) to (5.center); \draw (4.center) to (5.center); \draw (2.center) to (4.center); \draw [style=dashededge](2.center) to (5.center); \draw [style=dashededge](3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw (1.center) to (5.center); \draw (4.center) to (5.center); \draw (2.center) to (4.center); \draw [style=dashededge](2.center) to (5.center); \draw [style=dashededge](3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw [style=dashededge](1.center) to (5.center); \draw (4.center) to (5.center); \draw (2.center) to (4.center); \draw (2.center) to (5.center); \draw [style=dashededge](3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw (1.center) to (5.center); \draw (4.center) to (5.center); \draw (2.center) to (4.center); \draw (2.center) to (5.center); \draw [style=dashededge](3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw [style=dashededge](1.center) to (5.center); \draw (4.center) to (5.center); \draw (2.center) to (4.center); \draw [style=dashededge](2.center) to (5.center); \draw (3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw (1.center) to (5.center); \draw (4.center) to (5.center); \draw (2.center) to (4.center); \draw [style=dashededge](2.center) to (5.center); \draw (3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw [style=dashededge](1.center) to (5.center); \draw (4.center) to (5.center); \draw (2.center) to (4.center); \draw (2.center) to (5.center); \draw (3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\quad \begin{tikzpicture}[scale = 0.75] \begin{pgfonlayer}{nodelayer} \node [style=root] (1) at (150:1.00) {}; \node [style=root] (2) at (210:0.75) {}; \node [style=root] (3) at (330:0.75) {}; \node [style=root] (4) at (30:1.00) {}; \node [style=vertex] (5) at (90:1.00) {}; \end{pgfonlayer} \begin{pgfonlayer}{edgelayer} \draw [style=dashededge](1.center) to (2.center); \draw [style=dashededge](1.center) to (3.center); \draw [style=dashededge](2.center) to (3.center); \draw [style=dashededge](1.center) to (4.center); \draw (1.center) to (5.center); \draw (4.center) to (5.center); \draw (2.center) to (4.center); \draw (2.center) to (5.center); \draw (3.center) to (5.center); \draw (3.center) to (4.center); \end{pgfonlayer} \end{tikzpicture}\] Let \(A_1,\dots,A_5\) be \(\frac{1}{143327232}\) times the following five matrices, respectively. \[\scalebox{0.86}{\displaystyle \begin{bmatrix} 111346560& 37116000& 37117440& -37113120& 37113120& -37117440& -37116000& -111346560\\37116000& 15935040& 10588320& -10592640& 10592640& -10588320& -15935040& -37116000\\37117440& 10588320& 15940800& -10588320& 10588320& -15940800& -10588320& -37117440\\-37113120& -10592640& -10588320& 15932160& -15932160& 10588320& 10592640& 37113120\\37113120& 10592640& 10588320& -15932160& 15932160& -10588320& -10592640& -37113120\\-37117440& -10588320& -15940800& 10588320& -10588320& 15940800& 10588320& 37117440\\-37116000& -15935040& -10588320& 10592640& -10592640& 10588320& 15935040& 37116000\\-111346560& -37116000& -37117440& 37113120& -37113120& 37117440& 37116000& 111346560\end{bmatrix}}\]

\[\scalebox{0.325}{\displaystyle \begin{bmatrix}435680640& 70673592& 39214152& -260606268& 72061368& 39335040& -338621760& 86257368& 86238720& 54772560& 157012560& -101640708& 7852320& -49221936& -101576160& 7853760& -377510400& -34020000& -34018560& -216305280\\70673592& 191632176& -8295120& -82544568& -63666864& 59861552& -57466080& -18302400& -51233652& -17892000& 49856694& 174706704& -199401120& -432096& -6262716& 107982720& -47568960& -206556480& -4969440& -83658240\\39214152& -8295120& 196475040& -11959452& 60297904& -116484417& -30909600& 39916800& 11403288& 12787200& 36371248& -163641600& 11918880& -37222560& 184695468& -96532525& -18162720& -54787680& -135158784& -61253280\\-260606268& -82544568& -11959452& 297408258& -82909440& -11988000& 205597440& 59905440& 59905440& 62311680& -101155968& -76668000& -24187680& -9070974& -76364640& -24187680& 194530656& 26231040& 26231040& 146456640\\72061368& -63666864& 60297904& -82909440& 191393280& -8298720& -57477600& -51651948& -18295200& -17902080& 50505546& -7638828& 107974080& -505440& 174657600& -199406880& -47550240& -4980960& -206565120& -83665440\\39335040& 59861552& -116484417& -11988000& -8298720& 196477920& -30909600& 11478240& 39916800& 12787200& 36743384& 184800960& -96457901& -37225440& -163658880& 11918880& -18144000& -135064800& -54790560& -61253280\\-338621760& -57466080& -30909600& 205597440& -57477600& -30909600& 263714400& -64717920& -64717920& -41860800& -122960160& 74178720& -4764960& 37575360& 74178720& -4764960& 293060160& 30054240& 30054240& 169935840\\86257368& -18302400& 39916800& 59905440& -51651948& 11478240& -64717920& 194987520& 128100960& 157282560& 31332960& -211580640& -89569440& -61008528& -89136492& 45912960& -120479184& -95251680& 32365440& -40068000\\86238720& -51233652& 11403288& 59905440& -18295200& 39916800& -64717920& 128100960& 194987520& 157282560& 31332960& -88853652& 45912960& -61171200& -211563360& -89570880& -120471840& 32365440& -95251680& -40068000\\54772560& -17892000& 12787200& 62311680& -17902080& 12787200& -41860800& 157282560& 157282560& 269326080& 36077688& -78715008& -66294720& -22145904& -78926400& -66294720& -135064800& -125085600& -125085600& -56609280\\157012560& 49856694& 36371248& -101155968& 50505546& 36743384& -122960160& 31332960& 31332960& 36077688& 80334720& 10646994& -38059200& -27440496& 10075038& -38059200& -131751360& -102418560& -102418560& -122489280\\-101640708& 174706704& -163641600& -76668000& -7638828& 184800960& 74178720& -211580640& -88853652& -78715008& 10646994& 671797872& -56574720& 53529312& -149957280& -83285280& 117402144& -94150080& -238908540& -42465600\\7852320& -199401120& 11918880& -24187680& 107974080& -96457901& -4764960& -89569440& 45912960& -66294720& -38059200& -56574720& 405617760& 19202760& -83284920& -205366425& 1827360& 430138080& -78634752& 73526400\\-49221936& -432096& -37222560& -9070974& -505440& -37225440& 37575360& -61008528& -61171200& -22145904& -27440496& 53529312& 19202760& 55267074& 53434080& 19202400& 32843520& 41379804& 41506980& 41217120\\-101576160& -6262716& 184695468& -76364640& 174657600& -163658880& 74178720& -89136492& -211563360& -78926400& 10075038& -149957280& -83284920& 53434080& 671453280& -56574720& 117309600& -239035716& -94150080& -42465600\\7853760& 107982720& -96532525& -24187680& -199406880& 11918880& -4764960& 45912960& -89570880& -66294720& -38059200& -83285280& -205366425& 19202400& -56574720& 405617760& 1827360& -78412320& 430138080& 73526400\\-377510400& -47568960& -18162720& 194530656& -47550240& -18144000& 293060160& -120479184& -120471840& -135064800& -131751360& 117402144& 1827360& 32843520& 117309600& 1827360& 386765424& 19686240& 19686240& 179305920\\-34020000& -206556480& -54787680& 26231040& -4980960& -135064800& 30054240& -95251680& 32365440& -125085600& -102418560& -94150080& 430138080& 41379804& -239035716& -78412320& 19686240& 643044960& 171445104& 188179200\\-34018560& -4969440& -135158784& 26231040& -206565120& -54790560& 30054240& 32365440& -95251680& -125085600& -102418560& -238908540& -78634752& 41506980& -94150080& 430138080& 19686240& 171445104& 643044960& 188179200\\-216305280& -83658240& -61253280& 146456640& -83665440& -61253280& 169935840& -40068000& -40068000& -56609280& -122489280& -42465600& 73526400& 41217120& -42465600& 73526400& 179305920& 188179200& 188179200& 191786400\end{bmatrix}}\]

\[\scalebox{0.465}{\displaystyle \begin{bmatrix}160709760& 80356320& 80356320& 2880& 80356320& 2880& 2880& -80350560& 80350560& -2880& -2880& -80356320& -2880& -80356320& -80356320& -160709760\\80356320& 40583520& 40039920& 267120& 40025520& 252720& -290880& -40063680& 40063680& 290880& -252720& -40025520& -267120& -40039920& -40583520& -80356320\\80356320& 40039920& 40538880& 222480& 40070160& -246240& 252720& -40063680& 40063680& -252720& 246240& -40070160& -222480& -40538880& -40039920& -80356320\\2880& 267120& 222480& 486720& -260640& 3600& -41040& 223200& -223200& 41040& -3600& 260640& -486720& -222480& -267120& -2880\\80356320& 40025520& 40070160& -260640& 40538880& 208080& 252720& -40078080& 40078080& -252720& -208080& -40538880& 260640& -40070160& -40025520& -80356320\\2880& 252720& -246240& 3600& 208080& 457920& -41040& 208800& -208800& 41040& -457920& -208080& -3600& 246240& -252720& -2880\\2880& -290880& 252720& -41040& 252720& -41040& 502560& 208800& -208800& -502560& 41040& -252720& 41040& -252720& 290880& -2880\\-80350560& -40063680& -40063680& 223200& -40078080& 208800& 208800& 40495680& -40495680& -208800& -208800& 40078080& -223200& 40063680& 40063680& 80350560\\80350560& 40063680& 40063680& -223200& 40078080& -208800& -208800& -40495680& 40495680& 208800& 208800& -40078080& 223200& -40063680& -40063680& -80350560\\-2880& 290880& -252720& 41040& -252720& 41040& -502560& -208800& 208800& 502560& -41040& 252720& -41040& 252720& -290880& 2880\\-2880& -252720& 246240& -3600& -208080& -457920& 41040& -208800& 208800& -41040& 457920& 208080& 3600& -246240& 252720& 2880\\-80356320& -40025520& -40070160& 260640& -40538880& -208080& -252720& 40078080& -40078080& 252720& 208080& 40538880& -260640& 40070160& 40025520& 80356320\\-2880& -267120& -222480& -486720& 260640& -3600& 41040& -223200& 223200& -41040& 3600& -260640& 486720& 222480& 267120& 2880\\-80356320& -40039920& -40538880& -222480& -40070160& 246240& -252720& 40063680& -40063680& 252720& -246240& 40070160& 222480& 40538880& 40039920& 80356320\\-80356320& -40583520& -40039920& -267120& -40025520& -252720& 290880& 40063680& -40063680& -290880& 252720& 40025520& 267120& 40039920& 40583520& 80356320\\-160709760& -80356320& -80356320& -2880& -80356320& -2880& -2880& 80350560& -80350560& 2880& 2880& 80356320& 2880& 80356320& 80356320& 160709760\end{bmatrix}}\]

\[\scalebox{0.4}{\displaystyle \begin{bmatrix}1065864960& 523195200& 523186560& -19483200& 554580000& 11910240& -200564640& -573173280& 554580000& -200564640& 11901600& -573173280& 56669760& -500610240& -500610240& -1113488640\\523195200& 1161790560& 81041040& 719636400& 37884240& 676479600& -279832320& -65400480& -185004000& 91743840& -627158160& -144646560& -362469600& -102686400& -789251040& -621838080\\523186560& 81041040& 1161816480& 719670960& -185023440& -627168960& 91748160& -144646560& 37864800& -279828000& 676494720& -65400480& -362465280& -789246720& -102682080& -621838080\\-19483200& 719636400& 719670960& 1458790560& -701719200& 37400400& 12480480& 363126240& -701719200& 12480480& 37434960& 363126240& -781604640& -391322880& -391322880& -130187520\\554580000& 37884240& -185023440& -701719200& 820376640& 303680880& 59425920& -278488800& 444052800& -344040480& -295550640& -724645440& 440424000& 25254720& -173819520& -570840480\\11910240& 676479600& -627168960& 37400400& 303680880& 968250240& -19841760& 229284000& -295531200& -51732000& -934610400& -296118720& 21284640& 423178560& -462460320& -79189920\\-200564640& -279832320& 91748160& 12480480& 59425920& -19841760& 563444640& 506995200& -344040480& -289496160& -51727680& -100910880& -133950240& 2678400& 153290880& 343703520\\-573173280& -65400480& -144646560& 363126240& -278488800& 229284000& 506995200& 805611312& -724645440& -100910880& -296118720& 180476208& -346079520& 209865600& 126900000& 706842720\\554580000& -185004000& 37864800& -701719200& 444052800& -295531200& -344040480& -724645440& 820376640& 59425920& 303661440& -278488800& 440424000& -173819520& 25254720& -570840480\\-200564640& 91743840& -279828000& 12480480& -344040480& -51732000& -289496160& -100910880& 59425920& 563444640& -19837440& 506995200& -133950240& 153286560& 2678400& 343703520\\11901600& -627158160& 676494720& 37434960& -295550640& -934610400& -51727680& -296118720& 303661440& -19837440& 968254560& 229284000& 21288960& -462456000& 423182880& -79189920\\-573173280& -144646560& -65400480& 363126240& -724645440& -296118720& -100910880& 180476208& -278488800& 506995200& 229284000& 805611312& -346079520& 126900000& 209865600& 706842720\\56669760& -362469600& -362465280& -781604640& 440424000& 21284640& -133950240& -346079520& 440424000& -133950240& 21288960& -346079520& 592915680& 203122080& 203122080& -141816960\\-500610240& -102686400& -789246720& -391322880& 25254720& 423178560& 2678400& 209865600& -173819520& 153286560& -462456000& 126900000& 203122080& 654004800& 105485760& 579165120\\-500610240& -789251040& -102682080& -391322880& -173819520& -462460320& 153290880& 126900000& 25254720& 2678400& 423182880& 209865600& 203122080& 105485760& 654004800& 579165120\\-1113488640& -621838080& -621838080& -130187520& -570840480& -79189920& 343703520& 706842720& -570840480& 343703520& -79189920& 706842720& -141816960& 579165120& 579165120& 1430248320\end{bmatrix}}\]

\[\scalebox{0.4}{\displaystyle \begin{bmatrix}583735680& -55248480& 597395520& -41588640& 597404160& -41580000& 611064000& -27920160& 51732000& -587252160& -209541600& -609305760& -209541600& -609305760& -375550560& -631359360\\-55248480& 366158880& 84818880& 506226240& 84853440& 506260800& 224920800& 646328160& -512079840& -90672480& -434609280& -151960320& -434609280& -151960320& -421761600& -213248160\\597395520& 84818880& 1101008160& 588431520& 347487840& -165088800& 851100480& 338523840& -247639680& -760216320& -317183040& -720502560& -539814240& -818877600& -499284000& -779163840\\-41588640& 506226240& 588431520& 1136246400& -165062880& 382752000& 464957280& 1012772160& -811451520& -263636640& -542250720& -263157120& -764881920& -361532160& -545495040& -361052640\\597404160& 84853440& 347487840& -165062880& 1100995200& 588444480& 851078880& 338528160& -247648320& -760199040& -539809920& -818868960& -317178720& -720493920& -499292640& -779163840\\-41580000& 506260800& -165088800& 382752000& 588444480& 1136285280& 464935680& 1012776480& -811460160& -263619360& -764877600& -361523520& -542246400& -263148480& -545503680& -361052640\\611064000& 224920800& 851100480& 464957280& 851078880& 464935680& 1091115360& 704972160& -547020000& -933163200& -647451360& -930065760& -647451360& -930065760& -623026080& -926968320\\-27920160& 646328160& 338523840& 1012772160& 338528160& 1012776480& 704972160& 1379220480& -1110831840& -436583520& -872519040& -472720320& -872519040& -472720320& -669237120& -508857120\\51732000& -512079840& -247639680& -811451520& -247648320& -811460160& -547020000& -1110831840& 909727200& 345915360& 679108320& 348196320& 679108320& 348196320& 494095680& 350477280\\-587252160& -90672480& -760216320& -263636640& -760199040& -263619360& -933163200& -436583520& 345915360& 842495040& 454040640& 805541760& 454040640& 805541760& 447884640& 768588480\\-209541600& -434609280& -317183040& -542250720& -539809920& -764877600& -647451360& -872519040& 679108320& 454040640& 827146080& 622935360& 543080160& 427468320& 664891200& 596363040\\-609305760& -151960320& -720502560& -263157120& -818868960& -361523520& -930065760& -472720320& 348196320& 805541760& 622935360& 914245920& 427468320& 749649600& 586859040& 858353760\\-209541600& -434609280& -539814240& -764881920& -317178720& -542246400& -647451360& -872519040& 679108320& 454040640& 543080160& 427468320& 827146080& 622935360& 664891200& 596363040\\-609305760& -151960320& -818877600& -361532160& -720493920& -263148480& -930065760& -472720320& 348196320& 805541760& 427468320& 749649600& 622935360& 914245920& 586859040& 858353760\\-375550560& -421761600& -499284000& -545495040& -499292640& -545503680& -623026080& -669237120& 494095680& 447884640& 664891200& 586859040& 664891200& 586859040& 986947200& 725833440\\-631359360& -213248160& -779163840& -361052640& -779163840& -361052640& -926968320& -508857120& 350477280& 768588480& 596363040& 858353760& 596363040& 858353760& 725833440& 948119040\end{bmatrix}}\] The matrices \(A_1,A_2,A_3,A_4\) and \(A_5\) are PSD and, for each graph \(J\) of order six (of which there are 156, up to isomorphism), we have \[(5/6)t_{\mathop{\mathrm{inj}}}(D,J) + (7/6)t_{\mathop{\mathrm{inj}}}(M,\overline{J})-\sum_{q=1}^5\sum_{i=1}^{t_q}\sum_{j=1}^{t_q}A_q(i,j)a_q(F^q_{i},F^q_{j}; J)\geq 1/36.\] The full list of calculations required to verify this for all graphs \(J\) on six vertices will be included in an ancillary file with with a later arxiv preprint of the paper. ◻

6 Concluding Remarks↩︎

We conclude the paper by proposing some open problems related to this work. It seems to us that it would be particularly interesting to determine or estimate \(c(K_3,K_4)\), as this may provide a natural “bridge” between the classical result of Goodman [14] that \(c(K_3)=1/4\) and the seemingly impossible open problem of determining \(c(K_4)\).

Problem 1. Determine \(c(K_3,K_4)\).

A flag algebra calculation on \(7\)-vertex graphs yields a bound of \(c(K_3,K_4)> 0.052634\) and suggests that, if this is tight, then the optimal value of \(\lambda\) is approximately \(0.52103\). However, we caution that these values are from an approximate solution to a semi-definite program that was found by computer, and so they may contain rounding errors. It would also be interesting to compute the balanced Ramsey multiplicity of other pairs of small graphs; in particular, the following is open.

Problem 1. Determine \(c(K_3,C_4)\).

A flag algebra calculation in the universe of \(7\)-vertex graphs suggest that \(c(K_3,C_4)> 0.075159\) with the optimal \(\lambda\) being approximately \(0.37367\); once again, these values have been copied directly from the output of a computer program and so they should not necessarily be trusted.

One of the great triumphs in Ramsey theory during the 20th century was the determination of the asymptotics of \(r(K_3,K_k)\) as \(k\to\infty\). The upper bound \(r(K_3,K_k)=O(k^2/\log(k))\) was first proven by Ajtai, Komlós and Szemerédi [31] and subsequently improved by Shearer [32] and the lower bound was proven by Kim [33]. A new proof of Kim’s [33] result was obtained by Bohman [34] by analyzing the triangle-free process; the best known lower bound on \(r(K_3,K_k)\) was obtained in the seminal works of Fiz Pontiveros, Griffiths and Morris [35] and Bohman and Keevash [36] via a far more detailed analysis of this process. We propose a Ramsey multiplicity analogue of this problem.

Problem 1. Prove sharp bounds on the asymptotics of \(c(K_3,K_k)\) as \(k\to\infty\).

Very recently, Mattheus and Verstraëte [37] determined the asymptotics of \(r(K_4,K_k)\) up to a factor of \(O(\log^2(k))\). Apart from this breakthrough and the aforementioned results on \(r(K_3,K_k)\), the growth rate of \(r(K_s,K_k)\) for fixed \(s\) and \(k\to\infty\) is not well understood. It would also be interesting to analyze the asymptotics of the analogous balanced Ramsey multiplicity constant \(c(K_s,K_k)\) for fixed \(s\geq4\) as \(k\) tends to infinity.

We are also interested in the range of possible values for \(c(H_1,H_2)\). While there are probably many pairs of graphs for which \(c(H_1,H_2)\) is irrational, it is hard to imagine that it could be trancendental.

Conjecture 1. There do not exist graphs \(H_1\) and \(H_2\) such that \(c(H_1,H_2)\) is transcendental.

Classical (i.e. diagonal) Ramsey multiplicity has also been studied in the multicolour setting [7], [16]–[18], [38]. It may be interesting to investigate a generalization of the balanced Ramsey multiplicity constant to \(r\)-tuples of graphs \((H_1,\dots,H_r)\) in \(r\)-edge colourings of \(K_n\) for large \(n\) when \(r\geq3\).

Acknowledgements 1. The authors would like to thank Joseph Hyde and Jae-baek Lee for several enlightening conversations on topics related to the subject of this paper. In particular, we thank Joseph for helpful comments on early drafts of this paper which improved the exposition and for an idea which helped us to discover the construction in Proposition 1. The second author thanks Jan Volec for sharing some tips on how to “round” matrices to convert computer outputs into rigorous flag algebra proofs. In particular, we may not have managed to make the proof of Theorem 1 rigorous without this advice.

References↩︎

[1]

F. P. Ramsey. On a Problem of Formal Logic. Proc. Lond. Math. Soc. (2), 30(4):264–286, 1929.

[2]

S. P. Radziszowski. Small Ramsey numbers. Electron. J. Combin., 1:Dynamic Survey 1, 30, 1994.

[3]

D. Conlon, J. Fox, and B. Sudakov. Recent developments in graph Ramsey theory. In Surveys in combinatorics 2015, volume 424 of London Math. Soc. Lecture Note Ser., pages 49–118. Cambridge Univ. Press, Cambridge, 2015.

[4]

J. Fox. There exist graphs with super-exponential Ramsey multiplicity constant. J. Graph Theory, 57(2):89–98, 2008.

[5]

D. Conlon. On the Ramsey multiplicity of complete graphs. Combinatorica, 32(2):171–186, 2012.

[6]

A. Grzesik, J. Lee, B. Lidický, and J. Volec. On tripartite common graphs. Combin. Probab. Comput., 31(5):907–923, 2022.

[7]

J. Fox and Y. Wigderson. amsey multiplicity and the Turán coloring. E-print arXiv:2207.07775v1, 2022.

[8]

C. Even-Zohar and N. Linial. A note on the inducibility of 4-vertex graphs. Graphs Combin., 31(5):1367–1380, 2015.

[9]

O. Parczyk, S. Pokutta, C. Spiegel, and T. Szabó. New Ramsey multiplicity bounds and search heuristics. E-print arXiv:2206.04036v1, 2022.

[10]

S. Nieß. Counting monochromatic copies of \(K_4\): a new lower bound for the Ramsey multiplicity problem. E-print arXiv:1207.4714v1, 2012.

[11]

K. Sperfeld. On the minimal monochromatic \(K_4\)-density. E-print arXiv:1106.1030v4, 2011.

[12]

A. Thomason. A disproof of a conjecture of Erdős in Ramsey theory. J. Lond. Math. Soc. (2), 39(2):246–255, 1989.

[13]

A. Thomason. Graph products and monochromatic multiplicities. Combinatorica, 17(1):125–134, 1997.

[14]

A. W. Goodman. On sets of acquaintances and strangers at any party. Amer. Math. Monthly, 66:778–783, 1959.

[15]

A. F. Sidorenko. Cycles in graphs and functional inequalities. Mat. Zametki, 46(5):72–79, 104, 1989.

[16]

C. Jagger, P. Šťovı́ček, and A. Thomason. Multiplicities of subgraphs. Combinatorica, 16(1):123–141, 1996.

[17]

D. Kráľ, J. Volec, and F. Wei. Common graphs with arbitrary chromatic number. E-print arXiv:2206.05800v1, 2022.

[18]

D. Kráľ, J. A. Noel, S. Norin, J. Volec, and F. Wei. Non-bipartite \(k\)-common graphs. Combinatorica, 42(1):87–114, 2022.

[19]

N. Behague, N. Morrison, and J. A. Noel. Off-diagonal commonality of graphs via entropy. In preparation, 2023.

[20]

S. Ko and J. Lee. Common graphs with arbitrary connectivity and chromatic number. E-print arXiv:2207.09427v1, 2022.

[21]

H. Hatami, J. Hladký, D. Kráľ, S. Norine, and A. Razborov. Non-three-colourable common graphs exist. Combin. Probab. Comput., 21(5):734–742, 2012.

[22]

J.-B. Lee and J. A. Noel. Disconnected common graphs via supersaturation. E-print arXiv:2303.09296v1, 2023.

[23]

A. F. Sidorenko. A correlation inequality for bipartite graphs. Graphs Combin., 9(2):201–204, 1993.

[24]

P. Erdős and M. Simonovits. Cube-supersaturated graphs and related problems. In Progress in graph theory (Waterloo, Ont., 1982), pages 203–218. Academic Press, Toronto, ON, 1984.

[25]

D. Conlon and J. Lee. Sidorenko’s conjecture for blow-ups. Discrete Anal., Paper No. 2, 13, 2021.

[26]

L. Lovász. Large networks and graph limits, volume 60 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2012.

[27]

L. Lovász and B. Szegedy. Szemerédi’s lemma for the analyst. Geom. Funct. Anal., 17(1):252–270, 2007.

[28]

L. Lovász and B. Szegedy. Limits of dense graph sequences. J. Combin. Theory Ser. B, 96(6):933–957, 2006.

[29]

N. Behague, N. Morrison, and J. A. Noel. Common pairs of graphs. E-print arXiv:2208.02045v3, 2023.

[30]

A. A. Razborov. Flag algebras. J. Symbolic Logic, 72(4):1239–1282, 2007.

[31]

M. Ajtai, J. Komlós, and E. Szemerédi. A note on Ramsey numbers. J. Combin. Theory Ser. A, 29(3):354–360, 1980.

[32]

J. B. Shearer. A note on the independence number of triangle-free graphs. Discrete Math., 46(1):83–87, 1983.

[33]

J. H. Kim. The Ramsey number \(R(3,t)\) has order of magnitude \(t^2/\log t\). Random Structures Algorithms, 7(3):173–207, 1995.

[34]

T. Bohman. The triangle-free process. Adv. Math., 221(5):1653–1677, 2009.

[35]

G. Fiz Pontiveros, S. Griffiths, and R. Morris. The triangle-free process and the Ramsey number \(R(3,k)\). Mem. Amer. Math. Soc., 263(1274):v+125, 2020.

[36]

T. Bohman and P. Keevash. Dynamic concentration of the triangle-free process. Random Structures Algorithms, 58(2):221–293, 2021.

[37]

S. Mattheus and J. Verstraëte. The asymptotics of \(r(4,t)\). E-print arXiv:2306.04007v1, 2023.

[38]

J. Cummings, D. Král’, F. Pfender, K. Sperfeld, A. Treglown, and M. Young. Monochromatic triangles in three-coloured graphs. J. Combin. Theory Ser. B, 103(4):489–503, 2013.

Research supported by an NSERC Undergraduate Student Research Award (USRA).↩︎
Research supported by NSERC Discovery Grant RGPIN-2021-02460, NSERC Early Career Supplement DGECR-2021-00024 and a Start-Up Grant from the University of Victoria.↩︎
An alternative definition of \(c_\lambda(H_1,H_2)\) will be provided in Section 2 in the language of graph limits.↩︎
The name “moth graph” is inspired by the fact that the graph obtained by gluing two triangles on a vertex is often called the butterfly graph.↩︎

Off-Diagonal Ramsey Multiplicity