Erdős problem 775 · problems.science

Is there a $3$ -uniform hypergraph on $n$ vertices which contains at least $n-O(1)$ different sizes of cliques (maximal complete subgraphs)?

Sources

Browse retained paths and inspect the exact material available for this Problem.

4 retained statements2415f78e850a

FormalConjectures/ErdosProblems/

775.lean

Retained formal statement4 of 4

For graphs, Spencer [Sp71] constructed a graph which contains cliques of at least $n-\log_2n+O(1)$ different sizes.

FormalConjectures/ErdosProblems/775.leanErdos775.erdos_775.variants.spencer1 lineExact file

1∃ C, ∀ (n : ℕ), ∃ G, ↑n - Real.logb 2 ↑n - C ≤ ↑G.cliqueSizes.ncard

SolvedStatement only, no proof