Digraph extremal problems, hypergraph extremal problems, and the densities of graph structures (Q794664): Difference between revisions

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