List-decodability of Reed-Solomon codes has re-ceived a lot of attention, but the best-possible dependence between the parameters is still not well-understood. In this work, we focus on the case where the list-decoding radius is of the form$r=1-\varepsilon$for$\varepsilon$tending to zero. Our main result states that there exist Reed-Solomon codes with rate$\Omega(\varepsilon)$which are$(1-\varepsilon, O(1/\varepsilon)$-list-decodable, meaning that any Hamming ball of radius$1-\varepsilon$contains at most$O(1/\varepsilon)$codewords. This trade-off between rate and list-decoding radius is best-possible for any code with list size less than exponential in the block length. By achieving this trade-off between rate and list-decoding radius we improve a recent result of Guo, Li, Shangguan, Tamo, and Wootters, and resolve the main motivating question of their work. Moreover, while their result requires the field to be exponentially large in the block length, we only need the field size to be polynomially large (and in fact, almost-linear suffices). We deduce our main result from a more general theorem, in which we prove good list-decodability properties of random puncturings of any given code with very large distance.

We show that for any fixed dense graph $G$ and bounded-degree tree $T$ on the same number of vertices, a modest random perturbation of $G$ will typically contain a copy of $T$. This combines the viewpoints of the well-studied problems of embedding trees into fixed dense graphs and into random graphs, and extends a sizable body of existing research on randomly perturbed graphs. Specifically, we show that there is $c=c(\alpha,\Delta)$ such that if $G$ is an $n$-vertex graph with minimum degree at least $\alpha n$, and $T$ is an $n$-vertex tree with maximum degree at most $\Delta$, then if we add $cn$ uniformly random edges to $G$, the resulting graph will contain $T$ asymptotically almost surely (as $n\to\infty$). Our proof uses a lemma concerning the decomposition of a dense graph into superregular pairs of comparable sizes, which may be of independent interest.