• E

F Nous contacter

0

# Documents  05C80 | enregistrements trouvés : 48

O

Sélection courante (0) : Tout sélectionner / Tout déselectionner

P Q

## Self-interacting walks and uniform spanning forests Peres, Yuval | CIRM H

Post-edited

2 y

Research talks

In the first half of the talk, I will survey results and open problems on transience of self-interacting martingales. In particular, I will describe joint works with S. Popov, P. Sousi, R. Eldan and F. Nazarov on the tradeoff between the ambient dimension and the number of different step distributions needed to obtain a recurrent process. In the second, unrelated, half of the talk, I will present joint work with Tom Hutchcroft, showing that the component structure of the uniform spanning forest in $\mathbb{Z}^d$ changes every dimension for $d > 8$. This sharpens an earlier result of Benjamini, Kesten, Schramm and the speaker (Annals Math 2004), where we established a phase transition every four dimensions. The proofs are based on a the connection to loop-erased random walks. In the first half of the talk, I will survey results and open problems on transience of self-interacting martingales. In particular, I will describe joint works with S. Popov, P. Sousi, R. Eldan and F. Nazarov on the tradeoff between the ambient dimension and the number of different step distributions needed to obtain a recurrent process. In the second, unrelated, half of the talk, I will present joint work with Tom Hutchcroft, showing that the ...

## Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs Massoulié, Laurent | CIRM H

Post-edited

2 y

Research talks

A non-backtracking walk on a graph is a directed path such that no edge is the inverse of its preceding edge. The non-backtracking matrix of a graph is indexed by its directed edges and can be used to count non-backtracking walks of a given length. It has been used recently in the context of community detection and has appeared previously in connection with the Ihara zeta function and in some generalizations of Ramanujan graphs. In this work, we study the largest eigenvalues of the non-backtracking matrix of the Erdos-Renyi random graph and of the Stochastic Block Model in the regime where the number of edges is proportional to the number of vertices. Our results confirm the "spectral redemption" conjecture that community detection can be made on the basis of the leading eigenvectors above the feasibility threshold. A non-backtracking walk on a graph is a directed path such that no edge is the inverse of its preceding edge. The non-backtracking matrix of a graph is indexed by its directed edges and can be used to count non-backtracking walks of a given length. It has been used recently in the context of community detection and has appeared previously in connection with the Ihara zeta function and in some generalizations of Ramanujan graphs. In this work, we ...

## Bootstrap percolation on Erdos-Renyi graphs Angel, Omer | CIRM H

Post-edited

2 y

Research talks

We consider bootstrap percolation on the Erdos-Renyi graph: given an initial infected set, a vertex becomes infected if it has at least $r$ infected neighbours. The graph is susceptible if there exists an initial set of size $r$ that infects the whole graph. We identify the critical threshold for susceptibility. We also analyse Bollobas's related graph-bootstrap percolation model.
Joint with Brett Kolesnik.

## Séminaire Bourbaki. Vol. 2011/2012:exposés 1043-1058 | Société Mathématique de France 2013

Congrès

V

- xi; 556 p.
ISBN 978-2-85629-371-3

Astérisque , 0352

Localisation : Périodique 1er étage

Algorithme d'approximation # carte brownienne # cartes planaires # champ libre gaussien # champ moyen # choix social # concentration-compacité # condition nulle # configuration polynomiale # courbe elliptique # D-module holonome # difficulté d'approximation # équation aux dérivées partielles # équations d'Einstein # équations différentielles partielles # équations non-linéaires dispersives # espaces adiques # espaces de Berkovich # espaces homogènes # espaces métriques # espaces normés # espaces perfectoïdes # existence globale # fibré de Higgs # fibré holomorphe plat # forme quartique binaire # formule de KPZ # gravité quantique # groupe de Galois motivique # groupe de Selmer # groupes de Lie # groupes quasi-fuchsiens # hamiltonien # marches aléatoires # mélange exponentiel du fibré des repères # mesures de Liouville # mesures stationnaires # métrique harmonique # modération topologique # monodromie-poids # motifs de Tate mixtes # multizêtas # nonlinéaire # norme d'uniformité # orbites coadjointes # plongement métrique # principe de transfert # programmation semi-définie # Programme de Ribe # progression arithmétique # pureté # rang # réarrangement # Relativité générale # représentations des groupes algébriques réductifs # représentations des groupes de Lie compacts # résonances en espace temps # rigidité # singularités irrégulières # stabilité orbitale # surfaces enfermées # système stellaire auto-gravitant # théorème de Lefschetz difficile # théorie de Hodge # théorie géométrique des invariants # topologie étale # trous noirs # types stablement dominés # variétés de drapeaux # variétés hyperboliques de dimension 3 # Vlasov-Poisson Algorithme d'approximation # carte brownienne # cartes planaires # champ libre gaussien # champ moyen # choix social # concentration-compacité # condition nulle # configuration polynomiale # courbe elliptique # D-module holonome # difficulté d'approximation # équation aux dérivées partielles # équations d'Einstein # équations différentielles partielles # équations non-linéaires dispersives # espaces adiques # espaces de Berkovich # espaces ...

