Succinct Definitions in the First Order Theory of Graphs

Oleg Pikhurko, Joel Spencer, Oleg Verbitsky

We say that a first order sentence A defines a graph G if A is true on G but false on any graph non-isomorphic to G. Let L(G) (resp. D(G)) denote the minimum length (resp. quantifi…