University Seminar- Computability, Complexity, and Algebraic Structure-First-Order Logical Limit Laws, Ordered Structures, and Permutation Classes

Time: Friday, February 21, 2:30 – 3:30pm

Place: Phillips Hall, Room 209

Speaker:  Matthew Kukla, GWU

Title: First-Order Logical Limit Laws, Ordered Structures, and Permutation Classes

Abstract:  For a class of finite structures in some first-order language, it is natural to ask, “How does a randomly-selected large structure from this class behave?”  Logical limit laws are one tool for gaining insight into questions of this type.  We first show the existence of limit laws for several classes of ordered structures, along with an interdefinability condition allowing a limit law on one class to be “transferred” to another.  Using this result, we show a limit law for the class of layered permutations (viewed as structures in a language with two linear orders).  Although the class of all permutations cannot admit a limit law, it is possible for various subclasses to have one, with layered permutations being an example of one such subclass.