Matchings and snakes
greg mc
May 2021
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
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