El conde de Paley

El conde de Paley
Conde de Paley Orden 13
picos	q ≡ 1 mod 4, q es una potencia prima
costillas	q ( q - 1)/4
Propiedades	Gráfico de conferencia autocomplementario fuertemente regular
Designacion	QR( q )
Archivos multimedia en Wikimedia Commons

En la teoría de grafos, los gráficos de Paley (llamados así por Raymond Paley ) son gráficos densos no dirigidos construidos a partir de los términos de un campo finito adecuado mediante la conexión de pares de elementos que difieren en un residuo cuadrático . Los gráficos de Paley forman una familia infinita de gráficos de conferencias porque están estrechamente relacionados con la familia infinita de matrices de conferencias simétricas . Los gráficos de Paley brindan la oportunidad de aplicar las herramientas teóricas de la teoría de gráficos en la teoría de residuos cuadráticos y tienen propiedades interesantes que los hacen útiles para la teoría de gráficos en general.

Los gráficos de Paley están estrechamente relacionados con la construcción de Paley para construir matrices de Hadamard a partir de residuos cuadráticos (Paley, 1933) [1] . Fueron presentados como condes de forma independiente por Sachs (Sachs, 1962) y Erdős, junto con Rényi (Erdős, Rényi, 1963) [2] . Horst Sachs se interesó por ellos por su propiedad autocomplementaria, mientras que Erdős y Rényi estudiaron sus simetrías.

Los dígrafos de Paley son el análogo directo de los gráficos de Paley y corresponden a matrices de conferencias antisimétricas . Fueron introducidos por Graham y Spencer [3] (e independientemente por Sachs, Erdős y Renyi) como una forma de construir torneos con propiedades previamente conocidas solo para torneos aleatorios: en los dígrafos de Paley, cualquier subconjunto de vértices está dominado por algún vértice.

Definición

Sea q una potencia de un primo tal que q = 1 (mod 4). Nótese que esto implica la existencia de una raíz cuadrada de −1 en el único campo finito F q de orden q .

Sea también V = F q y

{\displaystyle E=\left\{(a,b)\in \mathbf {F}_{q}\times \mathbf {F}_{q}\ :\ ab\in (\mathbf {F}_{ q}^{\veces})^{2}\derecho\))

Este conjunto está bien definido porque a − b = −( b − a ), y −1 es un cuadrado de algún número, lo que implica que a − b es un cuadrado si y solo si b − a es un cuadrado.

Por definición, G = ( V , E ) es un gráfico de Paley de orden q .

Ejemplo

Para q = 13, el cuerpo F q está formado por números módulo 13. Números que tienen raíces cuadradas módulo 13:

±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í, el grafo de Paley está formado por vértices correspondientes a números en el intervalo [0,12], y cada vértice x está conectado a seis vecinos: x ± 1 (mod 13), x ± 3 (mod 13) y x ± 4 (módulo 13).

Propiedades

Los gráficos de Paley son autocomplementarios: el complemento de cualquier gráfico de Paley es isomorfo al gráfico mismo. [cuatro]
Estos gráficos son fuertemente regulares con parámetros

srg\left(q,{\tfrac {1}{2}}(q-1),{\tfrac {1}{4}}(q-5),{\tfrac {1}{4} }(q-1)\derecha).

Además, los gráficos de Paley, de hecho, forman una familia infinita de gráficos de conferencia .

Los valores propios de los gráficos de Paley son los números (con multiplicidad 1) y (ambos con multiplicidad ) y se pueden calcular usando sumas cuadráticas de Gauss . ${\tfrac{1}{2}}(q-1)$ ${\tfrac{1}{2}}(-1\pm {\sqrt {q}})$ ${\tfrac{1}{2}}(q-1)$

Si q es primo, los límites del número isoperimétrico i ( G ) son:

{\frac {q-{\sqrt {q}}}{4}}\leq i(G)\leq {\sqrt {\left(q+{\sqrt {q}}\right)\left( {\frac{q-{\sqrt {q}}}{2}}\right)}}

De ello se deduce que i(G)~O(q), y el gráfico de Paley es un expansor .

Si q es primo, su gráfico de Paley es el ciclo hamiltoniano de un gráfico circulante .

Los gráficos de Paley son casi aleatorios (Chang et al., 1989) [5] : el número de casos en los que un gráfico de orden constante resulta ser un subgráfico de un gráfico de Paley es (en el límite para q grande ) el mismo que para gráficos aleatorios y para grandes conjuntos de vértices, tiene aproximadamente el mismo número de aristas que los gráficos aleatorios.

Aplicaciones

El gráfico de Paley de orden 17 es el único gráfico G más grande de modo que ni él ni su complemento contienen un subgráfico completo de 4 vértices (Evans et al. 1981). [6] De aquí se sigue que el número de Ramsey R (4, 4) = 18.

El gráfico Paley de orden 101 es hasta ahora el único gráfico máximo conocido G tal que ni G ni su complemento contienen un subgráfico completo de 6 vértices.

