Structural Limits in Combinatorics

• Academic year of topic announcement: 2016/2017
• Thesis type: dissertation
• Thesis language: angličtina
• Department: Computer Science Institute of Charles University (32-IUUK)
• Supervisor: prof. RNDr. Jaroslav Nešetřil, DrSc.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 07.09.2017
• Date of assignment: 07.09.2017
• Confirmed by Study dept. on: 07.09.2017

Preliminary scope of work

L'analyse structurelle des grands r�eseaux d'interactions est l'un des enjeux
contemporains majeurs, qui concerne aussi bien les sciences sociales que la bio-
logie, la physique, l'informatique, et les math�ematiques. L'objectif d'une telle
analyse est de pouvoir fournir une repr�esentation d'un grand r�eseau sous la
forme d'un � mod�ele �, c'est-�a-dire d'en construire une approximation com-
pacte qui en reproduise les principales caract�eristiques. L'existence d'une telle
approximation est intrins�equement li�ee �a d'autres probl�ematiques :
| la notion de limite d'un r�eseau �evoluant dans le temps,
| la validation des m�ethodes exp�erimentales d'estimation de certaines pro-
pri�et�es d'un grand r�eseau au moyen d'�echantillonnages al�eatoires.
L'�etude des propri�et�es limites des grands graphes a re�cu r�ecemment une at-
tention importante, principalement dans deux directions : les limites de graphes
de degr�es born�es [1] et les limites de graphes denses [4]. Ces d�eveloppements
sont expos�es en profondeur dans la monographie r�ecente de Lov�asz [3]. Un for-
malisme uni�ant ces �etudes a �et�e propos�e tr�es r�ecemment par Ne�set�ril et Ossona
de Mendez, qui repose sur les notions de limite FO et d'appariement de Stone
[6, 7]. Pr�ecisemment, l'appariement de Stone h�;Gi d'une formule du premier
ordre � (de variables libres Fv(�)) et d'un graphe G est d�e�ni par l'expression
h�;Gi =
jf(v1; : : : ; vjFv(�)j) 2 GjFv(�)j : G j= �(v1; : : : ; vjFv(�)j)gj
jGjjFv(�)j :
En d'autres termes, h�;Gi est la probabilit�e que la formule � soit satisfaite
dans G pour une interpretation al�eatoire des variables libres par des sommets
de G choisis al�eatoirement (ind�ependement et uniform�ement) dans l'ensemble
des sommets de G.
L'appariement de Stone induit une notion de convergence : une s�equence de
graphes (Gn)n2N est FO-convergente si, pour toute formule du premier ordre
(dans le langage des graphes), les valeurs h�;Gni convergent lorsque n ! 1.
1
La th�ese propos�ee portera sur l'�etude des propri�et�es limites de structures
combinatoires. Elle se d�eroulera en cotutelle avec l'Universit�e Charles de Prague
(sous la direction de Jarsolav Ne�set�ril), et s'int�egrera au cadre du Laboratoire
Europ�een Associ�e Struco, qui est port�e par l'Universit�e Paris-Diderot et l'Uni-
versit�e Charles de Prague. Durant se th�ese, le doctorant passera un minimum de
six mois au sein de l'universit�e de Prague. �A
Paris, le doctorant sera coencadr�e
par Patrice Ossona de Mendez (Centre d'Analyse et de Math�ematique Sociales)
et Pierre Charbit (Laboratoire d'Informatique Algorithmique : Fondements et
Applications).
Le travail de recherche comportera des aspects th�eoriques | en connection
avec l'alg�ebre, l'analyse fonctionelle, les probabilit�es et la th�eorie des mod�eles
| ainsi que des aspects algorithmiques, tels que l'approximation de structures,
l'analyse spectrale de sous-structures �echantillonn�ees, etc.
Des collaborations transverses sont envisag�ees au sein du CAMS :
| discr�etisation des mod�eles continus de perception visuelle, en collabora-
tion avec Allesandro Sarti, dans le cadre du projet � Human Brain � [2]
(en particulier �etude de la convergence spectrale d'�echantillonnage du
noyau de Perona et Freeman[8]) ;
| l'�etude de la stabilit�e des solutions d'�equations de di�usion dans un r�eseau
convergeant structurellement dans le temps [5].
R�ef�erences
[1] I. Benjamini and O. Schramm, Recurrence of distibutional limits of �nite
planar graphs, Electron. J. Probab. 6 (2001), no. 23, 13pp.
[2] G. Citti and A. Sarti, A cortical based model of perceptual completion in
the roto-translation space, Journal of Mathematical Imaging and Vision 24
(2006), no. 3, 307{326.
[3] L Lov�asz, Large networks and graph limits, Colloquium Publications, vol. 60,
American Mathematical Society, 2012.
[4] L. Lov�asz and B. Szegedy, Limits of dense graph sequences, J. Combin.
Theory Ser. B 96 (2006), 933{957.
[5] G.S. Medvedev, The nonlinear heat equation on dense graphs and graph
limits, arXiv :1302.5804 [nlin.AO], 2013.
[6] J. Ne�set�ril and P. Ossona de Mendez, A model theory approach to structu-
ral limits, Commentationes Mathematic� Universitatis Carolin� 53 (2012),
no. 4, 581{603.
[7] , A uni�ed approach to structural limits (with application to the study
of limits of graphs with bounded tree-depth), arXiv :1303.6471v2 [math.CO],
October 2013.
[8] P. Perona and W. Freeman, A factorization approach to grouping, Computer
Vision | ECCV'98 (Hans Burkhardt and Bernd Neumann, eds.), Lecture
Notes in Computer Science, vol. 1406, Springer Berlin Heidelberg, 1998,
pp. 655{670.