Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
1982 | 10.1007/BF02579235 | Combinatorica |
Keywords | Field | DocType |
complete graph,independent set | Integer,Discrete mathematics,Combinatorics,Vertex (geometry),Constraint graph,Hypergraph,Independent set,Isomorphism,Mathematics | Journal |
Volume | Issue | ISSN |
2 | 3 | 1439-6912 |
Citations | PageRank | References |
12 | 2.97 | 1 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Paul Erdös | 1 | 111 | 23.10 |
Vera T. Sós | 2 | 318 | 62.21 |