Al Zimmermann's: Summertime

[dimkadimon]

Herbert that was a beautiful algorithm and image you posted in the discussion group. Do you mind posting it here as well.

[Herbert Kociemba]

dimkadimon в сообщении #1525466 писал(а):

Herbert that was a beautiful algorithm and image you posted in the discussion group. Do you mind posting it here as well.

It is a pleasure to do so.

The idea is quite easy to understand if not expressed as "mathematical"
as in the paper.

1. Divide the vertices into 5 parts as even as possible and position the
parts on a circle.
2. Connect the vertices:
a) within the parts with color 1
b) between vertices of parts which are neighbors with color 2
c) between vertices of parts which are not neighbors with color 3.

A little visualization is helpful

[Herbert Kociemba]

Fun fact:

color(i,j) = Floor(Abs(Abs(Floor(5 * i / N) - Floor(5 * j / N)) - 2.5))

gives the color (0, 1 or 2) of the edge between vertices i and j, 0<=i,j<N . So the asymtotic best solution is a one liner.

[dimkadimon]

Herbert Kociemba в сообщении #1525483 писал(а):

Fun fact:

color(i,j) = Floor(Abs(Abs(Floor(5 * i / N) - Floor(5 * j / N)) - 2.5))

gives the color (0, 1 or 2) of the edge between vertices i and j, 0<=i,j<N . So the asymtotic best solution is a one liner.

That's very nice. There is a similar one-line formula in https://oeis.org/A343608

The image has made me think a lot deeper about the problem. I realised a few things:

* We can use this approach to search for solutions for $K>3$ colours. Split the nodes into groups. Interconnect the groups with $K-1$ colours such that they don't form mono triangles and interconnect nodes in the same group with one remaining colour. So for $K=4$ we can use 16 groups as they can be connected with 3 colours without mono triangles.
* If the subgraph induced by a single colour is a tree or a cycle then it won't have any mono triangles. So to get a solution without any mono triangles we simply need to divide our graph into $K$ subgraphs (that are trees or cycles) that a) don't intersect and b) span the whole graph.

[dimkadimon]

No forget the idea of using trees and cycles - they don't have enough edges.

I also looked at triangle free strongly regular graphs. If we had one such 11-regular graph with 56 nodes then we could try to use 4 copies of it to make a 4-colouring with 56 nodes, which would be a record. However it is proven that such a graph doesn't exist. The closest is the Gewirtz graph, but it is only 10-regular:
https://en.m.wikipedia.org/wiki/Gewirtz_graph

[Herbert Kociemba]

dimkadimon в сообщении #1525504 писал(а):

We can use this approach to search for solutions for $K>3$ colours. Split the nodes into groups. Interconnect the groups with $K-1$ colours such that they don't form mono triangles and interconnect nodes in the same group with one remaining colour. So for $K=4$ we can use 16 groups as they can be connected with 3 colours without mono triangles.

It is possible that this approach also will give the configuration with a minimum number of monochromatic triangles for all N greater some N0. But for lower N this does not work very well. With K=4 and N=48 we already would have 16 monochromatic triangles, but for K=4 even for N=50 there exists a coloring without any mono triangles.

dimkadimon в сообщении #1525504 писал(а):

That's very nice. There is a similar one-line formula in https://oeis.org/A343608

The formula you refer to is the formula for the number of monochromatic triangles in that coloring I believe. But I think it is more amazing that the complete algorithm (Divide the vertices into 5 parts as even as possible ...) can be packed into a relatively simple formula.

[traffic_lights]

dimkadimon в сообщении #1525086 писал(а):

... Я наконец нашел все оптимальные решения. Первые 22 нашел методом отжига, а вот последние три никак не мог найти...

Я все решения нашел методом отжига: вплоть до n=63 решения выскакивают мгновенно, решение для n=215 появилось примерно через час (на 11 ядрах).

[Herbert Kociemba]

At least for N>=23 you will get the best known optimal solution for N+1 also almost immediately if you take best known solution for N, add a point and just do simulated annealing with the N new edges which end in this point. Annealing N edges instead of N(N+1)/2 edges is much faster.
This incremental method also works if you have the N=17 solution (5 triangles)to get the N=18 solution (10 triangles) and to go from there to the N=19 solution (15 triangles). The N=20 solution retrieved by this method from the N=19 solution has 21 triangles instead of the best known 20 triangles, so it fails here.

[traffic_lights]

Herbert Kociemba
Я приступил к реализации алгоритма только в пятницу 9 июля, т.к. онлайн работа со студентами отнимала очень много сил. К этому времени все это уже было известно, как и формула для ребер, которая сразу давала все искомые решения. В дискуссионной группе участники отмечали проблемы с отжигом. Меня это заинтересовало и действительно рабочий алгоритм отжига для данной задачи оказался нетривиальным. Поэтому я и решил поделиться с участниками конкурса своими результатами. Может быть, Ваш алгоритм отжига для работы со всей матрицей более эффективен?

