Gráficos con valores propios de multiplicidad grande

Question

Para una fuerza regular de la gráfica, hay exactamente 3 autovalores, todos distintos de cero (creo). Uno tiene multiplicidad 1, lo que significa que los otros dos tienen bastante alto de multiplicidades. Hay tablas que dan estos autovalores y multiplicidades:

http://www.win.tue.nl/~aeb/graphs/srg/srgtab1-50.html

Por ejemplo, el Schlaefli gráfica es la orden de 27, pero tiene un autovalor de orden 20.

Mi pregunta es, ¿hay otros conocidos gráficos (familias, tipos, o sólo gráficos) que tienen grandes multiplicidades de autovalores? Cuando me verificación aleatoria gráfico en Sage, parece que el max multiplicidad es principalmente 1.

Answer 1

Una clase de ejemplos son a distancia regular gráficos; es muy regular gráficos (esencialmente) distancia-regular los gráficos de diámetro. Distancia-regular los gráficos pueden ser construido a partir de matrices de Hadamard, simétrica diseños y códigos lineales.

Si todos los autovalores de la matriz de adyacencia $A$ de un gráfico es simple, cualquier matriz $P$ que conmuta con $A$ debe ser un polinomio en $A$. Se sigue de esto de que todos los automorfismos tener un orden, que divide en dos, y también que la gráfica es el grafo completo $K_2$ o no se puede vértice transitiva por Lo que cualquier vértice-transitiva en más de dos vértices tiene un valor propio que no es simple.

Usted puede aprender acerca de estas cosas en Biggs `Algebraica Teoría de grafos", por ejemplo.

Answer 2

Grafos aleatorios son propensos a tener distintos valores propios debido a su característica de polinomios son al azar, y el azar polinomios son propensos a tener un valor distinto de cero discriminante. Estoy seguro de que esto puede ser hecho preciso, pero yo no soy el uno para hacerlo.

En cualquier caso, usted quiere los gráficos que están lejos de ser aleatoria. Su mejor apuesta es encontrar gráficos con nonabelian automorphism grupos. Esto es debido a que el automorphism grupo $G$ de un gráfico que actúa sobre cada uno de los subespacios propios de su matriz de adyacencia, así, en particular, si $V$ denota el conjunto de vértices, a continuación, las representaciones irreducibles de $G$ que se producen en $\mathbb{C}^V$ se encuentran en subespacios propios, por lo tanto sus dimensiones dar a los límites inferiores de las multiplicidades de los autovalores.

La manera más fácil de construir los gráficos de esta propiedad es el uso de Schreier gráficos, que son generalizaciones de los grafos de Cayley. Usted quiere elegir un grupo de $G$ $G$- establecer $S$ tal que $\mathbb{C}^S$ ha irreductible subrepresentations de gran dimensión. Una forma de hacerlo es coger $G$ de manera tal que todos los de su trivial representaciones irreducibles tienen gran dimensión, por ejemplo, los grupos de $\text{PSL}_2(\mathbb{F}_q)$.