Gráfica de Paley
Gráfica de Paley
El gráfico de Paley de orden 13
Llamado en honor aRaymond Paley
Vérticesq ≡ 1 mod 4,
q potencia prima
Bordesq ( q −1)/4
Diámetro2
Propiedades
Gráfico de conferencia fuertemente regular
Autocomplementario
NotaciónQR( q )
Tabla de gráficos y parámetros

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]

Definición

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

mi = { { a , b }   :   a − b ∈ ( F q × ) 2 } {\displaystyle E=\left\{\{a,b\}\ :\ ab\in (\mathbf {F} _{q}^{\times })^{2}\right\}} .

Si un par { a , b } está incluido en E , está incluido bajo cualquiera de los 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 .

Ejemplo

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:

  • ±1 (raíces cuadradas ±1 para +1, ±5 para −1)
  • ±3 (raíces cuadradas ±4 para +3, ±6 para −3)
  • ±4 (raíces cuadradas ±2 para +4, ±3 para −4).

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).

Propiedades

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

s a gramo ( q , 1 2 ( q − 1 ) , 1 4 ( q − 5 ) , 1 4 ( q − 1 ) ) . {\displaystyle srg\left(q,{\frac {1}{2}}(q-1),{\frac {1}{4}}(q-5),{\frac {1}{4}}(q-1)\right).}

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] 1 2 ( q − 1 ) {\displaystyle {\tfrac {1}{2}}(q-1)} 1 2 ( − 1 ± q ) {\displaystyle {\frac {1}{2}}(-1\pm {\sqrt {q}})} 1 2 ( q − 1 ) {\displaystyle {\tfrac {1}{2}}(q-1)}

Si q es primo, el número isoperimétrico i ( G ) del grafo de Paley satisface los siguientes límites:

q − q 4 ≤ i ( GRAMO ) ≤ q − 1 4 . {\displaystyle \displaystyle {\frac {q-{\sqrt {q}}}{4}}\leq i(G)\leq {\frac {q-1}{4}}.} [7]

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]

  • El gráfico de Paley de orden 9 es un gráfico localmente lineal , un gráfico de torre y el gráfico del duoprisma 3-3 .
  • El gráfico de Paley de orden 13 tiene un grosor de libro de 4 y un número de cola de 3. [9]
  • El gráfico de Paley de orden 17 es el único gráfico más grande G tal que ni G ni su complemento contienen un subgrafo completo de 4 vértices. [10] De ello se deduce que el número de Ramsey R (4, 4) = 18.
  • El gráfico de Paley de orden 101 es actualmente el gráfico G más grande conocido tal que ni G ni su complemento contienen un subgráfico completo de 6 vértices.
  • Sasukara et al. (1993) utilizan gráficos de Paley para generalizar la construcción del fibrado de Horrocks-Mumford . [11]

Dígrafos de Paley

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

A = { ( a , b ) ∈ F q × F q   :   b − a ∈ ( F q × ) 2 } . {\displaystyle A=\left\{(a,b)\en \mathbf {F} _{q}\times \mathbf {F} _{q}\ :\ba\en (\mathbf {F} _{q}^{\times })^{2}\right\}.}

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 .

Género

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 1 24 ( q 2 − 13 q + 24 ) {\displaystyle {\tfrac {1}{24}}(q^{2}-13q+24)}

( q 2 − 13 q + 24 ) ( 1 24 + o ( 1 ) ) , {\displaystyle (q^{2}-13q+24)\left({\tfrac {1}{24}}+o(1)\right),}

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]

