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

*(English)*Zbl 0541.05035Let 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\).

Reviewer: K.-W.Lih

##### MSC:

05C35 | Extremal problems in graph theory |

05C20 | Directed graphs (digraphs), tournaments |

05C65 | Hypergraphs |

##### Keywords:

Turan type theorems; uniform directed hypergraph; maximum number of oriented hyperedges; extremal density
PDF
BibTeX
XML
Cite

\textit{W. G. Brown} and \textit{M. Simonovits}, Discrete Math. 48, 147--162 (1984; Zbl 0541.05035)

Full Text:
DOI

##### References:

[1] | W.G. Brown, On an open problem of Paul Turán concerning 3-graphs, Studies in Pure Mathematics, to the Memory of Paul Turán (Birkhäuser Verlag, Zurich; Akadémiai Kiadó, Budapest) 91-93. |

[2] | Brown, W.G; Erdös, P; Simonovits, M, Extremal problems for directed graphs, J. combin. theory (B), 15, 77-93, (1973), MR 52#7952 · Zbl 0253.05124 |

[3] | Brown, W.G; Erdös, P; Simonovits, M, Multigraph extremal problems, (), 63-66 |

[4] | Brown, W.G; Erdös, P; Simonovits, M, Multigraph extremal problems, (1975), about 180 pages · Zbl 1029.05080 |

[5] | W.G. Brown, P. Erdös and M. Simonovits, Inverse extremal digraph problems, Colloq. Math. Soc. János Bolyai nn (North-Holland, Amsterdam, 198n). |

[6] | Brown, W.G; Erdös, P; Simonovits, M, Algorithmic solution of extremal digraph problems, (1982), McGill University, Preprint |

[7] | Brown, W.G; Harary, F, Extremal digraphs, (), 135-198, MR 45#8576 · Zbl 0209.28501 |

[8] | Erdös, P; Stone, A.H, On the structure of linear graphs, Bull. amer. math. soc., 52, 1087-1091, (1946), MR 8, 333b · Zbl 0063.01277 |

[9] | Erdös, P, On extremal problems of graphs and generalized graphs, Israel J. math., 2, 174-181, (1964), MR 32#1134 |

[10] | Erdös, P, On some extremal problems on r-graphs, Discrete math., 1, 1-6, (1971), MR 45#6656 · Zbl 0211.27003 |

[11] | Erdös, P; Simonovits, M, A limit theorem in graph theory, Studia sci. math. hungar., 1, 51-57, (1966), MR 34#5702 · Zbl 0178.27301 |

[12] | P. Erdös and M. Simonovits, Oversaturated graphs and hypergraphs, Combinatorica, to appear. |

[13] | Erdös, P, Some recent results on extremal problems in graph theory (results), (), 118-123, MR 37#2634 |

[14] | Erdös, P, On some new inequalities concerning extremal properties of graphs, (), 77-81, MR 38#1026 |

[15] | Katona, Gy; Nemetz, T; Simonovits, M, Ujabb bizonyitás a Turán-féle gráftétele, és megjegyzések bizonyos általánositásaira, Matematikai lapok, 15, 228-238, (1964), MR 30#2483 |

[16] | Motzkin, T.S; Straus, E.G, Maxima for graphs and a new proof of a theorem of Turán, Canad. J. math., 17, 533-540, (1965), ME 31#89 · Zbl 0129.39902 |

[17] | Simonovits, M, A method for solving problems in graph theory, stability problems, (), 279-319, MR 38#2056 |

[18] | Simonovits, M, Extremal graph problems, degenerate extremal problems, and supersaturated graphs, () · Zbl 0556.05038 |

[19] | Sós, V.T; Erdös, P; Brown, W.G, On the existence of triangulated spheres in 3-graphs, and related problems, Periodica math. hung, 3, 221-228, (1973), MR 48#2003 · Zbl 0269.05111 |

[20] | Turán, P, Egy gráfelméleti szélsöérték feladatról, Mat. fiz. lapok, 48, 436-452, (1941), MR 8, 284j |

[21] | Turán, P, On the theory of graphs, Colloq. math., 3, 19-30, (1954), MR 15, 976b · Zbl 0055.17004 |

[22] | Turán, P, Research problems, Magyar tud. akad. kutató int. Közl., 6, 417-423, (1961), MR 31#2107 |

[23] | Sós, V.T; Straus, E.G, Extremals of functions on graphs, with applications to graphs and hypergraphs, J. combin. theory (B), 32, 246-257, (1982) · Zbl 0472.05035 |

[24] | Katona, Gy, Continuous versions of some extremal hypergraph problems, (), 653-678, MR 80e = 05071 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.