Some relations for the lengths of orbits on \(k\)-sets and \((k-1)\)-sets (Q1383612)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Some relations for the lengths of orbits on \(k\)-sets and \((k-1)\)-sets
scientific article

    Statements

    Some relations for the lengths of orbits on \(k\)-sets and \((k-1)\)-sets (English)
    0 references
    15 December 1998
    0 references
    The following two theorems are proved: (1) Let \(G\) be an Abelian or Hamiltonian group acting transitively on the finite set \(\Omega\). Let \(\Sigma\subseteq\Omega\) be a \(k\)-set and \(\Delta\) be a \((k-1)\)-subset of \(\Sigma\). Then the orbits \(\Sigma^G\) or \(\Delta^G\) are of length \(| G|\). (2) Let \(G\) be a permutation group on the set \(\Omega\) and let \(\Sigma\subseteq\Omega\) be a \(k\)-set, \(k\geq 2\). Then there is a \((k-1)\)-set \(\Delta\subset\Sigma\) such that \[ |\Delta^G|\geq {2\over k^2} |\Sigma^G|^{{k-1\over k}}. \]
    0 references
    Kruskal-Katona theorem
    0 references
    edge-deleted subgraph
    0 references
    permutation group
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references