Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
2  
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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