5
$\begingroup$

Let $G$ be a simple connected graph $D(G)$ its distance matrix and $n_{+}(G), n_{-}(G)$ the number of positive and negative eigenvalues of $D(G)$ respectively.

We call a graph $G$ optimistic if $n_{+}(G) > n_{-}(G).$ The notion being motivated by a remark of Graham and Lovász saying that is not known if such graphs exists.

A computer search indicates that there is no optimistic graph on up to 11 vertices. Yet it can be easily seen that the Paley graphs of order $n > 13$ have this property. More generally every conference graph does and there are many other examples of optimistic graphs as well.

The question that remains is

Is there any optimistic graph of order $12$? If not is the Paley graph of order $13$ the unique smallest optimistic graph?

My computational resources are just slightly too low to tackle this by a computer program while my intellect is way out to be able to reduce the search space or construct an example by hand.

Hence I leave it here in case anyone can run a computer program or suggest some reductions on the search space.

Edit 1. The distance matrix $D = (d_{i,j})$ of a connected graph with vertex set $_1,\ldots,v_n$ is the matrix whose entries are $d_{i,j} = d(v_i,v_j)$

Edit 2. In case someone has a powerful enough machine, here is a small Sage program searching for optimistic graphs. The best way to run it is in parallel in the following way

geng -c 12 12:0 | parallel --block 100M --pipe sage findIt.sage

$\endgroup$
  • $\begingroup$ could you please include a definition of this "distance matrix" --- I'm familiar with a few notions but am not sure which one is meant here. Thanks! $\endgroup$ – Suvrit Oct 1 '13 at 13:11
  • $\begingroup$ as a followup: what is "d(x,y)"? An arbitrary metric, or is the vertex set embedded into Euclidean space? or is it the shortest path length from $x$ to $y$? $\endgroup$ – Suvrit Oct 1 '13 at 13:28
  • $\begingroup$ Couldn't find regular graph on 12 vertices for a start. $\endgroup$ – joro Oct 1 '13 at 14:09
  • $\begingroup$ @survit $d(x,y)$ is the length of the shortest x-y path. $\endgroup$ – Jernej Oct 1 '13 at 14:14
  • $\begingroup$ joro: use McKay's geng to get regular graphs on 12 vertices. $\endgroup$ – Chris Godsil Oct 1 '13 at 14:39

Your Answer

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

Browse other questions tagged or ask your own question.