Конкурс Изящные Графы

[dmd]

Желаю удачи вашей команде.

Пожалуйста, не сочтите за труд, транслируйте на русский эту гипотезу. Не получается её однозначно перевести. Шаблон W(r,s) для оптимальных решений единственный? Или не существует оптимальных решение не описываемых этим шаблоном? Или что-то третье?

[dimkadimon]

dmd в сообщении #767644 писал(а):

Шаблон W(r,s) для оптимальных решений единственный?

Нет. Есть оптимальные решения которые нельзя описать этим шаблоном.

Гипотеза говорит что для всех N>12 существует оптимальное решение которое имеет формулу Wichmann. Гипотеза доказана для N<=21.

[Scryer]

In the parallel discussion Valery gives an example for n=29:

0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
2 * 15, 3 * 15, 4 * 15, ..., 14 * 15

This is similar to the construction given by Golomb in:

Golomb, S. W. "The Largest Graceful Subgraph of the Complete Graph." Amer. Math. Monthly 81, 499-501, 1974. The construction is on the first page of the paper, which is here:
http://www.jstor.org/discover/10.2307/2318592?uid=3739560&uid=374268951&uid=2&uid=3&uid=3739256&uid=60&sid=21102663112261

Golomb's construction yields:

0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,30,46,62,78,94,110,126,142,158,174,190,206,222,237

This is considerably lower than Wichmann. I agree that comparing different methods like this might be helpful.

[Scryer]

I should have said that Palovsky's n=29 example was:

0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
2 * 16-1,3 * 16-1,4 * 16-1, ..., 14 * 16-1

A shorter URL for the first page of the Golomb paper: http://goo.gl/NTWCk3

Golomb's construction gives:

0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,30,46,62,78,94,110,126,142,158,174,190,206,222,237

[dimkadimon]

Scryer в сообщении #767808 писал(а):

0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
2 * 15, 3 * 15, 4 * 15, ..., 14 * 15

Can you explain this notation?

[Scryer]

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

Scryer в сообщении #767808 писал(а):

0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
2 * 15, 3 * 15, 4 * 15, ..., 14 * 15

Can you explain this notation?

The usual: 2*15 = 30, 3*15 = 45, ... 14*15 = 210.
The sequence thus goes: 0,1,2,...,14,15,30,45,60,...,210.
Pavlovsky's sequence is similar but better: 0,1,2,...,14,15,31,47,...,224.
Golomb's is also similar and better yet, and still worse than Wichmann.

You're probably still in "figure out what Luschny means with his Wichmann notation" mode.

Also, when Google translates a page from Russian to English, it apparently also translates the English to Russian to English, and then messes up the notation -- perhaps that's what was going wrong with your display of the numbers?

[dimkadimon]

Доказательство что линейка должна начинаться с (0, 1, ... ). Допустим что это не так, тогда линейка имеет вид (0, i, ..., M-k, M), где i>1 и k>1. Но тогда нет ребра длиной M-1 и линейка не генерирует M разных ребр. Значит линейка должна начинаться с (0, 1, ...).

-- 26.09.2013, 21:22 --

Pavlovsky в сообщении #767296 писал(а):

Сильно еще не лазил по ссылкам. Может кто даст ссылку на статью, где доказыватеся, что патерн

1^r, r+1, (2r+1)^r, (4r+3)^s, (2r+2)^(r+1), 1^r

дает все различные разности в заданном диапозоне.

Тут написано что не все W(r,s) дают все разницы:
http://www.mathworks.com/matlabcentral/ ... ann-rulers

[Pavlovsky]

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

Доказательство что линейка должна начинаться с (0, 1, ... ).

Наша последовательность обязана иметь вид (0,...,М). Есть два способа чтобы в нашей последовательности была разность М-1: (0,1,...,М) или (0,...,М-1,М).

Лемма. Если последовательность $(0,A_2,A_3,...,M)$ удовлетворяет условиям задачи, тогда последовательность $(0,...,M-A_3,M-A_2,M)$ тоже удовлетворяет условиям задачи.

То есть последовательность (0,...,М-1,М) можно преобразовать к виду (0,1,...,М).

[malk]

Существуют ли оптимальные не-Wichmann решения для N>14?

[Scryer]

malk в сообщении #768034 писал(а):

Существуют ли оптимальные не-Wichmann решения для N>14?

I think all optimal solutions from N=15 through N=19 are Wichmann. I don't know if there are equal non-Wichmann optimal solutions for N=20 or N=21. I think Wichmann are the best known for N>21.

The highest optimal non-Wichmann solution I know of is for N=14.

[dmd]

1:r, (r+1):1, (2r+1):r, (4r+3):s, (2r+2):(r+1), 1:r

Пусть слева от ":" - основание, а справа от ":" - показатель.

Обратите внимание на взаимосвязи оснований:

(r+1)-(1)=(2r+1)-(r+1)
(2r+1)+(1)=(2r+2)
(2r+1)+(2r+2)=(4r+3) 

Сделав последнее основание параметром получим патерн:

1:r, (r+1):1, (2r+1):r, (4r+t+2):s, (2r+t+1):(r+1), t:r

Случайный брутфорс по этим трём параметрам показывает, что формула действует.
Пробовал в параметры превратить и все (без одного) показатели - тоже формула работает.
Причем N13L57 удалось повторить, N13L58 - нет.


Общая форма патерна

$1:s, \quad r_1:s_1, \quad ..., \quad r_k:s_k$
$N=s+s_1+...+s_k+1$ - число вершин
$L=s+r_1 s_1+...+r_k s_k$ - число рёбер


Если N задано, то один из показателей однозначно вычисляем. Соответственно количество параметров брутфорса равно 2k. Это много, надо искать дополнительные взаимосвязи между основаниями и показателями.


Если N и L заданы, то

$L=N-1+s_1(r_1-1)+...+s_k(r_k-1)$

[whitefox]

А что если линейку свернуть в кольцо?
Соединив её правый и левый концы?

Получим циклическую линейку.

Очевидно, что всякая полная линейка одновременно является и полной циклической линейкой. Обратное, скорее всего, не верно.

Для анализа циклических линеек длины $L$ можно применить теорию колец $\mathbb Z_L$.
В частности, имеется некоторая аналогия с циклическими разностными множествами (cyclic difference set).

[dimkadimon]

whitefox в сообщении #768601 писал(а):

А что если линейку свернуть в кольцо?

Вот у нас линейка (а1, а2, ..., а8, а9), мы соединим а1 и а9. Какое теперь растояние от а9 до а1?

[Scryer]

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

whitefox в сообщении #768601 писал(а):

А что если линейку свернуть в кольцо?

Вот у нас линейка (а1, а2, ..., а8, а9), мы соединим а1 и а9. Какое теперь растояние от а9 до а1?

I assumed he meant that each pair now has either one or two differences. For example if a1=0 and a9=9, this pair covers differences {1,9}: 9 in the usual direction, and 1 in the new direction.

The complete Kuratowski graph K5 would become ring-graceful -- I think you need to pick only four nodes to cover it - e.g. {0,1,2,5} with the fifth node arbitrary.

[dmd]

1:r, (r+1):1, (2r+1):r, (4r+3):s, (2r+2):(r+1), 1:r

Посмотрите на (4r+3):s. Оно всегда такое, что (4r+3)+s=N. Это часто повторяется и в других патернах, дающих неоптимальные решения.