加载中…
Given a countable graph, we say a set of its vertices is \emph{universal} if it contains every countable graph as an induced subgraph, and is \emph{weakly universal} if it contains every finite graph as an induced subgraph. We show that, for almost every graph on , every set of positive upper density is universal, and 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.

生成讲解博客的中文版本

生成AI智能校验的中文版本