User chris godsil - MathOverflow

Answer by Chris Godsil for Eigenvalues of Symmetric Tridiagonal Matrices

2013-05-23T01:17:35Z

Amongst the polynomials that can arise as characteristic polynomials of tridiagonal matrices with zero diagonal, one finds the Hermite polynomials. Schur showed that Hermite polynomials of even degree are irreducible and that their Galois groups are not solvable. Hence there can be no closed form expression for the zeros in terms of the $b_i$'s in general.

Answer by Chris Godsil for Do you set a one or two commas when using \mapsto?

2013-05-06T11:53:49Z

Halmos's advice in "How to write mathematics" is never use punctuation to separate notation.

Answer by Chris Godsil for Rigid Strongly Regular Graphs

2013-05-02T11:36:00Z

At Ted Spence's web page http://www.maths.gla.ac.uk/~es/srgraphs.php you can find all the strongly regular graphs on 25 and 26 vertices, and these include examples of asymmetric graphs. (No srg on fewer than 25 vertices is asymmetric.)

You get more examples as Latin square graphs. Take an $n\times n$ Latin square (with $n\ge 6$). Define the vertices of the graph to be the $n^2$ cells of the square, and declare two cells to be adjacent if they are in the same row, or in the same column, or have the same content. Most Latin squares will work.

You can also construct srgs on the triples of Steiner triple systems (adjacent if they overlap), and Babai proved that almost all of these are asymmetric.

Answer by Chris Godsil for Spectrum of composition of graphs( lexicographic product)

2013-04-30T01:41:00Z

If graphs $X$ and $Y$ have adjacency matrices $A$ and $B$ respectively, then the composition of $X$ around $Y$ has adjacency matrix $$ A\otimes J + I\otimes B $$

Assume $B$ is $k$-regular. Then the all-ones vector $\textbf{1}$ is an eigenvector for $B$ with eigenvalue $k$ and if $x$ is an eigenvector for $A$ with eigenvalue $\lambda$, then $x\otimes\textbf{1}$ is an eigenvector for the composition with eigenvalue $\lambda|V(Y)| +k$. If $y$ is an eigenvector for $B$ orthogonal to $\textbf{1}$ with eigenvalue $\mu$, then $x\otimes y$ is an eigenvector for the composition with eigenvalue $\mu$.

If $B$ is not regular then there is no simple expression for the spectrum; it can be shown that it is determined by the spectrum of $X$, $Y$ and the complement of $Y$.

Answer by Chris Godsil for signs of eigenvalues

2013-04-22T00:19:46Z

The eigenvalues of $C_6$ are 2, 1,$-1$ and $-2$ with respective multiplicities 1, 2, 2, 1. The eigenvalues of two disjoint copies of $K_3$ are $2$ and $-1$ with multiplicities 2 and 4. In this case the squares of the adjacency matrices have the same spectrum. As Carlo has stated, this shows that we cannot recover the eigenvalue signs of the adjacency matrix from the spectrum of its square.

Answer by Chris Godsil for A short question about the DFT matrix

2013-03-26T23:26:10Z

Call a unitary matrix flat if all its entries have the same absolute value. In operator theory these arise as a class of type-II matrices, which were used by Vaughan Jones in his work on link invariants. Currently they are also of interest in physics, because of their connection with "mutually unbiased bases". In this context they are known as generalized Hadamard matrices (which is a good enough name, but has a different meaning among design theorists).

