Skip to main content
MathOverflow

Return to Question

added logic tag and changed EF to Ehrenfeucht–Fraïssé
Source Link
Tony Huynh
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

I would like to ask if there is any good list of graph properties that one can express in the MSO2 (i.e., using quantification over sets of edges) but provably not in MSO1 (i.e., using quantification over sets of vertices only). I know that this should be Hamilton path but I think that there has to be plenty such examples. Ideal are those that are suitable as exercises for non-expressibility results using EFEhrenfeucht–Fraïssé games.

I would like to ask if there is any good list of graph properties that one can express in the MSO2 (i.e., using quantification over sets of edges) but provably not in MSO1 (i.e., using quantification over sets of vertices only). I know that this should be Hamilton path but I think that there has to be plenty such examples. Ideal are those that are suitable as exercises for non-expressibility results using EF games.

I would like to ask if there is any good list of graph properties that one can express in the MSO2 (i.e., using quantification over sets of edges) but provably not in MSO1 (i.e., using quantification over sets of vertices only). I know that this should be Hamilton path but I think that there has to be plenty such examples. Ideal are those that are suitable as exercises for non-expressibility results using Ehrenfeucht–Fraïssé games.

Source Link
Dušan Knop
Dušan Knop
  • 81
  • 2

MSO2-expressible graph properties unexpressible in MSO1

I would like to ask if there is any good list of graph properties that one can express in the MSO2 (i.e., using quantification over sets of edges) but provably not in MSO1 (i.e., using quantification over sets of vertices only). I know that this should be Hamilton path but I think that there has to be plenty such examples. Ideal are those that are suitable as exercises for non-expressibility results using EF games.