MSO limit laws for unlabelled addable minor-closed classes

From papers

Let G\mathcal{G} be an addable, minor-closed class and let UG\mathcal{U}\mathcal{G} be its corresponding collection of unlabelled graphs. Let CnuUCnC_n \in_u \mathcal{U}\mathcal{C}_n be a uniformly random connected unlabelled graph from G\mathcal{G}, and let GnuUGnG_n \in_u \mathcal{U}\mathcal{G}_n be a uniformly random unlabelled graph from G\mathcal{G}. Unlabelled MSO limit-law conjecture. The random connected graph CnC_n obeys the \textscMSO\textsc{MSO}-zero-one law, and GnG_n obeys the \textscMSO\textsc{MSO}-convergence law. The paper strongly expects the labelled results for addable classes to extend to the unlabelled setting, but no proof is supplied.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Peter Heinig, Tobias Muller, Marc Noy and Anusch Taraz, “Logical limit laws for minor-closed classes of graphs”, arXiv:1401.7021 (2018).

Solutions 0

No solutions have been posted yet.