6
$\begingroup$

Here I ask a question on permutations of $n$ distinct real numbers.

QUESTION: Let $a_1,a_2,\ldots,a_n\ (n>1)$ be (pairwise) distinct real numbers. Is there a permutation $b_1,\ldots,b_n$ of $a_1,\ldots,a_n$ with $b_1 = a_1$ such that the $n−1$ numbers $$|b_1 −b_2|,\ |b_2 −b_3|,\ \ldots,\ |b_{n−1} −b_n|$$ are pairwise distinct ?

Actually, I formulated this question in 2013 and conjectured that the answer should be positive. If $a_1$ is the smallest (or largest) number among $a_1,\ldots,a_n$, then it is easy to construct a desired permutation $(b_1,\ldots,b_n)$. In fact, when $a_1<a_2<\ldots<a_n$ we may take $$(b_1,b_2,\ldots,b_n)=(a_1,a_n,a_2,a_{n-1},\ldots,a_{\lfloor n/2\rfloor+1})$$ to meet the purpose.

In 2015, Francesco Monopoli [Electron. J. Combin. 22(2015), no. 3, #P3.20] showed that my question for $a_1,\ldots,a_n$ has a positive answer if the set $A=\{a_1,a_2,\ldots,a_n\}$ forms an arithmetic progression.

As any path is a tree, in 2014 I made the following conjecture which unifies my question and Ringel and Kotzig's graceful tree conjecture.

Conjecture. Let $a_1,a_2,\ldots,a_n$ be $n > 1$ distinct real numbers, and let $T$ be any tree with vertices $v_1,\ldots,v_n$, where $v_1$ is a leaf (i.e., $\deg_T(v_1) = 1$). Then there is a bijection $f$ from the vertex set $V(T)$ of the tree $T$ to $A = \{a_1,\ldots,a_n\}$ with $f (v_1) = a_1$ such that those $|f (v_i)−f (v_j)|$ with $v_i$ and $v_j$ adjacent are pairwise distinct.

Any ideas towards the final solution of my question? Comments on the above general conjecture are also welcome!

$\endgroup$
9
$\begingroup$

A simple brute-force of trees yields a counter-example with $n = 7$. Let $\{a_1, \ldots, a_7\} = [7]$, $T$ be a path of four vertices $v_1, v_2, v_3, v_4$, with $v_4$ adjacent to $v_5, v_6, v_7$. If we fix $f(v_1) = 4$, the conjecture is failed. I have not come up with a simple proof yet (other than trying all options of $f$), may update later.

UPD: ok, here is the proof. Consider all options of $f(v_2)$:

  • $f(v_2) = 3$ ($5$ is symmetrical). Note that in the set $\{1, 2, 5, 6, 7\}$ each element has another one with absolute difference $1$, hence for all options of $f(v_4)$ there is an index $j \in \{3, 5, 6, 7\}$ such that $|f(v_4) - f(v_j)| = |f(v_1) - f(v_2)| = 1$.

  • $f(v_2) = 2$ ($6$ is symmetrical). The only element of $\{1, 3, 5, 6, 7\}$ not at distance $2$ from another element is $6$. But if $f(v_4) = 6$, there are distinct $i, j \in \{3, 5, 6, 7\}$ with $f(v_i) = 5$ and $f(v_j) = 7$, hence $|f(v_4) - f(v_i)| = |f(v_4) - f(v_j)| = 1$.

  • $f(v_2) = 1$ ($7$ is symmetrical). The only element of $\{2, 3, 5, 6, 7\}$ not at distance $3$ from another element is $7$. Let $f(v_4) = 7$ and $f(v_3) = x$, but then $f(v_i) = 8 - x$ for a certain $i \in \{5, 6, 7\}$, and $|f(v_2) - f(v_3)| = |f(v_4) - f(v_i)| = x - 1$.

$\endgroup$
  • $\begingroup$ Thank you for your counterexample to the general conjecture for trees. My question still remains open since it involves only paths. $\endgroup$ – Zhi-Wei Sun Jun 27 '18 at 5:16

Your Answer

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

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