## Random graphs'85.Based on lectures presented at the 2nd international seminar on random graphs and probabilistic methods in combinatoricsPoznan # august 5-9, 1985 Karonski, Michal ; Palka, Zbigniew | North-Holland 1987

Congrès

V

- vii; 354 p.
ISBN 978-0-444-70265-4

North-Holland mathematics studies , 0144

Localisation : Colloque RdC

## Surveys in combinatorics 2011.Papers from the 23rd British combinatorial conferenceExeter # july 3-8, 2011 Chapman, Robin | Cambridge University Press 2011

Congrès

V

- vii; 437 p.
ISBN 978-1-107-60109-3

London mathematical society lecture note series , 0392

Localisation : Collection 1er étage

combinatoires # graphe topologique # hypergraphe # graphe aléatoire

## Combinatorial stochastic processes :école d'été de probabilités de Saint-Flour XXXII#2002 Pitman, Jim ; Picard, Jean | Springer 2006

Congrès

V

- 256 p.
ISBN 978-3-540-30990-1

Lecture notes in mathematics , 1875

Localisation : Collection 1er étage

arbre aléatoire # mouvement brownien # probabilité combinatoire # processu stochastique # combinatoire asymptotique # position aléatoire

## Random discrete structuresproceedings of a workshop of the 1993-94 IMA program on emerging applications of probability Aldous, David ; Pemantle, Robin | Springer 1996

Congrès

V

ISBN 978-0-387-94623-8

The IMA volumes in mathematics and its applications , 0076

Localisation : Colloque RdC

approximation normale par méthode de Stein # arbre aléatoire # couverture universelle de graphe # distribution aléatoire de masse # distribution de probabilités sur cladogramme # ensemble régénératif # environnement aléatoire # grande déviation # graphe libre de triangle # intersection et limite # marche aléatoire transitoire # matrice positive complètement # méthode du second moment # métrique sur composition et coïncidence # processus aléatoire # recurrence amenabilité # stabilité de processus auto-organisant # structure discrète aléatoire # suite de renouvellement # théorème du cycle impaire long # tresse de jeux de minimax aléatoire # énergie et intersection de chaîne de Markov approximation normale par méthode de Stein # arbre aléatoire # couverture universelle de graphe # distribution aléatoire de masse # distribution de probabilités sur cladogramme # ensemble régénératif # environnement aléatoire # grande déviation # graphe libre de triangle # intersection et limite # marche aléatoire transitoire # matrice positive complètement # méthode du second moment # métrique sur composition et coïncidence # processus ...

## Expanding graphs :proceedings of a DIMACS workshop#May 11-14 Friedman, Joel | American Mathematical Society 1993

Congrès

V

- 142 p.
ISBN 978-0-8218-6602-3

DIMACS series in discrete mathematics and theoretical computer science , 0010

Localisation : Collection 1er étage

approche corps de fonction de graphe et diagramme de Ramanuj # construction algébrique de graphe dense de grand contour et # graphe de Cayley aléatoire et expanseur # graphe demi-plan supérieur fini et Ramanujan # graphe en expansion # graphe en expansion hautement tiré de groupe diédral # groupe et expanseur # géométrie spectral et constante de Cheeger # investigation numérique du spectre pour famille de graphe de # laplacien d'hypergraphe # seconde valeur propre et développement linéaire de graphe ré # simulation de chaîne de Markov # échantillonnage uniforme modulo ou groupe de symétrie approche corps de fonction de graphe et diagramme de Ramanuj # construction algébrique de graphe dense de grand contour et # graphe de Cayley aléatoire et expanseur # graphe demi-plan supérieur fini et Ramanujan # graphe en expansion # graphe en expansion hautement tiré de groupe diédral # groupe et expanseur # géométrie spectral et constante de Cheeger # investigation numérique du spectre pour famille de graphe de # laplacien d'hypergraphe # ...

