Maximum number of constant weight vertices of the unit \(n\)-cube contained in a \(k\)-dimensional subspace (Q1878586)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Maximum number of constant weight vertices of the unit \(n\)-cube contained in a \(k\)-dimensional subspace
scientific article

    Statements

    Maximum number of constant weight vertices of the unit \(n\)-cube contained in a \(k\)-dimensional subspace (English)
    0 references
    0 references
    0 references
    0 references
    7 September 2004
    0 references
    The largest intersection \(| U\cap E(n,w)| \) is determined where \(U\) is a \(k\)-dimensional subspace of \(\mathbb{R}^n\) and \(E(n,w)\) is the set of length-\(n\) 0-1 sequences with \(w\) 1-entries. It is \(k \choose w\) for \(w\leq k/2\), \({{2(k-w)} \choose {k-w}}2^{2w-k}\) for \(k/2<w<k-1\), and \(2^{k-1}\) for \(k-1\leq w \leq n/2\). An extension of Erdős-Moser type and one on multisets are also given.
    0 references
    0 references
    extremal set theory
    0 references
    0 references