×

What we know and what we do not know about Turán numbers. (English) Zbl 0839.05050

Three equivalent combinatorial problems are considered. The Turán number \(T(n, k, r)\) is the minimum size of a system of \(r\)-element subsets of an \(n\)-set \(X_n\) such that every \(k\)-element subset of \(X_n\) contains a member of the system; any such system is called a Turán \((n, k, r)\)-system. The covering number \(C(n, m, p)\) is the minimum number of \(m\)-subsets of \(X_n\) needed to cover all \(p\)-subsets. \(U(n, q, r)\) is the minimum number of subsets of size at least \(r\), for which any transversal contains at least \(k\) elements. It is observed that \(C(n, m, p)= T(n, n- p, n- m)\), \(U(n, q, r)= T(n, n- q+ 1,r)\). The limit \(\lim_{n\to \infty} {T(n, k, r)\over {n\choose r}}\) is known to exist, and denoted by \(t(k, r)\). Under sections headed Recursive Inequalities, Lower Bounds, Upper Bounds, The Case of Small \({n\over k-1}\), The Case \(r= 2\), The Case \(r= 3\), The Case \(r= 4\), The Case of Small \(n- k\) (Covering Numbers), the author describes the present status of the problem of determining or bounding these numbers; he includes seven conjectures concerning the numbers \(T(n, k, r)\), the limits \(t(k, r)\), and extremal configurations.

MSC:

05C35 Extremal problems in graph theory
05D05 Extremal set theory
05D15 Transversal (matching) theory
Full Text: DOI

References:

