Turán's extremal problem in random graphs: Forbidding even cycles (Q1898722): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/jctb.1995.1035 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2029810714 / rank | |||
Normal rank |
Revision as of 22:18, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Turán's extremal problem in random graphs: Forbidding even cycles |
scientific article |
Statements
Turán's extremal problem in random graphs: Forbidding even cycles (English)
0 references
18 December 1995
0 references
For \(0< \gamma\leq 1\) and graphs \(G\) and \(H\), we write \(G@>> \gamma> H\) if any \(\gamma\)-proportions of the edges of \(G\) span at least one copy of \(H\) in \(G\). As customary, we write \(C^k\) for a cycle of length \(k\). We show that, for every fixed integer \(\ell\geq 2\) and real \(\gamma> 0\), there exists a constant \(C= C(\ell, \gamma)> 0\) such that almost every random graph \(G_{n, p}\) with \(p= p(n)\geq Cn^{- 1+ 1/(2\ell- 1)}\) satisfies \(G_{n, p}@>> \gamma> C^{2\ell}\). In particular, for any fixed \(\ell\geq 2\) and \(\gamma> 0\), this result implies the existence of very sparse graphs \(G\) with \(G@>> \gamma> C^{2\ell}\).
0 references
Turán's extremal problem
0 references
Szemerédi's lemma
0 references
cycle
0 references
random graph
0 references
sparse graphs
0 references