Erdős Problem #1158

Erdős Problem 1158 --- GPT 6 Astra Ultra partial attempt

FORMAL RESTATEMENT

For fixed integers $t,r\geq2$, let $K_t(r)$ have $t$ vertex classes of size $r$, with every transversal $t$-set an edge. Is \[ \operatorname{ex}_t(n,K_t(r))\geq n^{\,t-r^{1-t}-o(1)} \qquad(n\to\infty) \] always true?

CONTEXT AND SCOPE

This replaces the earlier statement-only record with an elementary mathematical attempt. The arguments below establish only their stated partial results; no novelty or full solution is claimed.

The parameter range t,r>=2 is the nondegenerate Turan-problem range; the official wording says 'for all t,r' without spelling it out.

ATTACK PLAN AND WORK

The elementary random construction quantifies a specific exponent gap. Write $v=tr$ and $e=r^t$ for the vertex and edge counts of the forbidden hypergraph. In a random $t$-uniform hypergraph on $n$ vertices with edge probability $p$, the expected numbers of edges and labeled forbidden copies are respectively $\binom nt p$ and at most $n^{tr}p^{r^t}$. Remove one edge per surviving copy. The resulting graph is forbidden-copy-free and retains at least the original edge count minus the original copy count.

Put $a=(tr-t)/(r^t-1)$ and $p=c n^{-a}$. The two expectations both have exponent $t-a$, since $tr-ar^t=t-a$. For a sufficiently small constant $c=c(t,r)>0$, the positive term, of order $c n^{t-a}$, dominates the negative term of order $c^{r^t}n^{t-a}$. Some outcome therefore gives \[\operatorname{ex}_t(n,K_t(r))\gg n^{t-(tr-t)/(r^t-1)}.\tag{1}\]

The loss in $1$ is strictly larger than the requested $r^{1-t}$, because $t(r-1)r^{t-1}>r^t-1$ for $t,r\ge2$. For $t=r=2$, for instance, this method gives exponent $4/3$ rather than $3/2$. This comparison is about this construction, not a claim that $4/3$ is the best known bound in that special case.

VERIFICATION AND REMAINING GAP

A construction with correlated edges or algebraic structure is needed to beat the deletion cost of independent random edges and reach the conjectured exponent. The elementary alteration does not do so.

SOURCES

https://www.erdosproblems.com/1158

FINAL

UNRESOLVED. The full source problem remains outside the scope of the proved partial results.

COMPLETION ESTIMATE

$8\%$. This is a conservative subjective estimate toward the whole problem, not a probability that the argument is correct or a claim that a fixed fraction of the problem has been solved.