Let D(n)(D(n, k)) denote the maximum possible d such that there exists a d-regular hypergraph (d-regular k-uniform hypergraph, respectively) on n vertices containing no proper regular spanning subhypergraph. The problem of estimating D(n) arises in Game Theory and Huckemann and Jurkat were the first to prove that it is finite. Here we give two new simple proofs that D(n), D(n, k) are finite, and determine D(n, 2) precisely for all n ≥ 2. We also apply this fact to Invariant Theory by showing how it enables one to construct an explicit finite set of generators for the invariants of decomposable forms.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics