[CS] Leonardo Coregliano Dissertation Defense/May 10, 2021

[pbaclawski at uchicago.edu]

This is an announcement of Leonardo Coreglinao's Dissertation Defense.
===============================================

Candidate: Leonardo Coregliano

Date: Monday, May 10, 2021

Time: 2:30PM CST

Place: Via Zoom

https://uchicago.zoom.us/j/93847533683?pwd=WkE3R0tDK3Q1dFgxVXFPTEhjYWxrQT09
Meeting ID: 938 4753 3683
Passcode: 137871

Title: Applications of Continuous Combinatorics to Quasirandomness and External Combinatorics

Abstract: The theory of continuous combinatorics studies how to represent large combinatorial objects as a limit object. The inaugural limit theory of graphons captures limits of dense graph sequences in a semantic/geometric limit. Since the theory of graphons is specifically tailored to graphs, several other ad-hoc semantic limit theories have been developed in the literature. On the other hand, the theory of flag algebras explored a syntactic/algebraic approach and produced a limit object for general combinatorial objects. In a previous work with A. Razborov, we complemented the theory of flag algebras with the theory of theons, which is a semantic/geometric limit in the same level of generality as the aforementioned theory. In this talk, I will present two applications of continuous combinatorics that explore both the semantic and the syntactic approaches to the subject.

The first application is to quasirandomness. Similarly to limit theory, after the inaugural theory of graph quasirandomness, several other ad-hoc theories have been explored in the literature for different combinatorial objects such as hypergraphs, tournaments, permutations, etc. We develop a more general and systematic study of quasirandomness in the same level of generality of flag algebras/theons. Our main motivation is to study "natural" quasirandomness properties in the sense that they are preserved under local combinatorial constructions. Our properties mainly revolve around the notion of couplings of limit objects, which are alignments of limit objects in the combined theory.

The second application is a generalization of the celebrated Erdős--Stone--Simonovits Theorem. We prove that in the general setting of graphs with extra structure without any induced copies of some forbidden family, the maximum edge density is completely determined by an "abstract chromatic number". Furthermore, this number can be computed algorithmically when the underlying theory is finitely axiomatizable (and the family is finite).

The first application is joint work with Alexander Razborov.

Advisor: Alexander Razborov

Committee Members: Alexander Razborov, Janos Simon, Laszlo Babi