Sasakura [7] usó gráficos de Paley para generalizar la construcción de la gavilla de Horrocks-Mumford .

Digrafos de Paley

Sea q una potencia de un primo tal que q = 3 (mod 4). Entonces el campo finito F q de orden q no tiene raíz cuadrada de −1. Por lo tanto, para cualquier par ( a , b ) de elementos distintos de F q , ya sea a − b o b − a , pero no ambos, son cuadrados. Un dígrafo de Paley es un grafo dirigido con un conjunto de vértices V = F q y un conjunto de arcos

A=\left\{(a,b)\in \mathbf {F}_{q}\times \mathbf {F}_{q}\ :\ba\in (\mathbf {F}_{ q}^{\veces})^{2}\derecha\}.

El dígrafo de Paley es un torneo porque cada par de vértices distintos está conectado por un arco en una y solo una dirección.

El dígrafo de Paley conduce a la construcción de algunas matrices de conferencias antisimétricas y geometría de dos planos .

El género de la cuenta

Los seis vecinos de cada vértice en un gráfico de Paley de orden 13 están conectados en un ciclo para que el gráfico sea localmente cíclico . Por lo tanto, este gráfico se puede incrustar en una triangulación de Whitney de un toro , 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 se puede anidar de manera que todas sus caras sean triángulos, podemos calcular el género de la superficie resultante utilizando la característica de Euler . Bojan Mohar (2005) conjeturó que el género mínimo de una superficie en la que se puede incrustar un gráfico de Paley está en algún lugar alrededor de este valor cuando q es un cuadrado, y planteó la cuestión de si tales límites se pueden generalizar. En particular, Mohar conjeturó que los gráficos de Paley de orden cuadrado podrían incrustarse en superficies de género ${\tfrac{1}{24}}(q^{2}-13q+24)$

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

donde el término o(1) puede ser cualquier función de q tendiendo a cero cuando q tiende a infinito.

White (2001) [8] encontró una incrustación de gráficos de Paley de orden q ≡ 1 (mod 8) al generalizar la incrustación natural de un gráfico de Paley de noveno orden como una red cuadrada en un toro. Sin embargo, el género de la incrustación de Whitney es aproximadamente tres veces mayor que el límite que Mohar estableció en su conjetura.

Enlaces

↑ REAC Paley. Sobre matrices ortogonales // J. Math. física . - T. 12 . — S. 311–320 .
↑ Gráficos asimétricos // Acta Mathematica Academiae Scientiarum Hungaricae. - 1963. - T. 14 , núm. 3–4 . — S. 295–315 . -doi : 10.1007/ BF01895716 .
↑ R. L. Graham, J. H. Spencer. Una solución constructiva a un problema de torneo // Canadian Mathematical Bulletin . - 1971. - T. 14 . — págs. 45–48 . -doi : 10.4153 / CMB-1971-007-1 .
↑ Horst Sachs. Über selbstkomplementäre Graphen // Publicationes Mathematicae Debrecen. - 1962. - T. 9 . — S. 270–288 .
↑ Chung, Fan RK, R. Graham , RM Wilson,. Graps cuasi-aleatorios // Combinatorica . - 1989. - T. 9 , núm. 4 . — S. 345–362 . -doi : 10.1007/ BF02125347 .
↑ Evans, RJ; Pulham, JR; Sheehan, J. Sobre el número de subgrafos completos contenidos en ciertos gráficos // Journal of Combinatorial Theory, Series B . - 1981. - T. 30 , núm. 3 . — S. 364–371 . -doi : 10.1016 / 0095-8956(81)90054-X .
↑ Sasakura, Nobuo; Enta, Yoichi; Kagesawa, Masataka. Construcción de poleas reflexivas de rango dos con propiedades similares al paquete Horrocks-Mumford // Proc. Japan Acad., Ser. A.- 1993.- T. 69 , núm. 5 . — S. 144–148 . doi : 10.2183 /pjab.69.144 .
↑ White, A. T. Gráficos de grupos sobre superficies // Interacciones y modelos. - Amsterdam: North-Holland Mathematics Studies 188, 2001.

Baker, RD; Ebert, G. L.; Hemmeter, J.; Woldar, AJ Camarillas máximas en los gráficos Paley de orden cuadrado // J. Statist. Planificar inferencia. - 1996. - T. 56 . — págs. 33–38 . - doi : 10.1016/S0378-3758(96)00006-7 .
Broere, I.; Domán, D.; Ridley, JN Los números de camarilla y los números cromáticos de ciertos gráficos de Paley // Quaestiones Mathematicae. - 1988. - T. 11 . — S. 91–93 . doi : 10.1080 / 16073606.1988.9631945 .

Enlaces externos

Brouwer, Andries E. Paley graps (enlace inaccesible - historia ) . (indefinido) (enlace no disponible)
Mohar, Bojan. PaleyGenus.html Género de uvas Paley (2005). (indefinido) (enlace no disponible)