Claims

../

1958_03_01_erdos_hajnal: Erdős and Hajnal (1958) prove that every mapping of pairs of an n-set to outside points admits an independent set of order n^(1/3) and that some mapping admits none above order root(n log n); refereed, both superseded.

1972_05_01_spencer: Spencer's Turán theorem for k-graphs (1972) gives every pair mapping on an n-set an independent set of order the square root of n, the lower bound half of the problem; refereed in Discrete Mathematics and credited by the curator.

1991_05_01_furedi: Füredi (1991) proves (2 root 3/9) root n < g(n) < 2 root n, the lower bound from Spencer's theorem and the upper bound by a block construction, settling the order of g(n) before Conlon, Fox and Sudakov; in SIAM J. Discrete Math.

2015_07_02_conlon_fox_sudakov: A pair mapping on a square-grid ground set with no independent set larger than a constant times the square root of n, which with Spencer's lower bound gives g(n) of order root n; refereed in J. Combin. Theory Ser. B.

---