UNE THÉORIE ALGÉBRIQUE DES CHEMINS
COMBINATOIRE SUR LES GRAPHES & ANALYSE DES RÉSEAUX
Pierre-Louis Giscard, Paul Rochet
P.-L. GISCARD
▸ Gregory Lawler (1987)
▸ Factorisation en cycles et chemins simples Pour des cycles cycles simples sont premiers
×2
w ργ1 γ2 γ3
UNE THÉORIE DES CHEMINS?
�|w.w0 ) �|w ou �|w0w, w0
P.-L. GISCARD, P. ROCHET 2/19
P.-L. GISCARD
▸ Gregory Lawler (1987)
▸ Factorisation en cycles et chemins simples Pour des cycles cycles simples sont premiers
×2
w ργ1 γ2 γ3
Une théorie des nombres pour les chemins ?!
UNE THÉORIE DES CHEMINS?
�|w.w0 ) �|w ou �|w0w, w0
P.-L. GISCARD, P. ROCHET 2/19
▸ Cartier & Foata (1969)Mots sur les arêtes eij d’un graphe, forment un monoïd M semi-commutatif eij eik ≠ eik eij eij ekl = eij eklRANDONNÉES: H ⊊M, autant d’arêtes entrantes que sortantes (cycles)
P.-L. GISCARD
COMBINATOIRE ALGÉBRIQUE DES RANDONNÉES
3/19
1) Formaliser l’observation de Lawler
P.-L. GISCARD, P. ROCHET
▸ Cartier & Foata (1969)Mots sur les arêtes eij d’un graphe, on impose eij eik ≠ eik eij eij ekl = eij ekl
Classes d’équivalences forment un monoïd M
RANDONNÉES: H ⊊M, autant d’arêtes entrantes que sortantes (cycles)
▸ Viennot (1987): empilements de pièces H = empilements de cycles simples
P.-L. GISCARD
COMBINATOIRE ALGÉBRIQUE DES RANDONNÉES
�|h.h0 ) �|h ou �|h0
Une randonnée
3/19
1) Formaliser l’observation de Lawler
h.h0 = h0.h () V(h) \ V(h0) = ;h
×2
P.-L. GISCARD, P. ROCHET
P.-L. GISCARD
COMBINATOIRE ALGÉBRIQUE DES RANDONNÉES
4/19
Le bestiaire des randonnées
×2
×2
Randonnée
Chemin
Auto-évitante
Première
P.-L. GISCARD, P. ROCHET
▸ Rota et al. (1964-1974): Théorie des nombres à partir de posets!
Poset de randonnées ordonnées par divisibilité
▸ Algèbre d’incidence : matrices Q indexées par
P.-L. GISCARD
COMBINATOIRE ALGÉBRIQUE DES RANDONNÉES 2) Comment construire une théorie?
h|h0 ) h h0
5/19P.-L. GISCARD, P. ROCHET
PH :=�H,�
I(PH) Hh ⇥ h0 ) Qh,h0 = 0, h h0 ) Qh,h0 Qh,h = 1
▸ Rota et al. (1964-1974): Théorie des nombres à partir de posets!
Poset de randonnées ordonnées par divisibilité
▸ Algèbre d’incidence : matrices Q indexées parMatrices triangulaires, 1 sur la diagonale!
P.-L. GISCARD
COMBINATOIRE ALGÉBRIQUE DES RANDONNÉES 2) Comment construire une théorie?
h|h0 ) h h0
5/19P.-L. GISCARD, P. ROCHET
PH :=�H,�
Zh,h0 := 1 () h h0
I(PH) Hh ⇥ h0 ) Qh,h0 = 0, h h0 ) Qh,h0
M := Z�1
Qh,h = 1
▸ Doubilet, Rota (1972)Débarrassons nous des matrices!
▸ Réduction:
P.-L. GISCARD
COMBINATOIRE ALGÉBRIQUE DES RANDONNÉES 2) Comment construire une théorie?
6/19P.-L. GISCARD, P. ROCHET
h1 h2, h3 h4, [h1, h2] ⇠ [h3, h4] () h2/h1 = h4/h3
Qh1,h2 = Qh3,h4 = q(h2/h1)
▸ Doubilet, Rota (1972)Débarrassons nous des matrices!
▸ Réduction:
P.-L. GISCARD
COMBINATOIRE ALGÉBRIQUE DES RANDONNÉES 2) Comment construire une théorie?
6/19P.-L. GISCARD, P. ROCHET
R(PH,⇠) �!
h1 h2, h3 h4, [h1, h2] ⇠ [h3, h4] () h2/h1 = h4/h3
I(PH)
Qh1,h2 = Qh3,h4 = q(h2/h1)
Algèbre des séries formelles sur le poset
Q !X
h2Hq(h)e�s`(h)h Z !
X
h2He�s`(h)h = ⇣(s)
▸ Doubilet, Rota (1972)Débarrassons nous des matrices!
▸ Réduction:
P.-L. GISCARD
COMBINATOIRE ALGÉBRIQUE DES RANDONNÉES 2) Comment construire une théorie?
6/19P.-L. GISCARD, P. ROCHET
R(PH,⇠) �!
h1 h2, h3 h4, [h1, h2] ⇠ [h3, h4] () h2/h1 = h4/h3
I(PH)
Qh1,h2 = Qh3,h4 = q(h2/h1)
Algèbre des séries formelles sur le poset
Q !X
h2Hq(h)e�s`(h)h Z !
X
h2He�s`(h)h = ⇣(s)
MANIP. ALGÉBRIQUES RESPECTENT LA RELATION D’ORDRE
▸ Si tout les cycles commutent
P.-L. GISCARD
Randonnees Theorie des nombres
Randonnee h Entier n
h, h0disjointes n,m copremiers
h auto-evitante n sans facteur carre
h cycle simple n premier
h chemin n = pk
Mais...
h.h0 6= h0.h nm = mn
h primitive orbit n premier
h auto-commutante n entier
.
.
.
.
.
.
... ...
......
UNE EXTENSION DE LA THÉORIE DES NOMBRES
7/19P.-L. GISCARD, P. ROCHET
THÉORÈME
R(PH,⇠) �!Théorie des nombres cas spécial
Séries de Dirichlet
P.-L. GISCARD
▸ Zêta, Möbius déjà connues Cartier & Foata (1969), Viennot (1987) pas le reste!
UNE EXTENSION DE LA THÉORIE DES NOMBRES
8/19
Randonnees Theorie des nombres
Zeta
⇣ = S1 =
Ph2H h ⇣R(s) =
Pn>0
1ns
⇣ =
1det(I�W)
Mobius
µ(h) =
((�1)
⌦(h), h auto-evitante
0, sinon.
µ(n) =
((�1)
⌦(n), n sans facteur carre
0, sinon.
Von Mangoldt
⇤(h) =
(`(p), h chemin, p|h a droite
0, sinon.
⇤(n) =
(log(p), n = pk
0, sinon.
S⇤ = Tr
h�I�W
��1i
Liouville
�(h) = (�1)
⌦(h) �(h) = (�1)
⌦(n)
S� =
1perm(I�W)
.
.
.
.
.
.
P.-L. GISCARD, P. ROCHET
P.-L. GISCARD
UNE EXTENSION DE LA THÉORIE DES NOMBRES
9/19
Randonnees Theorie des nombres
Nombre de
diviseurs
⇣2 ⇣R(s)2
Log Zeta
log ⇣ =
Ph
⇤(h)`(h) h log ⇣R(s) =
Pn
⇤(n)log(n)
1
ns
Log-Mangoldt
`(h) =P
h0|h ⇤(h0) log(n) =
Pd|n ⇤(n)
Fonctions
totalement
multiplicatives
f�1
=
Ph µ(h)f(h)h f�1
=
Pn
µ(n)f(n)ns
f 0/f = �P
h ⇤(h)f(h)h f 0/f =
Pn
⇤(n)f(n)ns
Fonctions
totalement
additives
�f ⇤ µ
�(h) =
(f(p), h chemin, p|h a droite
0, sinon.
(f ⇤ µ)(n) =(f(p), n = pk
0, sinon.
⇣ 0/⇣ via les
premiers
�X
�: cycle simple
`(�)det(I�W\�)det(I�W)
�P
p log pp�s
1�p�s
Serie ⌦
X
w: chemin
w = det(I�W)
X
h2H⌦(h)h
X
p,n
1
p�ns= ⇣R(s)
�1
X
n
⌦(n)
ns
.
.
.
.
.
.
P.-L. GISCARD, P. ROCHET
Si la théorie est mature on doit pouvoir l’utiliser concrètement
P.-L. GISCARD
ET ALORS?
10/19
P (z) :=X
�: cycle simple
z`(�)
P.-L. GISCARD, P. ROCHET
P.-L. GISCARD
COMBINATOIRE ALGÉBRIQUE DES RANDONNÉES
11/19
Basic projections
×2
×2
Randonnée
Chemin
Auto-évitante
Première
⇤
perm(I�W)
µ = det(I�W)
P.-L. GISCARD, P. ROCHET
⇤ � µ
P.-L. GISCARD
COMBINATOIRE ALGÉBRIQUE DES RANDONNÉES
12/19
Projections
×2
×2
Randonnée
Chemin
Auto-évitante
Première
⇤
perm(I�W)
µ = det(I�W)
µ � ⇤
P.-L. GISCARD, P. ROCHET
Si la théorie est mature on doit pouvoir l’utiliser concrètement
P.-L. GISCARD
ET ALORS?
P (z) :=X
�: cycle simple
z`(�)
‣Ca marche!
13/19
µ � ⇤ =d
dzP (z) =
X
H�GH connecte
Tr�(zAH)
|H|(I� zAH)|N(H)|�
⇤ � µ =d
dzP (z) =
X
H�G
det(�zAH)d
dzperm(I+ zAG�H)
‣ Combinatoire algébrique + théorie des nombres = 10 formules (!!)
P.-L. GISCARD, P. ROCHET
Conséquences directes: combinatoire & analyse des réseaux
P.-L. GISCARD
ET ALORS?
‣Algorithme: compter jusqu’à coûte
Meilleur algo. général si “Moins de sous-graphes induits connectés que de cycles simples”
‣ Matlab File Exchange « CycleCount » Solution à un vieux (1946) problème de sociologie
‣ Formulation en fraction continues de toute fonction de matrices
‣ Solution à des problèmes de dynamique quantiquePropagation de croyance exacte sur tout les graphes (belief prop.)
14/19
d
dzP (z) =
X
H�GH connecte
Tr�(zAH)
|H|(I� zAH)|N(H)|�
P.-L. GISCARD, P. ROCHET
O�V + E + (`! + `�)|S`|
�`
` = 20V = 130 000+
Conséquences directes: théorie des graphes
P.-L. GISCARD
ET ALORS?
‣ Génération de paires cospectrales and co-immantales par Λ !
‣ Résilience des systèmes complexes
THÉORÈME Graphes non-orientés connectés: Le poset des randonnées PH L’ensemble des commutateurs entre premiers}Invariants
parfaitsException
15/19
ET SON ENNEMI JURÉ… Graphes orientés: H tout entier ne suffit plus Il existe des PH sans graphe} Théorie des chemins
à part entière
P.-L. GISCARD, P. ROCHET
P.-L. GISCARD
LES PREMIERS LONGS Combien de polygones auto-évitants?
Asymptotique ?` ! 1
« A widely open problem » Flajolet & Sedgewick
µ` `11/32
16/19P.-L. GISCARD, P. ROCHET
P.-L. GISCARD
LES PREMIERS LONGS Combien de polygones auto-évitants?
Asymptotique ?` ! 1
« A widely open problem » Flajolet & Sedgewick
µ` `11/32
Extension semi-commutative du théorème des nombres premiers
16/19P.-L. GISCARD, P. ROCHET
P.-L. GISCARD
LES PREMIERS LONGS Combien de polygones auto-évitants?
Asymptotique ?` ! 1
« A widely open problem » Flajolet & Sedgewick
‣ Cribles d’Erathostènes-Legendre, Brun, Selberg
µ` `11/32
Extension semi-commutative du théorème des nombres premiers
‣ Idempotents algébriques (fonctions-L, ζ, Ψ, … )
‣ Abelianisation (homologie de Hochschild de H)
16/19P.-L. GISCARD, P. ROCHET
P.-L. GISCARD
LES PREMIERS LONGS Combien de polygones auto-évitants?
Asymptotique ?` ! 1
« A widely open problem » Flajolet & Sedgewick
‣ Cribles d’Erathostènes-Legendre, Brun, Selberg
µ` `11/32
Extension semi-commutative du théorème des nombres premiers
16/19
Série de polylogs ?
P.-L. GISCARD, P. ROCHET
Lin(f(�,�⇤))
Reseau Hexagonal Kagome Carre Triangulaire
�2 + log �
2 1.91 2 (ordre 0) 2.69 4.10
µ 1.85 2.56 2.64 4.15
P.-L. GISCARD
COMBINATOIRE ALGÉBRIQUE DES RANDONNÉES
17/19
Bialgèbres
×2
×2
Randonnée
Chemin
Auto-évitante
Première
P.-L. GISCARD, P. ROCHET
Hopf 1 Hopf 2
Un bialgèbre infinitésimal non-unitaire semi-commutatif
?
P.-L. GISCARD
COMBINATOIRE ALGÉBRIQUE DES RANDONNÉES
17/19
Bialgèbres
×2
×2
Randonnée
Chemin
Auto-évitante
Première
P.-L. GISCARD, P. ROCHET
?
Idempotents = projections⇤Dynkin
Euler⇤ � µ =
d
dzP (z) =
X
H�G
det(�zAH)d
dzperm(I+ zAG�H)
Euler
Eulerd
dzP (z) =
X
H�GH connecte
Tr�(zAH)
|H|(I� zAH)|N(H)|�
D log ⇣
P.-L. GISCARD
LES PREMIERS LONGS « A widely open problem » Flajolet & Sedgewick
D’autres applications
18/19
d
dzP (z) =
X
H�GH connecte
Tr�(zAH)
|H|(I� zAH)|N(H)|�
P.-L. GISCARD, P. ROCHET
P.-L. GISCARD
LES PREMIERS LONGS « A widely open problem » Flajolet & Sedgewick
D’autres applications
X
Polygones
auto-evitants
`(�) z`(�) =X
Polyominos
Tr⇣�
zAp
�Aire(p)�
I� zAp
�Perimetre(p)
⌘
La croissance asymptotique des deux cotés de cette équation est inconnue!
18/19P.-L. GISCARD, P. ROCHET
P.-L. GISCARD
VISION GLOBALE
Théorie des chemins
Bialgèbres &
Théorie des nombres
Monoïds des tracesCribles
idempotents
Paires cospectrales
Fonctions de matrices
Formules exactes &
Grands réseaux
Dynamique quantique
Résilience des systèmes complexes
Combinatoire algébrique
algorithmes d’énumération
Posets
APPROCHE LENTE ET SYSTÉMATIQUE
19/19P.-L. GISCARD, P. ROCHET
RÉFÉRENCES 1
P.-L. Giscard, P. Rochet. Algebraic Combinatorics on Trace Monoids: Extending Number Theory to Walks on Graphs. arXiv:1601.01780v2, accepté SIAM Journal on Discrete Mathematics (2016a).
P.-L. Giscard, P. Rochet. Enumerating simple paths from connected induced subgraphs. arXiv:1606.00289 (2016b).
P.-L. Giscard, P. Rochet, R. C. Wilson. An Hopf algebra for counting simple cycles. arXiv:1607.00902 (2016c).
P.-L. Giscard, P. Rochet, R. C. Wilson. Evaluating balance on social networks from their simple cycles. arXiv:1606.03347, accepté Journal of Complex Networks (2016d).
P.-L. Giscard, N. Kriege, and R. C. Wilson. A general purpose algorithm for counting simple cycles and simple paths of any length. arXiv:1612.05531 (2016e).
P.-L. Giscard, Z. Choo, S. Thwaite, D. Jaksch. Exact Inference on Gaussian Graphical Models of Arbitrary Topology using Path-Sums. Journal of Machine Learning Research 17, 1-19 (2016f).
N. Kriege, P.-L. Giscard, R. C. Wilson. On Valid Optimal Assignment Kernels and Applications to Graph Classification. 29th Conference on Neural Information Processing Systems (NIPS) (2016g).
RÉFÉRENCES 2
P. Cartier, D. Foata. Problèmes combinatoires de commutation et réarrangements. Lecture notes in mathematics, 85 (1969).
G. X. Viennot. Heaps of pieces, i: Basic denitions and combinatorial lemmas. Annals of the New York Academy of Sciences, 576, pp. 542-570 (1989).