gpt 6 astra ultra attempt on Math-410

Turan Conjecture on the Turan Density of K_4^{$3$}

Definitions and mathematical statement

A $3$-uniform hypergraph on $n$ vertices is a family of three-element subsets. Write $K_4^{(3)}$ for all four triples of a four-element set and let $\operatorname{ex}(n,K_4^{(3)})$ be the maximum number of edges avoiding a copy of this hypergraph. Its Turán density is \[ \pi(K_4^{(3)})=\lim_{n\to\infty} \frac{\operatorname{ex}(n,K_4^{(3)})}{\binom n3}. \] The conjecture is $\pi(K_4^{(3)})=5/9$. A copy means all four required edges are present, with no induced-subgraph restriction. The question is an asymptotic density, not an exact formula for every finite $n$, nor the related problem of forbidding a tetrahedron with one edge removed.

Formulation and concept references: [S1].

Short English statement

Is the maximum asymptotic edge density of a triple system with no complete four-vertex triple system exactly five ninths?

Research attempt

Process and attack route.

This attempt was generated by GPT-6 Astra Ultra on 27 September 2026. We prove the standard $5/9$ construction directly, derive an elementary finite-subgraph upper bound, and test two routes toward closing the gap: perturbing the construction's part sizes and cloning vertices to force a simpler extremal structure. The part-size calculation gives only a local statement within one family, while the cloning calculation exposes a concrete loss of edges.

The introduction of [S1] distinguishes the tetrahedron problem from the tight-cycle-minus-an-edge problems treated in that paper. In particular, a theorem for $K_4^{(3)}$ with an edge removed is not an answer for the complete four-vertex 3-graph here. We seek the asymptotic density, not an exact formula for every finite $n$. The bounds below are elementary baselines and are not claimed to improve the literature.

Existence of the limiting density.

Let $e_n=\operatorname{ex}(n,K_4^{(3)})$ and $p_n=e_n/\binom n3$ for $n\ge3$. In any $K_4^{(3)}$-free 3-graph on $n$ vertices, the expected number of edges in a uniformly chosen $m$-vertex subset is \[ e(H)\frac{\binom m3}{\binom n3},\qquad 3\le m\le n. \] Every induced $m$-vertex subgraph is still free of the tetrahedron, so this expectation is at most $e_m$. Applying the inequality to an extremal $H$ proves $p_n\le p_m$. Since $0\le p_n\le1$, the sequence decreases to a limit. This proves the existence of $\pi(K_4^{(3)})$ by averaging and shows how any exact small-order bound gives an upper bound for the limit.

The cyclic three-part construction.

Partition the vertices into $A,B,C$ of sizes $a,b,c$. Include every triple with one vertex in each part, every triple with two vertices in $A$ and one in $B$, every triple with two in $B$ and one in $C$, and every triple with two in $C$ and one in $A$. No other triples are included. Its edge number is \[ abc+\binom a2b+\binom b2c+\binom c2a. \tag{406.1} \] We verify freedom from $K_4^{(3)}$ by the distribution of four vertices among the parts. If at least three lie in one part, the triple consisting of three vertices in that part is absent. If the distribution is $2+2$, the two required types of repeated-part triples point in opposite directions between the same two parts; only one direction is allowed by the cycle $A\to B\to C\to A$. Thus at least one required triple is absent. If the distribution is $2+1+1$, the repeated pair would have to form allowed triples with both of the other parts, but its part has only one outgoing direction. Again a triple is missing. These cases exhaust all possibilities.

Choose part sizes differing by at most one. Then $a,b,c=n/3+O(1)$, and $406.1$ is \[ \frac{n^3}{27}+3\frac{n^3}{54}+O(n^2) =\frac{5n^3}{54}+O(n^2). \] Since $\binom n3=n^3/6+O(n^2)$, this proves \[ \pi(K_4^{(3)})\ge5/9. \tag{406.2} \] The proof is an explicit construction and counting argument, not an assumption that extremal examples must have three parts.

An elementary upper bound from five vertices.

A $K_4^{(3)}$-free 3-graph on five vertices has at most seven edges. Indeed each of the five four-vertex subsets must contain a missing triple. Each missing triple belongs to exactly two of those four-vertex subsets. Therefore at least $\lceil5/2\rceil=3$ of the ten possible triples are missing. The construction $406.1$ with $(a,b,c)=(2,2,1)$ has seven edges, so the five-vertex bound is sharp.

