  We study the classical online bipartite matching problem: One side of the
graph is known and vertices of the other side arrive online. It is well known
that when the graph is edge-weighted, and vertices arrive in an adversarial
order, no online algorithm has a nontrivial competitive-ratio. To bypass this
hurdle we modify the rules such that the adversary still picks the graph but
has to reveal a random part (say half) of it to the player. The remaining part
is given to the player in an adversarial order. This models practical scenarios
in which the online algorithm has some history to learn from.
  This way of modeling a history was formalized recently by the authors (SODA
20) and was called the AOS model (for Adversarial Online with a Sample). It
allows developing online algorithms for the secretary problem that compete even
when the secretaries arrive in an adversarial order. Here we use the same model
to attack the much more challenging matching problem.
  We analyze a natural algorithmic framework that decides how to match an
arriving vertex $v$ by applying an offline matching algorithm to $v$ and the
sample. We get roughly $1/4$ of the maximum weight by applying the offline
greedy matching algorithm to the sample and $v$. Our analysis ties the
performance of this algorithm to the performance of the offline greedy matching
on the online part and we also prove that it is tight. Surprisingly, when
replacing greedy with an optimal algorithm for maximum matching, no constant
competitive-ratio can be guaranteed when the size of the sample is comparable
to the size of the online part. However, when the sample is quadratic in the
size of the online part, we do get a competitive-ratio of $1/e$.
