Snakes:
I could define a snake in a formal inductive way, but I don't want to.
I'll try to give a intuitive definition instead.
The basic unit of a snake is a 2-by-2 graph with two x-edges (colored
in red) and two y-edges (colored in green):
Snakes are just a bunch of these units connected together by z-edges (colored
in blue). Note that the connections can only be made to the north or east,
and never to the south or west.
Exs:
Matchings of snakes:
The matching of a snake is defined in the same way as perfect matchings
in ladder graphs.
That is, each vertex must be connected to exactly one of its neighbors.
Exs:
Cuts of matchings:
A cut of matching is simply a line dividing the plane, such that:
Exs:
Note that the first example is a vertical cut and the third one is a horizontal
cut. I'll use the term "possible" cut to refer to a cut that could be there,
but it is not because intersects an edge of the graph (and therefore, it
is not a real cut).
Proper Horizontal or Vertical Cuts:
A proper horizontal or vertical cut is a cut that "could" intersect at
most two edges of the matching (if they were there). In the examples for
cuts given above, the first one is a proper vertical cut, and the third one
is a horizontal cut, but it is not proper, as it could intersect 4
edges of the matching.
Snake Matching Polynomials:
Snake matching polynomials are polynomials on x,y and z that equals the
sum of all the possible matchings of a snake.
Ex:
Snake Markov Polynomials:
If a Snake has n vertices, width w and height h, its Snake Markov polynomial
is just the Snake Matching polynomial divided by z^(n/4) * y^((w-2)/2) *
x^((h-2)/2). The snake used in the example above has, for example, 8 vertices,
width 4 and height 2. To find its Markov polynomial we would have to divide
its matching polynomial by z^2*y^1*x^0.
Markov Polynomials:
Markov polynomials are triples of polynomials defined inductively. We
start with the triple (x,y,z). At any step you can replace one element of
the triple by the sum of the squares of the other two divided by the old
element.
If you have (A,B,C), then you can replace C by (A^2+B^2)/C to get the
triple (A,B,(A^2+B^2)/C).
Next