En matemáticas , los gráficos de Paley son gráficos no dirigidos construidos a partir de los miembros de un campo finito adecuado conectando pares de elementos que difieren en un residuo cuadrático . Los gráficos de Paley forman una familia infinita de gráficos de conferencia , que producen una familia infinita de matrices de conferencia simétricas . Los gráficos 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 gráficos de Paley llevan el 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 gráficos 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 gráficos 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 antes se sabía que se realizaba sólo en torneos aleatorios: en un dígrafo de Paley, cada pequeño subconjunto de vértices es 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 impar no pitagórico. Esta elección de q implica que en el campo finito único F q de orden q , el elemento −1 tiene raíz cuadrada.
Ahora sea V = F q y sea
Si un par { a , b } está incluido en E , está incluido en cualquier orden de sus dos elementos. Porque, a − b = −( b − a ), y −1 es un cuadrado, de lo cual se deduce 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 entera módulo 13. Los números con raíces cuadradas mod 13 son:
Por lo tanto, 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 gráficos de Paley son autocomplementarios : el complemento de cualquier gráfico de Paley es isomorfo a él. Un isomorfismo es a través del mapeo que lleva un vértice x a xk (mod q ) , donde k es cualquier mod q sin residuo . [2]
Los gráficos de Paley son gráficos fuertemente regulares , con parámetros
De hecho, esto se deriva del hecho de que el gráfico es transitivo en arco y autocomplementario. Los gráficos fuertemente regulares con parámetros de esta forma (para una q arbitraria ) se llaman gráficos de conferencia , por lo que los gráficos de Paley forman una familia infinita de gráficos de conferencia. La matriz de adyacencia de un gráfico de conferencia, como un gráfico 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 multiplica por su transpuesta. [5]
Los valores propios de las gráficas 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 gráficas fuertemente regulares. [6]
Si q es primo, el número isoperimétrico i ( G ) del gráfico 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 casi aleatorios : el número de veces que cada posible gráfico de orden constante aparece como un subgrafo de un gráfico de Paley es (en el límite para q grande ) el mismo que para los gráficos aleatorios, y los conjuntos grandes de vértices tienen aproximadamente lo mismo. número de aristas como lo harían en gráficos aleatorios. [8]
Sea q una potencia prima tal que q = 3 (mod 4). Por tanto, el campo 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 , ya sea a − b o b − a , pero no ambos, es un cuadrado. El dígrafo de Paley es el gráfico 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 conferencias antisimétricas y geometrías biplanas .
Los seis vecinos de cada vértice en el gráfico de Paley de orden 13 están conectados en un ciclo; es decir, la gráfica es localmente cíclica . Por lo tanto, esta gráfica se puede incrustar como una triangulación de Whitney de un toroide , en la que cada cara es un triángulo y cada triángulo es una cara. De manera más general, si cualquier gráfico de Paley de orden q pudiera incrustarse de modo que todas sus caras fueran triángulos, podríamos calcular el género de la superficie resultante mediante 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 gráfico 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 ser válido de manera más general. Específicamente, Mohar conjetura que las gráficas 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 llegue a cero en el límite cuando q llegue al infinito. [12]
White (2001) encuentra incrustaciones de los gráficos de Paley de orden q ≡ 1 (mod 8) que son altamente simétricas y autoduales, generalizando una incrustación natural del gráfico 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]
