The unlabelled bridge-addable connectivity lower-bound conjecture

About 6 years old · traced to

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~n∈uA~\tilde{R}_n \in_u \tilde{\mathcal A} be sampled uniformly from this set. Let τ\tau be the constant determined by

∣T~n∣∣F~n∣⟶τ≈e−0.5226≈0.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 inf⁡n→∞P(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.

References

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.