  In the hard-core model on a finite graph we are given a parameter lambda>0,
and an independent set I arises with probability proportional to lambda^|I|. On
infinite graphs a Gibbs distribution is defined as a suitable limit with the
correct conditional probabilities. In the infinite setting we are interested in
determining when this limit is unique and when there is phase coexistence,
i.e., existence of multiple Gibbs states. On finite graphs we are interested in
determining the mixing time of local Markov chains.
  On Z^2 it is conjectured that these problems are related and that both
undergo a phase transition at some critical point lambda_c approx 3.79. For
phase coexistence, much of the work to date has focused on the regime of
uniqueness, with the best result being recent work of Restrepo et al. showing
that there is a unique Gibbs state for all lambda < 2.3882. Here we give the
first non-trivial result in the other direction, showing that there are
multiple Gibbs states for all lambda > 5.3646. Our proof adds two significant
innovations to the standard Peierls argument. First, building on the idea of
fault lines introduced by Randall, we construct an event that distinguishes two
boundary conditions and always has long contours associated with it, obviating
the need to accurately enumerate short contours. Second, we obtain vastly
improved bounds on the number of contours by relating them to a new class of
self-avoiding walks on an oriented version of Z^2.
  We extend our characterization of fault lines to show that local Markov
chains will mix slowly when lambda > 5.3646 on lattice regions with periodic
(toroidal) boundary conditions and when lambda > 7.1031 with non-periodic
(free) boundary conditions. The arguments here rely on a careful analysis that
relates contours to taxi walks and represent a sevenfold improvement to the
previously best known values of \lambda.
