The Turán density of H_r_t is Θ_t(1/r)

Jeff Pickhardt

Loading document…

The Turán density of H_r_t is Θ_t(1/r)

Abstract

Let H_r_t be the r-uniform hypergraph with r + 1 vertices and t edges, also known as the (t, t−1)-daisy. We determine its Turán density up to a constant depending only on t: π(Hr t ) = Θt(1/r) for every fixed t ≥ 3, with an explicit lower bound π(Hr t ) ≥ 3/(256 r) whose constant does not depend on t, improving to (√2 − 1)/e − o(1)/r on optimising the parameters. That leaves a factor of e(1 + √2) = 6.56 . . . against the counting upper bound 1/r. The constant is optimal within the uniform independent-labelling calculation with q ∼ βr and m ∼ αr2; we do not rule out improvements from structured labellings. This determines the order of magnitude in a line of questions going back to the 1984 work of Frankl and Füredi [1]. The strongest previous lower bound, due to Yang and Zhu [6], was π(Hr 3 ) ≥ cε r−1(log r)−(2+ε), and hence π(Hr 3 ) = r−1+o(1). Their result leaves a polylogarithmic gap to the known upper bound; we remove that gap by a method unrelated to theirs. The construction is algebraic, in a sense that appears to be new for this problem at general r. Label each vertex with a pair (ϕv , cv ) ∈ F r−1 q × Fq and select an r-set when its space of linear relations is a full-support line that is isotropic for the diagonal form P v cv λ e v . Every selected facet of an (r+1)-set then contributes a distinct isotropic line to that set’s two-dimensional relation space, and a binary form of degree e has at most e roots in P1. So the family is H_r e+1-free for the algebraic reason that a conic in P1 has at most two points, and Hr t -freeness follows on taking e = t − 1. For every fixed e, a random labelling achieves density ≥ 1/(64r) once r is large enough, and Hr t -freeness survives blow-ups. Section 8 reports the computational checks: the two counting lemmas and the danger fraction are confirmed exactly by complete enumeration, and the cap is verified over every one of the m r+1 parents at the parameters the theorems actually use.

File Details

v1 paper.pdf