User matt ollis - MathOverflow

Answer by Matt Ollis for Counting graceful paths

2011-05-31T12:28:25Z

An efficient algorithm is described in a paper by Michael Adamaszek which is powerful enough to count the number of graceful labelings of paths up to length 40. It concludes: "It also remains an open question to find an exponential upper bound on [the number of graceful labelings of paths of length n]"

Answer by Matt Ollis for Mathematical ideas named after places

2011-05-11T20:15:52Z

Italian squares which include Latin squares, Tuscan squares, Roman squares, Florentine squares and Vatican squares as special cases.

Answer by Matt Ollis for Mathematical ideas named after places

2011-05-11T18:42:53Z

The Oberwolfach Problem and the Hamilton-Waterloo Problem

Answer by Matt Ollis for Generating fixtures for a chess league, with a twist

2011-04-10T12:13:14Z

This is an answer to the general advice part of the question rather than the specifics of the chess league problem.

I think the field of math to look at is that of Combinatorial Designs. Roughly speaking, this deals with arranging objects according to constraints and it has subfields that look particularly at various types of tournament/league design (I haven't come across anything that reminds me closely of your particular problem, but that's not good evidence that there isn't something out there already). If you can get access to The Handbook of Combinatorial Designs somehow, that will probably give you some good pointers. (I don't have a copy nearby at the moment to be more specific, sorry.)

The second area you could look at is from the computational side: hill-climbing algorithms. Implementing such an algorithm would mean that you did not have to search through all of the possible combinations, with the trade-off that you are not guaranteed the optimal result. The idea is that you ignore the extra constraint initially and generate a valid schedule. Then you successively tweak the schedule to reduce the number of times teams from the same club play on the same evening. If it doesn't get close enough, start over and try again. You'll need a method of generating initial schedules (which I guess you already have) and a method for tweaking that works nicely with the constraint (usually the difficult step).

Hope this helps.

Answer by Matt Ollis for Hamilton Paths in $K_{2n}$

2011-04-06T23:24:27Z

We can explicitly construct such a decomposition.

Label the vertices of the graph with ${0,1,...,n-1}$, take the first path to be $0, n-1, 1, n-2, 2,... ,n/2$ and generate the other paths by addition modulo $n$ (the $n$ paths come in pairs in which one is the reverse of the other).

More generally, a symmetric sequencing in a group with a single involution is sufficient to construct the decomposition.

Comment by Matt Ollis

2011-06-09T16:40:43Z

Oops, didn't see Emil's comment before I posted (and I also swapped a and c).

Comment by Matt Ollis

2011-06-09T16:39:46Z

I'm not convinced that the best strategy is to get two numbers as big as possible (I'm not convinced otherwise either). What if we try and win on $a$ and $c$ and give up on $b$? That suggests a strategy of the form $a = b = (1-c)/2$, and if we choose $c > 1/2$ we beat someone using your method.