On Ramsey—Turán type theorems for hypergraphs
Tóm tắt
LetH
r
be anr-uniform hypergraph. Letg=g(n;H
r
) be the minimal integer so that anyr-uniform hypergraph onn vertices and more thang edges contains a subgraph isomorphic toH
r
. Lete =f(n;H
r
,εn) denote the minimal integer such that everyr-uniform hypergraph onn vertices with more thane edges and with no independent set ofεn vertices contains a subgraph isomorphic toH
r
. We show that ifr>2 andH
r
is e.g. a complete graph then
$$\mathop {\lim }\limits_{\varepsilon \to 0} \mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} f(n;H^r ,\varepsilon n) = \mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} g(n;H^r )$$
while for someH
r
with
$$\mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} g(n;H^r ) \ne 0$$
$$\mathop {\lim }\limits_{\varepsilon \to 0} \mathop {\lim }\limits_{n \to \infty } \left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)^{ - 1} f(n;H^r ,\varepsilon n) = 0$$
. This is in strong contrast with the situation in caser=2. Some other theorems and many unsolved problems are stated.
Tài liệu tham khảo
B. Bollobás andP. Erdős, On a Ramsey—Turán type problem,J. Comb. Th. Ser. B 21 (1976) 166–168.
P. Erdős, A. Hajnal, V. T. Sós andE. Szemerédi, More results on Ramsey—Turán type problems,Combinatorica,3 (1) (1983).
P. Erdős andA. Hajnal, On chromatic number of graphs and set systems,Acta Math. Acad. Sci. Hungar. 17 (1966) 61–99.
P. Erdős, On extremal problems of graphs and generalized graphs,Israel J. Math. 2 (1964) 183–190.
P. Erdős andV. T. Sós, Some remarks on Ramsey’s and Turán’s theorem.Comb. Theory and Appl. (P. Erdős et al. eds.)Math. Coll. Soc. J. Bolyai 4 Balatonfüred (1969) 395–404.
P. Erdős andM. H. Stone, On the structure of linear graphs,Bull. Amer. Math. Soc. 52 (1946) 1087–1091.
V. T. Sós, On extremal problems in graph theoryProc. Calgary Internat. Conf. on Comb. Structures (1969) 407–410.
E. Szemerédi, On graphs containing no complete subgraph with 4 vertices (in Hungarian),Mat. Lapok 23 (1972) 111–116.
P. Turán. Eine Extremalaufgabe aus der Graphentheorie (in Hungarian),Mat. Fiz. Lapok 48 (1941) 436–452.see also: On the theory of graphs,Colloquium Math. 3 (1954), 19–30.