Files

Abstract

The theory of limits of dense combinatorial objects studies the asymptotic behavior of densities of small templates in an increasing sequence of combinatorial objects. The inaugural limit theory of graphons captures limits of graph sequences in a semantic limit object that can be thought of as a fractional version of an adjacency matrix. Since graphons are tailored to graphs, to study other combinatorial objects, limit theories have been developed in a case-by-case basis. On the other hand, the theory of flag algebras explored a syntactic approach to the subject, producing limits for general combinatorial objects. While the minimalist nature of the syntactic approach generates an elegant and clean theory, it has the drawback of losing the geometric intuition of the underlying objects. To address this issue, in a joint work with A.~Razborov, we have developed the theory of theons, a semantic limit that works in the same general setting of flag algebras. In this dissertation we review the theory of theons and apply these tools of limit theory to two different settings. Our first application of limit theory is to quasirandomness. The existing theory of quasirandomness provides a plethora of quasirandomness properties for several different combinatorial objects such as graphs, hypergraphs, permutations, tournaments, etc. However, such study of quasirandomness in the literature, much like in the early limit theory, has been made in case-by-case fashion for each type of combinatorial object. We develop a more general and systematic study of quasirandomness in the same setting of theons. Our main motivation is to study ``natural'' quasirandomness properties that are preserved under local combinatorial constructions, which are captured by open interpretations. Our properties mainly revolve around the notion of couplings of limit objects and uniquely coupleable limit objects. We prove several implications, separations and characterizations of our quasirandomness properties and we show the best possible separation between our properties and the quasirandomness properties of the literature. Our second application is a generalization of the celebrated Erd\H{o}s--Stone--Simonovits Theorem and its generalization by Alon--Shikhelman that characterize the asymptotic behavior of the maximum density $\pi^t_\mathcal F$ of the $t$-clique $K_t$ in a (non-induced) $\mathcal F$-free graph in terms of the chromatic numbers of the graphs in $\mathcal F$. We show that these theorems extend to local combinatorial constructions encoded by an open interpretation $I\colon T_{\operatorname{Graph}}\leadsto T$ in the sense that we can characterize the maximum density $\pi_I^t$ of a $t$-clique $K_t$ obtained from a limit graph interpreted from a limit object of $T$ in terms of an abstract chromatic number $\chi(I)$. This in particular covers the case where the forbidden graphs of $\mathcal F$ are instead assumed to be induced, and the case where we have graphs with extra structure (e.g., a (cyclic) order). We also show that if $T$ is finitely axiomatizable, then $\chi(I)$ is algorithmically computable.

Details

Actions

Preview

Downloads Statistics

from
to
Download Full History