Turán's extremal problem in random graphs: Forbidding even cycles (Q1898722): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
Created claim: Wikidata QID (P12): Q97694827, #quickstatements; #temporary_batch_1714942991822 |
||
Property / Wikidata QID | |||
Property / Wikidata QID: Q97694827 / rank | |||
Normal rank |
Latest revision as of 23:06, 5 May 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