Abstract | ||
---|---|---|
Given a family L of graphs, set p = p(L) = minL ⊂ L χ(L) - 1 and, for n ≥ 1, denote by P(n, L) the set of graphs with vertex set [n] containing no member of L as a subgraph, and write ex(n, L) for the maximal size of a member of P(n, L). Extending a result of Erdös, Frankl and Rödl (Graphs Combin. 2 (1986) 113), we prove that |P(n, L)|≤ 2½(1-1/p)n2 . O(n2-σ) for some constant γ = γ(L) 0, and characterize γ in terms of some related extremal graph problems. In fact, if ex(n, L) = O(n2 δ), then any γ |
Year | DOI | Venue |
---|---|---|
2004 | 10.1016/j.jctb.2003.08.001 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
family l,graphs combin,vertex set,maximal size,related extremal graph problem | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Lemma (mathematics),Stability theorem,Mathematics | Journal |
Volume | Issue | ISSN |
91 | 1 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
22 | 1.79 | 10 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
József Balogh | 1 | 862 | 89.91 |
Béla Bollobás | 2 | 2696 | 474.16 |
Miklós Simonovits | 3 | 578 | 98.20 |