Digraph extremal problems, hypergraph extremal problems, and the densities of graph structures (Q794664)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Digraph extremal problems, hypergraph extremal problems, and the densities of graph structures
scientific article

    Statements

    Digraph extremal problems, hypergraph extremal problems, and the densities of graph structures (English)
    0 references
    1984
    0 references
    Let r and q be positive integers. An r-uniform directed q-hypergraph H is a set V(H) of vertices, together with a family E(H) of ordered r-tuples of distinct elements of V(H); an r-tuple with a given order may occur at most q times. We may also speak of an (r,q)-digraph. Let \(G^ m\) be an (r,q)-digraph with m vertices. Let the vector \(u=(u_ 1,u_ 2,...,u_ m)\) range over the standard (m-1)-simplex in \({\mathbb{R}}^ m\). We consider the real multilinear form \(f_ G(u)=\sum u_{i_ 1}u_{i_ 2}...u_{i_ r}\) summed over \((i_ 1,i_ 2,...,i_ r)\) such that \((v_{i_ 1},v_{i_ 2},...,v_{i_ r})\) is an edge of \(G^ m\) with multiplicities taken into acount. The maximum of \(f_ G(u)\) is called the density of \(G^ m\) and denoted by \(g(G^ m)\). For fixed r and q, the set of densities attained is denoted by \({\mathcal D}_ g\). If ex(n,\({\mathbb{L}})\) is the maximum number of oriented hyperedges in an n- vertex (r,q)-digraph not containing a member of \({\mathbb{L}}\), \(\lim_{n\to \infty}ex(n,{\mathbb{L}})/n^ r\) is called the extremal density of \({\mathbb{L}}\). For fixed r and q, the set of extremal densities attained is denoted by \({\mathcal D}_ e\). Motivated from results for ordinary graphs, digraphs, and multigraphs, relations between these two notions are established. For example, \({\mathcal D}_ g\subseteq {\mathcal D}_ e\) and \({\mathcal D}_ g\) is dense in \({\mathcal D}_ e\).
    0 references
    0 references
    0 references
    0 references
    0 references
    Turan type theorems
    0 references
    uniform directed hypergraph
    0 references
    maximum number of oriented hyperedges
    0 references
    extremal density
    0 references
    0 references
    0 references
    0 references