|
|||||
|
|
Induced subgraphs of given sizes |
|
| Institution: | a Mathematical Institute of the Hungarian Academy, pf. 127, H-1364, Budapest, Hungary b Department of Mathematics, University of Illinois, 1409 w. Green Street, Urbana, IL 61801-2975, USA c Department of Mathematics, University of Californina, Los Angeles, CA 90024, USA |
| 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,(k2)) for e> tk − 1(n) and (n,e)  (k2)), 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. |
| Keywords: | Turán's theorem Density Ramsey's theorem |
| 本文献已被 ScienceDirect 等数据库收录！ | |