Bounded-rank characterization by bounded alternation rank
Bounded-rank characterization by bounded alternation rank
Let be a hereditary graph class. Bounded-rank alternation conjecture. The class has bounded rank if and only if there is such that every first-order formula is equivalent on to a formula of alternation rank . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.