# Is there an appropriate labeling for the colored graph

Motivation:

For those of you who care to know, I thought about this question after looking at this question.

Let $X=\{1,2,\dots,N\}$, and let $f:X\to X$ be a bijection. We define the two-colored (complete) graph $G(f)$ on $N$ nodes as follows:

Label the nodes $1,2,\dots ,N$. Take any $1\leq i<j\leq N$, and color the edge $e_{ij}$ by the following scheme: if $f(i)<f(j)$, let $e_{ij}$ be red. Otherwise, (if $f(i)>f(j)$) let $e_{ij}$ be blue

Question:

Given $N$ unlabeled nodes and a complete two-colored graph, can we label the nodes in such a way that the resulting graph is $G(f)$ for $X=\{1,2,\dots,N\}$ and some bijection $f:X\to X$?

It's clear to me that some labelings won't work on some graphs. For example, the graph with red edges $\color{red}{1\mapsto 2},\color{red}{2\mapsto 3}$ and the blue edge $\color{blue}{1 \mapsto 3}$ does not correspond to any valid bijection, but we can relabel this graph appropriately as $\color{blue}{1\mapsto2},\color{red}{2\mapsto3,1\mapsto3}$ corresponding to the bijection $\{1,2,3\}\overset{f}{\to}\{2,1,3\}$.

On the other hand, any monochromatic graph admits all labelings.

Any information regarding this (or a similar problem I might not have heard of) is very much appreciated.

-

It seems that the answer is negative for large $N$ , because for the complete graph on $N$ vertices the number $2^{N(N-1)/2}$ of different colorings is asymptotically greater than the number $N!$ of different labelings.

-
Or rather, the number $2^{N(N-1)/2}$ of different colorings is asymptotically greater than the number $N!$ of different labelings times the number $N!$ of different bijections. – Chris Culter Jul 23 '13 at 6:38
@ChrisCulter Thanks for the correction. – Alex Ravsky Jul 23 '13 at 7:56
Interesting observation, but many labelings can admit multiple colorings. There is still no guarantee that there will be a coloring that lacks a valid associated labeling. – Omnomnomnom Jul 23 '13 at 18:31
But any pair (labelling, bijection) uniquely determines the coloring, isn't it? So Chris Culter's remark should imply the negative answer. – Alex Ravsky Jul 24 '13 at 10:49
@AlexRavsky I must have misunderstood the comment and your answer when I first read it, you were right. Also, thank you for editing my answer and giving me a satisfying explanation for my observation! – Omnomnomnom Jul 26 '13 at 18:00

After writing a Python script to exhaust the possibilities, I have determined that there is no bijection corresponding to the following graph: $$\color{red}{1\mapsto 2\mapsto3\mapsto4\mapsto5\mapsto1}\\ \color{blue}{1\mapsto3\mapsto5\mapsto2\mapsto4\mapsto1}$$ The only explanation I have as of now is that I've checked all $5!$ possibilities, and there is no $f$ such that $G_f$ has a blue (or red) degree of $2$ at each node.

Added by Alex Ravsky. It seems I can explain why the graph has no bijections. (Since my explanation is too big and formatted, I think it would be better to add it to the answer body instead to write it as a comment). Let $X=\{1,2,3,4,5\}$ be its set of vertices, $g:X\to X$ be a labeling of the graph and $f:X\to X$ be a bijection such that for every $1\leq g(i)<g(j)\leq 5$, if $fg(i)<fg(j)$ then $e_{ij}$ is red and otherwise $e_{ij}$ is blue. Now let $i,j,k$ be the consequent numbers of a cyclic sequence $\{\dots,1,2,3,4,5,1,2,\dots\}$. Then the edges $e_{ij}$ and $e_{jk}$ are red and $e_{ik}$ is blue. Then the following condition holds: $$[[(g(i)<g(j))\&(fg(i)<fg(j))]\vee[(g(i)>g(j))\&(fg(i)>fg(j))]]\&$$ $$[[(g(j)<g(k))\&(fg(j)<fg(k))]\vee [(g(j)>g(k))\&(fg(j)>fg(k))]]\&$$ $$[[(g(i)<g(k))\&(fg(i)>fg(k))]\vee [(g(i)>g(k))\&(fg(i)<fg(k))]].$$

It implies that both cases $g(i)<g(j)<g(k)$ and $g(i)>g(j)>g(k)$ are impossible.

Hence the map $g$ satisfies one of the conditions: $$g(1)>g(2)<g(3)>g(4)<g(5)>g(1)<g(2)>\dots$$ or $$g(1)<g(2)>g(3)<g(4)>g(5)<g(1)>g(2)<\dots.$$ Both are contradictions.

-
I added my explanation to the answer body. Feel free to edit it. – Alex Ravsky Jul 26 '13 at 5:10
@AlexRavsky: Thank you! I really appreciate the time you put in to this. – Omnomnomnom Jul 26 '13 at 20:59