zbMATH — the first resource for mathematics

Exact solution of some Turán-type problems. (English) Zbl 0661.05003
Fifteen years ago Chvátal conjectued that if $${\mathcal F}$$ is a family of k subsets of an n-set, $$| {\mathcal F}| >\left( \begin{matrix} n-1\\ k- 1\end{matrix} \right)$$, d is an arbitrary integer with $$d\leq k-1$$ and $$(d+1)k\leq dn$$, then there exist $$d+1$$ sets in $${\mathcal F}$$ with empty intersection such that the intersection of any d of them is non-empty. The validity of this conjecture is established for $$n\geq n_ 0(k)$$, in a more general framework. Another problem which is solved asymptotically is when the excluded configuration is a fixed sunflower.

MSC:
 05A05 Permutations, words, matrices 05C65 Hypergraphs
Full Text:
References:
 [1] Abbott, H.L; Hanson, D; Sauer, N, Intersection theorems for systems of sets, J. combin. theory ser. A, 12, 381-389, (1972) · Zbl 0247.05004 [2] Bermond, J.C; Frankl, P, On a conjecture of chvátal on m-intersecting hypergraphs, Bull. London math. soc, 9, 310-312, (1977) · Zbl 0407.05007 [3] Bollobás, B, On generalized graphs, Acta math. acad. sci. hungar., 16, 447-452, (1965) · Zbl 0138.19404 [4] Bollobás, B, Three-graphs without two triples whose symmetric difference is contained in a third, Discrete math., 8, 21-24, (1974) · Zbl 0291.05114 [5] Bollobás, B, Extremal graph theory, (1978), Academic Press London · Zbl 0419.05031 [6] Brown, W.G; Erdös, P; Sós, V.T, On the existence of triangulated spheres in 3-graphs, and related problems, Period. math. hungar., 3, 221-228, (1973) · Zbl 0269.05111 [7] Brown, W.G; Erdös, P; Sós, V.T, Some extremal problems on r-graphs, “new directions in the theory of graphs,”, (), 53-63, 1973 [8] de Caen, D, Extension of a theorem of Moon and Moser on complete hypergraphs, Ars. combin., 16, 5-10, (1983) · Zbl 0532.05037 [9] Chung, F.R.K; Erdös, P; Graham, R.L, Research problem, (), 875, 1984 [10] {\scF. R. K. Chung and P. Frankl}, The maximum number of edges in a 3-graph not containing a given star, Graphs and Combin., in press. · Zbl 0633.05051 [11] Chvátal, V, (), 279-280, Problem 6 [12] Chvátal, V, An extremal set-intersection theorem, J. London math. soc., 9, 355-359, (1974) · Zbl 0296.05002 [13] Deza, M; Erdös, P; Frankl, P, Intersection properties of systems of finite sets, (), 368-384, (3) · Zbl 0407.05006 [14] Duke, R.A; Erdös, P, Systems of finite sets having a common intersection, (), 247-252 [15] Erdös, P, On sequences of integers no one of which divides the product of two others and some related problems, Mitt. forschung. inst. math. mech., 2, 74-82, (1938), Tomsk · JFM 64.0988.02 [16] Erdös, P, On extremal problems of graphs and generalized graphs, Israel J. math., 2, 183-190, (1964) · Zbl 0129.39905 [17] Erdös, P, A problem of independent r-tuples, Ann. univ. Budapest, 8, 93-95, (1965) · Zbl 0136.21302 [18] Erdös, P, Topics in combinatorial analysis, (), 2-20 [19] Erdös, P, Problems and results in graph theory and combinatorial analysis, (), 169-192 [20] Erdös, P, () [21] Erdös, P, On the combinatorial problems which I would most like to see solved, Combinatorica, 1, 25-42, (1981) · Zbl 0486.05001 [22] Erdös, P, Extremal problems in graph theory, (), 29-36 [23] Erdös, P; Ko, C; Rado, R, Intersection theorems for systems of finite sets, Quart. J. math. Oxford, 12, 2, 313-320, (1961) · Zbl 0100.01902 [24] Erdös, P; Milner, E.C; Erdös, P; Milner, E.C, Canad. math. bull., Canad. math. bull., 16, 145-146, (1973), Solution [25] Erdös, P; Rado, R, Intersection theorems of systems of sets, J. London math. soc., 35, 85-90, (1960) · Zbl 0103.27901 [26] Erdös, P; Simonovits, M, On supersaturated graphs, Combinatorica, 3, 181-192, (1983) · Zbl 0529.05027 [27] Frankl, P, Sperner systems satisfying an additional condition, J. combin. theory ser. A, 20, 1-11, (1976) · Zbl 0328.05002 [28] Frankl, P, The Erdös-ko-Rado theorem is true for n = ckt, (), 365-375, 1978 · Zbl 0401.05001 [29] Frankl, P, A general intersection theorem for finite sets, Ann. discrete math, 9, 43-49, (1980) · Zbl 0468.05016 [30] Frankl, P, On a problem of chvátal and Erdös on hypergraphs containing no generalized simplex, J. combin. theory ser. A, 30, 169-182, (1981) · Zbl 0475.05066 [31] Frankl, P, A new short proof for the Kruskal-katona theorem, Discrete math., 48, 327-329, (1984) · Zbl 0539.05006 [32] Frankl, P, Asymptotic solution of a locally Turán problem, Studia sci. hungar., 19, (1984) · Zbl 0634.05005 [33] Frankl, P; Füredi, Z, A new generalization of the Erdös-ko-Rado theorem, Combinatorica, 3, 341-349, (1983) · Zbl 0529.05001 [34] Frankl, P; Füredi, Z, An exact result for 3-graphs, Discrete math., 50, 323-328, (1984) · Zbl 0538.05050 [35] Frankl, P; Füredi, Z, Forbidding just one intersection, J. combin. theory ser. A, 39, 160-176, (1985) · Zbl 0573.05001 [36] Frankl, P; Katona, G.O.H, If the intersection of any r sets has a size ≠ r − 1, Studia sci. math. hungar., 14, 47-49, (1979) · Zbl 0483.05001 [37] Frankl, P; Rödl, V, Lower bounds for Turán’s problem, Graphs and combin., 1, 213-216, (1985) · Zbl 0577.05039 [38] Frankl, P; Singhi, N.M, Linear dependencies among subsets of a finite set, European J. combin., 4, 313-318, (1983) · Zbl 0532.05006 [39] Frankl, P; Wilson, R.M, Intersection theorems with geometric consequences, Combinatorica, 1, 357-368, (1981) · Zbl 0498.05048 [40] Füredi, Z, On finite set-systems whose every intersection is a kernel of a star, Discrete math., 47, 129-132, (1983) · Zbl 0531.05002 [41] Füredi, Z, Graphs without quadrilaterals, J. combin. theory ser. B, 34, 187-190, (1983) · Zbl 0505.05038 [42] Gyárfás, A, Problèmes combinatoires et théorie des graphes, () [43] Kalai, G, A new approach to Turán’s conjecture, Graphs and combin., 1, 107-109, (1985) · Zbl 0579.05003 [44] {\scG. Kalai}, Personal communication, 1984. [45] Katona, G.O.H; Katona, G.O.H, A theorem of finite sets, (), 187-207, Tihany, Hungary · Zbl 0878.05079 [46] Katona, G.O.H, Extremal problems for hypergraphs, (), 13-42, Math. Centre Tracts, Vol. 56 Amsterdam · Zbl 0298.05142 [47] Katona, G.O.H; Nemetz, T; Simonovits, M, On a problem of Turán in the theory of graphs, Mat. lapok, 15, 228-238, (1964), [Hungarian, English summary] · Zbl 0138.19402 [48] Kruskal, J.B, The numbers of simplices in a complex, (), 251-278 [49] Larman, D.G, A note on the realization of distances within sets in Euclidean space, Comment. math. helv., 53, 529-535, (1978) · Zbl 0408.52005 [50] Lovász, L, Combinatorial problems and exercises, (1979), Akadémiai Kiadó Budapest, and North-Holland, Amsterdam · Zbl 0439.05001 [51] Mantel, W, Wiskundige opgaven, 10, 60-61, (1907), Problem 28 [52] Razborov, A.A, Lower bounds of the monotone complexity of certain Boolean functions, Dokl. akad. nauk. SSSR, 281, 798-801, (1985) · Zbl 0621.94027 [53] Rödl, V, On a packing and covering problem, European J. combin., 6, 69-78, (1985) · Zbl 0565.05016 [54] Ruzsa, I.Z; Szemerédi, E, Triple systems with no six points carrying three triangles, (), 939-945 · Zbl 0393.05031 [55] Sós, V.T, Remarks on the connection of graph theory, finite geometry and block designs, (), 223-233, 1976 [56] {\scA. F. Sidorenko}, Solution of a problem of Bollobás for 4-graphs, Mat. Zametki, to appear. [Russian] [57] Turán, P, An extremal problem in graph theory, Mat. fiz. lapok, 48, 436-452, (1941), [Hungarian] [58] Turán, P; Turán, P, Some unsolved problems, MTA mat. kutató int. Közl., Mathematika, 7, 101-107, (1963) [59] Wilson, R.M, The exact bound in the Erdös-ko-Rado theorem, Combinatorica, 4, 247-257, (1984) · Zbl 0556.05039
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.