The unlabelled bridge-addable fragment-size 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. For a graph GG, define its fragment size by

frag(G)=V(G)max{V(C):C is a component of G}.\operatorname{frag}(G)=|V(G)|-\max\{|V(C)|:C\text{ is a component of }G\}.

Let R~nuA~\tilde{R}_n \in_u\tilde{\mathcal A} be sampled uniformly from the unlabelled graphs in A\mathcal A on nn vertices. Unlabelled bridge-addable fragment-size conjecture. For each such graph class A\mathcal A, there is a constant cAc_{\mathcal A} such that, for each positive integer nn,

E[frag(R~n)]cA.\mathbb E[\operatorname{frag}(\tilde{R}_n)]\leq c_{\mathcal A}.

The labelled analogue has a uniform expectation bound, while the source gives an unlabelled example showing that the expectation can grow linearly for a particular class; the conjectured bound remains open in general.

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.