Supersaturated graphs and hypergraphs (Q787158): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/bf02579292 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2115730400 / rank | |||
Normal rank |
Revision as of 08:33, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Supersaturated graphs and hypergraphs |
scientific article |
Statements
Supersaturated graphs and hypergraphs (English)
0 references
1983
0 references
In this paper are investigated supersaturated graphs and hypergraphs. Let \(\mathcal L\) be a family of graphs (hypergraphs) and ex \((n,\mathcal L)\) denote the maximum number of edges (hyperedges) of a graph (hypergraph) on \(n\) vertices which do not contain a subgraph from \(\mathcal L\). A graph (hypergraph) with \(n\) vertices containing more than \(\text{ex}(n,\mathcal L)\) edges es called a supersaturated graph (hypergraph). The problem solved in this paper is to determine the number of copies of a subgraph from \(\mathcal L\) which must occur in a supersaturated graph (hypergraph) with \(\text{ex}(n,\mathcal L)+k\) edges. There are given some lower bounds for the number of subgraphs from \(\mathcal L\) with respect to value of \(k\). In the case of ordinary graphs the characterisation of supersaturated graphs with a low number of prohibited subgraphs is given.
0 references
uniform hypergraph
0 references
forbidden subgraphs
0 references
Turan graphs
0 references
supersaturated hypergraph
0 references