Does the clique-coclique bound hold for all walk-regular graphs?

EDIT: The answer is no, see comment below.

In every case I know of, the clique-coclique bound can be proven for a class of graphs by proving the stronger fact that $\vartheta(G)\bar{\vartheta}(G) \le |V(G)|$ for all $G$ in that class, where $\vartheta(G)$ is the Lovasz theta number of $G$ and $\bar{\vartheta}(G) := \vartheta(\bar{G})$ is the Lovasz theta number of the complement of $G$. It is well known that $\alpha(G) \le \vartheta(G) \le \chi(\bar{G})$, i.e., that $\omega(G) \le \bar{\vartheta}(G) \le \chi(G)$, for all graphs $G$. Thus if $\vartheta(G)\bar{\vartheta}(G) \le |V(G)|$, then $\alpha(G)\omega(G) \le |V(G)|$ follows immediately.

In general, $\vartheta(G)\bar{\vartheta}(G) \ge |V(G)|$ holds for any graph $G$, but in some cases the other inequality holds and so you get equality. So if you could prove that $\vartheta(G)\bar{\vartheta}(G) = |V(G)|$ for any walk-regular graph $G$, then you are done. Unfortunately, we will see that this turns out not to be the case. However, we can prove it for a related, but smaller, class of graphs.

First, it is known that $\vartheta(G)\bar{\vartheta}(G) = |V(G)|$ for 1-walk-regular graphs $G$ (actually I do not know if this is written anywhere in the literature, but it is true). A graph is 1-walk-regular if it is walk-regular and additionally the number of walks of length $\ell$ starting from one end of an edge and ending at the other does not depend on the edge. In terms of the adjacency matrix $A$, this says that $A \circ A^\ell$ is a constant times $A$ for all $\ell \in \mathbb{N}$, where $\circ$ denotes the Schur (entrywise) product (the walk-regularity conidition is of course equivalent to $I \circ A^\ell$ being a constant times $I$). So for walk-regular graphs that are additionally 1-walk-regular (or their complement is 1-walk-regular), the clique-coclique bound holds. Unfortunately, there are walk-regular graphs that are not 1-walk-regular and their complements are not 1-walk-regular, so this does not prove what you want. But let's take a closer look at why it works for 1-walk-regular graphs

The Lovasz theta number of a graph can be defined by the following semidefinite program:

\begin{equation}\label{eq:dual} \begin{array}{lc} \vartheta(G) \ = & \begin{array}[t]{ll} \max & \text{sum}(B) \tag{D} \\ \text{s.t.} & B_{ij} = 0 \text{ for } i \sim j \\ & \text{Tr}(B) = 1 \\ & B \succeq 0 \end{array} \end{array} \end{equation} where $\text{sum}(B)$ denotes the sum of the entries of $B$, which is also equal to $\text{Tr}(BJ)$ where $J$ is the all ones matrix. One can also define Lovasz theta (of the complement) of $G$ by the following semidefinite program:

\begin{equation}\label{eq:primal} \begin{array}{lc} \bar{\vartheta}(G)= & \begin{array}[t]{ll} \min & t \tag{P}\\ \text{s.t.} & M_{ii} = t-1 \text{ for } i \in V(G) \\ & M_{ij} = -1 \text{ for } i \sim j \\ & M \succeq 0 \end{array} \end{array} \end{equation}

