Regular hypergraphs, Gordon's lemma, Steinitz' lemma and invariant theory

N. Alon, K. A. Berman

Research output: Contribution to journalArticlepeer-review

16 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)91-97
Number of pages7
JournalJournal of Combinatorial Theory, Series A
Volume43
Issue number1
DOIs
StatePublished - Sep 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Regular hypergraphs, Gordon's lemma, Steinitz' lemma and invariant theory'. Together they form a unique fingerprint.

Cite this