Bounded degree and planar spectra

DOI10.23638/LMCS-13(4:6)2017MaRDI QIDQ4596783zbMATH OpenFDO

Authors Anuj Dawar, Eryk Kopczyński

Publication date 11 December 2017

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

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)

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.

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

Cited in

(3)

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

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)