## Ecole d'été de probabilités de Saint-Flour XXI - 1991cours donnés à l'école d'été de calcul des probabilités de Saint-Flour du 18 Août au 4 sept., 1991 Hennequin, P. L. | Springer-Verlag 1993

Congrès

V

ISBN 978-3-540-56622-9

Lecture notes in mathematics , 1541

Localisation : Collection 1er étage

branchement à valeur de mesure # calcul stochastique # distribution de Palm # fonctionnelle de Log-Laplace # mesure aléatoire # mesure de Campbell # probabilité # problème de martingale # processus de Markov naissance # processus de Markov à valeur de mesure # processus de construction à valeur de mesure et interaction # regénération # représentation d'amas de Poisson # représentation de De Finetti # retournement # structure de famille # super mouvement Brownien branchement à valeur de mesure # calcul stochastique # distribution de Palm # fonctionnelle de Log-Laplace # mesure aléatoire # mesure de Campbell # probabilité # problème de martingale # processus de Markov naissance # processus de Markov à valeur de mesure # processus de construction à valeur de mesure et interaction # regénération # représentation d'amas de Poisson # représentation de De Finetti # retournement # structure de famille # super ...

## Probabilistic combinatorics and its applicationsproceedings of a symposia held in San Francisco, CaliforniaJanv.14-15 Bollobas, Bela ; Chung, Fan R. K. ; Diaconis, Persi | American Mathematical Society 1991

Congrès

V

ISBN 978-0-8218-5500-3

Proceedings of symposia in applied mathematics , 0044

Localisation : Collection 1er étage

calcul du volume des corps convexes # chaîne de Markov se mélangeant rapidement # combinatoire probabiliste # graphe aléatoire # inégalité isopérimétrique discrète # méthode de Fourier finie

## Probabilistic problems of discrete mathematics Kolchin, V. F. | American Mathematical Society 1989

Congrès

V

- 217 p.
ISBN 978-0-8218-3123-6

Proceedings of the Steklov institute of mathematics , 0177

Localisation : Collection 1er étage

mathematique discrete # probabilite # probleme probabiliste # statistique

## Graph theory and combinatoricsproceedings of the cambridge combinatorial conference in honour of paul erdos,cambridge,trinity college,21-25 march,1983 Bollobas, Bela | Academic Press 1984

Congrès

V

ISBN 978-0-12-111760-3

Localisation : Colloque RdC

## Random hyperbolic graphs Kiwi, Marcos | CIRM H

Multi angle

y

Research talks

Random hyperbolic graphs (RHG) were proposed rather recently (2010) as a model of real-world networks. Informally speaking, they are like random geometric graphs where the underlying metric space has negative curvature (i.e., is hyperbolic). In contrast to other models of complex networks, RHG simultaneously and naturally exhibit characteristics such as sparseness, small diameter, non-negligible clustering coefficient and power law degree distribution. We will give a slow pace introduction to RHG, explain why they have attracted a fair amount of attention and then survey most of what is known about this promising infant model of real-world networks. Random hyperbolic graphs (RHG) were proposed rather recently (2010) as a model of real-world networks. Informally speaking, they are like random geometric graphs where the underlying metric space has negative curvature (i.e., is hyperbolic). In contrast to other models of complex networks, RHG simultaneously and naturally exhibit characteristics such as sparseness, small diameter, non-negligible clustering coefficient and power law degree ...

## Connected chord diagrams, bridgeless maps, and perturbative quantum field theory Yeats, Karen | CIRM H

Multi angle

y

Research talks

Rooted connected chord diagrams can be used to index certain expansions in quantum field theory. There is also a nice bijection between rooted connected chord diagrams and bridgeless maps. I will discuss each of these things as well as how the second sheds light on the first. (Based on work with Nicolas Marie, Markus Hihn, Julien Courtiel, and Noam Zeilberger.)

