Bounded-rank characterization by bounded alternation rank

Let C C be a hereditary graph class. Bounded-rank alternation conjecture. The class C C has bounded rank if and only if there is kNk\in\mathbb{N} such that every first-order formula is equivalent on C C to a formula of alternation rank kk. This conjecture generalizes the theorem preceding it in the source and relates the structural notion of rank to a uniform bound on quantifier alternation; the source leaves it as a conjecture for future work.

Sources & referencesView supporting material

Primary source

Jakub Gajarský, Michał Pilipczuk, Marek Sokołowski, Giannos Stamoulis and Szymon Toruńczyk, “Elementary first-order model checking for sparse graphs”, arXiv:2401.16230 (2025).

Additional references

2 papers in this index state this conjecture (2012–2024). The statement above is taken from the most recent of them; the others are arXiv:1211.5823.

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.