The universal asymptotic unlabelled 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. Universal asymptotic unlabelled fragment-size conjecture. There is a constant cc such that, for each bridge-addable and decomposable graph class A\mathcal A,

lim supnE[frag(R~n)]c.\limsup_{n\to\infty}\mathbb E[\operatorname{frag}(\tilde{R}_n)]\leq c.

The source describes this as a speculative final conjecture. It differs from the preceding assertion by proposing one universal constant rather than a constant depending on A\mathcal A.

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.