Egan's construction is best possible if you only allow edges of weight 1 and 2

[Vince Vatter]

Hello everyone!

Today, Michael Albert, Jay Pantone, and I considered the question of whether Egan's construction is best possible if you only allow edges of weight 1 and 2 (Michael, Jay, and I are all at the same conference this week). Our conclusion (in the attached pdf) is that it is.

One implication of this result is that improving the upper bound will require at least a few edges of weight 3 or more (shorter optimal constructions suggest that that there might be an optimal superpermutation using precisely n-3 edges of weight 3). 

Cheers,

Vince

[Greg Egan]

Great result, well done!

[Robin Houston]

Thanks for sharing this, Vince. This is great!

To relate it to what I’ve been saying (e.g. in this message), we know that if p is a Hamiltonian path in G_n then

  w(p) ≥ n! + (n-1)! - 3 + c2

where c2 is the number of 2-cycles visited by p. We also know that

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

where cc is the number of connected components of the 2-cycle graph of p. (That’s the graph whose nodes are the 2-cycles visited by p, and where there is an edge between two 2-cycles if they share at least one 1-cycle.)

The case considered here is where the 2-cycle graph is connected, i.e. cc = 1, hence (n-2)c2 + 1 ≥ (n-1)!. Thus c2 ≥ (n-2)! + (n-3)! - 1/(n-2). Since c2 is a whole number, for n > 3 this implies c2 ≥ (n-2)! + (n-3)!. So

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

whenever n > 3, if the 2-cycle graph is connected.

Cheers,

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/0fdbcf61-e152-4330-9ed8-e15cf3c51eb1%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Robin Houston]

PS. Obviously the same argument works whenever cc < n-2, so it shows that we need at least (n-2) connected components – i.e. at least (n-3) edges of weight ≥ 3 – if we want to do better than the Egan construction.