1 Introduction↩︎

Improving methods for bounding the clique number of a graph reduces the need for extensive computational search and enables deeper analytical insight into clique structure. In his 1973 thesis, Philippe Delsarte introduced a novel linear programming approach for bounding cliques in graphs arising from association schemes [1]. This result, known as the Delsarte linear programming bound, simplifies to the Delsarte bound when applied to a single graph within an association scheme. Shortly thereafter, Alan Hoffman extended the Delsarte bound to all regular graphs, and Willem Haemers subsequently generalised it further to arbitrary graphs.¹ Together, these bounds have become fundamental tools for estimating clique numbers and are widely used across graph theory and its applications.

In 2010, Leonard Soicher introduced a new bound designed for the study of edge-regular graphs [2], which he termed the Clique Adjacency Polynomial (CAP). This bound has since played a significant role in the analysis of cliques in both edge-regular and strongly regular graphs, with further developments by Soicher [3], and Greaves & Soicher [4]. Greaves and Soicher showed that the CAP improves upon the Delsarte bound for “infinitely many feasible parameter tuples for strongly regular graphs" [4]. In this paper, we investigate how the CAP may be extended beyond edge-regular graphs to provide bounds on the clique numbers of general graphs. For a clique \(S\) of a possibly non-regular and non-edge-regular graph \(\Gamma\), define averages \(\langle k\rangle_S:=\frac{1}{|S|}\sum_{u\in S}\deg_\Gamma(u)\) and \(\langle\lambda\rangle_S:=\binom{|S|}{2}^{-1} \sum_{\{u,w\}\in\binom{S}{2}}|\Gamma(u)\cap\Gamma(w)|\).

After outlining the effective application of the generalised CAP bound, we present several illustrative examples in which the bound from 1 improves upon both the Delsarte linear programming bound and the Hoffman bound. In addition, we prove (9 and 10) that the CAP bound surpasses the Delsarte bound for two infinite families of graphs, \(\Gamma_{q^+}\) and \(\Gamma_{q^-}\), arising from conics in Desarguesian projective planes. Finally, we give two infinite families of strictly edge-regular graphs for which the CAP improves upon the Delsarte bound. We also exhibit an infinite family of regular graphs where the generalised CAP improves on the Hoffman bound, as well as an infinite family of graphs for which it improves on the Haemers bound (11 and 12).

2 Background↩︎

2.1 Delsarte’s clique bounds↩︎

An association scheme \(\mathcal{A} = (V, \mathcal{R})\) can be represented as a colouring of \(K_{|V|}\), where \(i\)-coloured edges correspond to vertices related by \(R_i \in \mathcal{R}\). For \(X \subseteq \mathcal{R}\), we define the regular graph \(\Gamma_X\) as the graph on \(V\) arising from the union of \(X\). In his 1973 thesis [1], Delsarte provides a novel way to bound the clique number of an association scheme graph \(\Gamma_X\). Given an \(n\)-class association scheme \(\mathcal{A} =(V, \mathcal{R})\), consider a non-empty subset \(S \subseteq V\). Delsarte defines the inner distribution vector \(a := (a_0,a_1,\dots, a_n)\) of \(S\) where: \[a_i = \frac{|(S \times S) \cap R_i|}{|S|},\] for \(R_i \in \mathcal{R}\). By considering the inner distribution vector with respect to a maximal choice of \(X \subseteq \mathcal{R}\), ² Delsarte produces the following linear program. \[\begin{align} \mathrm{\small maximise: } & \sum_{i=0}^{n} a_i, \\ \mathrm{\small subject to: } & (a Q)_j \geqslant 0 \textrm{ for all entries } j, \\ & a_0 = 1, \\ & a_i \geqslant 0 \textrm{ for } R_i \in X,\\ & a_i = 0 \textrm{ for } R_i \notin X. \end{align}\] Here, \(Q\) is the second eigenmatrix of the relevant association scheme. The objective value of the linear program DELSARTE provides an upper bound on \(\omega(\Gamma_X)\), which is referred to as the Delsarte LP bound. Delsarte also observed the following:

