The unlabelled bridge-addable fragment-size conjecture
Statement
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. For a graph , define its fragment size by
Let be sampled uniformly from the unlabelled graphs in on vertices. Unlabelled bridge-addable fragment-size conjecture. For each such graph class , there is a constant such that, for each positive integer ,
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.