Induced universal hypergraphs

Noga Alon, Nadav Sherman

Research output: Contribution to journalArticle

Abstract

We prove that the minimum number of vertices of a hypergraph that contains every d-uniform hypergraph on k vertices as an induced subhypergraph is (1 + o(1))2 \Bigl(k d \Bigr) /k. The proof relies on the probabilistic method and provides a nonconstructive solution. In addition we exhibit an explicit construction of a hypergraph on \Theta (2 \Bigl(k d \Bigr) /k) vertices, containing every d-uniform hypergraph on k vertices as an induced subhypergraph.

Original languageEnglish (US)
Pages (from-to)629-642
Number of pages14
JournalSIAM Journal on Discrete Mathematics
Volume33
Issue number2
DOIs
StatePublished - Jan 1 2019

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Hypergraph
  • Labeling
  • Universal

Fingerprint Dive into the research topics of 'Induced universal hypergraphs'. Together they form a unique fingerprint.

  • Cite this