Improving the lower bound

[Robin Houston]

Is anyone looking at how far we can push the lower bound? I think it can be improved at least a little without much trouble.

(Honestly it feels as though it’s almost in reach now to bring the bounds together all the way, and get a definitive answer; but that will require a bit more work.)

Anyway, the purpose of this message is to improve the lower bound by one, to n! + (n-1)! + (n-2)! - 2, as a sort of demonstration of why I think it can be improved more generally.

Anonymous’s proof of the lower bound establishes that any Hamiltonian path p in the permutation graph G_n has weight at least:

  n! + (n-1)! + V - 3

where V is the number of 2-cycles visited by p.

Now, if V is as small as possible, i.e. if V = (n-2)!, then the 2-cycles visited by p are disjoint. It follows that each 1-cycle belongs to just one 2-cycle, so p completely traverses each 1-cycle before leaving it, therefore that p may be obtained by applying the recursive construction to some Hamiltonian path p' in G_{n-1}.

In this case w(p) = n! + w(p') ≥ n! + (n-1)! + (n-2)! + (n-3)! - 3.

The other possibility is that V is not as small as possible, i.e. V > (n-2)!.

In either case w(p) > n! + (n-1)! + (n-2)! - 3. QED.

As for how to improve it further, I wonder what bounds we can find in terms of the number of connected components of the 2-cycle graph – i.e. the graph whose nodes are the 2-cycles visited by p, and where there is an edge A–B iff A and B overlap. It is obviously true that having fewer connected components means we need to visit more 2-cycles; and it is intuitively plausible that having many connected components means we are forced to use edges of weight > 3.

Best wishes,

Robin

[Robin Houston]

On Thu, 1 Nov 2018 at 21:18 Robin Houston <robin....@gmail.com> wrote:

p completely traverses each 1-cycle before leaving it, therefore that p may be obtained by applying the recursive construction to some Hamiltonian path p' in G_{n-1}.

That implication isn’t actually true, is it? Sorry. I guess some more work is needed even to improve the bound by one! But surely something along these lines can be made to work…

R

[Vince Vatter]

Hi Robin,

Yes, I think a lot of people have been looking at pushing the lower bound! In particular, Jay Pantone and I have been chatting about this for a week now. Our thoughts have centered around first finding a lower bound for superpermutations that satisfy the "Egan rules": never revisit a permutation, and never take an edge of weight 3 or more. We're fairly confident that in this case, Greg's construction is best possible (though we hope his construction can be improved by 1, in general, because that would make everything work out nicely). We just don't have anything we're willing to put out for public consumption yet.

Cheers,

Vince

[Robin Houston]

Thank you, Vince. That sounds great! I look forward to it.

I imagine you have other good reasons for wanting to wait till you have something coherent to say, but for the avoidance of doubt and for everyone else here, I’d like to emphasise that half-baked ideas are very welcome on this forum.

In the spirit of which: let me have another go at showing that the n! + (n-1)! + (n-2)! - 3 bound can be improved by one. I’ll try to be a bit more careful this time.

I’ll use the formulation where the graph G_n includes improper edges, and we are considering Hamiltonian paths – only because this is the setting in which I’ve been thinking about it.

Let p be a Hamiltonian path in G_n. It follows from the Anonymous proof that, for the bound to be tight,

• p must visit only (n-2)! different 2-cycles, and
• p contains no edge of weight > 3, and
• each weight-3 edge goes from a finished 1-cycle to a 2-cycle that has not previously been visited.
  

(The late Harold Simmons once told me that a claim that follows directly from the proof of some theorem – rather than from its statement – may be called a Scholium. It’s a shame this is so non-standard, because it would be a useful term.)

If p visits more than (n-2)! 2-cycles we are done; so suppose p visits precisely (n-2)! 2-cycles, which must therefore be disjoint.

Since each 1-cycle of G_n belongs to only a single 2-cycle visited by p, that 1-cycle may be entered only once; so each 1-cycle is completely traversed by p before p moves to a different 1-cycle.

If there is any edge e in p that has w(e) > 3, we are done, so suppose every edge of p has weight at most 3. An edge that joins two disjoint 2-cycles must necessarily have weight > 2.

Since each weight-3 edge has to go to a new 2-cycle, we cannot return to a previously-visited 2-cycle. So each 2-cycle also must be completely traversed by p before p leaves that 2-cycle.

Suppose we have traversed a 2-cycle in this way, completing each 1-cycle before leaving it, starting at the permutation xXab and ending at baxX. (Here a, b, x are distinct symbols and X is a word containing the remaining symbols.) This 2-cycle is b/xXa in the notation Greg Egan and I have been using. The next edge of p must have weight 3. Of the six edges of this weight, three lead to the 2-cycle we have just traversed, and two more lead to 2-cycles that overlap that one. The sixth is baxX → Xxab.

So in fact p must consist of a single 3-cycle, and cannot be a Hamiltonian path at all if n > 4.

This line of thinking can surely be pushed a bit further at least, but I’ll leave it here for now.

Best wishes,

Robin

--
You received this message because you are subscribed to the Google Groups "Superpermutators" group.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/d340e85a-2270-4afd-a6af-18524c56b178%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Tahg]

