@article{d550eb83828f4d2b8a1316a0c1c82158,
title = "Induced universal hypergraphs",
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.",
keywords = "Hypergraph, Labeling, Universal",
author = "Noga Alon and Nadav Sherman",
note = "Funding Information: \ast Received by the editors January 3, 2018; accepted for publication (in revised form) February 11, 2019; published electronically April 9, 2019. http://www.siam.org/journals/sidma/33-2/M116375.html Funding: The first author's research was supported in part by ISF grant 281/17, GIF grant G-1347-304.6/2016, and by the Simons Foundation. The second author's research was supported in part by an ISF grant. \dagger Department of Mathematics, Princeton University, Princeton, NJ, and Schools of Mathematics and Computer Science, Tel Aviv University, Tel Aviv, Israel (nogaa@tau.ac.il). \ddagger Sackler School of Mathematics, Tel Aviv University, Tel Aviv 69978, Israel (nadav.sherman@ gmail.com). Publisher Copyright: \bigcirc c 2019 Society for Industrial and Applied Mathematics",
year = "2019",
doi = "10.1137/18M1163750",
language = "English (US)",
volume = "33",
pages = "629--642",
journal = "SIAM Journal on Discrete Mathematics",
issn = "0895-4801",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "2",
}