1
$\begingroup$

Is there a way to quickly display all the perfect matchings of the vertices of a square lattice?

The following code only finds one:

HighlightGraph[
 GridGraph[{4, 4}, VertexStyle -> White, 
  EdgeStyle -> Gray], {Style[
   FindIndependentEdgeSet[GridGraph[{4, 4}]], Blue,Thick]}]

enter image description here

$\endgroup$
  • 2
    $\begingroup$ I will recommend IGLargestIndependentVertexSets in my this answer $\endgroup$ – yode May 23 '17 at 8:24
  • $\begingroup$ Yes it will run faster I think. $\endgroup$ – Alexander Kartun-Giles May 23 '17 at 8:30
1
$\begingroup$

Ok, so the trick I have used is to construct the LineGraph of the lattice, and then find all its largest independent vertex sets.

On e.g. the 4 x 4 square lattice, the following code outputs all 36 perfect matchings of the vertices:

    perfectsets[g_] := Module[{},
    allsets = FindIndependentVertexSet[LineGraph[g], Infinity, All];
    maximalsets = {};
    For[i = 1, i <= Length[allsets], i++,
    If[Length[allsets[[i]]] == 2 n,
    maximalsets = Append[maximalsets, allsets[[i]]];
    ];]; maximalsets];

    n = 4;
    g = GridGraph[{n, n}, VertexStyle -> White, 
       EdgeStyle -> {Gray, Thick}];

    matchings = EdgeList[g][[#]] & /@ perfectsets[g];
    ListofPerfectMatchings = 
     Table[HighlightGraph[
       GridGraph[{n, n}, VertexStyle -> White, 
        EdgeStyle -> Gray], {Style[matchings[[i]], Blue, Thick]}], {i, 1, 
       Length[matchings]}]

i.e.

All perfect matchings of the vertices of the 4x4 square lattice.

See also yode's answer in this post, which is where I got the idea.

$\endgroup$
  • $\begingroup$ Note this will find all matchings, not necessarily perfect, so a modification according to yode's comment to the OP will speed things up, but it requires an external package to be installed. $\endgroup$ – Alexander Kartun-Giles May 23 '17 at 8:31
  • $\begingroup$ Also note $n$ must be even for a perfect matching to exist. $\endgroup$ – Alexander Kartun-Giles May 23 '17 at 8:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.