On Κ4-free subgraphs of random graphs
Authors:
- Y. Kohayakawa,
- Tomasz Łuczak,
- V. Rödl
Abstract
For 0 < γ ≤ 1 and graphs G and H, write G → γ H if any γ-proportion of the edges of G spans at least one copy of H in G. As customary, write Κr for the complete graph on r vertices. We show that for every fixed real η > 0 there exists a constant C = C(η) such that almost every random graph Gn,p withp=p(n) ≥ Cn-2/5 satisfies Gn,p → 2/3+η Κ4. The proof makes use of a variant of Szemerédi's regularity lemma for sparse graphs and is based on a certain superexponential estimate for the number of pseudo-random tripartite graphs whose triangles are not too well distributed. Related results and a general conjecture concerning H-free subgraphs of random graphs in the spirit of the Erdös-Stone theorem are discussed.
- Record ID
- UAM8de5235ed2fa4782bf6f54cafd3306b7
- Author
- Journal series
- Combinatorica, ISSN 0209-9683
- Issue year
- 1997
- Vol
- 17
- No
- 2
- Pages
- 173-213
- ASJC Classification
- ;
- DOI
- DOI:10.1007/BF01200906 Opening in a new tab
- URL
- https://www.sciencedirect.com/science/article/pii/S0012365X96000763?via%3Dihub Opening in a new tab
- Language
- (en) English
- File
-
- File: 1
- Kohayakawa1997_Article_OnK4-freeSubgraphsOfRandomGrap.pdf
-
- Score (nominal)
- 0
- Score source
- journalList
- Publication indicators
- = 59; = 62; : 1999 = 1.069; : 2006 (2 years) = 0.784 - 2007 (5 years) =0.758
Share
- Uniform Resource Identifier
- https://researchportal.amu.edu.pl/info/article/UAM8de5235ed2fa4782bf6f54cafd3306b7/
- URN
urn:amu-prod:UAM8de5235ed2fa4782bf6f54cafd3306b7
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or PerishOpening in a new tab system.