  In this paper we study pattern-replacement equivalence relations on the set
$S_n$ of permutations of length $n$. Each equivalence relation is determined by
a set of patterns, and equivalent permutations are connected by
pattern-replacements in a manner similar to that of the Knuth relation.
  One of our main results generalizes the celebrated Erdos-Szekeres Theorem for
permutation pattern-avoidance to a new result for permutation
pattern-replacement. In particular, we show that under the $\{123 \cdots k, k
\cdots 321\}$-equivalence, all permutations in $S_n$ are equivalent up to
parity when $n \ge \Omega(k^2)$.
  Additionally, we extend the work of Kuszmaul and Zhou on an infinite family
of pattern-replacement equivalences known as the rotational equivalences.
Kuszmaul and Zhou proved that the rotational equivalences always yield either
one or two nontrivial equivalence classes in $S_n$, and conjectured that the
number of nontrivial classes depended only on the patterns involved in the
rotational equivalence (rather than on $n$). We present a counterexample to
their conjecture, and prove a new theorem fully classifying (for large $n$)
when there is one nontrivial equivalence class and when there are two
nontrivial equivalence classes.
  Finally, we computationally analyze the pattern-replacement equivalences
given by sets of pairs of patterns of length four. We then focus on three
cases, in which the number of nontrivial equivalence classes matches an OEIS
sequence. For two of these we present full proofs of the enumeration and for
the third we suggest a potential future method of proof.
