Graphique de Paley

En mathématiques , les graphes de Paley sont des graphes non orientés construits à partir des éléments d'un corps fini approprié en reliant les paires d'éléments qui diffèrent par un résidu quadratique . Les graphes de Paley forment une famille infinie de graphes de conférence , qui induisent une famille infinie de matrices de conférence symétriques . Les graphes de Paley permettent d'appliquer des outils de la théorie des graphes à la théorie des nombres des résidus quadratiques et possèdent des propriétés intéressantes qui les rendent utiles en théorie des graphes de manière plus générale.

Les graphes de Paley doivent leur nom à Raymond Paley . Ils sont étroitement liés à la construction de Paley permettant de construire des matrices de Hadamard à partir de résidus quadratiques. Ils ont été introduits indépendamment comme graphes par et Rényi (1963) . Sachs s'y est intéressé pour leurs propriétés d'auto-complémentarité, tandis qu'Erdős et Rényi ont étudié leurs symétries.

Les digraphes de Paley sont des analogues orientés des graphes de Paley qui produisent des matrices de conférence antisymétriques . Ils ont été introduits par et Spencer (1971) (indépendamment de Sachs, Erdős et Rényi) comme moyen de construire des tournois possédant une propriété jusque-là réservée aux tournois aléatoires : dans un digraphe de Paley, tout petit sous-ensemble de sommets est dominé par un autre sommet.

Définition

