On Induced Subgraphs of Finite Graphs not Containing Large Empty and Complete Subgraphs
From MaRDI portal
Publication:6237213
arXiv1211.3876MaRDI QIDQ6237213FDOQ6237213
Publication date: 16 November 2012
Abstract: In their celebrated paper [Ramsey-Type Theorems, Discrete Appl. Math. 25 (1989) 37-52], ErdH{o}s and Hajnal asked the following: is it true, that for any finite graph H there exists a constant c(H) such that for any finite graph G, if G does not contain complete or empty induced subgraphs of size at least |V(G)|^c(H), then H can be isomorphically embedded into G ? The positive answer has become known as the ErdH{o}s-Hajnal conjecture. In Theorem 3.20 of the present paper we settle this conjecture in the affirmative. To do so, we are studying here the fine structure of ultraproducts of finite sets, so our investigations have a model theoretic character.
Model theory of finite structures (03C13) Generalized Ramsey theory (05C55) Nonstandard measure theory (28E05) Ultraproducts and related constructions (03C20)
This page was built for publication: On Induced Subgraphs of Finite Graphs not Containing Large Empty and Complete Subgraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6237213)