The displayed inequality in Theorem 2 is referred to as the Delsarte bound.

2.2 The Hoffman bound↩︎

When considering a regular graph \(\Gamma\) which does not arise from an association scheme, the Delsarte bound does not necessarily hold. For this circumstance we could instead apply the Hoffman bound – a generalisation of the Delsarte bound to arbitrary regular graphs. Hoffman never formally published his bound, however an outline of its context can be found in Haemers’ 2021 paper [5]. Traditionally, the Hoffman bound is given in terms of the independence number, however we consider it in the following form.

2.3 The Haemers bound↩︎

Similarly, when considering a non-regular graph \(\Gamma\), the Hoffman bound does not necessarily hold. The Haemers bound is a generalisation of the Hoffman bound to all graphs.

2.4 The Clique Adjacency Polynomial↩︎

Soicher first realised the CAP as a specific case of the block intersection polynomial (BIP) [2]. We will introduce the CAP in the same way as Soicher does, introducing relevant concepts in the derivation of the BIP – a polynomial intended for analysis of block-design structures. For a graph \(\Gamma\), and \(S, T, W \subseteq V(\Gamma)\) we let \[n_i (\Gamma, S, W ) := \left|\{u \in W : \left| \Gamma(u) \cap S\right|=i\}\right|,\] and call it the \(i\)-th intersection number. The quantity \(n_i (\Gamma, S, W )\) counts the number of vertices in \(W\) such that \(\left|\Gamma(u) \cap S\right| = i\). We also define \[\lambda_T (\Gamma, W) := |\{u \in W: T \subseteq \Gamma(u)\}|.\] Here, \(\lambda_T(\Gamma, W)\) counts the number of vertices in \(W\) adjacent to all vertices in \(T\). Let \(s := |S|\). For \(0 \leqslant j \leqslant s\), define \[\lambda_j (\Gamma, S, W) := \binom{s}{j}^{-1} \sum_{T \subseteq S, |T|=j}\lambda_T (\Gamma, W).\] The quantity \(\lambda_j (\Gamma, S, W)\) is the average \(\lambda_T (\Gamma, W)\) across all \(j\)-sized subsets \(T\) of \(S\).

Consider a strongly regular graph \(\Gamma\) with parameters \((v,k,\lambda, \mu)\). For \(j=2\), the value \(\lambda_T(\Gamma, W)\) is not necessarily constant for a given \(S\) because there are two potential \(j\)-sized subsets to consider – adjacent and non-adjacent vertices ³. However, notice if \(S\) corresponds to a clique of \(\Gamma\), then the value \(\lambda_T(\Gamma, W)\) for \(j=2\) is indeed constant because there are no non-adjacent vertices in \(S\). In particular, for an \(s\)-clique we have that \(\lambda_T(\Gamma, W) = \lambda-(s-2)\) for all \(2\)-subsets. We provide all the \(\lambda_j(\Gamma, S, W)\) values for \(S\) an \(s\)-clique and \(W = V(\Gamma) \setminus S\) in Table 1.

Since there is no non-edge valency requirement \(\mu\) in Table 1, these values also hold for edge-regular graphs. We can also link \(n_i (\Gamma, S, W )\) to \(\lambda_j (\Gamma, S, W)\) through a counting argument explored by Soicher.

Now, we introduce Soicher’s BIP. For \(z\) a non-negative integer, define the polynomial \[P(x,z) := x(x -1) \cdots (x-z + 1),\] and for real number sequences \([m_0, \dots ,m_s]\), \([\lambda_0, \dots , \lambda_t ]\), with \(t \leqslant s\), Soicher defines the block intersection polynomial \[\label{BIP1} B(x, [m_0, \dots ,m_s], [\lambda_0, \dots , \lambda_t ]) := \sum^t_{j=0}\binom{t}{j} P(-x, t - j) \left[P(s, j)\lambda_j - \sum^s_{i=j}P(i, j)m_i\right].\tag{1}\]

Using the equation from Theorem 5 and (1 ) we can rearrange the BIP into a useful form.

Furthermore for a BIP of this form, Soicher provides the following:

