Hypergraphs with independent neighborhoods (Q653790)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Hypergraphs with independent neighborhoods |
scientific article |
Statements
Hypergraphs with independent neighborhoods (English)
0 references
19 December 2011
0 references
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\).
0 references
hypergraph
0 references
independent neighbourhood
0 references
extremal problem
0 references