CIRM - Videos & books Library

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

We will overview two probabilistic methods used to prove the existence of diverse combinatorial objects with desired properties: First, we will introduce Lovász Local Lemma as a classical tool to prove that, informally speaking, with non-zero probability none of the “bad” events occur if those bad events are of low probability and somewhat essentially independent from each other. Next, we will move on to its algorithmic counterpart, the Entropy Compression Method, used to ensure that a randomized algorithm eventually finds a solution with desired properties. The two methods will be illustrated by applying them to various settings in graph theory, combinatorics, and geometry.
https://www.labri.fr/perso/fkardos/[-]

We will overview two probabilistic methods used to prove the existence of diverse combinatorial objects with desired properties: First, we will introduce Lovász Local Lemma as a classical tool to prove that, informally speaking, with non-zero probability none of the “bad” events occur if those bad events are of low probability and somewhat essentially independent from each other. Next, we will move on to its algorithmic counterpart, the Entropy ...[+]

05C15 ; 05C80

Sélection Signaler une erreur

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

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 ...[+]

05C50 ; 05C80 ; 68T05 ; 91D30

Sélection Signaler une erreur

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

05C80

Sélection Signaler une erreur

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

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.

05C80 ; 60G15

Sélection Signaler une erreur

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

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 ...[+]

05C80 ; 60D05 ; 60G55

Sélection Signaler une erreur

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

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 ...[+]

05C80 ; 05C81 ; 60G50 ; 60J10

Sélection Signaler une erreur

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

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.

05C80 ; 60K35 ; 60C05

Sélection Signaler une erreur

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

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 ...[+]

05C80 ; 05C10 ; 05A16

Sélection Signaler une erreur

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

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 ...[+]

05C05 ; 05C80 ; 60G50 ; 60J10 ; 60K35 ; 82B43

Sélection Signaler une erreur

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

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 ...[+]

05C80 ; 68Q87 ; 74E35

Sélection Signaler une erreur

TUTELLES

PARTENAIRES

Destination de la recherche

Raccourcis

Documents 05C80 33 résultats

Probabilistic methods: entropy compression - Kardoš, František (Auteur de la conférence) | CIRM H Nouveau

Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs - Massoulié, Laurent (Auteur de la conférence) | CIRM H Nouveau

Random irregular graphs are nearly Ramanujan - Puder, Doron (Auteur de la conférence) | CIRM H Nouveau

Spectral measures of factor of i.i.d. processes on the regular tree - Backhausz, Agnes (Auteur de la conférence) | CIRM H Nouveau

Anchored expansion in the hyperbolic Poisson Voronoi tessellation - Paquette, Elliot (Auteur de la conférence) | CIRM H Nouveau

Random walk on random digraph - Salez, Justin (Auteur de la conférence) | CIRM H Nouveau

Recurrence of half plane maps - Angel, Omer (Auteur de la conférence) | CIRM H Nouveau

Random cubic planar graphs revisited - Rué, Juanjo (Auteur de la conférence) | CIRM H Nouveau

Self-interacting walks and uniform spanning forests - Peres, Yuval (Auteur de la conférence) | CIRM H Nouveau

Random hyperbolic graphs - Kiwi, Marcos (Auteur de la conférence) | CIRM H Nouveau