## Random cubic planar graphs revisited Rué, Juanjo | CIRM H

Multi angle

y

Research School

We analyze random labelled cubic planar graphs according to the uniform distribution. This model was analyzed first by Bodirsky et al. in a paper from 2007. Here we revisit and extend their work. The motivation for this revision is twofold. First, some proofs where incomplete with respect to the singularity analysis and we provide full proofs. Secondly, we obtain new results that considerably strengthen those known before. For instance, we show that the number of triangles in random cubic planar graphs is asymptotically normal with linear expectation and variance, while formerly it was only known that it is linear with high probability.
This is based on a joint work with Marc Noy (UPC) and Clément Requilé (FU Berlin - BMS).
We analyze random labelled cubic planar graphs according to the uniform distribution. This model was analyzed first by Bodirsky et al. in a paper from 2007. Here we revisit and extend their work. The motivation for this revision is twofold. First, some proofs where incomplete with respect to the singularity analysis and we provide full proofs. Secondly, we obtain new results that considerably strengthen those known before. For instance, we show ...

## Recurrence of half plane maps Angel, Omer | CIRM H

Multi angle

y

Research talks

On a graph $G$, we consider the bootstrap model: some vertices are infected and any vertex with 2 infected vertices becomes infected. We identify the location of the threshold for the event that the Erdos-Renyi graph $G(n, p)$ can be fully infected by a seed of only two infected vertices. Joint work with Brett Kolesnik.

## Random walk on random digraph Salez, Justin | CIRM H

Multi angle

y

Research talks

A finite ergodic Markov chain exhibits cutoff if its distance to equilibrium remains close to its initial value over a certain number of iterations and then abruptly drops to near 0 on a much shorter time scale. Originally discovered in the context of card shuffling (Aldous-Diaconis, 1986), this remarkable phenomenon is now rigorously established for many reversible chains. Here we consider the non-reversible case of random walks on sparse directed graphs, for which even the equilibrium measure is far from being understood. We work under the configuration model, allowing both the in-degrees and the out-degrees to be freely specified. We establish the cutoff phenomenon, determine its precise window and prove that the cutoff profile approaches a universal shape. We also provide a detailed description of the equilibrium measure. A finite ergodic Markov chain exhibits cutoff if its distance to equilibrium remains close to its initial value over a certain number of iterations and then abruptly drops to near 0 on a much shorter time scale. Originally discovered in the context of card shuffling (Aldous-Diaconis, 1986), this remarkable phenomenon is now rigorously established for many reversible chains. Here we consider the non-reversible case of random walks on sparse ...

## Anchored expansion in the hyperbolic Poisson Voronoi tessellation Paquette, Elliot | CIRM H

Multi angle

y

Research talks

We show that random walk on a stationary random graph with positive anchored expansion and exponential volume growth has positive speed. We also show that two families of random triangulations of the hyperbolic plane, the hyperbolic Poisson Voronoi tessellation and the hyperbolic Poisson Delaunay triangulation, have 1-skeletons with positive anchored expansion. As a consequence, we show that the simple random walks on these graphs have positive speed. We include a section of open problems and conjectures on the topics of stationary geometric random graphs and the hyperbolic Poisson Voronoi tessellation. We show that random walk on a stationary random graph with positive anchored expansion and exponential volume growth has positive speed. We also show that two families of random triangulations of the hyperbolic plane, the hyperbolic Poisson Voronoi tessellation and the hyperbolic Poisson Delaunay triangulation, have 1-skeletons with positive anchored expansion. As a consequence, we show that the simple random walks on these graphs have positive ...

## Spectral measures of factor of i.i.d. processes on the regular tree Backhausz, Ágnes | CIRM H

Multi angle

y

Research talks

We prove that a measure on $[-d,d]$ is the spectral measure of a factor of i.i.d. process on a vertex-transitive infinite graph if and only if it is absolutely continuous with respect to the spectral measure of the graph. Moreover, we show that the set of spectral measures of factor of i.i.d. processes and that of $\bar{d}_2$-limits of factor of i.i.d. processes are the same.

##### Codes MSC

Nuage de mots clefs ici

Ressources Electroniques

Books & Print journals

Recherche avancée

0
Z