12
$\begingroup$

Let $G=(V,E)$ be a finite graph with weights $\phi: V\to \{1,...,|V|\}$ assigned to vertices. We can view $V$ as the set of numbers $1,...,|V|$, and $\phi$ as a permutation of $V$. For every edge $e$ we assign its energy $\phi(e_-)*\phi(e_+)$ (the product of weights of its end vertices). The energy of $\phi$ is the sum of energies of all edges from $E$. We are interested in $\phi$ that maximizes the energy of $G$. Is anything known about this problem?

For example, if $G$ is an $n$-cycle, $1-2-...-n-1$, then for $n=3$ all $\phi$'s have the same energy. If $n=4$, then the maximal energy is given by $\phi=(1,2,4,3)$, for $n=5$, we get $\phi=(1,2,4,5,3)$, for $n=6$, $\phi=(1,2,4,6,5,3)$, etc. (the new number gets inserted between two biggest numbers in the previous permutation. The interesting thing is that the sequence $1,2,3, 1,2,4,5,3, 1,2,3,4,6,5,3,...$ seems to coincide with A194983 which is defined in OEIS in a completely different way. I can prove it for $n\le 10$. Is it possible to prove the coincidence for all $n$?

Update. Gjergji answered the question about the cycle. See comments below about other interesting graphs, other collections of weights and the problem of minimalizing the energy (maximizing the cost).

$\endgroup$
6
  • $\begingroup$ Regarding your n-cycle example, is it observation or fact that "the new number gets inserted between the two biggest numbers in the previous permutation"? $\endgroup$
    – JHM
    Jun 2 '12 at 22:13
  • $\begingroup$ I guess that the first 3 in $\phi$ for $n=6$ should be deleted (also because $\phi$ should have six components and not seven) $\endgroup$ Jun 2 '12 at 22:18
  • $\begingroup$ @Martel: I think it's a fact, following by the purpose to maximize the energy. Maybe it can be used as a tool for a proof by induction. $\endgroup$ Jun 2 '12 at 22:20
  • $\begingroup$ If indeed fact, then what remains is verifying that the maximal energy is the floor of $1+n/\sqrt{5}$. $\endgroup$
    – JHM
    Jun 2 '12 at 22:33
  • $\begingroup$ Is there a specific family of graphs you are interested in? I'm curious to know what the answer is for the Cayley graph of $\mathbb Z/a\mathbb Z\times \mathbb Z/b\mathbb Z$ (torus grids). $\endgroup$ Jun 3 '12 at 1:15
8
$\begingroup$

In the case of the $n$-cycle there will be two ways to write the optimal permutations. In the case when we write them like $$(1),(1,2),(1,2,3),(1,2,4,3),(1,2,4,5,3),(1,2,4,6,5,3),\dots$$ this will be the fractalization of the sequence $$1,2,3,3,4,4,5,5,6,6,\dots$$ Notice that the coincidence with the fractalization of $1+\lfloor n/\sqrt{5} \rfloor$ stops after $n=10$. For example the permutation $(1, 2, 4, 6, 8, 11, 10, 9, 7, 5, 3)$ which appears in A194983 is not optimal.

I would prefer to write the permutations with the opposite orientation, so that one gets $$(1),(1,2),(1,3,2),(1,3,4,2),(1,3,5,4,2),\dots$$ which is the fractalization of $1+\lfloor n/2\rfloor$.

This is of course just a fancy way of saying that the optimal permutations contain the two largest entries in consecutive positions and can be generated recursively by inserting $n+1$ between $n$ and $n-1$. This can be proven easily by induction.

Proof: Let C(n) be the value of $\sum \pi(i)\pi(i+1)$ (cyclic sum) for these permutations. We have $C(n)=C(n-1)+n^2-2$. Suppose the statement is true for $n-1$. Now let $\sigma\in S_n$ be a random permutation. We will prove that $\sum \sigma(i)\sigma(i+1)\le C(n)$. But $\sum \sigma(i)\sigma(i+1)=n(a+b)-ab+\sum \sigma'(i)\sigma'(i+1)\le C(n-1)+n(a+b)-ab$ where $\sigma'\in S_{n-1}$ is obtained from sigma by deleting $n$, so we just need to show $$C(n-1)+n(a+b)-ab\le C(n)$$ which can be written as $(n-a)(n-b)\geq 2$, so we are done.

For the general problem, this is close to the problem of minimizing the $\lambda$-cost over all labelings $\pi$. Where the cost of an edge is $|\pi(i)-\pi(j)|^\lambda$. In fact for regular graphs your problem is equivalent to minimizing the cost for $\lambda=2$. Unfortunately, I don't think much is known about this beyond $\lambda=1$.

$\endgroup$
2
  • $\begingroup$ @Gjergji: Thank you! Where can I read about minimizing $\lambda$-cost? The question about cycles was asked by Ilya Sinitsky. In fact he asked about the case when arbitrary (different) positive weights are assigned to the vertices, not necessarily $1,...,n$, i.e. an arbitrary function $\phi:V\to \{\alpha_1,...,\alpha_n\}$. From your solution, it looks like the result (the optimal $\phi$) will depend on $\alpha$'s. You need that the highest weight $h$ and any two other weights $a,b$ satisfy $(h−a)(h−b)\ge 2$? Another problem he asked: about the minimal energy, i.e. maximal $2$-cost. $\endgroup$
    – user6976
    Jun 3 '12 at 3:30
  • 1
    $\begingroup$ @Gjergji: OK, I think I understand why your proof works for arbitrary weights. $\endgroup$
    – user6976
    Jun 3 '12 at 18:36

Your Answer

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