## Turán's extremal problem in random graphs: Forbidding odd cycles

### Authors:

- P.E. Haxell,
- Y. Kohayakawa,
- Tomasz Łuczak

### Abstract

For 0 < γ ≤ 1 and graphs G and Η, we write G →
_{γ}
Η if any γ-proportion of the edges of G span at least one copy of Η in G. As customary, we write C
^{k}
for a cycle of length k. We show that, for every fixed integer l≥1 and real η>0, there exists a real constant C=C(l,η), such that almost every random graph G
_{n,p}
with p=p(n) ≥ Cn
^{-1+1/2l}
satisfies G
_{n,p}
→
_{1/2+η}
C
^{2l+1}
. In particular, for any fixed l ≥ 1 and η > 0, this result implies the existence of very sparse graphs G with G →
_{1/2+η}
C
^{2l+1}
.

- Record ID
- UAM9ea7faa660ed49ad826fbda2746232d3
- Author
- Journal series
- Combinatorica, ISSN 0209-9683
- Issue year
- 1996
- Vol
- 16
- Pages
- 107-122
- ASJC Classification
- ;
- DOI
- DOI:10.1007/BF01300129 opening in a new tab
- Language
- en English
- Score (nominal)
- 35
- Score source
- journalList
- Publication indicators
- = 24.000; : 1999 = 1.069; : 2006 = 0.784 (2) - 2007=0.758 (5)

- Uniform Resource Identifier
- https://researchportal.amu.edu.pl/info/article/UAM9ea7faa660ed49ad826fbda2746232d3/

* 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.

Back