Workshop

Zoom Link

Many real world networks possess the so-called small world phenomenon where every node is relatively close to every other node and have a large clustering coefficient, i.e., friends of friends are likely friends. The task of learning an adequate similarity measure on various feature spaces often involves graphs with high clustering coefficients.

We investigate the clustering effect in sparse clustering graphs byexamining the structural and spectral properties as well as the enumeration of patterns. In addition, we consider random graph models for clustering graphs that can be used to analyze the behavior of complex networks.

Zoom Link

In this talk, we would like to give an overview on recent and past results on large deviations for sparse random graphs and coagulation processes. In particular, recently there have been progresses in the study of inhomogeneous random graphs and random graphs with marks in this framework, with some interesting similarities between different models appear when studying their large deviation rate functions. On the other hand, an approach that exploits the description of interaction in spatial coagulation processes with random tree-like structures has proved useful in proving large deviations for such Markov processes. We will describe such approach and outline possible future directions.

This talk is based on joint works with W. K ̈onig, H. Langhammer, E. Magnanini (WIAS Berlin) and M. Kolodziejczyk (PoliMi).

Zoom Link

This talk examines the problem of sampling proper 𝑘-colorings from the uniform distribution using Markov chains. The Glauber dynamics, a simple single-site update Markov chain, was shown by Jerrum (1995) to achieve an optimal mixing time of 𝑂(𝑛log(𝑛)) when the number of colors 𝑘 > 2Δ, where Δ is the maximum degree of the graph being colored. In 1999, Vigoda introduced flip dynamics, a generalization of Glauber dynamics, and demonstrated that it has optimal mixing time when 𝑘>11/6Δ. This result remained the best known for general graphs for 20 years until Chen et al. (2019) established optimal mixing of flip dynamics when 𝑘 > (11/6 − 𝜖), where 𝜖 is approximately 10^(-5). Recently, Carlson and Vigoda (2024) provided the first substantial improvement over these results by proving an optimal mixing time for flip dynamics when 𝑘 ≥ 1.809 Δ. Their proof employs a path coupling argument with a simple weighted Hamming distance for "unblocked" neighbors. In this talk, we review the problem of sampling proper colorings, the development of flip dynamics, and the tools used in the aforementioned results

Zoom Link

The loop-erased random walk (LERW) is a model for random self-avoiding curves. Since its introduction by Lawler in the early 1980s, the scaling limits of LERW have been thoroughly studied. While these limits are well-understood in dimensions 2 and 4 and higher, the three-dimensional case presents unique challenges.

This talk will present recent advances on the Minkowski content of the scaling limit of the three-dimensional LERW. Due to the absence of essential tools in the continuum in this dimension, key parts of the analysis are carried out in discrete space. Specifically, we establish sharp estimates for the one-point function and ball-hitting probabilities for the LERW on $\mathbb{Z}^3$. This talk is based on joint work with Xinyi Li and Daisuke Shiraishi.