Which subsets of an infinite random graph look random?
classification
🧮 math.CO
math.LO
keywords
grapheveryuniversalrandomalmostcontainscountabledivergent
read the original abstract
Given a countable graph, we say a set $A$ of its vertices is \emph{universal} if it contains every countable graph as an induced subgraph, and $A$ is \emph{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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.