The basic examples are Hadamard matrices and character tables of abelian groups, as noted by Mark and Steve. The class of flat unitary matrices is closed under Kronecker product, and this gives us examples which are neither Hadamard nor character tables. A survey of the subject by physicists appears as arXiv:quant-ph/0512154. (And if you search on quant-ph for articles with "Hadamard" in the title, you'll find many more papers on the subject.)

Answer by Chris Godsil for signing a strongly regular graph

2013-03-16T17:16:37Z

Suppose we have a set of unit vectors $x_1,\ldots,x_m$ in $\mathbb{R}^d$ such that (for $i=j$) either $x_i^Tx_j=0$ or $|x_i^Tx_j|=a$. The Gram matrix of these vectors can be written as $I+aS$, where $S$ is symmetric, has zero diagonal, and entries in ${0,\pm}$. So we have a signed graph. (Hi Tom.) Replacing $x_i$ by $-x_i$ for some $i$'s does not change anything of interest, we're really dealing with sets of lines.

By results of Delsarte, Goethals and Seidel "Spherical Codes and designs" we know that $m\le \binom{n+2}3$. They mention two examples where this bound is tight: $d=8$ as in your question and 2300 lines when $d=23$. It's likely that these are the only known examples where the bound is tight. I think DGS supply enough theory to show that the underlying graph will be strongly regular in this case.

DGS also derive a bound $$ m \le \frac{d(d+2)(1-a^2)}{3-(d+2)a^2}. $$ I'd expect that sets of lines meeting these bounds will give strongly regular graphs (but I could not see exactly what I needed in a quick skim and my coffee break is coming to an end).

Forgive me if you knew all this and were really fishing for more examples.

Edit: Let $H$ be an $n\times n$ Hadamard matrix and let $A$ be given by $$ A =\begin{pmatrix}0&H^T\\ H&0\end{pmatrix} $$ Then $A^2=nI$ and $A$ is a signing of the complete bipartite graph. These examples may appear a bit trivial, but there are a lot of them. More generally any antipodal distance-regular graph with diameter four (and antipodal fibres of size two) will give rise to examples. Unfortunately this will only produce three further examples, and the margin is too small to deal with these.

Edit2: The fact equality in the given bound implies that the graph on the lines is strongly regular appears as (part of) Proposition 3.12 in the paper by Calderbank, Cameron, Kantor and Seidel on Kerdock codes over $\mathbb{Z}_4$. They also prove that equality in the bound imples that the signed adjacency matrix has exactly to eigenvalues.

Answer by Chris Godsil for When can a matrix with negative entries have a completely non-negative dominant eigenvector?

2013-03-15T21:54:17Z

Let $J$ be the all-ones matrix, order $n\times n$ and set $M=J-2I$. The largest eigenvalue is $n-2$ with the all-ones vector as the eigenvector, all other eigenvalues are $-2$. So assume $n\ge5$.

For an alternative, take your favourite non-negative irreducible matrix $M$ and let $z$ be the eigenvector for the dominant eigenvalue with norm 1. Let $L$ be an orthogonal matrix whose columns are an orthonormal basis that contains $z$. Then $L^TML$ has the same eigenvalues as $M$ and the eigenvector belonging to the dominant eigenvalue is $z$. But in general $L^TML$ will not be non-negative.

So it's hard to see what a useful answer to your question would look like.

Answer by Chris Godsil for Non symmetric matrices with real eigenvalues

2013-03-12T12:42:31Z

$$ \begin{pmatrix}1&0\\0&k^{-1/2}\end{pmatrix} \begin{pmatrix}A_1&A_2\\ kA_2^T&A_3\end{pmatrix} \begin{pmatrix}1&0\\0&k^{1/2}\end{pmatrix} = \begin{pmatrix}A_1& k^{1/2}A_2\\ k^{1/2}A_2^T&A_3\end{pmatrix} $$

Note that $A_3$ only needs to be symmetric.

Answer by Chris Godsil for Eigenvalues of principle minors Vs. eigenvalues of the matrix

2013-03-04T19:39:23Z

A counterexample (to the unedited question): $$ A = \begin{pmatrix}1+x&1\\1&1+x\end{pmatrix}. $$ Eigenvalues of $A$ are $2+x$ and $x$, principal minors have one eigenvalue $1+x$.

Voting to close.

Answer by Chris Godsil for Is there any relation between automorphism group of a Cayley graph over a group and over its subgroup?

2013-02-28T19:17:26Z

I am reasonably confident that the real answer to your question is "No". For example, if $T=H\setminus 1$ then the automorphism group of $\mathrm{Cay}(H,T)$ is the full symmetric group. For another, take $S=T$; then $\Gamma$ will have a large automorphism graph, a wreath product. (If you want your Cayley graphs connected, take complements.) So adding generators may reduce symmetry, or increase it.

Note that questions phrased as you have are a bit difficult to answer, since the answer depends on what you mean by "any relation between".

Answer by Chris Godsil for On duality on finite projective planes

2013-02-11T21:47:41Z

Your statement of the principle of duality is wrong, as Andreas has noted. What it says is that, if you have a theorem then the dual theorem, which you get by swapping points and lines, is also a theorem. It is very easy to derive incorrect results by applying the duality principle with too much enthusiasm.

The Hall planes are one of many classes of planes that are not isomorphic to their duals. Examples can be constructed as follows. Let $V$ be a vector space of dimension $d$ over $GF(q)$ and let $S$ be a set of $q^d$ matrices chased so the the difference of any two distinct elements of $S$ is invertible. Now construct an incidence structure with the elements of $V\oplus V$ as its points, and with the sets $$ L_{A,b} = {(x,Ax+b): x\in V} $$ as lines. Here $A\in S$ and $b\in V$. This structure is an affine plane, a so-called translation plane, and there is a very large literature devoted to them.

One example arises by choosing the matrices in $S$ so that they form the extension field of $GF(q)$, with order $q^d$. (In which case we get the classical Desarguesian plane.) But there are many other examples, and in general they are not self dual.

In fact there is a theorem that a translation plane is self dual if and only if it can be constructed from a set $S$ which is a semifield, that is, which satisfies all axioms for a field except associativity. Most translation planes do not come from semifields.

The most accessible treatment of this is still probably the book "Projective Planes" by Hughes and Piper. Note that my semifields are their division rings. Note also that I wrote "most accessible", not "accessible".

Answer by Chris Godsil for The number of non-isomorphic strongly regular graphs on n vertices

2013-02-05T14:32:15Z

No formula is known. Since Latin squares and Steiner triple systems give strongly regular graphs, lower bounds on the numbers of these structure give lower bounds if $n$ is square or if $n=v(v-1)/6$ and $v\equiv1,3$ mod 6. (Presumably these lower bounds are very weak.) According to Brouwer's tables we have exact enumeration up to 36; the numbers on 37 and 41 are not known. (I expect that the number of srgs on $p$ vertices, $p$ prime increases with $p$, but this has not been proved.)

Of course we do not know the number of isomorphism classes of graphs on $n$ vertices. We have a procedure that allows us to compute the number for moderate values of $n$, and we know that asymptotically the number is $2^{n(n-1)/2}/n!$. Given this, our knowledge for strongly regular graphs does not seem quite so bad.

Answer by Chris Godsil for Full-rank linearly independent matrices

2013-02-01T12:13:58Z

If the characteristic of $\mathbb{F}$ is not two and $E_{i,j}$ $(1\le i,j\le n)$ is the "standard basis", then the matrices $I+E_{i,j}$ are invertible. They are linearly independent if $n+1\ne0$ in $\mathbb{F}$. If the characteristic of $\mathbb{F}$ is greater than 2, we can use $I-E_{i,j}$ instead and these are linearly independent if $n-1\ne0$. So we have explicit examples except in characteristic two.

Answer by Chris Godsil for coincidence between minimal triangulation numbers and chromatic numbers

2013-01-29T13:10:05Z

The answer to your "is it obvious" is "no". But it is a theorem in many cases. Wikipedia + one click takes to you "Solution of the Heawood map coloring problem" by Ringel and Youngs. There they completed the proof that Heawood's bound on the chromatic number was tight for surfaces with positive genus. As they explain in their introduction, they do this by producing an embedding of a complete graph in each case. The embedding for $K_N$ is triangular if $N$ is congruent to 0, 3, 4, or 7 mod 12.

To see this, note that Ringels and Young show that if $\gamma=\lceil (n-3)(n-4)/12\rceil$, then there is an embedding of $K_n$ in the surface of genus $\gamma$, whence the chromatic number of the surface is at least $n$. By Euler's formula $n-e+f=2-2g$ and for $K_n$ we have $e=n(n-1)/2$ and $3f \le 2e$ (with equality if and only if each face is a triangle). Hence $$ -n(n-7)/6 \ge 2-2g $$ or equivalently $g \le (n-3)(n-4)/12$. So in the mod 12 cases listed the embedding is triangular.

Answer by Chris Godsil for Godsil-Mckay switching applied on the Paley graph

2013-01-22T19:58:32Z

If you apply what I call local switching to $C$, then the graph that results can be obtained by Seidel switching as follows. Let $Y$ be the Paley graph with an extra isolated vertex. Apply Seidel switching to set $C$, to get a new graph $Y'$. Then $Y'$ still has an isolated vertex, the remaining vertices induce a graph isomorphic to $P(q)$. (This is a property of the switching class of $P(q)\cup K_1$.)

The key here is that in $P(q)$, each vertex not in $C\cup\nu$ is joined to exactly half the vertices in $C$.

For the benefit of outsiders, if $C$ is subset of the vertices of a graph $X$ the Seidel switching on $C$ produces the graph $Y$ on the same vertex set, where if $x\in C$ and $y\notin C$ then $xy$ is an edge in $Y$ if and only if it is not an edge in $X$. If $X$ and $Y$ are regular with the same valency, they are cospectral.

For local switching choose $C$ so that the subgraph it induces is regular and each vertex not in $C$ is adjacent to all, none, or exactly half the vertices in $C$. Now for each vertex half-joined to $C$, delete those edges joining it to $C$ and the the complementary set. Again the new graph is cospectral to the original graph, and is often not isomorphic to it. (It's going to be really embarrassing if I made a mistake in this description.)

Answer by Chris Godsil for Strongly regular graphs with the same parameters as Paley graph

2013-01-22T19:37:58Z

If $p$ is a prime congruent to 3 (mod 4) and $q$ is an even power of $q$, there are the Peisert graphs which are arc-transitive, self-complementary conference graphs, not isomorphic to Paley graphs.

More generally, start with the affine plane over $GF(q)$ where $q$ is odd, with point set $GF(q)\times GF(q)$. Choose a subset $P$ of $GF(q)\cup\infty$ and define $X(P)$ to be the graph with the points of the plane as vertices, with two points adjacent if they are distinct and the slope of the affine line joining them is in $P$. Then $X(P)$ is strongly regular, and if $|P|=(1+q)/2$, then $X(P)$ is a conference graph. When $q$ is large, we get many non-isomorphic graphs. (The Peisert graphs can be obtained in this way.)

For more on these topics, see Natalie Mullin's Ph.D. thesis (http://uwspace.uwaterloo.ca/bitstream/10012/4264/1/nm_thesis.pdf)

As you can see from Brouwer's tables (http://www.win.tue.nl/~aeb/graphs/srg/srgtab.html), there are 41 conference graphs on 29 vertices. According to the same source, conference graphs on fewer than 25 vertices are Paley graphs and there are 15 conference graphs on 25 vertices.

I do not recall seeing any general procedure for constructing conference graphs on a prime number of vertices that are not isomorphic to Paley graphs.

Answer by Chris Godsil for Mathematical "proof" of the stability of atoms?

2013-01-21T18:01:07Z

Googling on the obvious took me to http://www.pas.rochester.edu/~rajeev/phy246/lieb.pdf

Answer by Chris Godsil for About writing of mathematical papers

2013-01-17T15:42:42Z

The answer to your question is "No".

In Halmos's "How to write mathematics" (which you can find by googling), he refers to using symbols rather than words as "writing in code". It might make the writer's task easier but that is irrelevant, because it makes the reader's life considerably harder.

Halmos's article is a very good guide.

Answer by Chris Godsil for Connection between eigenvalues of matrix and its Laplacian.

2013-01-14T13:06:42Z

Essentially your question is equivalent to asking for the relation between the spectrum of $A+D$ and $A$, where are $A$ is symmetric, $D$ is diagonal and both matrices are real. And, by change of basis, this is equivalent to asking for between the spectrum of $A+B$ and $A$ when $A$ and $B$ are real symmetric. A lot of thought has been given to this question. The short summary is that eigenvalues of $A$ provide no information useful towards computing the eigenvalues of $A+D$.

It might also be worth pointing out that there are many more that two definitions of graph spectrum (normalized and unsigned Laplacian, Seidel, spectrum of complement, to mention four more that come quickly to mind). All of these provide the same information for regular graphs, but in no case does computing one provide much help in computing another.

Answer by Chris Godsil for real symmetric matrix has real eigenvalues - elementary proof

2013-01-11T16:59:11Z

We can do it in two steps.

Step 1: show that if $A$ is a real symmetric matrix, there is an orthogonal matrix $L$ such that $A=LHL^T$, where $H$ is tridiagonal and its off-diagonal entries are non-negative. (Apply Gram-Schmidt to sets of vectors of the form ${x,Ax,\ldots,A^mx}$, or use Householder transformations, which is the same thing.)

Step 2. We need to show that the eigenvalues of tridiagonal matrices with non-negative off-diagonal entries are real. We can reduce to the case where $H$ is indecomposable. Assume it is $n\times n$ and let $\phi_{n-r}$ the the characteristic polynomial of the matrix we get by deleting the first $r$ rows and columns of $H$. Then $$ \phi_{n-r+1} = (t-a_r)\phi_{n-r} -b_r \phi_{n-r-1}, $$ where $b>0$. Now prove by induction on $n$ that the zeros of $\phi_{n-r}$ are real and are interlaced by the zeros of $\phi_{n-r-1}$. The key here is to observe that this induction hypothesis is equivalent to the claim that all poles and zeroes of $\phi_{n-r-1}/\phi_{n-r}$ are real, and in its partial fraction expansion all numerators are positive. From this it follows that the derivative of this rational function is negative everywhere it is defined and hence, between each consecutive pair of zeros of $\phi_{n-r-1}$ there must be a real zero of $\phi_{n-r}$.

Answer by Chris Godsil for What are the major open problems in design theory nowaday?

2013-01-10T18:06:35Z

Fix $\lambda>1$. Are there infinitely many symmetric $(v,k,\lambda)$ designs? (The Hadamard conjectures would be at the top of my list though.)

Answer by Chris Godsil for Ihara zeta and chromatic number of graphs

2013-01-07T20:05:29Z

For regular graphs the Ihara zeta function is determined by the spectrum of the adjacency matrix, and so graphs can have the same zeta function and different chromatic number. For examples take the complements of the Shrikande graph and the line graph of $K_{4,4}$ (which have chromatic numbers 6 and 4 respectively).

Answer by Chris Godsil for power of adjacency matrix

2013-01-04T03:41:34Z

Call a walk in $X$ reduced if it does not contain any subsequence of the form $uvu$, and let $p_r(A)$ denote the matrix whose $uv$-entry is the number of reduced walks from $u$ to $v$. Let $\Delta$ be the disgonal matrix such that $\Delta_{u,u}$ is the valency of $u$. Then if $r>2$, we have $$ Ap_{r-1}(A) = p_r(A) + (\Delta-I)p_{r-2}(A) $$ If $\Phi(X,t)$ is the generating function $\sum_r p_r(A)t^r$, it follows that $$ (I-tA+t^2(\Delta-I)) \Phi(X,t) = (1-t^2)I. $$ It follows that we can effectively count reduced walks. And if $X$ is a tree, then $\Phi(X,t)$ is actually a polynomial. [So $K_2$ is not a problem :-) ]

Of course I agree with Richard Stanley's remark about the general case.

Answer by Chris Godsil for Finding a subspace disjoint from a union of subspaces

2013-01-03T12:35:22Z

Let $B$ be the oriented vertex-edge incidence matrix of a graph, viewed as a matrix over $GF(p)$. Let the subspaces $V_i$ be the 1-dimensional subspaces spanned by the columns of $B$. There is a subspace of codimension 1 disjoint from these subspaces if and only if there is a non-zero vector $a$ such that no entry of $a^TB$ is zero.

But the columns of $B$ are each of the form $e_i-e_j$, for an edge $ij$ of $G$, and we can view $a$ as a function on the vertices of $G$. The condition that no entry of $a^TB$ is zero is then equivalent to the condition that the map from a vertex to the corresponding entry of $a$ is a proper vertex-coloring with $p$ colors. Hence your problem is NP-hard.

Over GF(2) is can be shown that finding a subspace of codimension two disjoint from the columns is equivalent to 4-coloring.

Answer by Chris Godsil for The cliques of cospectral graphs

2013-01-02T03:42:29Z

Let $X$ and $Y$ be two cospectral graphs with maximum clique size $a$ and $b$ respectively. Then their $k$-fold strong powers $X(k)$ and $Y(k)$ are cospectral and the maximum size of a clique is $a^k$ and $b^k$ respectively. (The cliques of maximum size in a strong product are strong products of maximum sized cliques in the factors.) Since the strong product of connected graphs is connected, we have our examples.

We could take $X$ and $Y$ to be the Shrikande graph ($a=3$) and the line graph of $K_{4,4}$ ($b=4$). There are smaller examples, but I am too lazy to look right now.

Answer by Chris Godsil for The smallest eigenvalue from an equitable partitions

2012-12-22T15:50:45Z

There are infinitely many counterexamples. Let $\pi$ be the distance partition relative to a vertex in a strongly regular graph. Then $\pi$ is equitable and $G/\pi$ is a path, so its eigenvalues are all simple. But if $G$ is not bipartite, its least eigenvalue is not simple.

Answer by Chris Godsil for Difference of the maximum eigenvalue of a graph with the one of one-edge-deleted subgraph

2012-12-17T21:44:30Z

It's always useful to test these questions on actual examples. The largest eigenvalue of the cycle $C_n$ is 2 and the largest eigenvalue of the path $P_n$ on $n$ vertices is $2\cos(\pi/(n+1))$. When $n=8$, this is 1.879385 and $2-1.8793852=0.120615 <1/8$.

In fact it is not hard to see that for large $n$ the difference $2-2\cos(\pi/(n+1))$ is of order $\pi^2/(n+1)^2$, and so your lower bound is not even of the right order.

Answer by Chris Godsil for are there pairs of combinatorial graphs that are both isospectral and have the same matroid?

2012-12-13T16:56:15Z

Choose a graph $X$ with vertices $u$ and $v$ such that $X\backslash u$ and $X\backslash v$ are cospectral. (In this case I say that $u$ and $v$ are cospectral vertices.) Assume that there is no automorphism of $X$ that swaps $u$ and $v$. Now form the graph $Y$ from two copies of $X$ by identifying vertex $u$ in the first copy with vertex $u$ in the second, and vertex $v$ in the first with $v$ in the second. Next form $Z$ from two copies of $X$ by identifying $u$'s with $v$'s.

If $u$ and $v$ are adjacent, then then will be a double edge, so we assume that $u$ and $v$ are not adjacent. This means that $Y$ and $Z$ are related by a Whitney flip and hence they have the same cycle matroid.

The graphs $Y$ and $Z$ are cospectral. This follows from Corollary 4.3.2 in my book "Algebraic Combinatorics". Since we only need examples we do not need the proof though, we can just carry out the construction and check.

As example, use Schwenk's tree, constructed as follows. Start with the path on 8 vertices 0,1,...,7 and add a vertex 8 adjacent to 5. Vertices 3 and 6 are cospectral. The graphs we get from the construction are not cospectral. (I just checked using sage.)

For more examples, take any strongly regular graph with trivial automorphism group and take $u$ and $v$ to be two nonadjacent vertices. These examples will be 2-connected.

Answer by Chris Godsil for Shannon capacity determined by $\alpha(G)$ and $\chi^*(\bar{G})$???

2012-12-08T20:19:33Z

I will work with the complements. We first want a graph $G$ such that $\omega(G)$ (the maximum size of a clique) is equal to $\chi_f(G)$, its fractional chromatic number. Take $G$ to be the Kneser graph $K_{9:3}$; its vertices are the 84 triples from a set of size nine, with two triples adjacent if they are disjoint. So $\omega(G)=3$ and $\alpha(G)=28$ (by the EKR theorem). Since $G$ is vertex transitive, $$ \chi_f(G) = |V(G)|/\alpha(G) = 3. $$ By a theorem of Lovasz, $\chi(K_{v:k})=v-2k+2$ and so $\chi(G)=5$.

In fact $K_{3k:k}$ works whenever $k\ge2$.

Comment by Chris Godsil

2013-05-17T11:44:32Z

If you read the faq, you'll see that this is not the right place to post this question.

Comment by Chris Godsil

2013-05-16T12:18:05Z

Please see the FAQ for a description of the questions appropriate on this site.

Comment by Chris Godsil

2013-05-05T17:21:38Z

@Hans: the statement of your question is incomplete.

Comment by Chris Godsil

2013-05-02T17:51:54Z

Yes, you pipe them through nasty, or use sage.

Comment by Chris Godsil

2013-04-30T11:47:29Z

@Roberto: I meant $V(Y)$, it's fixed now.

Comment by Chris Godsil

2013-04-08T14:40:08Z

Your basically asking: how do we find the global optimum solution to an optimization problem. This is of course a very important question, but unanswerable.

Comment by Chris Godsil

2013-04-05T14:36:28Z

I think I'd look for information on so-called MDS codes. (MDS = maximum distance separable.) I do not think these are the same thing, but they should lead you closer to what you want.

Comment by Chris Godsil

2013-03-31T23:59:28Z

In the context of association schemes, these matrices are not called Bose-Mesner matrices. The matrices given do belong to the Bose-Mesner algebra of the complete graph, but I have never seen any matrix in any Bose-Mesner algebra referred to as a Bose-Mesner matrix.

Comment by Chris Godsil

2013-03-30T21:20:23Z

@Nathann Cohen: I am not aware of any such database, nor do I know of any potential application for one.

Comment by Chris Godsil

2013-03-30T12:46:41Z

If you prvided more information, these question might be suitable for math.stackexchange. It does not belong here (see the FAQ).

Comment by Chris Godsil

2013-03-29T13:54:46Z

The is an old paper by Pavol Hell "Graphs with given neighbourhoods". This is not focussed on vertex-transitive graphs (iirc), but I think there is a good chance that some of the methods carry over.

Comment by Chris Godsil

2013-03-26T11:21:54Z

I agree entirely with what Dima has written, but in the text quoted above I was actually thinking of the many useful details about permutation groups that appear in the first few chapters of Wielandt's book and which I have not seen elsewhere.

Comment by Chris Godsil

2013-03-21T12:55:03Z

This question is out of place here, it would be better on math.stackexchange, for example.

Comment by Chris Godsil

2013-03-16T02:37:26Z

This question is not appropriate for this site, see the FAQ. It should do fine at math.stackexchange.

Comment by Chris Godsil

2013-03-15T22:01:00Z

Posting questions on math.stackexchange and here simultaneously will lose you friends at this site.