On the abstract chromatic number and its computability for finitely axiomatizable theories

DOI10.1016/J.JCTB.2022.01.001MaRDI QIDQ2668017zbMATH OpenOpenAlexFDO

Authors Leonardo Nagami Coregliano

Publication date 3 March 2022

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2009.04606

zbMATH Keywords

Erdős-Stone-Simonovits theoremfinite model theoryRamsey's theorem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Abstract: The celebrated ErdH{o}s--Stone--Simonovits theorem characterizes the asymptotic maximum edge density in $mathcalF$-free graphs as $1-1/(chi(mathcalF)-1)+o(1)$, where $chi(mathcalF)$ is the minimum chromatic number of a graph in $mathcalF$. In Examples 25 and 31 of [L. N. Coregliano and A. A. Razborov. Semantic limits of dense combinatorial objects. Uspekhi Mat. Nauk, 75(4(454)):45-152, 2020], it was shown that this result can be extended to the general setting of graphs with extra structure: the maximum asymptotic density of a graph with extra structure without some induced subgraphs is $1-1/(chi(I)-1)+o(1)$ for an appropriately defined abstract chromatic number $chi(I)$. As the name suggests, the original formula for the abstract chromatic number is so abstract that its (algorithmic) computability was left open. In this paper, we both extend this result to characterize maximum asymptotic density of $t$-cliques in of graphs with extra structure without some induced subgraphs in terms of $chi(I)$ and we present a more concrete formula for $chi(I)$ that allows us to show its computability when both the extra structure and the forbidden subgraphs can be described by a finitely axiomatizable universal first-order theory. Our alternative formula for $chi(I)$ makes use of a partite version of Ramsey's Theorem for structures on first-order relational languages.

Recommendations

• Independence and chromatic densities of graphs
• Triangle-free graphs with large chromatic numbers
• Excluding induced subgraphs. II: Extremal graphs
• Asymptotic enumeration and a 0-1 law for m-clique free graphs
• Chromatic Ramsey theory

Cites work

• Edge-ordered Ramsey numbers
• Extremal theory of vertex or edge ordered graphs
• Forbidden paths and cycles in ordered graphs and matrices
• scientific article; zbMATH DE number 46958 (Why is no real title available?)
• scientific article; zbMATH DE number 3221981 (Why is no real title available?)
• scientific article; zbMATH DE number 3285073 (Why is no real title available?)
• scientific article; zbMATH DE number 2209719 (Why is no real title available?)
• scientific article; zbMATH DE number 3188526 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• Many \(T\) copies in \(H\)-free graphs
• On the structure of linear graphs
• Ordered Ramsey numbers
• Ordered Ramsey numbers of loose paths and matchings
• Ramsey classes: examples and constructions
• Ramsey numbers for partially-ordered sets
• Semantic limits of dense combinatorial objects
• The partite construction and Ramsey set systems
• The Voting Problem

Cited in

(1)

• On Turán-type problems and the abstract chromatic number

This page was built for publication: On the abstract chromatic number and its computability for finitely axiomatizable theories

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2668017)