Connection matrices and the definability of graph parameters

Abstract. In this paper we extend and prove in detail the Finite Rank The-orem for connection matrices of graph parameters definable in Monadic Sec-ond Order Logic with counting (CMSOL) from B. Godlin, T. Kotek and J.A. Makowsky (2008) and J.A. Makowsky (2009). We demonstrate its vast applica-bility in simplifying known and new non-definability results of graph properties and finding new non-definability results for graph parameters. We also prove a Feferman-Vaught Theorem for the logic CFOL, First Order Logic with the modular counting quantifiers