Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-27T09:42:25.528Z Has data issue: false hasContentIssue false
  • English
  • Français

Constructive Upper Bounds for the Turán Number

Published online by Cambridge University Press:  01 December 1997

ULRICH MATTHIAS
ULRICH MATTHIAS
Affiliation:
Mathematical Institute, University of Heidelberg, Heidelberg, Germany; (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

The Turán Number T(n, k, r) is the smallest possible number of edges in a k-graph of order n such that every set of r vertices contains an edge. The limit

formula here

exists, but there is no pair (k, r) with r>k[ges ]3 for which this function could be determined as yet. We give a constructive proof of the upper bound

formula here

for every k and r with r[ges ]k[ges ]2. In the case k=6, r=11 we improve this result, refuting thereby a conjecture of Turán.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 6 , Issue 4 , December 1997 , pp. 475 - 479
Copyright
1997 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)