# Mathematical Logic Quarterly

## Which subsets of an infinite random graph look random?

### 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 $\mathbb{N}$, (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 $\mathbb{N}$ 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.

View all

View all