The universal asymptotic unlabelled fragment-size conjecture
The universal asymptotic unlabelled fragment-size 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. For a graph , define its fragment size by
Let be sampled uniformly from the unlabelled graphs in on vertices. Universal asymptotic unlabelled fragment-size conjecture. There is a constant such that, for each bridge-addable and decomposable graph class ,
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 .
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.