Logic Seminar
Henry Towsner
University of Pennsylvania
Ultraproducts of Quasirandom Graphs and Hypergraphs
Abstract: The many equivalent characterizations of quasirandomness for graphs have been extensively studied. When generalized to hypergraphs, these notions split into a partially ordered family of distinct notions, recently shown by Lenz and Mubayi to not even be linearly ordered.
The ultraproduct setting, equipped with Loeb measure, turns out to be a natural place to examine these notions; in this setting, the different notions of quasirandomness for hypergraphs match up to certain natural algebras of definable sets. Considering all possible variations of these algebras includes all the notions studied so far, and introduces a few new notions. For some characterizations of graph randomness we are able to produce a generalization corresponding to each possible algebra. In particular, for each algebra we identify the class of hypergraphs which appear with the "correct" frequency in any hypergraph random for that algebra.
Tuesday March 11, 2014 at 4:00 PM in SEO 427