Article ID Journal Published Year Pages File Type
4652066 Electronic Notes in Discrete Mathematics 2013 7 Pages PDF
Abstract
We consider extremal problems for subgraphs of pseudorandom graphs. Our results implies that for (n,d,λ)-graphs Γ satisfyingλ2k−1≪d2kn(logn)−2(k−1)(2k−1) any subgraph G⊂Γ not containing a cycle of length 2k+1 has relative density at most 12+o(1). Up to the polylog-factor the condition on λ is best possible and was conjectured by Krivelevich, Lee and Sudakov.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,