Problem 500

What is $\mathrm{ex}_3(n,K_4^3)$ ? That is, the largest number of $3$ -edges which can placed on $n$ vertices so that there exists no $K_4^3$ , a set of 4 vertices which is covered by all 4 possible $3$ -edges.

Source: erdosproblems.com/500

Graph theory
Hypergraphs
Turán numbers

Wiki page

Status

Open

No claim settles this problem.

Open. Turán's construction (three almost equal parts $X_1,X_2,X_3$ ; the triples with one vertex in each part and the triples with two vertices in $X_i$ and one in $X_{i+1}$ ) gives $\mathrm{ex}_3(n,K_4^3)\ge(\tfrac59+o(1))\binom n3$ , and Turán conjectured that this is the truth. The best rigorous upper bound on record is $\pi(K_4^3)\le0.5615$ , from Section 5.1 of Baber's 2012 preprint [Ba12] (result page; a flag-algebra certificate whose data are on arXiv; no refereed version found, so the preprint qualification applies). Razborov's refereed Theorem 1 [Ra10] (result page) settles the density at $5/9$ only under the additional exclusion of four vertices spanning exactly one edge, and the 2008 preprint records the unrestricted figure $0.561666$ as a floating-point computation that Razborov did not convert into a rigorous proof; before it the rigorous record was Chung and Lu's $\pi(K_4^3)\le(3+\sqrt{17})/12\approx0.5936$ , as Razborov quotes it. The site's figure $0.5611666$ matches neither [Ra10] nor [Ba12] and is recorded below as a discrepancy. No proof of $5/9$ , no better construction and no new rigorous upper bound was found in the search whose scope the Current assessment records. This is a bounded negative finding, not a certificate of openness.

Er61: Erdős, Paul, Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. 6 (1961), 221--254; Part II, item 8, p. 243. Library home: Erdős 1961 (the 34-page Rényi archive scan).
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 (a scan); the passage is 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, and the comparison sentence, p. 81. Library home: Erdős 1974 (a typescript scan).
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).
Ra10: Razborov, Alexander A., On 3-hypergraphs with forbidden 4-vertex configurations. SIAM J. Discrete Math. 24 (2010), no. 3, 946--963, doi:10.1137/090747476 (Crossref record read; the site's reference text gives "SIAM J. Discrete Math. (2010), 946-963"). Library home: Razborov 2010 (the author's preprint of 15 December 2008; the journal text is not held).
Ba12: Baber, Rahil, Turán densities of hypercubes. arXiv:1201.3587v2 (13 November 2012; v1 17 January 2012); Section 5.1, p. 14. A preprint. Library home: Baber 2012.
GGTW25: Georgiev, B., Gómez-Serrano, J., Tao, T. and Wagner, A. Z., Mathematical exploration and discovery at scale. arXiv:2511.02864 (v3 22 December 2025, 81 pages; abstract read). A report of searches with AlphaEvolve over 67 problems; lead, recorded below.
KKLLSW26: Kielak, B., Král', D., Lamaison, A., Liu, H., Shu, X. and Wu, Z., Solution of uniform Turán's tetrahedron problem. arXiv:2609.08336 (v2 10 September 2026; abstract read); [Bu26] Bucić, M., The uniform Turán density of the tetrahedron. arXiv:2609.11802 (10 September 2026; abstract read). Both concern the uniform Turán density, a different quantity; leads, recorded below.

Problem 500

Status

Proof claims

Discussion