= Tripartite graph encoding of a grid
{title2=$z=x+y$}
For $A\subseteq[n]^2$, use three disjoint labelled <vertex> classes $X=[n]$, $Y=[n]$, $Z=[2n]$. Each $(x,y)\in A$ inserts the three <edges> $xy,x(x+y),y(x+y)$, producing pairwise <edge-disjoint triangles>. Every <triangle in a graph> with labels $(x,y,z)$ corresponds to the three points $(x,y),(x,z-x),(z-y,y)$ of $A$. It is canonical when $z=x+y$; otherwise it gives a <corner in an integer grid> with nonzero displacement $z-x-y$.
Back to article page
