En matemáticas , los gráficos de Paley son gráficos densos no dirigidos construidos a partir de los miembros de un campo finito adecuado conectando pares de elementos que se diferencian por un residuo cuadrático . Los gráficos de Paley forman una familia infinita de gráficos de conferencias , que producen una familia infinita de matrices de conferencias simétricas . Gráficos Paley permitir que el gráfico de la teoría de las herramientas que han de aplicarse a la teoría de los números de los 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 ( Paley 1933 ). 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, mientras que Erdős y Rényi estudiaron sus simetrías.
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 solo se realizaba mediante torneos aleatorios: en un dígrafo de Paley, cada pequeño subconjunto de vértices es dominado por algún otro vértice.
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.
Si se incluye un par { a , b } en E , se incluye en cualquier orden de sus dos elementos. Porque, a - b = - ( b - a ), y −1 es un cuadrado, de lo cual se sigue que a - b es un cuadrado si y solo si b - a es un cuadrado.
Para q = 13, el campo F q es solo un número entero aritmético módulo 13. Los números con raíces cuadradas mod 13 son: