Je m'intéresse de plus en plus à la théorie des graphes spectraux, que je trouve fascinante, et j'ai commencé à rassembler quelques documents que je n'ai pas encore lus plus attentivement que ce que j'ai jusqu'à présent. Cependant, je suis curieux d'une déclaration apparue dans plusieurs sources...
Si est un graphe irrégulier d non orienté et S est un sous-ensemble des sommets de cardinalité ≤ | V | / 2 , appelez l' expansion de bord de S la quantitéG = ( V, E)G=(V,E)G=(V,E)réddSSS≤ | V| / 2≤|V|/2\leq |V|/2SSS ϕ ( S) : = Erége s ( S, V- S)ré⋅ | S| ⋅ | V- S|ϕ(S):=Edges(S,V−S)d⋅|S|⋅|V−S|\phi(S)...
Habituellement, on construit un graphe et pose ensuite des questions sur la décomposition des valeurs propres de la matrice d'adjacence (ou d'un parent proche comme le laplacien ) (également appelée spectre d'un graphe ). Mais qu'en est-il du problème inverse? Étant donné valeurs propres, peut-on...
J'ai lu dans de nombreux articles que déterminer la constante de Cheeger d'un graphe est -hard. Cela semble être un théorème populaire, mais je n'ai jamais trouvé ni citation ni preuve pour cette affirmation. À qui dois-je donner du crédit? Dans un vieux document (Isoperimetric Numbers of Graphs,...
Quelles sont les références de base? Existe-t-il de bonnes enquêtes de haut niveau sur SGT et ses applications à CS en général et à l'apprentissage machine en
Soit le nombre d'arbres couvrant un graphe à sommets. Il existe un algorithme qui calcule dans les opérations arithmétiques . Cet algorithme consiste à calculer , où Q est le laplacien de G et J est la matrice constituée uniquement de 1 . Pour plus d'informations sur cet algorithme, voir Biggs -...
(également demandé ici , pas de réponses) Un expanseur quantique est une distribution sur le groupe unitaire avec la propriété que: a) , b) , où \ mu_H est la mesure de Haar. Si , au lieu des distributions sur unitaries nous considérons les distributions sur les matrices de permutation, il est...
Nous savons par exemple de Koutis-Miller-Peng (basé sur les travaux de Spielman & Teng), que nous pouvons résoudre très rapidement des systèmes linéaires pour les matrices qui sont la matrice de graphes laplaciens pour certains graphes clairsemés avec des poids de bord non négatifs .Ax=bAx=bA x...
Soit un graphe connexe G = ( V , E ) avec des noeuds V = 1 ... n et des bords E . Soit w i le poids (entier) du graphe G , avec ∑ i w i = m le poids total du graphe. Le poids moyen par nœud est alors ˉ w = m / n . Soit e i = w i - ˉ w la déviation du nœudGGGG = ( V, E)G=(V,E)G = (V,E)V= 1 … nV=1…nV...
Je voulais savoir quelles sont les applications de SGT dans le domaine de la théorie de l'information et du codage et peut-être des communications. Le plus lié qui me vient à l'esprit est le travail sur les codes d'extension Michael Sipser et Daniel Spielman, "Expander Codes", IEEE Transactions on...