Definitions


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:

  • The ends of the snake end up in opposite regions of the plane.
  • The dividing line does not intercept any edges of the matching.
    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
  •