zbMATH — the first resource for mathematics

On extremal problems of graphs and generalized graphs. (English) Zbl 0129.39905
An \(r\)-graph \(G\) consists of a set \(V(G)\) of elements called vertices of \(G\) and a set \(E(G)\) whose elements (called edges of \(G\)) are subsets of \(V(G)\) with cardinal number \(r\). (Thus a 2-graph is a graph in the usual sense.) The paper deals with the following problem: given positive integers \(n,r,l\), estimate the smallest value of \(f\) such that, for every \(r\)-graph \(G\) with \(n\) vertices and \(f\) edges, \(V(G)\) has \(r\) disjoint subsets \(S_1,...,S_r\) of cardinal number \(l\) such that \(\{x_1,...,x_r\} \in E(G)\) whenever \(x_1 \in S_1,...,x_r \in S_r\). Some related matters are also briefly discussed and some interesting results and unsolved problems in this area are mentioned.

05C35 Extremal problems in graph theory
Full Text: DOI
[1] P. Erdös,On sequences of integers no one of which divides the product of two others and on some related problems. Izv. Nauk Mat. i Mech. Tomsk2 (1938), 74–82. (The best estimation off(n;K 2(2, 2)) is due to I. Reiman, Über ein Problem von K. Zaranbievicz, Acta Math. Hung Acad. Sci.,9 (1958), 269–273.
[2] P. Erdös and A. H. Stone,On the structure of linear graphs, Bull. Amer. Math. Soc.52 (1946), 1087–1091. · Zbl 0063.01277 · doi:10.1090/S0002-9904-1946-08715-7
[3] P. Erdös,Some remarks on the theory of graphs, Bull. Amer. Math. Soc.53 (1947), 292–294. · Zbl 0032.19203 · doi:10.1090/S0002-9904-1947-08785-1
[4] P. Erdös and A. Rényi,On the evolution of random graphs, Publ. Inst. Hung. Acad. Sci.5 (1960), 17–61. · Zbl 0103.16301
[5] P. Turán,On the theory of graphs, Colloqium Math.3 (1954), 19–30. · Zbl 0055.17004
[6] T. Kövári, Sós V.T. and P. Turán,On a problem of K. Zarankiewicz, Colloquium Math.3 (1954), 50–57.
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.