Smallness of the class Q\mathcal{Q}

Let Q\mathcal{Q} be the graph class defined in the preceding construction. A graph class is small if there is a constant cc such that the number of its labelled nn-vertex graphs is at most cnn!c^n n!. Smallness conjecture for Q\mathcal{Q}. There exists a constant cc such that the number of nn-vertex graphs in Q\mathcal{Q} is at most

cnn!,c^n n!,

i.e. the class Q\mathcal{Q} is small. If true, this would make Q\mathcal{Q} an explicit counterexample to the small conjecture, which asserts that every small class has bounded twin-width; the supplied text does not resolve the conjecture.

Sources & referencesView supporting material

Primary source

Bogdan Alecu, Vladimir E. Alekseev, Aistis Atminas, Vadim Lozin and Viktor Zamaraev, “Graph parameters, implicit representations and factorial properties”, arXiv:2303.04453 (2023).

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.