Averaging over all five-vertex subsets of an arbitrary larger graph gives \[ e(H)\binom{n-3}{2}\le7\binom n5, \qquad \frac{e(H)}{\binom n3}\le\frac7{10} \quad(n\ge5). \tag{406.3} \] Thus the arguments written here place the density between $5/9$ and $7/10$. The upper estimate is intentionally weak. More elaborate local constraints may improve it, but the five-vertex inequality alone cannot yield $5/9$, because its sharp ratio is exactly $7/10$.

Testing nearby part-size perturbations.

Let the three part proportions tend to $\alpha,\beta,\gamma\ge0$ with sum one. The limiting density of $406.1$ is \[ F(\alpha,\beta,\gamma) =6\alpha\beta\gamma+3(\alpha^2\beta+\beta^2\gamma+\gamma^2\alpha). \tag{406.4} \] Set $\alpha=1/3+u$, $\beta=1/3+v$, $\gamma=1/3+w$, where $u+v+w=0$. Direct expansion gives \[ F=\frac59-(u^2+v^2+w^2) +6uvw+3(u^2v+v^2w+w^2u). \tag{406.5} \] For $\eta=\max(|u|,|v|,|w|)$, the cubic terms have absolute value at most $6\eta(u^2+v^2+w^2)$. One bound is $|uvw|\le\eta(u^2+v^2)/2$ together with $|u^2v+v^2w+w^2u|\le\eta(u^2+v^2+w^2)$. Consequently, if $\eta<1/6$ and the perturbation is nonzero, \[ F\le\frac59-(1-6\eta)(u^2+v^2+w^2)<\frac59. \tag{406.6} \] Thus a sufficiently small imbalance in the familiar construction cannot furnish a density counterexample. The calculation proves a strict local maximum inside this particular three-part family. It neither optimizes all possible hypergraphs nor proves that every extremal sequence has that form. Such a structural reduction would be a major additional statement.

A vertex-cloning calculation and its lost term.

For vertices $u\ne v$, let $d(u)$ be the number of incident edges and let $d(u,v)$ be their codegree, the number of edges containing both. Define a clone operation by deleting all edges containing $u$ and replacing them by the triples $\{u,a,b\}$ for which $\{v,a,b\}$ was an old edge with $a,b\notin\{u,v\}$. The resulting graph has no edge containing both $u$ and $v$.

This operation preserves tetrahedron-freeness. A putative tetrahedron containing both $u$ and $v$ would require an edge containing that pair, which is absent. A putative tetrahedron containing $u$ but not $v$ would, on replacing $u$ by $v$, give a tetrahedron in the original graph. A tetrahedron not containing $u$ would already have been present. These exhaust the cases.

However, its exact change in edge count is \[ e(H')-e(H)=-d(u)+d(v)-d(u,v). \tag{406.7} \] The last term is essential: the edges containing both old vertices cannot become valid new clone edges. Choosing a vertex $v$ of at least as high a degree as $u$ does not guarantee that the operation increases, or even preserves, the total number of edges.

For a concrete countertest, take the construction with three parts of size two. It has fourteen edges on six vertices. Every vertex has degree seven, while every pair has positive codegree: two for a pair in the same part and three for a pair in different parts. Thus every clone operation of the form just defined strictly decreases the edge number, by two or three. This rules out a proposed monotone simplification based solely on selecting a maximum-degree vertex and cloning it. It does not rule out other symmetrizations with additional structure.

The graph-theoretic instinct behind cloning is still useful as a diagnostic. In a hypergraph, links overlap through nontrivial codegrees, and a degree comparison omitting that overlap has the wrong objective value. A successful upper-bound proof must account for those interactions instead of discarding them.

Verification and outcome.

The accompanying enumeration checks all $2^{10}$ 3-graphs on five labeled vertices, confirms that the largest tetrahedron-free examples have seven edges, and checks the cyclic construction for a range of part sizes. It separately verifies every clone operation in the balanced six-vertex example and the polynomial identity $406.5$. These finite computations support the stated lemmas; they do not determine the limiting density.

UNRESOLVED. The construction proves the conjectured lower bound, while the elementary upper bound remains $7/10$. Local part-size optimization and the cloning test do not establish a general upper bound of $5/9$ or produce a denser tetrahedron-free family.

Sources

• S1 B. Lidicky, C. Mattes, and F. Pfender, The Hypergraph Turan Densities of Tight Cycles Minus an Edge, Introduction $2024$. https://lidicky.name/pub/c5-.pdf. Formulation source.
• E1 B. Lidický, C. Mattes, and F. Pfender, The Hypergraph Turán Densities of Tight Cycles Minus an Edge, arXiv:2409.14257v2. https://arxiv.org/pdf/2409.14257. Accessible version of the inherited formulation source; introduction checked 27 September 2026.