Hypergraphs with independent neighborhoods (Q653790)

From MaRDI portal





scientific article; zbMATH DE number 5990557
Language Label Description Also known as
default for all languages
No label defined
    English
    Hypergraphs with independent neighborhoods
    scientific article; zbMATH DE number 5990557

      Statements

      Hypergraphs with independent neighborhoods (English)
      0 references
      0 references
      0 references
      0 references
      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
      0 references

      Identifiers