Supersaturated graphs and hypergraphs |
| |
Authors: | Paul Erdős Miklós Simonovits |
| |
Affiliation: | (1) Mathematical Institute of the Hungarian Academy of Sciences, Budapest, Hungary |
| |
Abstract: | We shall consider graphs (hypergraphs) without loops and multiple edges. Let ? be a family of so called prohibited graphs and ex (n, ?) denote the maximum number of edges (hyperedges) a graph (hypergraph) onn vertices can have without containing subgraphs from ?. A graph (hyper-graph) will be called supersaturated if it has more edges than ex (n, ?). IfG hasn vertices and ex (n, ?)+k edges (hyperedges), then it always contains prohibited subgraphs. The basic question investigated here is: At least how many copies ofL ε ? must occur in a graphG n onn vertices with ex (n, ?)+k edges (hyperedges)? |
| |
Keywords: | 05 C 35 05 C 65 |
本文献已被 SpringerLink 等数据库收录! |
|