---

A proof claim submitted on 2026-09-15 to the site's proof-claim tab by Samuel Korsky, using GPT Astra as the tab names the system, with the proof in an external file linked from the submission. The site states that a listing on the tab is no guarantee of correctness and that nobody associated with the site has examined the proof. The account below follows the submission's summary.

Submission note. Posted to erdosproblems.com as a proof claim by Samuel Korsky (account SamKorsky) on 15 September 2026, giving "GPT Astra" as the AI used:

We prove that $f(n) = (1 + o(1))\sqrt{n}$, resolving the problem fully (even though it is already marked as solved) and positively answering Alon's conjecture. The idea is to start with a Erdős–Rényi orthogonal polarity graph $ER_p$ which already has many desirable properties (the right max degree, diameter 2, all triangles edge-disjoint) and replace each vertex by a fiber $W_v\cong\mathbb F_q^2$ for a prime $q \sim 2p$. Furthermore, we replace every base edge by a bipartite graph defined by a linear equation. Equal forms around a base triangle make its three cross-edge equations inconsistent, whereas forms with distinct kernels along a nontriangular two-edge path produce a unique common neighbor. A sparse local graph inside each fiber supplies the remaining two-edge paths and controls the degree added during maximal completion. This gives the desired bound for a dense sequence of orders; a final independent blow-up realizes every intermediate order.

The claim. $f(n)=(1+o(1))\sqrt n$: the trivial lower bound $f(n)\ge\sqrt{n-1}$ is asymptotically sharp, which answers in the affirmative the conjecture in Alon's 2024 note, also cited on Problem 134. In outline, as the submission's summary describes it, the construction is a fibered polarity graph. The base is the Erdős--Rényi polarity graph $ER_p$, whose maximum degree is already of order $\sqrt{|V|}$, whose diameter is $2$ and whose triangles are pairwise edge-disjoint. Over each base vertex sits a copy of $\mathbb F_q^2$, with $q$ a prime close to $2p$, and each base edge is replaced by the bipartite graph between the two copies defined by one linear equation. The linear forms are chosen so that the three equations around any base triangle have no common solution, which kills the triangles, while along a path of two base edges that is not part of a triangle the forms have different kernels, so the two end vertices get exactly one common neighbor. Paths of length two inside a single copy come from a sparse graph placed there, and the final step, completing to a maximal triangle-free graph, raises the degree only by a controlled amount. The argument reaches the bound for a sequence of orders $n$ that is dense enough, and a blow-up of the construction fills in the orders between them.

Relation to the accepted claims. The submission says it resolves the problem fully, and the asymptotic does settle both questions, the order of growth and whether $f(n)/\sqrt n\to\infty$; both are already settled by the accepted claims of Füredi and Seress and Haviv and Levy, so the submission's content beyond those claims is the value of the constant, $f(n)/\sqrt n\to1$, which the problem does not ask.

Depends on. Nothing in this wiki; the construction is self-contained.

Standing. Claimed: the submission is pending on the site's tab with no comments, no review and no other posting found; it is not refereed, and no check of the argument was made here.