Hypergraphs with independent neighborhoods (Q653790): Difference between revisions

For \(n\geq k\geq 2\), determine \(f(n,k)\), the maximum number of edges in a \(k\)-uniform hypergraph with all neighborhoods being independent sets. (A neighborhood of a \((k-1)\) set \(S\) in a \(k\)-uniform graph is the set of such vertices \(v\) so that \(S\cup \{v\}\) is an edge. A set of vertices is called independent if it does not span an edge.) Thus, \(f(n,2)=\left\lfloor \frac{n^{2}}{4}\right\rfloor\) by \textit{W. Mantel} [Wiskundige Opgaven 10, 60-61 (1907; JFM 38.0270.01)] and \textit{P. Turán} [Mat.\ Fiz.\ Lapok 48, 436--452 (1941; Zbl 0026.26903)]. Let \(\rho_{k}=\frac{f(n,k)}{\binom{n}{k}}.\) The authors give sharp estimates on the rate at which \(\rho _{k}\) converges to \(1\).