In order to prove the inequality $\vartheta(G)\bar{\vartheta}(G) \ge |V(G)|$ for any graph $G$, the usual proof takes an optimal solution $M$ to (\ref{eq:primal}), and uses the matrix $(1/nt)(M+J)$ (where $t = \bar{\vartheta}(G)$ and $n = |V(G)|$) as a feasible solution to (\ref{eq:dual}). This feasible solution will have objective value $$\frac{1}{nt}\text{Tr}((M+J)J) = \frac{1}{nt}(\text{Tr}(MJ) + \text{Tr}(J^2)) \ge \frac{1}{nt}\text{Tr}(J^2) = n/t$$ since $\text{Tr}(MJ) \ge 0$ because $M,J \succeq 0$. To prove $\vartheta(G)\bar{\vartheta}(G) \le |V(G)|$ for certain classes of graphs, the usual proof takes an optimal solution $B$ to (\ref{eq:dual}) that has constant diagonal and a constant row sum and uses $(n^2/s)B - J$ where $s = \vartheta(G)$ as a feasible solution to (\ref{eq:primal}). This will have objective value equal to $n/s$, thus proving the desired inequality. Though the assumptions on the graph $G$ may vary, I believe that the existence of an optimal solution $B$ to (\ref{eq:dual}) with constant diagonal and constant row sum is the essential ingredient. In fact, you can show that $\vartheta(G)\bar{\vartheta}(G) = |V(G)|$ if and only if such an optimal solution to (\ref{eq:dual}) exists (I don't know if this is in the literature). You can also show that the $i^\text{th}$ row sum is equal to $\vartheta(G)$ times the $i^\text{th}$ diagonal entry for any optimal solution to (\ref{eq:dual}), and so it is necessary and sufficient to find an optimal solution with constant diagonal.

For example, if $G$ is vertex transitive, then you can easily find such an optimal solution by "symmetrizing" any optimal solution using the automorphisms of $G$. But there is something more general you can do, and it involves coherent algebras.

A coherent algebra is a subalgebra of the $n \times n$ complex matrices that contains the identity and all ones matrices, is closed under conjugate transposition, and is closed under Schur product. It is easy to see that the intersection of two coherent algebras is a coherent algebra, and this allows one to define the coherent algebra of a graph $G$ as the smallest coherent algebra containing the adjacency matrix of $G$. Based on your personal webpage, you already know what these are, so I won't elaborate too much. If we consider the coherent algebra $\mathcal{C}$ of a graph $G$ as a subspace of the vector space of $n \times n$ matrices, we can construct a linear map $\Phi$ that is the orthogonal projection onto $\mathcal{C}$. It turns out that this map has some very nice properties. In particular, if $M$ is positive semidefinite, then so is $\Phi(M)$. Also, $\Phi$ is trace-preserving, maps the identity to itself, and it is "doubly-stochastic" in the sense that it maps (entrywise) nonnegative matrices to nonnegative matrices, preserves the sum of the entries of a matrix, and maps the all ones matrix to itself. These (and a few other) properties show that if $B$ is a feasible solution to (\ref{eq:dual}), then $\Phi(B)$ is a feasible solution with the same objective value (and similarly for (\ref{eq:primal})). Of course, $\Phi(B)$ is contained in the coherent algebra of $G$, and is thus in the span of the unique basis of $01$-matrices of $\mathcal{C}$ (basically, the map $\Phi$ just smooths a matrix out over the entries of each of these 01-matrices). Thus, if $\mathcal{C}$ is homogeneous (meaning every matrix in $\mathcal{C}$ has constant diagonal), then there is always an optimal solution to (\ref{eq:dual}) with constant diagonal and so $\vartheta(G)\bar{\vartheta}(G) = |V(G)|$, and the clique-coclique bound holds. As far as I know, this includes almost all classes of graphs for which it is known that the clique-coclique bound holds. However, this does not suffice for the proof of the case of 1-walk-regular graphs, since their coherent algebras may not be homogeneous (for instance the Hoffman graph).

So how do we prove it for 1-walk-regular graphs? Well, you can show that if $G$ is the complement of a 1-walk-regular graph, then $A - \tau I$ is (up to a scalar) an optimal solution for (\ref{eq:dual}) where $\tau$ is the minimum eigenvalue of $G$ (see https://arxiv.org/abs/1305.5545 for a proof of this, but there 1-walk-regular is called 1-homogeneous). The matrix $A - \tau I$ obviously has constant diagonal and so we are done. But can we capture what is happening with 1-walk-regular graphs by a more general argument? Yes.

Define the partially coherent algebra of a graph $G$ to be the smallest subalgebra of the $|V(G)| \times |V(G)|$ complex matrices that contains the identity matrix, the all ones matrix, the adjacency matrix $A$ of $G$, is closed under conjugate transposition, and is closed under Schur product where one of the two factors involved is $I$ or $A$. This will necessarily be a (possibly equal) subalgebra of the coherent algebra of $G$. We can construct the map $\Phi'$ which is the orthogonal projection onto the partially coherent algebra of $G$. The map $\Phi'$ will not be quite as nice as the map $\Phi$ above, but it will still take feasible solutions to (\ref{eq:dual}) to feasible solutions to (\ref{eq:dual}) with the same objective value (and similarly for (\ref{eq:primal})). Thus, if every matrix in the partially coherent algebra of $G$ has constant diagonal, then $\vartheta(G)\bar{\vartheta}(G) = |V(G)|$. In an upcoming work by Laura Mančinska, Antonios Varvitsiotis, and myself, we show that the partially coherent algebra of a connected 1-walk-regular graph is equal to the adjacency algebra of $G$, i.e., the algebra of polynomials in its adjacency matrix. The matrices in the adjacency algebra will have constant diagonal since $G$ is necessarily walk-regular by assumption. In the case of a 1-walk-regular graph that is not connected, I think you can show that the partially coherent algebra is just the span of the adjacency algebra plus the all ones matrix, which is also the adjacency algebra of the complement. So in this case it still holds that the partially coherent algebra will only contain constant diagonal matrices, and so this shows that $\vartheta(G)\bar{\vartheta}(G) = |V(G)|$ for any 1-walk-regular graph.

Unfortunately, this doesn't work for walk-regular graphs. It is possible for the partially coherent algebra of a walk-regular graph to contain matrices that do not have constant diagonal. I suspected this was true but did not previously have a counterexample. But you do, on your webpage. In the post titled "Examples of Walk-Regular Graphs" from December 17, 2016, you give some examples of walk-regular graphs that are neither vertex transitive nor distance-regular. The first example you give has 12 vertices and has Graph6 string equal to ${\tt KU`OXC`XKpHW}$. If $A$ is its adjacency matrix, then the matrix $A\left(A \circ[A(A \circ A^2)]\right)$ is in the partially coherent algebra of this graph but does not have constant diagonal.

Of course, we could hope that there is some other way to prove that $\vartheta(G)\bar{\vartheta}(G) = |V(G)|$ for walk-regular graphs (and thus that the clique-coclique bound holds for these graphs), but this hope is crushed by your second example, with Graph6 string ${\tt KCOfeqkfJkLg}$, also having 12 vertices. This graph has $\bar{\vartheta}(G) = 4$ and $\vartheta(G) \approx 3.3431457$ according to Sage. But, the clique-coclique bound does hold for this graph since we have $\alpha(G) = 3$ and $\omega(G) = 4$.

So we don't have a counterexample to your conjecture, but if your conjecture is true, then walk-regular graphs will be the first "natural" family of graphs (that I am aware of) that satisfy the clique-coclique bound but do not satisfy $\vartheta(G)\bar{\vartheta}(G) = |V(G)|$. So I am not too optimistic that it is true.

P.S. Thanks for finding those examples of walk-regular graphs. I have wondered if $\vartheta(G)\bar{\vartheta}(G) = |V(G)|$ held for all walk-regular graphs for some time, but could find no proof. Now I know why.

This is an old thread and already answered, but in case it helps anyone, here is a smaller walk-regular graph that does not satisfy the clique/coclique bound. (It may not be the smallest.)

It has 18 vertices, and its automorphism group has two orbits on vertices (the pink and the blue in the picture).

Graph6: QGEENDpMGwpppowomEHp`FBEKMG

It has six maximum cliques of size $5$, with representative $\{0, 6, 7, 12, 13\}$ and six maximum cocliques of size $4$, with representative $\{0, 1, 9, 16\}$.

As $\alpha \times \omega = 4 \times 5 = 20 > 18$, this violates the clique-coclique condition.