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