Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let and define to be maximal such that there exists a family of subsets of of size such that for all .
Estimate for . In particular, is it true that for every there exists such that for all we have
Source: erdosproblems.com/703
An accepted solution exists. The statement is true.
Proved on the site (label PROVED at the access of 2026-09-04; page last edited 16 October 2025). The community database lists the status as proved (Lean) as of its last update, dated 2026-09-16, the Lean qualification resting on Collin Yuanjie Ren's formalization of the Frankl–Füredi theorem, which is linked from the Frankl–Füredi claim page (1984). The site records that trivially, that Frankl and Füredi [FrFu84b] determined for fixed and large in terms of (the extremal family being the sets of size less than together with the large sets of Katona's family, in its odd and even forms), that Frankl [Fr77b] had done the case for every , that a yes answer to the second question implies the exponential growth of the chromatic number of the unit-distance graph of , proved by other means by Frankl and Wilson [FrWi81] (see Problem 704), and that Frankl and Rödl [FrRo87] answered the second question yes.