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

Eryk Kopczynski, Tony Tan

The {\em spectrum} of a first-order logic sentence is the set of natural numbers that are cardinalities of its finite models. In this paper we show that when restricted to using on…