Soit q une puissance première telle que ${ extstyle q\equiv 1{\pmod {4 <semantics><mrow><mstyle><mi>q</mi><mo>≡</mo><mn>1</mn><mrow><mspace></mspace><mo>(</mo><mi>mod</mi><mspace></mspace><mn>4</mn><mo>)</mo></mrow></mstyle></mrow><annotation>{ extstyle q\equiv 1{\pmod {4}}}</annotation></semantics></math><img src=$ q doit être soit une puissance quelconque d'un nombre premier congru à 1 modulo 4 (un nombre premier pythagoricien ), soit une puissance paire d'un nombre premier impair non pythagoricien. Ce choix de q implique que dans l'unique corps fini F _q d'ordre q , l'élément −1 possède une racine carrée.

Soit maintenant V = F _q et soit

{\displaystyle E=\left\{\{a,b\}\ :\ a-b\in (\mathbf {F} _{q}^{ imes })^{2} ight\ <semantics><mrow><mstyle><mi>E</mi><mo>=</mo><mrow><mo>{</mo><mrow><mo>{</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>}</mo><mtext> </mtext><mo>:</mo><mtext> </mtext><mi>un</mi><mo>−</mo><mi>b</mi><mo>∈</mo><mo>(</mo><msubsup><mrow><mi>F</mi></mrow><mrow><mi>q</mi></mrow><mrow><mo>×</mo></mrow></msubsup><msup><mo>)</mo><mrow><mn>2</mn></mrow></msup></mrow><mo>}</mo></mrow></mstyle></mrow><annotation>{\displaystyle E=\left\{\{a,b\}\</annotation></semantics></math>:\ ab\in (\mathbf {F} _{q}^{ imes })^{2} ight\}} </span><img src=

Si une paire { a , b } est incluse dans E , elle l'est quel que soit l'ordre de ses deux éléments. En effet, a − b = −( b − a ), et −1 est un carré, d'où il découle que a − b est un carré si et seulement si b − a est un carré.

Par définition, G = ( V , E ) est le graphe de Paley d'ordre q .

La séquence des ordres des graphes de Paley commence

1, 5, 9, 13, 17, 25, 29, 37, 41, 49, 53, 61, 73, ... dans l' OEIS )

Exemple

Pour q = 13, le corps Fq se réduit à l'arithmétique des entiers modulo 13. Les nombres dont la racine carrée est modulo 13 sont_:

±1 (racines carrées ±1 pour +1, ±5 pour − 1)
±3 (racines carrées ±4 pour +3, ±6 pour − 3)
±4 (racines carrées ±2 pour +4, ±3 pour − 4).

Ainsi, dans le graphe de Paley, nous formons un sommet pour chacun des entiers de la plage [0,12], et connectons chaque entier x à six voisins : x ± 1 (mod 13), x ± 3 (mod 13) et x ± 4 (mod 13).

Propriétés

Les graphes de Paley sont auto-complémentaires : le complémentaire de tout graphe de Paley lui est isomorphe. Un isomorphisme possible est obtenu par l’application qui associe à un sommet , où .

Les graphes de Paley sont des graphes fortement réguliers , avec des paramètres

{\displaystyle srg\left(q,{ frac {1}{2}}(q-1),{ frac {1}{4}}(q-5),{ frac {1}{4}}(q-1) ight). <semantics><mrow><mstyle><mi>s</mi><mi>r</mi><mi>g</mi><mrow><mo>(</mo><mrow><mi>q</mi><mo>,</mo><mrow><mstyle><mfrac><mn>1</mn><mn>2</mn></mfrac></mstyle></mrow><mo>(</mo><mi>q</mi><mo>−</mo><mn>1</mn><mo>)</mo><mo>,</mo><mrow><mstyle><mfrac><mn>1</mn><mn>4</mn></mfrac></mstyle></mrow><mo>(</mo><mi>q</mi><mo>−</mo><mn>5</mn><mo>)</mo><mo>,</mo><mrow><mstyle><mfrac><mn>1</mn><mn>4</mn></mfrac></mstyle></mrow><mo>(</mo><mi>q</mi><mo>−</mo><mn>1</mn><mo>)</mo></mrow><mo>)</mo></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle srg\left(q,{ frac {1}{2}}(q-1),{ frac {1}{4}}(q-5),{ frac {1}{4}}(q-1) ight).}</annotation></semantics></math></span><img src=

Ceci découle du fait que le graphe est arc-transitif et auto-complémentaire. Les graphes fortement réguliers dont les paramètres sont de cette forme (pour un 1 , avec zéro sur la diagonale, et dont le produit par leur transposée est un multiple scalaire de la matrice identité .

Les valeurs propres des graphes de Paley sont ${\displaystyle { frac {1}{2}}(q-1) <semantics><mrow><mstyle><mrow><mstyle><mfrac><mn>1</mn><mn>2</mn></mfrac></mstyle></mrow><mo>(</mo><mi>q</mi><mo>−</mo><mn>1</mn><mo>)</mo></mstyle></mrow><annotation>{\displaystyle { frac {1}{2}}(q-1)}</annotation></semantics></math><img src=$ ${\displaystyle { frac {1}{2}}(-1\pm {\sqrt {q}}) <semantics><mrow><mstyle><mrow><mstyle><mfrac><mn>1</mn><mn>2</mn></mfrac></mstyle></mrow><mo>(</mo><mo>−</mo><mn>1</mn><mo>±</mo><mrow><msqrt><mi>q</mi></msqrt></mrow><mo>)</mo></mstyle></mrow><annotation>{\displaystyle { frac {1}{2}}(-1\pm {\sqrt {q}})}</annotation></semantics></math><img src=$ ${\displaystyle { frac {1}{2}}(q-1) <semantics><mrow><mstyle><mrow><mstyle><mfrac><mn>1</mn><mn>2</mn></mfrac></mstyle></mrow><mo>(</mo><mi>q</mi><mo>−</mo><mn>1</mn><mo>)</mo></mstyle></mrow><annotation>{\displaystyle { frac {1}{2}}(q-1)}</annotation></semantics></math><img src=$

Si du graphe de Paley satisfait les bornes suivantes :

{\displaystyle \displaystyle {\frac {q-{\sqrt {q}}}{4}}\leq i(G)\leq {\frac {q-1}{4}}. <semantics><mrow><mstyle><mstyle><mrow><mfrac><mrow><mi>q</mi><mo>−</mo><mrow><msqrt><mi>q</mi></msqrt></mrow></mrow><mn>4</mn></mfrac></mrow><mo>≤</mo><mi>je</mi><mo>(</mo><mi>G</mi><mo>)</mo><mo>≤</mo><mrow><mfrac><mrow><mi>q</mi><mo>−</mo><mn>1</mn></mrow><mn>4</mn></mfrac></mrow><mo>.</mo></mstyle></mstyle></mrow><annotation>{\displaystyle \displaystyle {\frac {q-{\sqrt {q}}}{4}}\leq i(G)\leq {\frac {q-1}{4}}.}</annotation></semantics></math></span><img src=

Lorsque grand ) le même que pour les graphes aléatoires, et les grands ensembles de sommets ont approximativement le même nombre d'arêtes que dans les graphes aléatoires.

Le graphe de Paley d'ordre 9 est un graphe localement linéaire , un graphe de tour et le graphe du duoprisme 3-3 .
Le graphe de Paley d'ordre 13 a une épaisseur de livre de 4 et un numéro de file d'attente de 3.
Le graphe de Paley d'ordre 17 est l'unique plus grand graphe G tel que ni G ni son complémentaire ne contiennent un sous-graphe complet à 4 sommets. Il s'ensuit que le nombre de Ramsey R (4, 4) = 18.
Le graphe de Paley d'ordre 101 est actuellement le plus grand graphe connu G tel que ni G ni son complément ne contiennent un sous-graphe complet à 6 sommets.
Sasukara et al. (1993) utilisent des graphes de Paley pour généraliser la construction du fibré de Horrocks–Mumford .

digraphes de Paley

Soit q une puissance d'un nombre premier telle que q ≡ 3 (mod 4). Ainsi, le corps fini d'ordre q , F _q , n'a pas de racine carrée de −1 . Par conséquent, pour toute paire ( a , b ) d'éléments distincts de F _q , soit a − b , soit b − a , mais pas les deux, est un carré. Le digraphe de Paley est le graphe orienté dont l'ensemble des sommets est V = F _q et l'ensemble des arcs est Σ q ...

{\displaystyle A=\left\{(a,b)\in \mathbf {F} _{q} imes \mathbf {F} _{q}\ :\ b-a\in (\mathbf {F} _{q}^{ imes })^{2} ight\}. <semantics><mrow><mstyle><mi>UN</mi><mo>=</mo><mrow><mo>{</mo><mrow><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo><mo>∈</mo><msub><mrow><mi>F</mi></mrow><mrow><mi>q</mi></mrow></msub><mo>×</mo><msub><mrow><mi>F</mi></mrow><mrow><mi>q</mi></mrow></msub><mtext> </mtext><mo>:</mo><mtext> </mtext><mi>b</mi><mo>−</mo><mi>un</mi><mo>∈</mo><mo>(</mo><msubsup><mrow><mi>F</mi></mrow><mrow><mi>q</mi></mrow><mrow><mo>×</mo></mrow></msubsup><msup><mo>)</mo><mrow><mn>2</mn></mrow></msup></mrow><mo>}</mo></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle A=\left\{(a,b)\in \mathbf {F} _{q} imes \mathbf {F} _{q}\</annotation></semantics></math>:\ ba\in (\mathbf {F} _{q}^{ imes })^{2} ight\}.} </span><img src=

Le digraphe de Paley est un tournoi car chaque paire de sommets distincts est reliée par un arc dans une seule et unique direction.

Le digraphe de Paley conduit à la construction de certaines matrices de conférence antisymétriques et de géométries biplanaires .

Genre

Dans le graphe de Paley d'ordre 13, les six voisins de chaque sommet sont liés par un cycle ; autrement dit, le graphe est localement cyclique . Par conséquent, ce graphe peut être plongé comme une triangulation de Whitney d'un tore , où chaque face est un triangle et chaque triangle est une face. Plus généralement, si tout graphe de Paley d'ordre q pouvait être plongé de sorte que toutes ses faces soient des triangles, on pourrait calculer le genre de la surface résultante à l'aide de la caractéristique d'Euler . ${\displaystyle { frac {1}{24}}(q^{2}-13q+24) <semantics><mrow><mstyle><mrow><mstyle><mfrac><mn>1</mn><mn>24</mn></mfrac></mstyle></mrow><mo>(</mo><msup><mi>q</mi><mrow><mn>2</mn></mrow></msup><mo>−</mo><mn>13</mn><mi>q</mi><mo>+</mo><mn>24</mn><mo>)</mo></mstyle></mrow><annotation>{\displaystyle { frac {1}{24}}(q^{2}-13q+24)}</annotation></semantics></math><img src=$ q est un carré, et se demande si une telle borne pourrait être valable de manière plus générale. Plus précisément, Mohar conjecture que les graphes de Paley d'ordre carré peuvent être plongés dans des surfaces de genre q.

{\displaystyle (q^{2}-13q+24)\left({ frac {1}{24}}+o(1) ight), <semantics><mrow><mstyle><mo>(</mo><msup><mi>q</mi><mrow><mn>2</mn></mrow></msup><mo>−</mo><mn>13</mn><mi>q</mi><mo>+</mo><mn>24</mn><mo>)</mo><mrow><mo>(</mo><mrow><mrow><mstyle><mfrac><mn>1</mn><mn>24</mn></mfrac></mstyle></mrow><mo>+</mo><mi>o</mi><mo>(</mo><mn>1</mn><mo>)</mo></mrow><mo>)</mo></mrow><mo>,</mo></mstyle></mrow><annotation>{\displaystyle (q^{2}-13q+24)\left({ frac {1}{24}}+o(1) ight),}</annotation></semantics></math></span><img src=

où le terme o(1) peut être n'importe quelle fonction de q qui tend vers zéro à la limite lorsque q tend vers l'infini.

q ≡ 1 (mod 8) qui sont hautement symétriques et auto-duaux, généralisant un plongement naturel du graphe de Paley d'ordre 9 sous la forme d'une grille carrée 3×3 sur un tore. Cependant, le genre des plongements de White est environ trois fois supérieur à la borne conjecturée par Mohar.

Pour en savoir plus

Baker, RD; Ebert, GL; Hemmeter, J.; Woldar, AJ (1996). « Cliques maximales dans le graphe de Paley d'ordre carré ». J. Statist. Plann. Inference . 56 : 33–38 . doi : 10.1016/S0378-3758(96)00006-7 .
Broere, I.; Döman, D.; Ridley, JN (1988). « Les nombres de cliques et les nombres chromatiques de certains graphes de Paley ». Quaestiones Mathematicae . 11 : 91– 93. doi : 10.1080/16073606.1988.9631945 .