Reed–Muller codes and Thomas’ conjecture

There will be a seminar on  Wednesday February 7th, 2018 at 1pm in Lecture Theatre D: Peter Cameron will speak on Reed–Muller codes and Thomas’ conjecture.

Abstract: A countable first-order structure is countably categorical if its automorphism group has only finitely many orbits on n-tuples of points of the structure for all n. (Homogeneous structures over finite relational languages provide examples.) For countably categorical structures, we can regard a reduct of the structure as a closed overgroup of its automorphism group. Simon Thomas showed that the famous countable random graph has just five reducts, and conjectured that any countable homogeneous structure has only finitely many reducts. Many special cases have been worked out but there is no sign of a general proof yet. In order to test the limits of the conjecture, Bertalan Bodor, Csaba Szabo and I showed that a vector space over GF(2) of countable dimension with a distinguished non-zero vector has infinitely many reducts. The proof can most easily be seen using an infinite generalisation of the binary Reed–Muller codes.