P.S.
Забыл отметить, что скорость программы прямо пропорциональна количеству ядер: на хорошем кластере для n=215 ответ можно получить сразу. Если алгоритм кого-то заинтересует, то после окончания конкурса я его выложу.

[Herbert Kociemba]

traffic_lights в сообщении #1525905 писал(а):

Если алгоритм кого-то заинтересует, то после окончания конкурса я его выложу.

Yes, I would be interested. I realized that my incremetal method is the same what dmd describes in his post. You can start with the solution with N=16 and 0 triangles. By adding point after point you get solutions for N=17, 18, 19, 20, 21, 22, 23, 24 with 5, 10, 15, 20, 25, 33, 41, 50 triangles. The solutions get worse than the default method for N>=22. It is interesting that all solutions in this series up to N=21 have only triangles of a single color, which is not the case for N>=22.
If you start with the default solution for some N, the incremental method obviously gives the default solution for N+1. And it seems, that that all known best solutions for all N >=22 are the default solutions. So basically, solutions with fewest (currently known) triangle numbers all can be generated with the incremental method from the two chains
N=16 (0 triangles)->17->18->19->20->21 and
N=22(default solution)->23->24->25-> ..... infinity

It also is interesting that though the N=19 solution obtained incrementally has 15 triangles of one color, there also exists a solution with 5 triangles of each color which I never happened to see with simulated annealing. Plotting only the triangles the solution looks like this:


The thick lines are the base of all triangles of one color.

Herbert Kociemba в сообщении #1525518 писал(а):

It is possible that this approach also will give the configuration with a minimum number of monochromatic triangles for all N greater some N0. But for lower N this does not work very well. With K=4 and N=48 we already would have 16 monochromatic triangles, but for K=4 even for N=50 there exists a coloring without any mono triangles.

I realized that this method is not as bad as I thought with K=4 colors. The number of triangles with m=Floor(N/16) and r = Mod(N,16) is
r*Binomial(m+1,3)+ (16-r)*Binomial(m,3)
and for N= 55, 56, 57 it gives 37, 40, 43 triangles. If you compare this with the data Martin Piotte gave in [e-mail] it seems that the default method with 4 colors gives good values for N>=56.

n     | number of monochromatic triangles
------+----------------------------------
<= 50 | 0
51    | 1
52    | 4
53    | 10
54    | 21
55    | 32
56    | 40
57    | 43

[traffic_lights]

Рассматривалась ли задача о минимальном количестве треугольников, все стороны которых имеют разный цвет?

[erraen]

traffic_lights в сообщении #1525835 писал(а):

dimkadimon в сообщении #1525086 писал(а):

... Я наконец нашел все оптимальные решения. Первые 22 нашел методом отжига, а вот последние три никак не мог найти...

Я все решения нашел методом отжига: вплоть до n=63 решения выскакивают мгновенно, решение для n=215 появилось примерно через час (на 11 ядрах).

Я отжег с достаточно хорошим качеством (но не до оптимума) для n=400 (порядка пары часов на одном ядре, при довольно медленной реализации), после чего начал последовательно выбрасывать вершины, дающие наибольшее количество одноцветных треугольников. Это дало оптимумы для всех значений n кроме 17, к-е пришлось дожечь отдельно.

[traffic_lights]

erraen
Где Вы взяли оптимум для n=400? Можете поточней "качество" полученного Вами решения указать? И каково Ваше время для n=215?

[traffic_lights]

traffic_lights в сообщении #1526285 писал(а):

Рассматривалась ли задача о минимальном количестве треугольников, все стороны которых имеют разный цвет?

Не минимальном количестве треугольников, а максимальное.

[erraen]

traffic_lights в сообщении #1526304 писал(а):

erraen
Где Вы взяли оптимум для n=400? Можете поточней "качество" полученного Вами решения указать? И каково Ваше время для n=215?

Моя реализация не очень эффективная и на не очень подходящем для числодробилок языке, писалась сугубо для "покрутить задачу", но как оказалось, этого было достаточно.
Она слишком медленна, чтобы найти оптимум "с нуля" за разумное время даже для 47, так что для 215 это бы заняло вечность.
Поэтому появилась идея построить бОльший граф, более-менее оптимальный, в надежде что он потом самооптимизируется при уменьшении, и это сработало.

Изначальный граф для n=400 построен последовательным добавлением точек, выбирая цвет рёбер при добавлении исходя из минимизации кол-ва одноцветных треугольников.
После отжига он имел 482622 полноцветных треугольника.
Точного значения оптимума для n=400 на тот момент я не знал, значение никак не выбиралось, действовал по принципу "достаточно долго улучшения нет, попробую поуменьшать".
Построение по асимтотической формуле от Herbert Kociemba дает 410800.

Т.е. фактически это похоже на то, что делал Vovka17, но с однократной оптимизацией и запасом по размеру для нивелировки неоптимальности графа после отжига