m
• D

F Nous contacter

0

# Documents  05C80 | enregistrements trouvés : 23

O

P Q

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Post-edited  Bootstrap percolation on Erdos-Renyi graphs Angel, Omer (Auteur de la Conférence) | CIRM (Editeur )

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.

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Post-edited  Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs Massoulié, Laurent (Auteur de la Conférence) | CIRM (Editeur )

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 ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Post-edited  Self-interacting walks and uniform spanning forests Peres, Yuval (Auteur de la Conférence) | CIRM (Editeur )

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 ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Post-edited  Graphons and graphexes as limits of sparse graphs - lecture 1 Chayes, Jennifer Tour (Auteur de la Conférence) | CIRM (Editeur )

Graphons and graphexes are limits of graphs which allow us to model and estimate properties of large-scale networks. In this pair of talks, we review the theory of dense graph limits, and give two alterative theories for limits of sparse graphs - one leading to unbounded graphons over probability spaces, and the other leading to bounded graphons (and graphexes) over sigma-finite measure spaces. Talk I, given by Jennifer, will review the general theory, highlight the unbounded graphons, and show how they can be used to consistently estimate properties of large sparse networks. This talk will also give an application of these sparse graphons to collaborative filtering on sparse bipartite networks. Talk II, given by Christian, will recast limits of dense graphs in terms of exchangeability and the Aldous Hoover Theorem, and generalize this to obtain sparse graphons and graphexes as limits of subgraph samples from sparse graph sequences. This will provide a dual view of sparse graph limits as processes and random measures, an approach which allows a generalization of many of the well-known results and techniques for dense graph sequences.
Graphons and graphexes are limits of graphs which allow us to model and estimate properties of large-scale networks. In this pair of talks, we review the theory of dense graph limits, and give two alterative theories for limits of sparse graphs - one leading to unbounded graphons over probability spaces, and the other leading to bounded graphons (and graphexes) over sigma-finite measure spaces. Talk I, given by Jennifer, will review the general ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Post-edited  Graphons and graphexes as limits of sparse graphs - lecture 2 Borgs, Christian (Auteur de la Conférence) | CIRM (Editeur )

Graphons and graphexes are limits of graphs which allow us to model and estimate properties of large-scale networks. In this pair of talks, we review the theory of dense graph limits, and give two alterative theories for limits of sparse graphs - one leading to unbounded graphons over probability spaces, and the other leading to bounded graphons (and graphexes) over sigma-finite measure spaces. Talk I, given by Jennifer, will review the general theory, highlight the unbounded graphons, and show how they can be used to consistently estimate properties of large sparse networks. This talk will also give an application of these sparse graphons to collaborative filtering on sparse bipartite networks. Talk II, given by Christian, will recast limits of dense graphs in terms of exchangeability and the Aldous Hoover Theorem, and generalize this to obtain sparse graphons and graphexes as limits of subgraph samples from sparse graph sequences. This will provide a dual view of sparse graph limits as processes and random measures, an approach which allows a generalization of many of the well-known results and techniques for dense graph sequences.
Graphons and graphexes are limits of graphs which allow us to model and estimate properties of large-scale networks. In this pair of talks, we review the theory of dense graph limits, and give two alterative theories for limits of sparse graphs - one leading to unbounded graphons over probability spaces, and the other leading to bounded graphons (and graphexes) over sigma-finite measure spaces. Talk I, given by Jennifer, will review the general ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Multi angle  Compter et optimiser avec les graphes unimodulaires - Cours 1 Bordenave, Charles (Auteur de la Conférence) | CIRM (Editeur )

L'objectif de ce mini-cours est de présenter de la façon la plus élémentaire possible la convergence faible locale des graphes introduite par Benjamini et Schramm en 2001 et développée par Aldous et Steele (2004), Aldous et Lyons (2007). Nous montrerons comment cette notion peut être utilisée dans des dénombrements asymptotiques et dans des problèmes d'optimisation combinatoire.

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Multi angle  Compter et optimiser avec les graphes unimodulaires - Cours 2 Bordenave, Charles (Auteur de la Conférence) | CIRM (Editeur )

L’objectif de ce mini-cours est de présenter de la façon la plus élémentaire possible la convergence faible locale des graphes introduite par Benjamini et Schramm en 2001 et développée par Aldous et Steele (2004), Aldous et Lyons (2007). Nous montrerons comment cette notion peut être utilisée dans des dénombrements asymptotiques et dans des problèmes d’optimisation combinatoire.

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Multi angle  Weighted distances in scale free random graphs Komjathy, Julia (Auteur de la Conférence) | CIRM (Editeur )

