Maximum hypergraphs without regular subgraphs

Research output: Contribution to journalArticlepeer-review


We show that an n-vertex hypergraph with no r-regular subgraphs has at most 2n-1+r-2edges. We conjecture that if n r, then every n-vertex hypergraph with no r-regular subgraphs having the maximum number of edges contains a full star, that is, 2n-1 distinct edges containing a given vertex. We prove this conjecture for n ≥ 425. The condition that n < r cannot be weakened.

Original languageEnglish (US)
Pages (from-to)151-166
Number of pages16
JournalDiscussiones Mathematicae - Graph Theory
Issue number1
StatePublished - 2014


  • Hypergraphs
  • Regular graph
  • Set system
  • Subgraph

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Maximum hypergraphs without regular subgraphs'. Together they form a unique fingerprint.

Cite this