Abstract
The numbers which are traditionally named in honor of Paul Turán were introduced by him as a generalization of a problem he solved in 1941. The general problem of Turán having anextremely simple formulation but beingextremely hard to solve, has become one of the most fascinatingextremal problems in combinatorics. We describe the present situation and list conjectures which are not so hopeless.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
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)
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
Caen, D. de: Extension of a theorem of Moon and Moser on complete subgraphs. Ars Combinatoria16, 5–10 (1983)
Caen, D. de: A note on the probabilistic approach to Turán's problem. J. Comb. TheoryB 34, 340–349 (1983)
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
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)
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)
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)
Erdos, P.: On the combinatorial problems I would most like to see solved. Combinatorica1, 25–42 (1981)
Fon-Der-Flaass, D.G.: A method for constructing (3,4)-graphs. Math. Notes44, (1988)
Fort, M.K., Hedlund, G.A.: Minimal coverings of pairs by triples. Pacific J of Mathematics8, 709–719 (1958)
Frankl, P., Rödl, V.: Lower bounds for Turán's problem. Graphs and Combinatorics1, 213–216 (1985)
Füredi, Z.: Covering pairs byq 2 +q + 1 sets. J. Comb. TheoryA 54, 248–271 (1990)
Gardner, B.: Results on coverings of pairs with special reference to coverings by quintuples. Congressus Numerantium23, 169–178 (1971)
Giraud, G.: Majoration du nombre de Ramsey ternaires-bicolore en (4,4). C. R. Acad. Sci. ParisAB269, A620-A622 (1969)
Giraud, G.: Remarques sur deus problèmes estrémaux. Discrete Mathematics84, 319–321 (1990)
Giraud, G.: Une minoration de la premiere fonction ternaire de Turán, manuscript
Gordon, D.M., Kuperberg, G., and Patashnik, O.: New constructions for covering designs. J. Comb. Design, to be published
Katona, G., Nemetz, T., and Simonovits, M.: On a graph problem of Turán, (in Hungarian). Mat. Lapok15, 228–238 (1964)
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
Kostochka, A.V.: A class of constructions for Turán's (3,4)-problem. Combinatorica2, 187–192 (1982)
Kuzyurin, N.N.: Asymptotic investigation of the covering problem. Cybernetic Problems37, 19–56 (1980)
Feng-Chu Lai, Chang, G.J.: An upper bound for the transversal numbers of 4-uniform hypergraphs. J. Comb. TheoryB 50, 129–133 (1990)
Lamken, E., Mills, W. H., Mullin, R.C., and Vanstone, S.A.: Covering of pairs by quintuples. J. Comb. TheoryA 44, 49–68 (1987)
Lorea, M., On Turán hypergraphs. Discrete Mathematics22, 281–285 (1978)
Mantel, W.: Vraagstuk XXVIII. Wiskundige Opgaven met de Oplossingen10, 60–61 (1907)
Mills, W.H.: On the covering of pairs by quadruples I. J. Comb. TheoryA 13, 55–78 (1972)
Mills, W.H.: On the covering of pairs by quadruples II. J. Comb. TheoryA 13, 138–166 (1973)
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
Mills, W.H.: Covering designs I: covering by a small number of subsets. Ars Combinatoria8, 199–315 (1979)
Mills, W.H.: A covering of pairs by quintuples. Ars Combinatoria18, 21–31 (1984)
Mills, W.H., Mullin, R.C.: Covering triples by quadruples: an asymptotic solution. J. Comb. TheoryA 41, 117–138 (1986)
Mills, W.H., Mullin, R.C.: Covering pairs by quintuples: the casev ≡ 3 modulo 4. J. Comb. TheoryA 49, 308–322 (1988)
Mills, W.H., Mullin, R.C.: Coverings and packings. In: Contemporary Design Theory: A Collection of Surveys, pp. 371–399. Wiley 1992
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)
Mullin, R.C.: On the determination of the covering numbersC(2, 5, v). J. of Combinatorial Mathematics and Combinatorial Computing4, 123–132 (1988)
Radziszowski, S.P., Zou, J.: Personal communication
Rödl, V.: On a packing and covering problem Europ. J. Comb.5, 69–78 (1985)
Schönheim, J.: On coverings. Pacific J. of Mathematics14, 1405–1411 (1964)
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)
Sidorenko, A.F.: Systems of sets that have theT-property. Moscow University Mathematics Bulletin36, no. 5, 22–26 (1981)
Sidorenko, A.F.: The method of quadratic forms and Turán's combinatorial problem. Moscow University Mathematics Bulletin37, no. 1, 1–5 (1982)
Sidorenko, A.F. Extremal constants and inequalities for distributions of sums of random vectors (in Russian). Ph.D. Thesis, Moscow State University, 1982
Sidorenko, A.F.: The Turán problem for 3-graphs (in Russian). Combinatorial Analysis (Russian), no. 6, pp. 51–57. Moscow State University, 1983
Sidorenko, A.F.: Exact values of Turán numbers. Math. Notes42, 913–918 (1987)
Sidorenko, A.: Upper bounds on Turán numbers. Submitted to J. Comb. Theory, ser. A
Stanton, R.G., Bate, J.A.: A computer search for B-coverings. Lect. Notes in Math., no. 829, 37–50 (1980)
Stanton, R.G., Buskens, R.W., and Allston, J.L.: Computation of the covering numberN(2, 5, 24). Utilitas Mathematica37, 127–144 (1990)
Surányi, J.: Some combinatorial problems of geometry (in Hungarian). Mat. Lapok22, 215–230 (1971)
Todorov D.T., Tonchev, V.D.: On some coverings of triples. C. R. Bulg. Acad. Sci.35, 1209–1211 (1982)
Todorov, D.T.: A method of constructing coverings. Math. Notes35, 869–876 (1984)
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
Todorov, D.T.: On the covering of pairs by 13 blocks. C. R. Bulg. Acad. Sci.38, 691–694 (1985)
Todorov, D.T.: On the covering of triples by eight blocks. Serdica12, 20–29 (1986)
Todorov, D.T.: Lower bounds for coverings of pairs by large blocks. Combinatorica9, 217–225 (1989)
Turán, P.: Egy gráfelméleti szélsöértékfeladatról. Mat. és Fiz. Lapok48, 436–453 (1941)
Turán, P.: Research problems. Maguar Tud. Akad. Mat. Kutato Int. Közl.6, 417–423 (1961)
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
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Sidorenko, A. What we know and what we do not know about Turán numbers. Graphs and Combinatorics 11, 179–199 (1995). https://doi.org/10.1007/BF01929486
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01929486