MSO limit laws for unlabelled addable minor-closed classes

About 12 years old · traced to

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 Cn∈uUCnC_n \in_u \mathcal{U}\mathcal{C}_n be a uniformly random connected unlabelled graph from G\mathcal{G}, and let Gn∈uUGnG_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.

References

Primary source

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

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.