Turán Densities for Daisies and Hypercubes

Abstract

An $r$-daisy is an $r$-uniform hypergraph consisting of the six $r$-sets formed by taking the union of an $(r-2)$-set with each of the 2-sets of a disjoint 4-set. Bollobás, Leader and Malvenuto, and also Bukh, conjectured that the Turán density of the $r$-daisy tends to zero as $r\to \infty$. In this paper we disprove this conjecture. Adapting our construction, we are also able to disprove a folklore conjecture about Turán densities of hypercubes. For fixed $d$ and large $n$, we show that the smallest set of vertices of the $n$-dimensional hypercube $Q_n$ that meets every copy of $Q_d$ has asymptotic density strictly below $1/(d+1)$, for all $d\ge 8$. In fact, we show that this asymptotic density is at most $c^d$, for some constant $c<1$. As a consequence, we obtain similar bounds for the edge-Turán densities of hypercubes. We also answer some related questions of Johnson and Talbot, and disprove a conjecture made by Bukh and by Griggs and Lu on poset densities.

14 pages. Minor corrections made since last version

Cited by in corpus (4)

• Positive co-degree densities and jumps
• Visibility polynomials, dual visibility spectrum, and characterization of total mutual-visibility sets
• $C_{10}$ has positive Turán density in the hypercube
• Turán Densities for Small Hypercubes