CanaDAM 2021
En ligne, 25 - 28 mai 2021

Random graphs

R W R DARLING, U.S. Department of Defense
Efficient comparison-based learning via partitioned local depth for near neighbors  [PDF]

A triplet comparison on a set $S$ takes $x \in S$, and for any pair $\{y, z\} \subset S \setminus \{x\}$ declares which of $y$ and $z$ is more similar to $x$. Such triplet comparisons supply an orientation to the line graph of the complete graph on $S$: $\{x, y\} \rightarrow \{x, z\}$ means $y$ is more similar to $x$ than $z$ is. No metric is involved. Partitioned local depth (PaLD) supplies a non-parametric partitioning of $S$, under such triplet comparisons, but suffers from a run time cubic in $n := |S|$. We use the Bounded Differences Inequality to analyze the quality of approximation obtained by restricting PaLD to the $K$-nearest neighbors of each object. Run time is $O(n K^2)$, while error decays exponentially in $-K^2$. The statistics of uniform random orientations of the line graph play a major role. Examples from spatial data at inhomogenous scales are examined.

DAVID DE BOER, Korteweg-de Vries Institute, UvA
Uniqueness of the Gibbs measure for the $4$-state anti-ferromagnetic Potts model on the regular tree  [PDF]

We show that the $4$-state anti-ferromagnetic Potts model with interaction parameter $w\in(0,1)$ on the infinite $(d+1)$-regular tree has a unique Gibbs measure for all $w\geq 1-\frac{4}{d+1}$ and $d\geq 4$. This is tight since it is known that there are multiple Gibbs measures when $0\leq w<1-\frac{4}{d+1}$ and $d\geq 4$. The transition from having a unique to several Gibbs measures is closely connected to phase transitions in statistical physics.

Our method also gives a new proof of the uniqueness of the Gibbs measure for the $3$-state Potts model on the $(d+1)$-regular tree for $w\geq 1-\frac{3}{d+1}$ when $d\geq 3$ and for $w\in (0,1)$ when $d=2$.

JEROEN HUIJBEN, University of Amsterdam
Sampling from the low temperature Potts model through a Markov chain on flows  [PDF]

We consider the algorithmic problem of sampling from the Potts model and computing its partition function at low temperatures. Instead of directly working with spin configurations, we consider the equivalent problem of sampling flows. We show, using path coupling, that a simple and natural Markov chain on the set of flows is rapidly mixing. As a result we find an $\varepsilon$-approximate sampling algorithm for the Potts model at low enough temperatures, whose running time is bounded by $O(m\log(m)\log(m\varepsilon^{-1}))$ for graphs $G$ with $m$ edges.

AMEDEO SGUEGLIA, London School of Economics
Clique factors in randomly perturbed graphs  [PDF]

We study the model of randomly perturbed dense graphs, which is the union of any $n$-vertex graph $G_\alpha$ with minimum degree $\alpha n$ and the binomial random graph $G(n,p)$. In this talk, we shall examine the following central question in this area: to determine when $G_\alpha \cup G(n,p)$ contains clique factors, i.e. spanning subgraphs consisting of vertex disjoint copies of the complete graph $K_k$. We offer several new sharp and stability results. This is joint work with Julia Böttcher, Olaf Parczyk, and Jozef Skokan.

Cycle saturation in random graphs  [PDF]

Given two graphs $G$ and $F$, an inclusion-maximum $F$-free spanning subgraph $H\subset G$ is called an {\it $F$-saturated subgraph of $G$}. The minimum number of edges in an $F$-saturated subgraph of $G$ is called {\it $F$-saturation number of $G$} and denoted by sat$(G,F)$. The stability of sat$(K_n,F)$ was studied by Korandi and Sudakov in 2017 for complete graphs and by Mohammadian and Tayfeh-Rezaie in 2018 for star graphs.

In 1972, Ollmann proved that sat$(K_n,C_4)=\lfloor\frac{3n-5}{2}\rfloor$ for all $n\geq 5$. In 2009, Chen proved that sat$(K_n,C_5)=\lceil\frac{10}{7}(n-1)\rceil$ for $n\geq 21$. For all other $\ell$, the exact value of sat$(K_n,C_{\ell})$ is not known. However, several non-trivial bounds are obtained. In particular, sat$(K_n,C_{\ell})>(1+\varepsilon(\ell))n$ for some $\varepsilon(\ell)>0$. We have proved that sat$(K_n,C_{\ell})$ is not asymptotically stable for all $\ell\geq 5$: with high probability sat$(G(n,p),C_{\ell})=n(1+o(1))$. We have also proved that there exists $\gamma$ such that with high probability sat$(G(n,p),C_4)\leq\gamma n$.\

This is joint work with Yury Demidovich.