The unlabelled bridge-addable connectivity conjecture

Let A\mathcal A be a class of graphs, 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} denote a graph sampled uniformly from A~n\tilde{\mathcal A}_n. A graph class is bridge-addable if adding an edge between vertices in distinct components preserves membership. Unlabelled bridge-addable connectivity conjecture. There is a δ>0\delta>0 such that, if A\mathcal A is bridge-addable, then

P(R~n is connected)δ\mathbb P(\tilde{R}_n \text{ is connected})\geq\delta

for each nn. This asks for a uniform positive lower bound on connectivity in the unlabelled setting; the source notes that little was known about this case and refers to a theorem below that bears on the question.

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.