The unlabelled bridge-addable connectivity lower-bound conjecture
The unlabelled bridge-addable connectivity lower-bound conjecture
Let 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 if and only if each of its components does. Let be the set of unlabelled graphs in on vertices, and let be sampled uniformly from this set. Let be the constant determined by
where and are the classes of trees and forests, respectively. Unlabelled bridge-addable connectivity lower-bound conjecture. If is bridge-addable and decomposable, then
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.