Name
Abstract | ||
|---|---|---|
We say ( n , e ) → ( m , f ), an ( m, f ) subgraph is forced, if every n -vertex graph of size e has an m -vertex spanned subgraph with f edges. For example, as Turán proved, ( n , e )→( k ,( k 2 )) for e > t k − 1 ( n ) and (n,e) ↛( k 2 )) , otherwise. We give a number of constructions showing that forced pairs are rare. Using tools of extremal graph theory we also show infinitely many positive cases. Several problems remain open. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1016/S0012-365X(98)00387-2 | Discrete Mathematics |
Keywords | Field | DocType |
density,ramsey's theorem,05c35,. turan's theorem,ramsey's theorem. this copy was printed on october 18,1998 s1018.tex to appear in discrete mathematics,turán's theorem,induced subgraphs,05d10,turan s theorem,extremal graph theory,ramsey s theorem | Turán's theorem,Discrete mathematics,Combinatorics,Vertex (geometry),Graph factorization,Vertex (graph theory),Ramsey's theorem,Extremal graph theory,Mathematics | Journal |
Volume | Issue | ISSN |
200 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
2 | 0.50 | 4 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul Erdős | 1 | 264 | 42.20 |
| Zoltán F¨redi | 2 | 2 | 0.50 |
| Bruce L. Rothschild | 3 | 2 | 0.50 |
| Vera T. Sós | 4 | 318 | 62.21 |