8
$\begingroup$

The clique-coclique bound is said to hold for a simple graph $G$ on $n$ vertices if $\lvert \omega(G) \rvert \lvert \alpha(G) \lvert \leq n$, letting $\omega(G)$ and $\alpha(G)$ denote its clique and coclique (independent set) numbers respectively.

It is known, in particular, that the clique-coclique bound holds for all vertex-transitive graphs and distance-regular graphs - two families of walk-regular graphs.

The clique-coclique also appears to hold for all of the examples of walk-regular graphs that I know of that are neither vertex-transitive nor distance-regular. It is also apparent that the clique-coclique bound holds for some other families of walk-regular graphs, namely semi-symmetric graphs.

Could it be possible that the clique-coclique bound actually holds for all (connected) walk-regular graphs?

By informal reasoning in head, it feels plausible to me that this could be the case? I wonder what would might be a good approach to take to try to prove or disprove this?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ I took your second example and looked at the strong product of it with itself. This is walk-regular with 144 vertices, but with independence number 10 and clique number 16, so it does not satisfy the clique-coclique bound. $\endgroup$ Jan 3 '18 at 15:52
  • 1
    $\begingroup$ No problem. I had wondered the same thing myself, and the question got me thinking about it again and the examples on your webpage led to a counterexample. By the way, I noticed you are at UWaterloo, that is where I did my PhD. Have you taken the Algebraic Graph Theory course yet? From your webpage it seems you are interested in that sort of stuff. $\endgroup$ Jan 13 '18 at 8:59
4
$\begingroup$

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.)

18-vertex walk-regular graph

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.

$\endgroup$
1
  • $\begingroup$ Nice example Gordon! $\endgroup$ Mar 5 '19 at 9:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.