Abstract. The canonical Ramsey theorem of Erdős and Rado implies that for any graph [Formula: see text], any edge-coloring (with an arbitrary number of colors) of a sufficiently large complete graph [Formula: see text] contains a monochromatic, lexicographic, or rainbow copy of [Formula: see text]. The least such [Formula: see text] is called the Erdős–Rado number of [Formula: see text], denoted by [Formula: see text]. Erdős–Rado numbers of cliques have received considerable attention, and in this paper we extend this line of research by studying Erdős–Rado numbers of sparse graphs. For example, we prove that if [Formula: see text] has bounded degree, then [Formula: see text] is polynomial in [Formula: see text] if [Formula: see text] is bipartite but exponential in general. We also study the closely related problem of constrained Ramsey numbers. For a given tree [Formula: see text] and given path [Formula: see text], we study the minimum [Formula: see text] such that every edge-coloring of [Formula: see text] contains a monochromatic copy of [Formula: see text] or a rainbow copy of [Formula: see text]. We prove a nearly optimal upper bound for this problem, which differs from the best known lower bound by a function of inverse Ackermann type.

Abstract. We investigate the maximum size of graph families on a common vertex set of cardinality [Formula: see text] such that the symmetric difference of the edge sets of any two members of the family satisfies some prescribed condition. We solve the problem completely for infinitely many values of [Formula: see text] when the prescribed condition is connectivity or 2-connectivity, Hamiltonicity, or the containment of a spanning star. We also investigate local conditions that can be certified by looking at only a subset of the vertex set. In these cases a capacity-type asymptotic invariant is defined and when the condition is to contain a certain subgraph this invariant is shown to be a simple function of the chromatic number of this required subgraph. This is proven using classical results from extremal graph theory. Several variants are considered and the paper ends with a collection of open problems.