1
$\begingroup$

Over the weekend I decided to model mimetic behaviour as a random graph colouring process and as I haven't taken any graph theory courses I decided to use my intuition. The adjacency matrix was modelled as a combination of random matrices and colour labels were chosen from the nth roots of unity:

\begin{equation} S_n = \{e^{i \frac{2 k \pi}{n}} : k \in [0,n-1] \} \tag{1} \end{equation}

My reason for choosing this representation was that it allows me to define a potential adjacency matrix $W$ where:

\begin{equation} w_{ij} = v_i \cdot \bar{v_j}= \begin{cases} 1,v_i = v_j\\ e^{i\theta} \neq 1, v_i \neq v_j \end{cases} \tag{2} \end{equation}

It's also useful to note that in the case of $n=2$ we have:

\begin{equation} S_2 = \{-1,+1 \} \tag{3} \end{equation}

so a change in color is simply multiplication by $-1$ and for general $n$ a switch of labels from $v_i \in S_n$ to $v_j \in S_n$ amounts to multiplying $v_i$ by:

\begin{equation} \bar{v_i} \cdot v_j \tag{4} \end{equation}

I found these properties quite convenient and have successfully used this representation in computer simulations for the case of $n=2$ colours. But, yesterday morning I did a literature review and couldn't find anything on using complex numbers as vertex labels in random graph colouring problems.

In fact, it appears that the use of integers as labels is the norm. Have I overlooked a niche area of random graph colouring or might the integer-label representation have advantages that I have overlooked?

References:

  1. Ben Stevens. Colored graphs and their properties. 2011.
  2. R.M.R Lewis. A Guide to Graph Colouring. 2016.
$\endgroup$
  • $\begingroup$ The case for $n=2$ colours is trivial, as it can be completed by a BFS search. Why not try $3$ colours? $\endgroup$ – Bullet51 Apr 30 at 14:48
  • 1
    $\begingroup$ Edges are sometimes labeled with complex numbers: "A complex unit gain graph is a graph where each orientation of an edge is given a complex unit, which is the inverse of the complex unit assigned to the opposite orientation." arXiv. $\endgroup$ – Joseph O'Rourke Apr 30 at 15:05
  • $\begingroup$ @Bullet51 I plan to tackle $n >> 2$ in less than two weeks using a combination of simulation and analysis. My main objective with special cases, in this case $n=2$, is that I find a good way to model the problem and not merely find a solution. $\endgroup$ – Aidan Rocke Apr 30 at 19:36

Your Answer

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

Browse other questions tagged or ask your own question.