Problem 712

Determine, for any $k>r>2$ , the value of

\frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}},

where $\mathrm{ex}_r(n,K_k^r)$ is the largest number of $r$ -edges which can placed on $n$ vertices so that there exists no set of $k$ vertices which is covered by all $\binom{k}{r}$ possible $r$ -edges.

Source: erdosproblems.com/712

Graph theory
Turán numbers
Hypergraphs

Wiki page

Status

Open

No claim settles this problem.

Open. Turán's 1941 theorem settles $r=2$ for every $k$ ; for $r>2$ no pair $k>r$ has a determined density in the sources listed under Search scope. The smallest case, $r=3$ and $k=4$ , is Problem 500 (Turán's conjectured $5/9$ against the rigorous upper bound $0.5615$ ), and for $r=3$ , $k=5$ Turán's conjectured value $g(2n;3,5)=2n\binom n2+1$ of the least number of triples on $2n$ points forcing a $K_5^3$ ([Er71], display (8); $f(2n,3,5)=n^2(n-1)+1$ in [Er69], p. 80), one more than the extremal number $n^2(n-1)$ , corresponds to the density $3/4$ (by the computation $n^2(n-1)/\binom{2n}3\to3/4$ ), also unproved. Erdős's offers stand as printed in [Er81] (Part III, item 1, p. 6): one prize "for even a single $k>r>2$ " and another "for clearing up the whole set of problems". No determination of any pair and no proof claim was found in the search whose scope the Current assessment records; the problem has no claim pages, so its frontmatter standing is open with no claim. The search is a bounded negative finding, not a certificate of openness.

Er71: Erdős, P., Some unsolved problems in graph theory and combinatorial analysis. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) (1971), 97--109; item 15, closing paragraph and display (8), p. 104. Library home: Erdős 1971; paged at Erdős 1971, Item 15 (pp. 103-104).
Er74c: Erdős, Paul, Extremal problems on graphs and hypergraphs. Hypergraph Seminar, Lecture Notes in Math. 411 (1974), 75--84; the Turán paragraph, p. 76. Library home: Erdős 1974.
Er81: Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), 25--42; Part III, item 1, p. 6 of the re-typeset copy. Library home: Erdős 1981 (a re-typeset copy with its own pagination; the site's reference text gives "Combinatorica (1981), 25-42").
Er64f: Erdős, P., On extremal problems of graphs and generalized graphs. Israel J. Math. 2 (1964), 183--190; pp. 183--184. Not cited by the site for this problem. Library home: Erdős 1964 (a Rényi archive scan).
Er69: Erdős, Paul, Some applications of graph theory to number theory. The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968), Springer (1969), 77--82; Turán's conjecture $f(2n,3,5)=n^2(n-1)+1$ , p. 80. Not cited by the site for this problem. Library home: Erdős 1969; the p. 80 paragraph is quoted at Erdős 1969, Conjecture (p. 81).

Problem 712

Status

Proof claims

Discussion