I think this is exactly the conclusion I came to, although I'm not that great with notation.  Where to go from there is more difficult though.  For my construction, I took a complete 3-cycle, and then inserted the remaining elements (one partial 2-cycle at a time [a total of a 2-cycle - 1-cycle worth of elements at a time])  Some observations:

1-cycles may have other elements within them. In particular, they may have the rest of a 2-cycle inserted. (And this is recursive, so 1-cycles within that inserted 2-cycle may themselves have 2-cycles, and so on)

All 1-cycles in the 2-cycle (or 3-cycle) have the same pivot symbol. ie given a 1-cycle of XpX, p is the pivot and X is the remaining symbols.

An inserted 2-cycle must have a different pivot than the 2-cycle it's being inserted into.

Completing 2-cycles in this way is more efficient than adding an equivalent number of elements in either 1-cycles or 3-cycles.  What I don't know is if this initial 3-cycle (not necessarily consecutive elements in the final path) is the most efficient construction or not.

Robin

To unsubscribe from this group and stop receiving emails from it, send an email to superpermutators+unsubscribe@googlegroups.com.
To post to this group, send email to superpermutators@googlegroups.com.

[Greg Egan]

This all looks correct to me!

It really takes a lot of exposure to this stuff to get a good sense of all the structures and their properties ... until you forced me to check, I would have sworn that there'd be more freedom with the choice of a weight-3 edge. But there isn't.

[Tahg]

Somehow allowing weight 3 edges allows a reduction by 1. What's confusing though to me is that there's n-3 weight-3 edges and I don't see how that corresponds to a reduction of 1 (or any reduction at all)

[Robin Houston]

I thought it would be fun to see what lower bound comes out if we make an educated guess about how far we might be able to push this line of thinking.

Specifically, I’ll make the following

Wild guess: w(p) ≥ n! + (n-1)! - 3 + c2 + ceiling (cc / (n-2)) - 1

where c2 is the number of 2-cycles visited by p, and cc is the number of connected components of the 2-cycle graph of p.

The idea is that I hope we may be able to show that p must have at least ceiling (cc / (n-2)) - 1 edges of weight > 3.

If we consider the 2-cycles one by one, in such an order that whenever possible the one we look at is linked in the 2-cycle graph to one we have previously looked at, and count how many 1-cycles each contributes, a 2-cycle from a new connected component contributes (n-1) 1-cycles, and the other 2-cycles contribute at most (n-2).

So we have the inequality

  cc + (n-2)c2 ≥ (n-1)!

Hence

  cc ≥ (n-1)! - (n-2)c2

Therefore

 ceiling (cc / (n-2)) ≥ cc / (n-2)

   ≥ (n-2)! + (n-3)! - c2

Combining this with the Wild guess gives:

  w(p) ≥ n! + (n-1)! + (n-2)! + (n-3)! - 4

which is precisely our conjectured upper bound.

It really does feel like we’re getting close! Exciting times.

R

--
You received this message because you are subscribed to the Google Groups "Superpermutators" group.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/ea6ffe47-d60f-4dbd-88c8-383125daea58%40googlegroups.com.

[Tahg]

Closer, we still have a discrepancy of 'n' when comparing to current minimums for 3-6 of: n! + (n-1)! + (n-2)! + (n-3)! + n - 4

To unsubscribe from this group and stop receiving emails from it, send an email to superpermutators+unsubscribe@googlegroups.com.
To post to this group, send email to superpermutators@googlegroups.com.

[Robin Houston]

That’s just the difference between looking at lengths of superpermutations and weights of Hamiltonian paths. The superpermutation corresponding to a Hamiltonian path of weight w has length n + w.

To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/ea6ffe47-d60f-4dbd-88c8-383125daea58%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

You received this message because you are subscribed to the Google Groups "Superpermutators" group.

To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/5feace1a-1672-4a6e-b52d-ebd740ef4f25%40googlegroups.com.

[Tahg]

Ah that makes sense.  I forget about that part because I don't deal with the problem conceptually as a graph of any sort.

To unsubscribe from this group and stop receiving emails from it, send an email to superpermutators+unsubscribe@googlegroups.com.
To post to this group, send email to superpermutators@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/ea6ffe47-d60f-4dbd-88c8-383125daea58%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "Superpermutators" group.

To unsubscribe from this group and stop receiving emails from it, send an email to superpermutators+unsubscribe@googlegroups.com.
To post to this group, send email to superpermutators@googlegroups.com.