[1] Boyer, E.D., Kreher, D.L., Radziszowski, S.P., Zou, J., and Sidorenko, A.: On (n, 5, 3)-Turán systems. Ars Combinatoria37, 1–19 (1994)
[2] Brown, W.G.: On an open problem of Paul Turán concerning 3-graphs. In: Studies in pure mathematics, pp. 91–93. Basel-Boston, Mass.: Birkhäuser 1983
[3] Caen, D. de: Extension of a theorem of Moon and Moser on complete subgraphs. Ars Combinatoria16, 5–10 (1983) · Zbl 0532.05037
[4] Caen, D. de: A note on the probabilistic approach to Turán’s problem. J. Comb. TheoryB 34, 340–349 (1983) · Zbl 0519.05050
[5] Caen, D. de: The current status of Turán’s problem on hypergraphs. In: Extremal Problems for Finite Sets, Visegrád (Hungary), 1991, Bolyai Society Mathematical Studies, Vol. 3, pp. 187–197
[6] Caen, D. de, Kreher, D.L., Radziszowski, S.P., and Mills, W.H.: On the coverings oft-sets with (t + 1)-sets:C(9, 5, 4) andC(10, 6, 5). Discrete Mathematics92, 65–77 (1991) · Zbl 0758.05038 · doi:10.1016/0012-365X(91)90267-6
[7] Caen, D. de, Kreher, D.L., and Wiseman, J.: On constructive upper bounds for the Turán numbersT(n, 2r + 1, r). Congressus Numerantium65, 277–280 (1988)
[8] Droesbeke, F., Lorea, M.: Détermination de valeurs du nombre de TuránT(n, 4, 6). Cahiers du Cent. Étud. Rech. Oper.24, 185–191 (1982) · Zbl 0497.05045
[9] Erdos, P.: On the combinatorial problems I would most like to see solved. Combinatorica1, 25–42 (1981) · Zbl 0486.05001 · doi:10.1007/BF02579174
[10] Fon-Der-Flaass, D.G.: A method for constructing (3,4)-graphs. Math. Notes44, (1988) · Zbl 0766.05061
[11] Fort, M.K., Hedlund, G.A.: Minimal coverings of pairs by triples. Pacific J of Mathematics8, 709–719 (1958) · Zbl 0084.01401
[12] Frankl, P., Rödl, V.: Lower bounds for Turán’s problem. Graphs and Combinatorics1, 213–216 (1985) · Zbl 0577.05039 · doi:10.1007/BF02582949
[13] Füredi, Z.: Covering pairs byq 2 +q + 1 sets. J. Comb. TheoryA 54, 248–271 (1990) · Zbl 0734.05033 · doi:10.1016/0097-3165(90)90034-T
[14] Gardner, B.: Results on coverings of pairs with special reference to coverings by quintuples. Congressus Numerantium23, 169–178 (1971) · Zbl 0265.05010
[15] Giraud, G.: Majoration du nombre de Ramsey ternaires-bicolore en (4,4). C. R. Acad. Sci. ParisAB269, A620-A622 (1969) · Zbl 0321.05005
[16] Giraud, G.: Remarques sur deus problèmes estrémaux. Discrete Mathematics84, 319–321 (1990) · Zbl 0714.05034 · doi:10.1016/0012-365X(90)90138-8
[17] Giraud, G.: Une minoration de la premiere fonction ternaire de Turán, manuscript
[18] Gordon, D.M., Kuperberg, G., and Patashnik, O.: New constructions for covering designs. J. Comb. Design, to be published · Zbl 0885.05053
[19] Katona, G., Nemetz, T., and Simonovits, M.: On a graph problem of Turán, (in Hungarian). Mat. Lapok15, 228–238 (1964) · Zbl 0138.19402
[20] Kim, K.H., Roush, F.W.: On a problem of Turán. In: Studies in pure mathematics, pp. 423–425. Basel-Boston, Mass.: Birkhäuser 1983
[21] Kostochka, A.V.: A class of constructions for Turán’s (3,4)-problem. Combinatorica2, 187–192 (1982) · Zbl 0502.05046 · doi:10.1007/BF02579317
[22] Kuzyurin, N.N.: Asymptotic investigation of the covering problem. Cybernetic Problems37, 19–56 (1980) · Zbl 0464.05021
[23] Feng-Chu Lai, Chang, G.J.: An upper bound for the transversal numbers of 4-uniform hypergraphs. J. Comb. TheoryB 50, 129–133 (1990) · Zbl 0739.05068 · doi:10.1016/0095-8956(90)90101-5
[24] Lamken, E., Mills, W. H., Mullin, R.C., and Vanstone, S.A.: Covering of pairs by quintuples. J. Comb. TheoryA 44, 49–68 (1987) · Zbl 0651.05025 · doi:10.1016/0097-3165(87)90059-8
[25] Lorea, M., On Turán hypergraphs. Discrete Mathematics22, 281–285 (1978) · Zbl 0374.05050 · doi:10.1016/0012-365X(78)90061-4
[26] Mantel, W.: Vraagstuk XXVIII. Wiskundige Opgaven met de Oplossingen10, 60–61 (1907) · JFM 38.0270.01
[27] Mills, W.H.: On the covering of pairs by quadruples I. J. Comb. TheoryA 13, 55–78 (1972) · Zbl 0243.05024 · doi:10.1016/0097-3165(72)90008-8
[28] Mills, W.H.: On the covering of pairs by quadruples II. J. Comb. TheoryA 13, 138–166 (1973) · Zbl 0261.05022 · doi:10.1016/S0097-3165(73)80003-2
[29] Mills, W.H.: On the covering of triples by quadruples. In: Proceedings of the Fifth Southeastern Conference on Combinatorics, Graph Theory and Computing, Boca Raton, Fla., 1974, pp. 573–581. Winnipeg: Utilitas 1974 · Zbl 0308.05009
[30] Mills, W.H.: Covering designs I: covering by a small number of subsets. Ars Combinatoria8, 199–315 (1979) · Zbl 0445.05041
[31] Mills, W.H.: A covering of pairs by quintuples. Ars Combinatoria18, 21–31 (1984) · Zbl 0554.05017
[32] Mills, W.H., Mullin, R.C.: Covering triples by quadruples: an asymptotic solution. J. Comb. TheoryA 41, 117–138 (1986) · Zbl 0587.05022 · doi:10.1016/0097-3165(86)90119-6
[33] Mills, W.H., Mullin, R.C.: Covering pairs by quintuples: the casev 3 modulo 4. J. Comb. TheoryA 49, 308–322 (1988) · Zbl 0666.05023 · doi:10.1016/0097-3165(88)90058-1
[34] Mills, W.H., Mullin, R.C.: Coverings and packings. In: Contemporary Design Theory: A Collection of Surveys, pp. 371–399. Wiley 1992 · Zbl 0783.05038
[35] Mullin, R.C.: On covering pairs by quintuples: the casesv 3 or 11 modulo 20, J. of Combinatorial Mathematics and Combinatorial Computing2, 133–146 (1987) · Zbl 0635.05018
[36] Mullin, R.C.: On the determination of the covering numbersC(2, 5, v). J. of Combinatorial Mathematics and Combinatorial Computing4, 123–132 (1988) · Zbl 0675.05019
[37] Radziszowski, S.P., Zou, J.: Personal communication
[38] Rödl, V.: On a packing and covering problem Europ. J. Comb.5, 69–78 (1985) · Zbl 0565.05016
[39] Schönheim, J.: On coverings. Pacific J. of Mathematics14, 1405–1411 (1964) · Zbl 0128.24501
[40] Sidorenko, A.F.: On Turán numbersT(n, 5, 4) and numbers of monochromatic 4-cliques in 2-colored 3-graphs (in Russian). Voprosi Kibernetiki no. 64, 117–124 (1980) · Zbl 0508.05035
[41] Sidorenko, A.F.: Systems of sets that have theT-property. Moscow University Mathematics Bulletin36, no. 5, 22–26 (1981) · Zbl 0493.05002
[42] Sidorenko, A.F.: The method of quadratic forms and Turán’s combinatorial problem. Moscow University Mathematics Bulletin37, no. 1, 1–5 (1982) · Zbl 0515.05037
[43] Sidorenko, A.F. Extremal constants and inequalities for distributions of sums of random vectors (in Russian). Ph.D. Thesis, Moscow State University, 1982
[44] Sidorenko, A.F.: The Turán problem for 3-graphs (in Russian). Combinatorial Analysis (Russian), no. 6, pp. 51–57. Moscow State University, 1983 · Zbl 0578.05011
[45] Sidorenko, A.F.: Exact values of Turán numbers. Math. Notes42, 913–918 (1987) · Zbl 0657.05004
[46] Sidorenko, A.: Upper bounds on Turán numbers. Submitted to J. Comb. Theory, ser. A
[47] Stanton, R.G., Bate, J.A.: A computer search for B-coverings. Lect. Notes in Math., no. 829, 37–50 (1980) · Zbl 0467.05025 · doi:10.1007/BFb0088898
[48] Stanton, R.G., Buskens, R.W., and Allston, J.L.: Computation of the covering numberN(2, 5, 24). Utilitas Mathematica37, 127–144 (1990) · Zbl 0761.05029
[49] Surányi, J.: Some combinatorial problems of geometry (in Hungarian). Mat. Lapok22, 215–230 (1971)
[50] Todorov D.T., Tonchev, V.D.: On some coverings of triples. C. R. Bulg. Acad. Sci.35, 1209–1211 (1982) · Zbl 0506.05021
[51] Todorov, D.T.: A method of constructing coverings. Math. Notes35, 869–876 (1984) · Zbl 0548.05020
[52] Todorov D.T.: Some coverings derived from finite planes. In: Colloq. Math. Soc. János Bolyai, Vol. 37, Finite and Infinite Sets, Eger, 1981, pp. 697–710. Budapest: Akad. Kiadó 1985
[53] Todorov, D.T.: On the covering of pairs by 13 blocks. C. R. Bulg. Acad. Sci.38, 691–694 (1985) · Zbl 0577.05013
[54] Todorov, D.T.: On the covering of triples by eight blocks. Serdica12, 20–29 (1986) · Zbl 0661.05022
[55] Todorov, D.T.: Lower bounds for coverings of pairs by large blocks. Combinatorica9, 217–225 (1989) · Zbl 0696.05009 · doi:10.1007/BF02124682
[56] Turán, P.: Egy gráfelméleti szélsöértékfeladatról. Mat. és Fiz. Lapok48, 436–453 (1941)
[57] Turán, P.: Research problems. Maguar Tud. Akad. Mat. Kutato Int. Közl.6, 417–423 (1961)
[58] Turán, P.: Applications of graph theory to geometry and potential theory. In: Combinatorial Structures and Their Applications, pp. 423–434. New York: Gordon and Breach 1970 · Zbl 0272.05119
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.