Embedding, randomised and structural problems in extremal graph theory
Quasi-random hypergraphs and spanning subhypergraph containment
| Full text | |
| Author(s): |
Kohayakawa‚ Y.
;
Kreuter‚ B.
;
Steger‚ A.
Total Authors: 3
|
| Document type: | Journal article |
| Source: | COMBINATORICA; v. 18, n. 1, p. 101-120, 1998. |
| Abstract | |
We study the maximal number of edges a C-2k-free subgraph of a random graph Gn,p may have, obtaining best possible results for a. range of p= p(n). Our estimates strengthen previous bounds of Furedi [12] and Haxell, Kohayakawa, and Luczak [13]. Two main tools are used here: the first one is an upper bound for the number of graphs with large even-girth, i.e., graphs without short even cycles, with a given number of vertices and edges, and satisfying a certain additional pseudorandom condition; the second tool is the powerful result of Ajtai, Komlos, Pintz;, Spencer, and Szemeredi [1] on uncrowded hypergraphs as given by Duke, Lefmann, and Rodl [7]. (AU) | |
| FAPESP's process: | 96/04505-2 - Structural and algorithmic aspects of combinatorial objects |
| Grantee: | Yoshiharu Kohayakawa |
| Support Opportunities: | Research Projects - Thematic Grants |