Locally finite z-homogeneous graphs

04/02/2013 - 12:15pm
04/02/2013 - 1:10pm
Speaker: 
Wai Yan Pong (California State University Dominguez Hills)
Abstract: 

A graph is locally finite if every vertex of it has finitely many neighbors. A connected graph G is connectedly homogeneous (or z-homogeneous) if any isomorphism between finite connected induced subgraphs of G extends to an automorphism of G. We classified the class of locally finite z-homogeneous graphs and identified their first order theories by showing that they are precisely the class of quantifier-eliminable graphs in the signature of distance predicates. This is a joint work with Shawn Hedman.

Where: 
Millikan 208 (Pomona College)