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.

The girth of a matrix is the least number of linearly dependent columns, in contrast to the rank which is the largest number of linearly independent columns. This paper considers the construction of high-girth matrices, whose probabilistic girth is close to their rank. Random matrices can be used to show the existence of high-girth matrices. This paper uses a recursive construction based on conditional ranks (inspired by polar codes) to obtain a deterministic and efficient construction of high-girth matrices for arbitrary relative ranks. Interestingly, the construction is agnostic to the underlying field and applies to both finite and continuous fields with the same binary matrix. The construction gives in particular the following: (i) over the binary field, high-girth matrices are equivalent to capacity-achieving codes, and our construction turns out to match exactly the BEC polar codes (even at finite block length). It hence gives a different interpretation of BEC polar codes, using the parity-check matrix instead of the generator matrix, and basic linear algebra instead of the mutual information, and generalizes to larger fields; (ii) for the BSC, our construction gives an operational meaning to the Bhattacharyya upper-bound process used in polar codes; (iii) for the reals, it gives an explicit candidate matrix for sparse recovery.