Wednesday, September 16 from 3 to 4pm
Room: MP 207
Speaker: John Clemens (BSU)
Title: Isomorphism of homogeneous structures
Abstract: The theory of Borel reducibility of equivalence relations can be used to gauge the complexity of the isomorphism problem for a collection of countable structures. Certain classes, such as that of graphs and trees, are known to have an isomorphism problem of maximal complexity. We may also consider only the homogeneous structures, those whose automorphism group acts transitively on the structure. I will discuss the question of when the isomorphism problem for a collection of homogeneous structures is as complicated as that for all such structures. This may be viewed as asking when information may be coded into a structure without using “local” coding. In particular, we can show that this is true for graphs, but not for trees.