En matemáticas , los grafos de Paley son grafos no dirigidos construidos a partir de los miembros de un cuerpo finito adecuado conectando pares de elementos que difieren en un residuo cuadrático . Los grafos de Paley forman una familia infinita de grafos de conferencia , que dan como resultado una familia infinita de matrices de conferencia simétricas . Los grafos de Paley permiten aplicar herramientas de teoría de grafos a la teoría de números de residuos cuadráticos y tienen propiedades interesantes que los hacen útiles en la teoría de grafos en general.
Los grafos de Paley reciben su nombre de Raymond Paley . Están estrechamente relacionados con la construcción de Paley para construir matrices de Hadamard a partir de residuos cuadráticos. [1] Fueron introducidos como grafos de forma independiente por Sachs (1962) y Erdős & Rényi (1963). Sachs estaba interesado en ellos por sus propiedades de autocomplementariedad, [2] mientras que Erdős y Rényi estudiaron sus simetrías. [3]
Los dígrafos de Paley son análogos dirigidos de los grafos de Paley que producen matrices de conferencia antisimétricas . Fueron introducidos por Graham y Spencer (1971) (independientemente de Sachs, Erdős y Rényi) como una forma de construir torneos con una propiedad que previamente se sabía que solo se realizaba mediante torneos aleatorios: en un dígrafo de Paley, cada pequeño subconjunto de vértices está dominado por algún otro vértice. [4]
Sea q una potencia prima tal que q = 1 (mod 4). Es decir, q debería ser una potencia arbitraria de un primo pitagórico (un primo congruente con 1 mod 4) o una potencia par de un primo no pitagórico impar. Esta elección de q implica que en el cuerpo finito único F q de orden q , el elemento −1 tiene una raíz cuadrada.
Ahora sea V = F q y sea
Si un par { a , b } está incluido en E , está incluido bajo cualquiera de los dos ordenamientos de sus dos elementos. Pues, a − b = −( b − a ), y −1 es un cuadrado, de lo que se sigue que a − b es un cuadrado si y solo si b − a es un cuadrado.
Por definición G = ( V , E ) es el gráfico de Paley de orden q .
Para q = 13, el campo F q es simplemente aritmética de enteros módulo 13. Los números con raíces cuadradas módulo 13 son:
Así, en el gráfico de Paley, formamos un vértice para cada uno de los números enteros en el rango [0,12], y conectamos cada uno de esos números enteros x con seis vecinos: x ± 1 (mod 13), x ± 3 (mod 13) y x ± 4 (mod 13).
Los grafos de Paley son autocomplementarios : el complemento de cualquier grafo de Paley es isomorfo a él. Un isomorfismo se da a través de la aplicación que toma un vértice x a xk (mod q ) , donde k es cualquier residuo no mod q . [2]
Los gráficos de Paley son gráficos fuertemente regulares , con parámetros
Esto, de hecho, se deduce del hecho de que el grafo es arco-transitivo y autocomplementario. Los grafos fuertemente regulares con parámetros de esta forma (para un q arbitrario ) se denominan grafos de conferencia , por lo que los grafos de Paley forman una familia infinita de grafos de conferencia. La matriz de adyacencia de un grafo de conferencia, como un grafo de Paley, se puede utilizar para construir una matriz de conferencia , y viceversa. Se trata de matrices cuyos coeficientes son ±1 , con cero en la diagonal, que dan un múltiplo escalar de la matriz identidad cuando se multiplican por su transpuesta. [5]
Los valores propios de los grafos de Paley son (con multiplicidad 1) y (ambos con multiplicidad ). Se pueden calcular utilizando la suma cuadrática de Gauss o utilizando la teoría de grafos fuertemente regulares. [6]
Si q es primo, el número isoperimétrico i ( G ) del grafo de Paley satisface los siguientes límites:
Cuando q es primo, el gráfico de Paley asociado es un gráfico circulante hamiltoniano .
Los gráficos de Paley son cuasialeatorios : la cantidad de veces que cada posible gráfico de orden constante ocurre como un subgráfico de un gráfico de Paley es (en el límite para q grande ) la misma que para los gráficos aleatorios, y los conjuntos grandes de vértices tienen aproximadamente la misma cantidad de aristas que tendrían en gráficos aleatorios. [8]
Sea q una potencia prima tal que q = 3 (mod 4). Por lo tanto, el cuerpo finito de orden q , F q , no tiene raíz cuadrada de −1. En consecuencia, para cada par ( a , b ) de elementos distintos de F q , a − b o b − a , pero no ambos, es un cuadrado. El dígrafo de Paley es el grafo dirigido con conjunto de vértices V = F q y conjunto de arcos
El dígrafo de Paley es un torneo porque cada par de vértices distintos está unido por un arco en una y sólo una dirección.
El dígrafo de Paley conduce a la construcción de algunas matrices de conferencia antisimétricas y geometrías biplanares .
Los seis vecinos de cada vértice en el grafo de Paley de orden 13 están conectados en un ciclo; es decir, el grafo es localmente cíclico . Por lo tanto, este grafo se puede incrustar como una triangulación de Whitney de un toro , en el que cada cara es un triángulo y cada triángulo es una cara. De manera más general, si cualquier grafo de Paley de orden q pudiera incrustarse de manera que todas sus caras fueran triángulos, podríamos calcular el género de la superficie resultante a través de la característica de Euler como . Bojan Mohar conjetura que el género mínimo de una superficie en la que se puede incrustar un grafo de Paley está cerca de este límite en el caso de que q sea un cuadrado, y se pregunta si dicho límite podría cumplirse de manera más general. Específicamente, Mohar conjetura que los grafos de Paley de orden cuadrado se pueden incrustar en superficies con género
donde el término o(1) puede ser cualquier función de q que tiende a cero en el límite cuando q tiende a infinito. [12]
White (2001) encuentra incrustaciones de los grafos de Paley de orden q ≡ 1 (mod 8) que son altamente simétricas y autoduales, generalizando una incrustación natural del grafo de Paley de orden 9 como una cuadrícula cuadrada de 3×3 sobre un toro. Sin embargo, el género de las incrustaciones de White es mayor en aproximadamente un factor de tres que el límite conjeturado de Mohar. [13]
