5
$\begingroup$

Let $\theta(G)$ denote the Shannon zero error capacity of graph $G$ and $\vartheta(G)$ be the Lovász upper bound for $\theta(G)$.

Let $C_{2n+1}$ denote the cycle graph with $2n+1$ nodes.

We know the following two things:

  1. $$\theta(C_{2n+1})\leq \vartheta(C_{2n+1})=\frac{n\cdot \cos(\frac\pi n)}{1+\cos(\frac\pi n)}.$$

  2. $$\theta(C_5)=\vartheta(C_5)=\sqrt{5}.$$

Let $\mathcal{Circ}_n$ be the collection of all circulant graphs on $n$ vertices. Naturally $C_n\in\mathcal{Circ}_n$.

Other than for $C_n$ is there any other class of $G\in\mathcal{Circ}_n$ for which an exact expression for $\vartheta(G)$ is known?

Improve this question
$\endgroup$
6
  • $\begingroup$ There are some further results, in particular for circulant graphs of degree four, in this paper: link.springer.com/chapter/10.1007/3-540-46521-9_24 $\endgroup$
    – Tobias Fritz
    Commented Apr 26, 2017 at 7:21
  • 2
    $\begingroup$ Powers of cycle graphs: arxiv.org/abs/1103.0444. Also, note that for vertex transitive graphs, which include circulants, the product of Loavsz theta for the graph and its complement is equal to the number of vertices, so knowing the value for the graph determines the value for the complement. Also, if the graph is vertex and edge transitive, then Lovasz theta of the complement is equal to 1 - (\lambda_max/\lambda_min) where \lambda_max is the max eigenvalue of the adjacency matrix, and \lambda_min is the min eigenvalue. $\endgroup$
    – David Roberson
    Commented Apr 26, 2017 at 17:06
  • $\begingroup$ @DavidE.Roberson can you please give the references for "Also, if the graph is vertex and edge transitive, then Lovasz theta of the complement is equal to 1 - (\lambda_max/\lambda_min) where \lambda_max is the max eigenvalue of the adjacency matrix, and \lambda_min is the min eigenvalue. "? $\endgroup$
    – Turbo
    Commented Apr 26, 2017 at 20:25
  • 2
    $\begingroup$ @Turbo This is more or less Theorem 9 of Lovasz' original paper: cs.elte.hu/~lovasz/scans/theta.pdf. You can weaken the assumption to being 1-walk-regular, and I think this was first proven here: arxiv.org/pdf/1305.5545.pdf. Note that that paper refers to 1-walk-regular graphs as 1-homogeneous graphs. $\endgroup$
    – David Roberson
    Commented Apr 26, 2017 at 21:43
  • 1
    $\begingroup$ @Turbo I don't honestly know, I haven't thought very hard about it. As Dima pointed out in your earlier post, for a circulant graph (or any graph that is the union of classes in a symmetric association scheme) the Lovasz theta function is equal to the value of a linear program. This linear program will be closely related to the eigenvalues of the graph, but I would be somewhat surprised if there were a closed form expression for this value for circulants, though it may be possible. You could check your expression against the powers of the cycle graphs from that first link I posted. $\endgroup$
    – David Roberson
    Commented Apr 26, 2017 at 22:03

1 Answer 1

Reset to default
1
$\begingroup$

$\vartheta(G_p)=\sqrt{p}$ if $G_p$ is the Paley graph of order $p$

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ By what is written in the comments, the following more general statement is true: if $G$ is vertex-transitive and self-complementary (as the Paley graphs are), then $\theta(G)=\sqrt n$ where $n$ is the number of vertices. $\endgroup$
    – M. Winter
    Commented Sep 10, 2020 at 22:48
  • 3
    $\begingroup$ Can you add a reference or details about why this is true? $\endgroup$
    – Amir Sagiv
    Commented Sep 11, 2020 at 0:01
  • 2
    $\begingroup$ @AmirSagiv: M. Winter's comment is Theorem 12 of Lovasz's 1979 paper where Lovasz introduced the Theta function. $\endgroup$
    – Eric Naslund
    Commented Jul 22 at 22:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .