On \(K^ 4\)-free subgraphs of random graphs
type: Item
instance of: scholarly article
title: On \(K^ 4\)-free subgraphs of random graphs
zbMATH Open document ID: 0889.05068
DOI: 10.1007/BF01200906
author: Tomasz Łuczak
author: Vojtěch Rödl
author: Yoshiharu Kohayakawa
published in: Combinatorica
publication date: 1998-05-06T00:00:00Z
review text: For \(0<\gamma\leq 1\) and graphs \(G\) and \(H\), write \(G\rightarrow_\gamma H\) if a \(\gamma\)-proportion of the edges of \(G\) spans at least one copy of \(H\) in \(G\). Let \(K^r\) be the complete graph on \(r\) vertices, and \(G_{n,p}\) be the (binomial) random graph on \(n\) vertices. The main result of this paper says that for every fixed real \(0<\eta\leq 1/3\), there is a constant \(C(\eta )\) for which the following holds. If \(0\leq p=p(n)\leq 1\) is such that \(p\geq Cn^{-2/5}\) for all large enough \(n\), then almost every \(G_{n,p}\) is such that \(G_{n,p}\rightarrow_{2/3+\eta} K_4\). This result is obtained by a sequence of lemmata which are interesting on their own. For instance, nice results on the distribution of triangles in random and pesudo-random graphs are obtained. The proof combines probabilistic arguments with a Turán type result and a version of Szemerédi's regularity lemma for sparse graphs. The paper contains a challenging conjecture, too.
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05D99
zbMATH DE Number: 1149466
zbMATH Keywords: graph
zbMATH Keywords: random graph
zbMATH Keywords: Turán type problem
zbMATH Keywords: regularity lemma
Wikidata QID: Q97694944
MaRDI profile type: Publication
cites work: Extremal subgraphs of random graphs
cites work: Subgraphs of a hypercube containing no small even cycles
cites work: Large triangle-free subgraphs in graphs without \(K_ 4\)
cites work: Random Ramsey graphs for the four-cycle
cites work: The Induced Size-Ramsey Number of Cycles
cites work: Turán's extremal problem in random graphs: Forbidding odd cycles
cites work: Turán's extremal problem in random graphs: Forbidding even cycles
cites work: Poisson approximation for large deviations
cites work: Szemerédi’s Regularity Lemma for Sparse Graphs
cites work: An extremal problem for random graphs and the number of graphs with large even-girth
cites work: Arithmetic progressions of length three in subsets of a random set
cites work: Threshold Functions for Ramsey Properties
cites work: Q4200109
full work available at URL: https://doi.org/10.1007/bf01200906
OpenAlex ID: W2054018639
DBLP publication ID: journals/combinatorica/KohayakawaLR97
description: scientific article; zbMATH DE number 1149466