ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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~n∈uA~\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.

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.