Abstract

Given a countable graph, we say a set A of its vertices is universal if it contains every countable graph as an induced subgraph, and A is weakly universal if it contains every finite graph as an induced subgraph. We show that, for almost every graph on, (1) every set of positive upper density is universal, and (2) every set with divergent reciprocal sums is weakly universal. We show that the second result is sharp (i.e., a random graph on will almost surely contain non‐universal sets with divergent reciprocal sums) and, more generally, that neither of these two results holds for a large class of partition regular families.