Bounded degree and planar spectra

DOI10.23638/LMCS-13(4:6)2017zbMATH Open1459.03036arXiv1609.01789MaRDI QIDQ4596783FDOQ4596783

Authors: Anuj Dawar, Eryk Kopczyński 

Publication date: 11 December 2017

Abstract: The finite spectrum of a first-order sentence is the set of positive integers that are the sizes of its models. The class of finite spectra is known to be the same as the complexity class NE. We consider the spectra obtained by limiting models to be either planar (in the graph-theoretic sense) or by bounding the degree of elements. We show that the class of such spectra is still surprisingly rich by establishing that significant fragments of NE are included among them. At the same time, we establish non-trivial upper bounds showing that not all sets in NE are obtained as planar or bounded-degree spectra.

Full work available at URL: https://arxiv.org/abs/1609.01789

Recommendations

• The Spectra of First-Order Sentences and Computational Complexity
• Regular graphs and the spectra of two-variable logic with counting
• Infinite spectra in the first order theory of graphs
• First-order spectra with one binary predicate
• scientific article; zbMATH DE number 2079026

zbMATH Keywords

finite model theoryplanar graphsspectrabounded degree graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)

Cited In (3)

• Regular graphs and the spectra of two-variable logic with counting
• Axiomatizing rectangular grids with no extra non-unary relations
• Point Degree Spectra of Represented Spaces

This page was built for publication: Bounded degree and planar spectra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4596783)