Hypergraphs with independent neighborhoods (Q653790)

From MaRDI portal
Revision as of 03:08, 11 February 2024 by RedirectionBot (talk | contribs) (‎Changed an Item)
scientific article
Language Label Description Also known as
English
Hypergraphs with independent neighborhoods
scientific article

    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
    0 references
    0 references
    0 references
    0 references
    hypergraph
    0 references
    independent neighbourhood
    0 references
    extremal problem
    0 references
    0 references
    0 references