Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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).

share|improve this question
    
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"? –  J. Martel Jun 2 '12 at 22:13
    
I guess that the first 3 in $\phi$ for $n=6$ should be deleted (also because $\phi$ should have six components and not seven) –  Valerio Capraro Jun 2 '12 at 22:18
    
@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. –  Valerio Capraro Jun 2 '12 at 22:20
    
If indeed fact, then what remains is verifying that the maximal energy is the floor of $1+n/\sqrt{5}$. –  J. Martel Jun 2 '12 at 22:33
    
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). –  Gjergji Zaimi Jun 3 '12 at 1:15

1 Answer 1

up vote 7 down vote accepted

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$.

share|improve this answer
    
@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. –  Mark Sapir Jun 3 '12 at 3:30
1  
@Gjergji: OK, I think I understand why your proof works for arbitrary weights. –  Mark Sapir Jun 3 '12 at 18:36

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.