Artículos con la etiqueta ‘Discrete Mathematics (cs.DM); Combinatorics (math.CO)’

Regular graphs and the spectra of two-variable logic with counting

Por • 14 abr, 2013 • Category: Crítica

The spectrum of a first-order logic sentence is the set of natural numbers that are cardinalities of its finite models. This notion has been shown to be closely linked with complexity theory. In fact, asking whether the spectra of first-order logic sentences is closed under complement is equivalent to asking whether NE=coNE. In this paper we show that when restricted to using only two variables, the spectra of first-order logic sentences are closed under complement. In particular, we show that they are semilinear. At the heart of our proof are semilinear characterisations for the existence of regular graphs, the class of graphs in which there are a priori bounds on the degrees of the vertices.