University Seminar- Computability, Complexity, and Algebraic Structure- Free structures and limiting density

Time: Friday, March 28, 3:05 – 4:05pm
Place: Phillips Hall, Room 209
Speaker: Meng-Che “Turbo” Ho, California State University, Northridge

Title: Free structures and limiting density

Abstract:  Gromov asked what a typical group looks like, and he suggested a way to make the question precise in terms of limiting density. The typical finitely presented group is known to share some important properties with the non-abelian free groups. Knight conjectured that the typical group satisfies a zero-one law and has the same first-order theory as the free group. Kharlampovich and Sklinos verified this conjecture for two-quantifier sentences.
We generalize Gromov's notion and Knight's question to structures in an arbitrary algebraic variety (in the sense of universal algebra). We give examples illustrating different behaviors of the limiting density of first-order sentences. We focus on unary structures (structures whose language has only unary functions, sometimes also called a functional graph), and show that a commutative bijective variety of unary structures satisfies the property that a sentence is true in the free structure iff it has limiting density 1. We will then discuss some ongoing work focused on the converse, and pose some examples and questions.
This is joint work with Johanna Franklin and Julia Knight.