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