Matchings and snakes

greg mc

May 2021

Principal drivers

length

\((p,q)\) curve

  • \(\sqrt p^2 + q^2\)
  • \(|p| + |q|\)
  • \(\ell_w\)
  • complexity of another object ?

A matching of a graph G is a set of pairwise non-adjacent edges, none of which are loops.

A perfect matching matches all vertices of the graph.

Matching polynomial

5 perfect matchings

  • \(x^4 + y^4 + x^2z^2 + 2x^2y^2\)
  • match \(\rightarrow\) monomial=product of labels

13 perfect matchings

src

Snake graph from primitive

\(A=(1,1)\), \(B=(2,1)\), \(C=(3,2)\)

Positivity conjecture

  • cluster algebras
  • seed is like a Markoff triple \((x,y,z)\)
  • mutation is like a Vieta flip
  • Markoff number \(\rightarrow\) Laurent polynomial
  • proof (idea) : coeffs are coeffs of the snake polynomial

Positivity conjecture

Calculus of arcs/snake graphs

  • sophistocated combinatorial proof
  • relations to continued fractions
  • looking for applications

Markoff numbers

\(A,B \in \mathbb{Z}^2\)
\(|AB|=\) number perfect matchings for associated snake graph

src

Exercise to prove

Prove the relation for matchings of triples of snake graphs

\(tr ab + tr ab^{-1} = (tr a) (tr b)\)

Ptolemy inequality