Abstract
Turán's problem is to determine the maximum numberT(n,k,t) oft-element subsets of ann-set without a complete sub-hypergraph onk vertices, i.e., allt-subsets of ak-set. It is proved that fora≥1 fixed andt sufficiently largeT(n, t+a,t)>(1-a(a+4+o(1))logt/( t a )( n t holds
This is a preview of subscription content, log in via an institution to check access.
Access this article
We’re sorry, something doesn't seem to be working properly.
Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.
Similar content being viewed by others
References
de Caen, D.: Extension of a theorem of Moon and Moser on complete subgraphs. Ars Comb.16, 5–10 (1983)
Erdös, P., Lovász, L.: On 3-chromatic hypergraphs. Infinite and finite sets. Colloq. Math. Soc. János Bolyai10, 609–627 (1975)
Katona, G.O.H., Nemetz, T., Simonovits, M.: On a graph-problem of Turán (in Hungarian). Mat. Lapok15, 228–238 (1964)
Kim, H.K., Roush, F.W.: On a problem of Turán. In: Studies in Pure Mathematics, pp. 423–425. Basel: Birkhäuser 1983
Tazawa, S.: Lecture delivered at Japan Math. Soc. Meeting, April 1983
Turán, P.: An extremal problem in graph theory (in Hungarian). Mat. Fiz. Lapok48, 436–452 (1941)
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Frankl, P., Rödl, V. Lower bounds for Turán's problem. Graphs and Combinatorics 1, 213–216 (1985). https://doi.org/10.1007/BF02582949
Issue date:
DOI: https://doi.org/10.1007/BF02582949