Hypergraph Turán Problems in ℓ_2-Norm

NEW

Problem: Reconstructed conjecture: in the category of finite simple 3-uniform hypergraphs, let

i.e. one vertex whose link contains a $K_4$. For a 3-graph $G$, let

and

where $\operatorname{exco}_2(n,H)$ is the maximum of $\operatorname{co}_2(G)$ over all $H$-free $n$-vertex 3-graphs. The conjecture is

This reconstruction is supported by the paper’s definitions of $\sigma$ and by its table definition of $J_4$.

Result: The conjecture is false. In fact,

Proof. Let $F$ be the complement of the Fano plane on vertex set $[7]$. Thus $F$ contains exactly those triples which are not Fano lines. Since every pair of vertices lies in exactly one Fano line, every pair in $F$ has codegree $4$.

Also $F$ is $J_4$-free: for any vertex $v$, the three Fano lines through $v$ remove a perfect matching from $K_6$, so the link graph $L_F(v)$ is $K_6$ minus a perfect matching, whose clique number is $3$. Hence no link contains a $K_4$.

Now define $G_m$ recursively for $n=7^m$. Partition $V(G_m)$ into seven equal classes $V_1,\dots,V_7$, each inducing a copy of $G_{m-1}$. Add all cross triples with one vertex in each of $V_i,V_j,V_k$ whenever $ijk\in E(F)$, and no triples with exactly two vertices in one top-level class.

We claim $G_m$ is $J_4$-free. Indeed, in any copy of $J_4$, if two vertices have the same top-level class but not all five do, then some edge of $J_4$ would have top-level pattern $a,a,b$, impossible in $G_m$. Hence a copy is either entirely inside one class, contradicting induction, or projects injectively to a copy of $J_4$ in $F$, impossible. Thus every $G_m$ is $J_4$-free.

Let

Pairs inside a top-level class contribute $C_{m-1}/343$. Pairs in two distinct top-level classes have codegree $4n/7$, and there are $\binom72(n/7)^2$ such pairs, contributing

Therefore

so

Consequently, along $n=7^m$,

Since $G_m$ is $J_4$-free,

Finally,

so $\sigma(J_4)\neq 0.28$.

Verification audit: the denominator used is exactly $\binom n2(n-2)^2$; the forbidden hypergraph is exactly the paper’s $J_4$; the construction is $J_4$-free; and the obtained lower bound strictly exceeds the conjectured value.

Citation: The conjecture and definitions are from Balogh–Clemen–Lidický, “Hypergraph Turán Problems in $\ell_2$-Norm,” arXiv:2108.10406, Conjecture 3.4. No existing cited source there gives this disproof.