[seqfan] Re: A264041

Neil Sloane njasloane at gmail.com
Sat Nov 7 21:53:33 CET 2015


Robert, A264041 is indeed a lovely sequence.

When n is odd, you say there can be more than one solution.

For odd n >= 7, there is quite a contrast between the pictures
on the left (for n odd) and on the right (for n even).

On the left the examples you give have no symmetry at all. If there are a
lot of solutions, is it possible that there are symmetric solutions that
you didn't see? For small odd n, 5, 7, 9, say, do you have a feeling for how
big the solution space is?

If it is the case that for some odd n the solution is unique AND ugly, that
would be an interesting fact

[This is of course a question that often arises in packing problems. Are
optimal solutions necessarily beautiful? But it is rare to see a problem
where half the time the solution is beautiful, half the time not.]

Best regards
Neil

Neil J. A. Sloane, President, OEIS Foundation.
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com


On Thu, Nov 5, 2015 at 8:11 PM, <israel at math.ubc.ca> wrote:

> Thanks, Rob. That seems like a good idea: this problem has maximal
> 4-cliques (corresponding to slashes meeting at an interior vertex) as well
> as 2-cliques. However, it still doesn't look like Cplex is going to manage
> to compute a(27) on my computer.
>
> Cheers,
> Robert
>
> On Nov 4 2015, Rob Pratt wrote:
>
> If you used an edge-based formulation with constraints of the form x_i +
>> x_j <= 1 for edge (i,j), you might be able to squeeze out a few more terms
>> by instead using a clique-based formulation. Explicitly, precompute all
>> (maximal) cliques and then use constraints sum {i in C} x_i <= 1 for each
>> clique C. This formulation has a tighter linear programming relaxation.
>>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>



More information about the SeqFan mailing list