The unlabelled bridge-addable connectivity lower-bound conjecture

Let A\mathcal A be a class of graphs that is bridge-addable, meaning that adding an edge between vertices in distinct components preserves membership, and decomposable, meaning that a graph belongs to A\mathcal A if and only if each of its components does. Let A~n\tilde{\mathcal A}_n be the set of unlabelled graphs in A\mathcal A on nn vertices, and let R~nuA~\tilde{R}_n \in_u \tilde{\mathcal A} be sampled uniformly from this set. Let τ\tau be the constant determined by

T~nF~nτe0.52260.5930,\frac{|\tilde{\mathcal T}_n|}{|\tilde{\mathcal F}_n|}\longrightarrow\tau\approx e^{-0.5226}\approx0.5930,

where T\mathcal T and F\mathcal F are the classes of trees and forests, respectively. Unlabelled bridge-addable connectivity lower-bound conjecture. If A\mathcal A is bridge-addable and decomposable, then

lim infnP(R~n is connected)τ.\liminf_{n\to\infty}\mathbb P(\tilde{R}_n\text{ is connected})\geq\tau.

This is the unlabelled counterpart of the labelled forest lower bound, which the source says was proved by Chapuy and Perarnau; the unlabelled assertion is described as more speculative.

Sources & referencesView supporting material

Primary source

Colin McDiarmid, “Connectivity for an unlabelled bridge-addable graph class”, arXiv:2001.05256 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.