Powered by OpenAIRE graph
Found an issue? Give us feedback
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

Applications of Continuous Combinatorics to Quasirandomness and Extremal Combinatorics

Authors: Nagami Coregliano, Leonardo;

Applications of Continuous Combinatorics to Quasirandomness and Extremal Combinatorics

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.

Keywords

FOS: Mathematics, Computer science, Mathematics

  • BIP!
    Impact byBIP!
    citations
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
citations
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!