Digraph extremal problems, hypergraph extremal problems, and the densities of graph structures

✍ Scribed by W.G Brown; M Simonovits

• Publisher: Elsevier Science
• Year: 1984
• Tongue: English
• Weight: 747 KB
• Volume: 48
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(84)90178-x

✦ Synopsis

We consider extremal problems 'of Tur~ type' for r-uniform ordered hypergraphs, where multiple oriented edges are permitted up to multiplicity q. With any such '(r, q)-graph' G" we associate an r-linear form whose maximum over the standard (n -1)-simplex in R" is called the (graph-) density g(G ") of G". If ex(n, L) is the maximum number of oriented hyperedges in an n-vertex (r, q)-graph not containing a member of L, lirn~ ex(n, L)/nr is called the examnal density of L. Motivated, in part, from results for ordinary graphs, digraphs, and multigraphs, we establish relations between these two notions.