Matching By Matching Model

AllPages RecentChanges Links to this page Edit this page Search Entry portal Advice For New Users

Let $N$ be a natural number, and let the vertex set of $G$ be three sets of size $N.$ Let $k$ be a number between $0$ and $N.$

Between each pair $(A,B)$ of these vertices choose three edge-independent matchings $m_0,$ $m_1,$ and $m_2.$ Into the edge set of $G$ put all of the edges from $m_0$ and $m_1,$ and $k$ randomly chosen edges from $m_2.$

Each vertex has minimum degree $2$ to each of the other default colour classes.

When $k=0$ we have a 4-regular graph, and the colouring is not unique. Specifically, between two of the default colour-classes $A$ and $B$ we have two edge-independent matchings. Start with any vertex from $A$ and follow $m_0$ over to $B$, then come back via $m_1.$ Repeat this until you end up where you started, and thus you have a cycle. A single over-and-back is effectively permuting the vertices of $A$, and since the matchings are edge-independent no vertex is taken to itself, so we have a derrangement.

This cycle will almost certainly not contain all of $A$ and $B$ and we refer to the intersection of the cycle with $A$ as an "enclave." So $A$ is partitioned into enclaves, and for each enclave, the vertices in it can each be swapped to have "the other colour."

At a minimum the colouring of $G$ will not be unique until enough edges from $m_2$ are included to connect all the enclaves. Even then we can construct cases where there are other colourings, but we can perhaps show that such "sporadic" other colourings are rare.

The enclaves are effectively a derrangement of the vertices, so there are expected to be about $log(n)$ of them. We then need to worry about how long it takes the third matching to cross-connect them all, assuming it ever does. Calculations can be done as to how likely the induced bipartite graph will be to become connected, and the expected time as we throw in edges from $m_2.$