Referencias

  1. ^ Paley, REAC (1933). "Sobre matrices ortogonales". J. Math. Phys. 12 (1–4): 311–320. doi :10.1002/sapm1933121311.
  2. ^ ab Sachs, Horst (1962). "Super selbstkomplementäre Graphen". Publicaciones Mathematicae Debrecen . 9 : 270–288. doi : 10.5486/PMD.1962.9.3-4.11 . SEÑOR  0151953.
  3. ^ Erdős, P .; Rényi, A. (1963). "Gráficos asimétricos". Acta Mathematica Academiae Scientiarum Hungaricae . 14 (3–4): 295–315. doi :10.1007/BF01895716. SEÑOR  0156334.
  4. ^ Graham, RL ; Spencer, JH (1971). "Una solución constructiva a un problema de torneo". Canadian Mathematical Bulletin . 14 : 45–48. doi :10.4153/CMB-1971-007-1. MR  0292715.
  5. ^ Brouwer, AE; Cohen, AM; Neumaier, A. (1989). "Matrices de conferencias y gráficos de Paley". Gráficos de distancia regular . Ergebnisse der Mathematik und ihrer Grenzgebiete. vol. 18. Berlín: Springer-Verlag. pag. 10. doi :10.1007/978-3-642-74341-2. ISBN 3-540-50619-5.Señor 1002568  .
  6. ^ Brouwer, Andries E.; Haemers, Willem H. (2012). "9.1.2 Los grafos de Paley". Espectros de grafos . Universitext. Nueva York: Springer. págs. 114-115. doi :10.1007/978-1-4614-1939-6. ISBN . 978-1-4614-1938-9.Señor 2882891  .Para obtener el espectro a partir de una regularidad fuerte, véase el teorema 9.1.3, pág. 116. Para la conexión con las sumas de Gauss, véase la sección 9.8.5 Ciclotomía, págs. 138-140.
  7. ^ Cramer, Kevin; Krebs, Mike; Shabazi, Nicole; Shaheen, Anthony; Voskanian, Edward (2016). "Las constantes isoperimétricas y de Kazhdan asociadas a un gráfico de Paley". Involve . 9 (2): 293–306. doi :10.2140/involve.2016.9.293. MR  3470732.
  8. ^ Chung, Fan RK ; Graham, Ronald L. ; Wilson, RM (1989). "Gráficos cuasi-aleatorios". Combinatorica . 9 (4): 345–362. doi :10.1007/BF02125347.
  9. ^ Wolz, Jessica (2018). Diseños lineales de ingeniería con SAT . Tesis de maestría. Universidad de Tübingen.
  10. ^ Evans, RJ; Pulham, JR; Sheehan, J. (1981). "Sobre el número de subgrafos completos contenidos en ciertos grafos". Journal of Combinatorial Theory . Serie B. 30 (3): 364–371. doi : 10.1016/0095-8956(81)90054-X .
  11. ^ Sasakura, Nobuo; Enta, Yoichi; Kagesawa, Masataka (1993). "Construcción de haces reflexivos de rango dos con propiedades similares al fibrado de Horrocks-Mumford". Proc. Japan Acad., Ser. A . 69 (5): 144–148. doi : 10.3792/pjaa.69.144 .
  12. ^ Mohar, Bojan (2005). "Triangulaciones y la conjetura de Hajós". Revista Electrónica de Combinatoria . 12 : N15. doi : 10.37236/1982 . MR  2176532.
  13. ^ White, AT (2001). "Gráficos de grupos sobre superficies". Interacciones y modelos . Ámsterdam: North-Holland Mathematics Studies 188.

Lectura adicional

  • Baker, RD; Ebert, GL; Hemmeter, J.; Woldar, AJ (1996). "Camillas máximas en el gráfico de Paley de orden cuadrado". J. Statist. Plann. Inference . 56 : 33–38. doi :10.1016/S0378-3758(96)00006-7.
  • Broere, I.; Döman, D.; Ridley, JN (1988). "Los números de camarilla y los números cromáticos de ciertos grafos de Paley". Quaestiones Mathematicae . 11 : 91–93. doi :10.1080/16073606.1988.9631945.
  • Brouwer, Andries E. "Gráficos de Paley".
  • Mohar, Bojan (2005). "Género de gráficos de Paley".
Obtenido de "https://es.wikipedia.org/w/index.php?title=Gráfico_de_Paley&oldid=1232686508"