The following is an immediate consequence of Soicher’s block-intersection polynomial theorem applied with \(t=2\) and \(m_i=0\) for all \(i\).

We can use the contrapositive of 7 to consider when cliques of a certain size cannot exist. For a graph \(\Gamma\), if we can represent \([\lambda_0, \lambda_1, \lambda_2]\) in terms of the size of a potential clique \(s\), we can simply check for the first \(s\) when \(B(x, [0^{s+1}], [\lambda_0, \lambda_1, \lambda_2]) < 0\) and produce an upper bound on \(\omega(\Gamma)\).

Soicher naturally applied 7 to the existence of \(s\)-cliques in edge-regular graphs for which, as we have seen in Table 1, \(\lambda_j\) values are constants in terms of \(s\) and graph parameters \((v,k,\lambda)\). He called this polynomial the CAP, and initially presents it in the form \[\mathrm{CA}_\Gamma(x,s) := B(x, [0^{s+1}], [\lambda_0,\lambda_1,\lambda_2]), \label{CAP}\tag{2}\] where \(\Gamma\) is a \((v,k,\lambda)\) edge-regular graph, \(S \subseteq V(\Gamma)\) which resembles a potential clique of size \(s\geqslant 2\), \(W = V(\Gamma) \setminus S\) and \(\lambda_j := \lambda_j(\Gamma,S,W)\). Expanding this by using (1 ), we see that \[\mathrm{CA}_\Gamma(x,s) = x(x+1)\lambda_0 -2x s \lambda_1+s(s-1)\lambda_2. \label{CAP2}\tag{3}\]

Using Table 1 we can fill in the values of \(\lambda_j\) to obtain the final form of Soicher’s CAP, which is how we, and Soicher in his later papers [3], will define it. Let \(\Gamma\) be an edge-regular graph, with parameters \((v,k, \lambda)\). The CAP is presented as: \[\label{CAP1} \mathrm{CA}_\Gamma(x,s) := x(x+1)(v-s) -2x s (k-s+1)+s(s-1)(\lambda -s+2).\tag{4}\] Thus, if this quadratic is negative for some integer \(x\), then no \(s\)-clique exists.

3 Generalising Soicher’s result to all graphs and further discussion↩︎

Soicher’s form of CAP hinges on 5, however this identity, as proven by Soicher, holds for all types of graphs, not only strictly edge-regular ones. Consider the CAP in the form of (2 ). Instead of naturally taking \(\Gamma\) to be edge-regular as Soicher did, we drop this requirement. To obtain a final formula for the generalised CAP we must now evaluate the \(\lambda_j\) coefficients generally, where \(S\) corresponds to a potential clique in any graph. We present this in Table 2 where \(\langle k\rangle_S\) is the average degree of the vertices in \(S\), and \(\langle\lambda\rangle_S\) is the average number of common neighbours in \(\Gamma\) over unordered pairs of vertices in \(S\). These expressions hold under the assumption that \(S\) induces a clique, so that each vertex in \(S\) has exactly \(s-1\) neighbours within \(S\).

Note in the case of an edge-regular graph \(\Gamma\), (?? ) is equivalent to the form of (4 ).

For a potential \(s\)-clique \(S\), the constants \(\langle k \rangle_S\) and \(\langle \lambda \rangle_S\) could take on a range of feasible values for a given \(s\). It helps to consider the CAP in the form presented in (4 ), but with \(k\), \(\lambda\) as new variables representing feasible \(\langle k \rangle_S\) and \(\langle \lambda \rangle_S\) respectively. So we present the generalised CAP as \(\mathrm{CA}_\Gamma(x,s,k,\lambda)\), in four input variables.

The next step is understanding how generalised \((k, \lambda)\) variables affect CAP values. To assist with further analysis we introduce a new polynomial called the Clique Existence Polynomial (CEP) denoted as \(\mathrm{CE}_\Gamma(s,k,\lambda)\) which removes the \(x\) variable from the CAP.

