Skip to content

Erdős problem 1028

Start work

Let H(n)=min⁡fmax⁡X⊆{1,…,n}∣∑x<y∈Xf(x,y)∣,H(n)=\min_f \max_{X\subseteq \{1,\ldots,n\}} \left\lvert \sum_{x<y\in X} f(x,y)\right\rvert, where ff ranges over all functions f:{1,…,n}2→{−1,1}f:\{1,\ldots,n\}^2\to \{-1,1\}. Estimate H(n)H(n).

Sources

The source's own material, retained exactly.

4 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

1028.lean

Retained formal statement2 of 4

Erdős and Spencer [ErSp71] proved that H(n)≫n3/2H(n)\gg n^{3/2}.

FormalConjectures/ErdosProblems/1028.leanErdos1028.erdos_1028.variants.erdos_spencer1 lineExact file
(fun n => ↑n ^ (3 / 2)) =O[Filter.atTop] fun n => ↑(Erdos1028.H n)
SolvedStatement only, no proof