Smallness of the class Q\mathcal{Q}

At least 2 years old · documented by

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.

References

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.