Strictly speaking, because of the nearest-integer correction term, \(\mathrm{CE}_\Gamma\) is a piecewise-polynomial function rather than a polynomial. We retain the name CEP to emphasise its role as the integer-existence analogue of the CAP. This polynomial is derived by rearranging the CAP into the form \(a x^2 +bx+c\). The existence of such an integer \(x\) as required for the non-existence of a clique, only relies on coefficients \(a,b\) and \(c\) themselves. Specifically, there exists an integer \(x\) such that \(f(x)<0\) if, and only if, \(b^2-4ac-a^2\left(1-\left|2\left(\frac{-b}{2a}- \left\lfloor \frac{-b}{2a} \right\rfloor\right)-1\right|\right)^2 > 0.\) ⁴

Again, considering \(\Gamma\) as the Paley graph on \(17\) vertices we can produce another plot, this time using the CEP.

See that the same information is recovered as was in 1, a clique of size \(4\), cannot exist in \(\Gamma\). Now we can conveniently plot over \(s\), instead of producing multiple plots over \(x\) for a given \(s\). The CEP is particularly useful in computation, and can be used in conjunction with the CAP to analyse the behaviour of the \(k\) and \(\lambda\) variables. This leads to the following lemma

While part (1) of 2 is clear from the definition of the CAP in the form of (4 ), the proof of part (2) is less intuitive. First, consider an arbitrary quadratic \(f(x) = ax^2 + bx + c\), with \(a > 0\) and \(b \leqslant a\). The general form of the CEP is given as \(b^2-4ac-a^2\left(1-\left|2\left(\frac{-b}{2a}- \left\lfloor \frac{-b}{2a} \right\rfloor\right)-1\right|\right)^2\). Since \(k\) only affects the \(b\) value in the CEP, we need to consider how \(b^2-a^2\left(1-\left|2\left(\frac{-b}{2a}- \left\lfloor \frac{-b}{2a} \right\rfloor\right)-1\right|\right)^2\) behaves as \(b\) changes. Since \(b \leqslant a\), we can rewrite this as \(b^2 - (a - |m - a|)^2\), where \(m = b \bmod 2a\). Given a fixed \(a\), we can consider this as a piecewise function in terms of \(b\): \[f(b)= \begin{cases} b^2 - m^2 & \textrm{if } 0 \leqslant m \leqslant a, \\ b^2 - (2a - m)^2 & \textrm{if } a < m < 2a. \end{cases}\] Since \(b \leqslant a\), it means that \(m = b + 2na\) for some \(n \in \mathbb{N} \cup \{0\}\). We can rewrite the piecewise cases by substituting \(m = b + 2na\) and simplifying: \[f(b)= \begin{cases} -4nab-4na^2 & \textrm{if } 0 \leqslant b + 2na \leqslant a, \\ 4(1-n)ab +4(1-n)a^2 & \textrm{if } a < b + 2na < 2a. \end{cases}\] Differentiating by \(b\) gives: \[f'(b)= \begin{cases} -4na & \textrm{if } 0 \leqslant b + 2na \leqslant a, \\ 4(1-n)a & \textrm{if } a < b + 2na < 2a. \end{cases}\] We can see that for all relevant values of \(n\) which constitute \(b \leqslant a\), we have \(f(b)\) monotonically non-increasing.⁵ This means that the CEP is monotonically non-increasing for \(v - (3 + 2 k) s + 2 s^2 \leqslant v-s\), which can be rearranged to \(k \geqslant s-1\). 2 leads to a useful corollary.

This is best understood visually, so we refer to 3. Recall that we associate the variable \(k\) with feasible values of \(\langle k \rangle_S\), and the variable \(\lambda\) with feasible values of \(\langle \lambda \rangle_S\). The blue shaded region represents all feasible pairs \((k,\lambda)\) corresponding to a potential \(s\)-clique in a graph \(\Gamma\).

If there exists a point \((k_s^*, \lambda_s^*)\) in the red shaded region such that \(\mathrm{CE}_\Gamma(s, k_s^*, \lambda_s^*) > 0\), then by 2, it follows that \(\mathrm{CE}_\Gamma(s, k, \lambda) > 0\) for all \((k,\lambda)\) in the black shaded region.

4 Bounding feasible regions for \((k,\lambda)\)↩︎

In this section we will outline methods for bounding \((k,\lambda)\) in different types of graphs, along with some sporadic examples of how to utilise these methods to produce a bound with the CAP.

4.1 Methods for bounding \(\lambda\) in association scheme graphs↩︎

Since degree valency of graphs of association scheme is always constant, we have a natural bound \(k_s^*\) on variable \(k\) for all \(s\), however, we are required to explore ways to produce an upper bound \(\lambda^*_s\) on the variable \(\lambda\) (average edge-degree of a potential \(s\)-clique). The main tool we use to do this will be Delsarte’s inner distribution vector.

Consider \(S\) such that \(|S|=s\), we can calculate its inner distribution vector \(a\) in some \(\Gamma_X\). We have the property \[\begin{align} s a_i = |(S \times S) \cap R_i|, \label{innerdid} \end{align}\tag{5}\] for \(R_i \in \mathcal{R}\).

For a non-trivial relation \(R_i\), the right-hand side of (5 ) counts each edge in \(S\) that belongs to \(R_i\) twice, once for each ordering of the endpoints. Let us denote \(\hat{a}_i\) as the number of edges in \(S\) that belong to the relation \(R_i\). We have the following relationship: \[\begin{align} \frac{s}{2} a_i = \hat{a}_i. \label{edgeconfig} \end{align}\tag{6}\] We can rescale a given inner distribution vector using this relationship. This allows us to draw some information regarding the configuration of the edges the inner distribution vector represents. We will denote this scaled vector \(\hat{a}\). Now also consider an edge-degree vector \(\mathcal{D}\) for \(\Gamma_X\), such that \(\mathcal{D} := (0, \lambda_1, \dots, \lambda_n)\) where \(\lambda_i\) is the edge-degree of an edge from \(R_i\).⁶

The edge-degree vector, along with the scaled inner distribution vector, allows us to observe the following:

3 provides a direct method to compute the average edge-degree of an \(s\)-clique induced by \(S\) from its inner distribution vector and intersection numbers of the scheme. Recall, an \(s\)-clique has \(\frac{s(s-1)}{2}\) edges, so we must have \[\langle \lambda \rangle_S = \frac{2 \hat{a}^\top \mathcal{D}}{s(s-1)}.\]

Using the framework from Delsarte’s linear program, a new integer linear program can be created, based on the feasibility of the scaled inner distribution vector of a potential \(s\)-clique \(S\) to obtain an upper bound \(\lambda^*_s\) on its average edge-degree \(\lambda\). If the integrality constraints are relaxed to \(\hat{a}_i\geqslant 0\), one obtains a linear programming relaxation. \[\begin{align} \mathrm{\small maximise: } & \frac{2 \hat{a}^\top \mathcal{D}}{s(s-1)}, \\ \mathrm{\small subject to: } & (\hat{a} Q)_j \geqslant 0 \textrm{ for all entries } j, \\ & \hat{a}_0 = s/2, \\ & \hat{a}_i = 0 \textrm{ for } R_i \notin X, \\ & \sum_{i=1}^n \hat{a}_i = \frac{s(s-1)}{2}, \\ & \hat{a}_i \in \mathbb{N} \textrm{ for all } i \geqslant 1. \end{align}\]

Aside from producing an upper bound on \(\lambda\), note that what was the objective of Delsarte’s program has now become a constraint. So, similar to Delsarte’s LP bound, this linear program can produce a bound on \(\omega(\Gamma_X)\), however in a slightly different way. Evidently we have:

4.2 Bounding \(\lambda\)↩︎

Here we provide some general methods to produce bounds for the variable \(\lambda\) in graphs that do not arise from association schemes. For a graph \(\Gamma\) we can define the edge-degree sequence of all its edges \(\mathcal{D}_\Gamma := \lambda_1, \lambda_2, \dots \lambda_m\) where for \(i<j\), \(\lambda_i \leqslant\lambda_j\) and \(m = |E(\Gamma)|\). Since there is no underlying structure on the edges, we must index each edge individually. We call the interval \(\left[\lambda_1, \lambda_m\right]\) the trivial bounds for \(\lambda\). These can be refined by noting that an \(s\)-clique contains \(\binom{s}{2}\) edges. Therefore,

\[\lambda \in \left[ \frac{\sum_{i=1}^{\binom{s}{2}} \lambda_i}{\binom{s}{2}}, \; \frac{\sum_{i=m-\binom{s}{2}+1}^{m} \lambda_i}{\binom{s}{2}} \right].\] These bounds are straightforward to obtain, and in some cases they can be sharpened. For a given vertex \(u \in V(\Gamma)\) of degree at least \(s-1\), we define an \(s\)-restricted edge-degree sequence \(\mathcal{D}_s(u)\). This is the increasing sequence \(\lambda_{1_u}, \dots, \lambda_{(s-1)_u}\) of the \((s-1)\) largest edge-degrees among edges incident with \(u\). Such a sequence can be computed for every \(u \in V(\Gamma)\).

From these, we construct a descending nested \(s\)-restricted edge-degree sequence using all the vertices of \(\Gamma\): \[\mathcal{D}_s(u_1), \mathcal{D}_s(u_2), \dots, \mathcal{D}_s(u_v),\] where the vertices are ordered so that for \(a < b\), \[\sum \mathcal{D}_s(u_a) \geqslant\sum \mathcal{D}_s(u_b).\]

Sharpness of bounds for regular graphs often relies on bounding \(\lambda\) as low as possible for each \(s\). This task can be computationally heavy, however it is faster than searching for the largest clique as vertex number increases. The methods above are particularly effective at producing sporadic examples where the generalised CAP improves on the Hoffman bound, or for single-graph analysis.

4.3 Bounding \(k\)↩︎

Similar to the edge-degree sequence, we can consider a degree sequence to bound \(k\). For a graph \(\Gamma\), the degree sequence \(\mathcal{K}_\Gamma := k_1, k_2, \dots k_v\) where \(k_i = |\Gamma(u_i)|\) for \(u_i \in V(\Gamma)\). The sequence is given in ascending order such that for \(i<j\), \(k_i \leqslant k_j\). For a potential \(s\)-clique, only the average of the largest \(s\) elements in \(\mathcal{K}_\Gamma\) needs to be considered: \[k \in \left[\frac{\sum_{i=1}^s k_i}{s}, \frac{\sum_{i=v-s+1}^v k_i}{s}\right].\] In this case \(\left[\delta_\Gamma, \Delta_\Gamma\right]\) is the trivial bounds for \(k\). Consistent with our earlier findings, these processes are useful at producing sporadic results for when the CAP bound outperforms the Haemers bound.

5 Infinite families↩︎

5.1 Edge-regular↩︎

First, consider some infinite family of \((v,k,\lambda)\) edge-regular graphs \(\mathcal{U}\), such that there is an upper bound \(N\) on \(\lambda\) for all \(\Gamma \in \mathcal{U}\). In this instance, we see that \[\mathrm{CA}_\Gamma(0,N+3)=(N+3)(N+2)(\lambda-N-1)\leqslant-(N+3)(N+2)< 0,\] for all \(\Gamma \in \mathcal{U}\). We get the following lemma.

While this bound is trivial (and almost never sharp for the CAP), for some families of graphs, spectral bounds cannot always reproduce these trivialities. We will consider two infinite families of edge-regular graphs with this property in this section.

For odd \(q\), consider the group action of \(\textrm{PGL}(2, q)\), as a subgroup of \(\textrm{PGL}(3, q)\), on the secant lines of a non-degenerate conic \(\mathcal{O}\) in \(\textrm{PG}(2,q)\). This action is generously transitive. We define \(\textrm{PGL}(2,q)^+\) as the Schurian association scheme generated by this action, where relations are given by its orbital graphs. One of the orbital graphs in particular we focus on, we refer to as \(\Gamma_{q^+}\), where \(\{a,b\} \in E(\Gamma_{q^+})\) if and only if \(a\) and \(b\) are polar conjugates with respect to the polarity induced by \(\mathcal{O}\). Since \(\Gamma_{q^+}\) is a graph of a single relation in an association scheme, it must be edge-regular.

Evidently, we can also see that \(\Gamma_{q^+}\) is isomorphic to an induced subgraph \(\mathcal{H}\) of the Erdős–Rényi polarity graph⁷ (\(\textrm{ER}_q\)), where \(V(\mathcal{H})\) is the external points of \(\mathcal{O}\), corresponding to the secant lines under the polarity mapping with respect to \(\mathcal{O}\).

Since \(\Gamma_{q^+}\) is isomorphic to \(\mathcal{H}\), by interlacing of eigenvalues we can retrieve the following:

For a visual understanding of 3, we generated the eigenvalues of \(\Gamma_{q^+}\) for the odd prime powers from \(7\) to \(89\) using GAP. It is indeed true that these values are always greater than or equal to \(-\sqrt{q}\), however in fact, they seem generally very close to \(-\sqrt{q}\). See the plot in 5 along with the lower bound of \(-\sqrt{q}\).

First we provide the following lemma:

This provides a bound of \(\lambda = 1\) for all \(\Gamma_{q^+}\). These graphs were analysed by Parsons initially [9], and in fact we can represent \((v,k)\) of \(\Gamma_{q^+}\), all in terms of \(q\). Specifically, \(v = \frac{q(q+1)}{2}\) and \(k = \frac{q-1}{2}\).

For odd \(q\), a similar result can be replicated when considering, the group action of \(\textrm{PGL}(2, q)\), as a subgroup of \(\textrm{PGL}(3, q)\), on the external lines of a non-degenerate conic \(\mathcal{O}\) in \(\textrm{PG}(2,q)\).

Again, one orbital graph, which we denote as \(\Gamma_{q^-}\), contains an edge between two external lines if and only if they are polar conjugate. Similarly to \(\Gamma_{q^+}\), we have that \(\Gamma_{q^-}\) is isomorphic to an induced subgraph \(\mathcal{N}\) of \(\textrm{ER}_q\), where \(V(\mathcal{N})\) is the set of non-external, non-absolute points of \(\mathcal{O}\), corresponding to the external lines under the polarity mapping with respect to \(\mathcal{O}\). For \(\Gamma_{q^-}\) we have \(v = \frac{q(q-1)}{2}\) and \(k= \frac{q+1}{2}\).

5.2 Regular graphs↩︎

Now observe what happens as \(n\) approaches infinity.

We can see that the Hoffman bound performs poorly for graphs of this nature, and produces a redundant solution. The largest possible size of a clique of \(\Gamma \square C_n\) is at most \(k+1\), for any \(\Gamma\). We can show that the generalised CAP is much more robust when bounding these types of graphs. This leads to:

5.3 Non-regular↩︎

Assuming that a graph \(\Gamma\) contains a universal vertex, we can evaluate the Haemers bound for \(\Gamma\). We get the following: \[\begin{align} \omega(\Gamma) \leqslant\frac{-v \gamma'_1\gamma'_{v}}{(v-(v-1)-1)^2-\gamma'_1\gamma'_{v}} = v. \end{align}\] The Haemers bound does not deal well with these types of graphs. The generalised CAP is more robust.

References↩︎

---

1. These generalisations are referred to as the Hoffman bound and the Haemers bound, respectively.↩︎

2. By convention, \(a_0=1\) always, regardless of whether \(R_0 \in X\).↩︎

3. That is, \(\lambda_T(\Gamma, W) = \lambda-(s-2)\) or \(\lambda_T(\Gamma, W) = \mu-(s-2)\)↩︎

4. Note that \(a = v-s \geqslant 0\), since a clique size is never bigger than the number of vertices in a graph. In the case \(a=0\), the CAP reduces to a linear function, which can be checked directly.↩︎

5. Note when \(n=0\), we have that \(b \leqslant a\) only holds when \(f'(b) = 0\), not for when \(f'(b) = 4a\), since in this case we have \(b>a\).↩︎

6. The edge-degree for an \(i\)-coloured edge in \(\Gamma_X\) can be calculated using the intersection parameters of the scheme↩︎

7. known to have minimum eigenvalue of \(-\sqrt{q}\) [8]↩︎