---

Claim. $g(n)\asymp n^{1/2}$, with explicit constants: Theorem 2.3 of Maximal independent subsets in Steiner systems and in planar sets states that

$$\frac{2\sqrt3}{9}\sqrt n<g(n)<2\sqrt n,$$

where $g(n)$ is the least, over all maps $f$ from the pairs of $\{1,\ldots,n\}$ to $\{1,\ldots,n\}$ with $f(x,y)\notin\{x,y\}$, of the largest independent set, as the problem defines it. The theorem is Section 2.2 of a paper whose main subject is independent subsets of planar point sets. Füredi recalls the question of Erdős and Hajnal [ErHa58] with their bounds $c_6n^{1/3}<g(n)<c_7\sqrt{n\log n}$, the lower from the greedy algorithm and the upper from the mean over random $f$, and observes that although the triples $\{i,j,f(i,j)\}$ resemble a Steiner triple system, the true order of $g(n)$ is not $\sqrt{n\log n}$, so the large-girth hypothesis in the Komlós–Pintz–Szemerédi inequality cannot be dropped. The lower bound is a special case of Spencer's theorem [Sp72], that a $3$-uniform hypergraph on $n$ vertices with average degree $d$ has an independent set of size at least $c\,n/\sqrt d$. The upper bound is an explicit map: partition $\{1,\ldots,n\}$ into $a=\lceil\sqrt n\rceil$ blocks $V_i=\{(i,1),\ldots,(i,b_i)\}$ with $b_1\le\cdots\le b_a=\lfloor\sqrt n\rfloor$, and for $i<j$, $x\ne y$ and $y\le b_j$ set $f((i,x),(j,y))=(j,x)$, the other values arbitrary. If $I$ is independent and $I_i$ is the set of second coordinates of $I\cap V_i$, then for $i<j$ the sets $I_i$ and $I_j$ cannot meet when $|I_j|>1$, which gives $|I|\le\lceil\sqrt n\rceil+\lfloor\sqrt n\rfloor-1$. As printed, the partition needs $\lceil\sqrt n\rceil\lfloor\sqrt n\rfloor\ge n$, which fails when $m^2+m<n<(m+1)^2$ with $m=\lfloor\sqrt n\rfloor$, for example at $n=7$. For those $n$, blocks of up to $m+1$ points cover $\{1,\ldots,n\}$, and the same argument gives $|I|\le2m+1$. Since $n\ge m^2+m+1$, $2m+1<2\sqrt n$, so the theorem stands. This answers the question as asked, the order of $g(n)$; the asymptotic constant is not determined. The same upper bound was proved independently later by Conlon, Fox and Sudakov, whose paper records Füredi's priority and whom the site credits; their page is Conlon, Fox and Sudakov 2016.

Depends on. Spencer's lower bound supplies $g(n)\gg n^{1/2}$, which the paper derives as a special case of Spencer's theorem and does not reprove.

Acceptance. Refereed: Z. Füredi, Maximal independent subsets in Steiner systems and in planar sets, SIAM J. Discrete Math. 4 (1991), no. 2, 196–199, received 2 December 1988 and accepted 18 December 1989, as the paper prints; the issue is dated May 1991 and the record gives no day, so the page is dated to the first day of that month. The site does not cite Füredi, so no curator credit is listed. Nothing here rests on this project's own review.