In this talk I will review the recent developments on weighted distances in scale free random graphs as well as highlight key techniques used in the proofs. We consider graph models where the degree distribution follows a power-law such that the empirical variance of the degrees is infinite, such as the configuration model, geometric inhomogeneous random graphs, or scale free percolation. Once the graph is created according to the model definition, we assign i.i.d. positive edge weights to existing edges, and we are interested in the proper scaling and asymptotic distribution of weighted distances.
In the infinite variance degree regime, a dichotomy can be observed in all these graph models: the edge weight distributions form two classes, explosive vs conservative weight distributions. When a distribution falls into the explosive class, typical distances converge in distribution to proper random variables. While, when a distribution falls into the conservative class, distances tend to infinity with the model size, according to a formula that captures the doubly-logarithmic graph distances as well as the precise behaviour of the distribution of edge-weights around the origin. An integrability condition decides into which class a given distribution falls.
This is joint work with Adriaans, Baroni, van der Hofstad, and Lodewijks.
In this talk I will review the recent developments on weighted distances in scale free random graphs as well as highlight key techniques used in the proofs. We consider graph models where the degree distribution follows a power-law such that the empirical variance of the degrees is infinite, such as the configuration model, geometric inhomogeneous random graphs, or scale free percolation. Once the graph is created according to the model ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Multi angle  Random graphs and applications to Coxeter groups Behrstock, Jason (Auteur de la Conférence) | CIRM (Editeur )

Erdös and Rényi introduced a model for studying random graphs of a given "density" and proved that there is a sharp threshold at which lower density random graphs are disconnected and higher density ones are connected. Motivated by ideas in geometric group theory we will explain some new threshold theorems we have discovered for random graphs. We will then explain applications of these results to the geometry of Coxeter groups. Some of this talk will be on joint work with Hagen and Sisto; other parts are joint work with Hagen, Susse, and Falgas-Ravry.
Erdös and Rényi introduced a model for studying random graphs of a given "density" and proved that there is a sharp threshold at which lower density random graphs are disconnected and higher density ones are connected. Motivated by ideas in geometric group theory we will explain some new threshold theorems we have discovered for random graphs. We will then explain applications of these results to the geometry of Coxeter groups. Some of this talk ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Multi angle  Random irregular graphs are nearly Ramanujan Puder, Doron (Auteur de la Conférence) | CIRM (Editeur )

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Multi angle  Spectral measures of factor of i.i.d. processes on the regular tree Backhausz, Ágnes (Auteur de la Conférence) | CIRM (Editeur )

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.

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Multi angle  Anchored expansion in the hyperbolic Poisson Voronoi tessellation Paquette, Elliot (Auteur de la Conférence) | CIRM (Editeur )

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 ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Multi angle  Random walk on random digraph Salez, Justin (Auteur de la Conférence) | CIRM (Editeur )

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 ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Multi angle  Recurrence of half plane maps Angel, Omer (Auteur de la Conférence) | CIRM (Editeur )

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.

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Multi angle  Random cubic planar graphs revisited Rué, Juanjo (Auteur de la Conférence) | CIRM (Editeur )

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 ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Multi angle  Connected chord diagrams, bridgeless maps, and perturbative quantum field theory Yeats, Karen (Auteur de la Conférence) | CIRM (Editeur )

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.)

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Multi angle  Random hyperbolic graphs Kiwi, Marcos (Auteur de la Conférence) | CIRM (Editeur )

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 ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Multi angle  Quasi-random graphs and pseudo-random binary sequences Sarközy, Andras (Auteur de la Conférence) | CIRM (Editeur )

The notion of quasi-random graphs was introduced in 1987 by F. R. K. Chung, R. L. Graham and R. M. Wilson, resp. A. Thomason. It has been shown that there is a strong connection between this notion and the pseudorandomness of (finite) binary sequences. This connection can be utilized for constructing large families of quasi-random graphs by considering graphs defined by a circular adjacency matrix whose first column is a binary sequence with strong pseudo-random properties. Starting out from this construction principle one may extend, generalize and sharpen some definitions and results on quasi-randomness of graphs.
The notion of quasi-random graphs was introduced in 1987 by F. R. K. Chung, R. L. Graham and R. M. Wilson, resp. A. Thomason. It has been shown that there is a strong connection between this notion and the pseudorandomness of (finite) binary sequences. This connection can be utilized for constructing large families of quasi-random graphs by considering graphs defined by a circular adjacency matrix whose first column is a binary sequence with ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

## Multi angle  Majority dynamics on the infinite 3-regular tree Sen, Arnab (Auteur de la Conférence) | CIRM (Editeur )

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Z