Publication

Expanding graphs, Ramanujan graphs, and 1-factor perturbations

Antoine Musitelli
2006
Journal Articles

Résumé

We construct (k±1)-regular graphs which provide sequences of expanders by adding or substracting appropriate 1- factors from given sequences of k- regular graphs. We compute numerical examples in a few cases for which the given sequences are from the work of Lubotzky, Phillips, and Sarnak (with k − 1 the order of a finite field). If k + 1 = 7, our construction results in a sequence of 7- regular expanders with all spectral gaps at least 6−2√5 ≈ 1.52; the corresponding minoration for a sequence of Ramanujan 7- regular graphs (which is not known to exist) would be 7 − 2√6 ≈ 2.10.

Source officielle

https://infoscience.epfl.ch/entities/publication/9357b184-f09b-4b08-ae75-b6c66c581801

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Antoine Musitelli
2006
Journal Articles

Résumé

Source officielle

https://infoscience.epfl.ch/entities/publication/9357b184-f09b-4b08-ae75-b6c66c581801

À propos de ce résultat

Concepts associés (32)

Taux d'expansion (théorie des graphes)

En mathématiques, et plus particulièrement en théorie des graphes, le taux d'expansion d'un graphe est une mesure de connectivité de ce graphe. Informellement, un grand taux d'expansion veut dire que n'importe quel sous-ensemble de sommets relativement petit possède beaucoup de connexions avec le reste du graphe. Cette mesure est surtout utilisée en raison des propriétés intéressantes des graphes ayant un fort taux d'expansion, parfois appelés graphes expanseurs. On les retrouve notamment en informatique théorique.

Théorie spectrale des graphes

En mathématiques, la théorie spectrale des graphes s'intéresse aux rapports entre les spectres des différentes matrices que l'on peut associer à un graphe et ses propriétés. C'est une branche de la théorie algébrique des graphes. On s'intéresse en général à la matrice d'adjacence et à la matrice laplacienne normalisée. Soit un graphe , où désigne l'ensemble des sommets et l'ensemble des arêtes. Le graphe possède sommets, notés et arêtes, notées .

Graphe régulier

En théorie des graphes, un graphe régulier est un graphe où tous les sommets ont le même nombre de voisins, c'est-à-dire le même degré ou valence. Un graphe régulier dont les sommets sont de degré est appelé un graphe -régulier ou graphe régulier de degré . Un graphe 0-régulier est un ensemble de sommets déconnectés; un graphe 1-régulier a un nombre pair de sommets et est un ensemble d'arêtes déconnectées ou couplage; enfin, un graphe 2-régulier est un ensemble de cycles déconnectés.

Afficher plus

Publications associées (4)

Afficher plus

Expanding graphs, Ramanujan graphs, and 1-factor perturbations

Chattez avec Graph Search

Isogeometric Analysis And Proper Orthogonal Decomposition For The Acoustic Wave Equation

Reconstruction of Images from Gabor Graphs with Applications in Facial Image Processing

On the inapproximability of independent domination in 2P3-free perfect graphs