Graphe de Ramanujan

Article connexe : théorie des graphes extrémaux.

Un graphe de Ramanujan, nommé d'après Srinivasa Ramanujan, est un graphe régulier dont le gap spectral est presque aussi large que possible. De tels graphes sont d'excellents graphes extenseurs. Autrement dit, il s'agit d'une famille de graphes où chaque sommet a un même degré (régulier) et les deux valeurs propres les plus élevées ont une différence presque aussi grande que possible.

Parmi les graphes de Ramanujan, on compte les cliques, les biparti complet $K n, n$ et le graphe de Petersen. Comme le fait remarquer Murty^[1], les graphes de Ramanujan « regroupent diverses branches des mathématiques, telles que la théorie des nombres, la théorie des représentations et la géométrie algébrique ».

Définition

Soit $G$ un graphe connecté $d$ -régulier ayant $n$ sommets, et soient $\lambda_0 \geq \lambda_1 \geq \ldots \geq \lambda_{n-1}$ les valeurs propres de la matrice d'adjacence de $G$ (voir théorie spectrale des graphes). Comme $G$ est connecté et $d$ -régulier, ses valeurs propres vérifient $d = \lambda_0 \geq \lambda_1 \geq \ldots \geq \lambda_{n-1} \geq -d$ . A chaque fois qu'il existe $λ i$ tel que $| λ i | < d$ , on définit

$\lambda(G) = \max_{|\lambda_i| < d} |\lambda_i|.\,$

Un graphe $d$ -régulier $G$ est un graphe de Ramanujan si $λ(G)$ est défini et vaut $\lambda(G) \leq 2\sqrt{d-1}$ .

Extrémalité des graphes de Ramanujan

Pour $d$ fixé et $n$ n, le graphe de Ramanujan $d$ -régulier à $n$ sommets Ramanujan minimise $λ(G)$ . Si $G$ est un graphe $d$ -régulier de diamètre $m$ , un théorème d'Alon Nilli^[2] donne :

$\lambda_1 \geq 2\sqrt{d-1} - \frac{2\sqrt{d-1} - 1}{m}.$

Lorsque $G$ est $d$ -régulier et connecté sur au moins trois de ses sommets, $| λ 1 | < d$ , d'où $\lambda(G) \geq \lambda_1$ . Soit $\mathcal{G}_n^d$ l'ensemble de tous les graphes $d$ -réguliers $G$ ayant au moins $n$ sommets. Comme le diamètre minimal de ces graphes $\mathcal{G}_n^d$ tend vers l'infini pour $d$ fixé et $n$ tendant vers l'infini, le théorème de Nilli implique le théorème d'Alon et Boppana, démontré plus tôt, qui affirme :

$\lim_{n \to \infty} \inf_{G \in \mathcal{G}_n^d} \lambda(G) \geq 2\sqrt{d-1}.$

Construction

La construction de graphes de Ramanujan se fait souvent à l'aide de graphes de Ramanujan $p + 1$ -réguliers, pour tout $p$ premier et tel que p ≡ 1 (mod 4). Leur preuve utilise la conjecture de Ramanujan, ce qui a donné leur nom aux graphes. Morgenstern étendit la construction à toutes les puissances de nombres premiers impairs.

Notes et références

↑ (en) M. Ram Murty, « Ramanujan Graphs », dans J.RamanujanMath.Soc., vol. 18, n^o 1, 2003, p. 20 [texte intégral (page consultée le 3 novembre 2009)]
↑ (en) Alon Nilli, On the second eigenvalue of a graph, Discrete Mathematics, volume 91, numéro 2, pages 207-210, 1991.

(en) Guiliana Davidoff et Peter Sarnak, Alain Valette, Elementary number theory, group theory and Ramanjuan graphs, vol. 55, Cambridge University Press, 2003 (ISBN 0-521-53143-8) (OCLC 50253269)
Alexander Lubotzky, R. Phillips, Peter Sarnak, « Ramanujan graphs », dans Combinatorica, vol. 8, 1988, p. 261–277 [lien DOI]
Moshe Morgenstern, « Existence and Explicit Constructions of q+1 Regular Ramanujan Graphs for Every Prime Power q », dans J. Combinatorial Theory, Series B, vol. 62, 1994, p. 44–62 [lien DOI]

Liens externes

(en) M. Ram Murty, État de l'art

Portail de l'informatique théorique

Catégorie :

Famille de graphes

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Graphe de Ramanujan de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants … Wikipédia en Français
Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… … Wikipédia en Français
Liste de conjectures mathématiques — Ce qui suit est une liste de conjectures mathématiques, non exhaustive. Elles sont divisées en quatre sections, en accord avec leur état en 2011. Voir aussi : Conjecture d Erdős (en), qui liste des conjectures de Paul Erdős et de ses… … Wikipédia en Français
Fonction zêta de Riemann — La fonction zêta de Riemann ζ(s) dans le plan complexe. La couleur d un point s code la valeur de ζ(s) : des couleurs vives indiquent des valeurs proches de 0 et la nuance indique l argument de la valeur. Le point blanc pour s = 1… … Wikipédia en Français
Partition d'un entier — Pour les articles homonymes, voir Partition. En particulier en mathématiques, ne pas confondre avec la notion de partition de l unité ni celle de partition d un ensemble … Wikipédia en Français
Fonction Zeta de Riemann — Fonction zêta de Riemann En mathématiques, la fonction ζ de Riemann est une fonction analytique complexe qui est apparue essentiellement dans la théorie des nombres premiers. La position de ses zéros complexes est liée à la répartition des… … Wikipédia en Français
Fonction Zêta De Riemann — En mathématiques, la fonction ζ de Riemann est une fonction analytique complexe qui est apparue essentiellement dans la théorie des nombres premiers. La position de ses zéros complexes est liée à la répartition des nombres premiers. Elle est… … Wikipédia en Français
Fonction dzêta de Riemann — Fonction zêta de Riemann En mathématiques, la fonction ζ de Riemann est une fonction analytique complexe qui est apparue essentiellement dans la théorie des nombres premiers. La position de ses zéros complexes est liée à la répartition des… … Wikipédia en Français
Fonction zeta de Riemann — Fonction zêta de Riemann En mathématiques, la fonction ζ de Riemann est une fonction analytique complexe qui est apparue essentiellement dans la théorie des nombres premiers. La position de ses zéros complexes est liée à la répartition des… … Wikipédia en Français
Fonction zéta — Fonction zêta de Riemann En mathématiques, la fonction ζ de Riemann est une fonction analytique complexe qui est apparue essentiellement dans la théorie des nombres premiers. La position de ses zéros complexes est liée à la répartition des… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Graphe de Ramanujan

Sommaire

Définition

Extrémalité des graphes de Ramanujan

Construction

Notes et références

Liens externes

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

Graphe de Ramanujan

Sommaire

Définition

Extrémalité des graphes de Ramanujan

Construction

Notes et références

Liens externes

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link