Доказательство обобщённой гипотезы Келли-Улама

[Tot]

Доказательство гипотезы вершинной реконструируемости псевдографа (обобщения гипотез Келли-Улама и новой гипотезы реконструируемости орграфов (new digraph reconstruction conjecture)).

Дан неизвестный псевдограф $G$ с $n$ вершинами. $n>2$. $\{v_1, v_2, ..., v_n\}$ -множество вершин псевдографа $G$. Псевдограф $G-v_i$ - это псевдограф, полученный из $G$ отсечением вершины $v_i$.
Оракул выполняет с каждым из $n$ псевдографов $G-v_i$ следующую работу. Он перенумеровывает вершины $G-v_i$ в произвольном порядке и матрицу смежности псевдографа с новой нумерацией записывает на карту(пустой бланк типа игральной карты).
Псевдограф, матрица смежности которого записана на $i$ой карте, изоморфен соответствующему псевдографу $G-v_i$.
Таким образом оракул получает полную колоду из $n$ карт. Эту колоду он демонстрирует нам.
Нужно доказать, что любой псевдограф, реконструируемый на основе предложенной полной колоды, изоморфен псевдографу $G$.

Замечание.Формулировка гипотезы реконструируемости через оракул в отличие от классической формулировки построения графа изоморфному данному по полной колоде карт, которая изоморфна полной колоде карт данного графа, позволяет единообразие в постановке вопроса для неориентированного и для ориентированного графов.
Получается избежать дополнительного условия на одинаковость чисел входов и выходов рёбер у отсечённой вершины соответствующих пар карт полных колод, которое позволяет обойти контрпримеры, возникающие при простом переносе гипотезы Келли-Улама на орграфы.

Доказательство.
Представим $i$ую карту колоды в виде матрицы, дополненной до матрицы смежности искомого графа.
\begin{bmatrix} a_{i,1,1} & a_{i,1,2} & ... & a_{i,1,n-1} & a_{i,1,n}? \\ a_{i,2,1} & a_{i,2,2} & ... & a_{i,2,n-1} & a_{i,2,n}? \\ ... & ... & ... & ... & ...\\ a_{i,n-1,1} & a_{i,n-1,2} & ... & a_{i,n-1,n-1} & a_{i,n-1,n}? \\ a_{i,n,1}? & a_{i,n,2}? & ... & a_{i,n,n-1}? & a_{i,n,n}? \end{bmatrix}
Вопросом отмечены переменные, которые нужно найти в процессе реконструкции.
Переменные, стоящие на диагонали с левого верхнего угла в нижний правый, показывают количество петель у вершины с соответствующим номером в нумерации $i$ой карты.
У каждого элемента три нижних индекса: номер карты в колоде, номер строки в карте, номер столбца в карте.
Элементы, находящиеся в строке и столбце, которые пересекаются в числе петель одной из вершин, выделим в отдельное множество.
Возьмём первую строку и первый столбец $i$ой карты. Рассмотрим множество

$$\{ a_{i,1,1}, (a_{i,1,2}, a_{i,2,1}),(a_{i,1,3}, a_{i,3,1}),...,(a_{i,1,n-1}, a_{i,n-1,1}),(a_{i,1,n}?, a_{i,n,1}?) \}$$

Назовём это множество крестовым первой вершины $i$ой карты колоды.
Выделим и другие крестовые множества в каждой карте. Всего по $n$ крестовых множеств в каждой карте.
Все крестовые множества обладают следующими свойствами:
1) множество содержит один одиночный элемент, характеризующий количество петель у соответствующей вершины;
2) множество содержит $(n-1)$ парных элемента, то есть одинаковые пары не поглощают друг друга;
3) одиночный элемент и пары внутри множества неупорядоченны;
4) внутри пары строгий порядок, в начале стоит элемент строки, а затем элемент столбца;
5) пары множества отражают взаимодействие вершины графа с данным номером в нумерации данной карты со всеми другими вершинами графа;
6) множество является инвариантом относительно синхронного перемещения строк и столбцов матрицы смежности при подстановке изоморфизма.
Имеем $n$ крестовых множеств, которые одни и те же в каждой карте полной колоды, дополненной
строкой и столбцом неизвестных до матрицы смежности графа $G$.
Рассмотрим неизвестные $i$ой карты колоды.
Диагональный элемент $n$ой строки $i$ой карты нам известен. Действительно, посчитаем количество каждого известного диагонального элемента по всем картам колоды, разделим полученные количества на $n-1$ и вычеркнем из полученного множества все известные диагональные элементы $i$ой карты. Получим искомое. Так можно получить неизвестный диагональный элемент у всех карт колоды.

Множество неизвестных $n$ой строки $i$ой карты нам известно. Действительно, посчитаем количество каждой уникальной пары известных элементов по всем картам колоды, разделим полученные количества на $n-1$, вычтем известные пары $i$ой карты. Полученное множество пар определяет множества неизвестных $n$ой строки и множество неизвестных $n$ого столбца $i$ой карты за вычетами из обоих множеств диагонального элемента, определённого ранее.

Предположим, что нам как-то удалось определить расположение всех неизвестных $n$ой строки $i$ого листа. Тогда по парам элементов мы автоматически знаем расположение всех неизвестных $n$ого столбца $i$го листа. Действительного, если есть две пары неизвестных элементов, то значит есть два одинаковых крестовых множества, а значит по свойствам крестовых множеств эти пары неизвестных взаимозаменяемы.
Следовательно, мы можем искать порядок только в строке неизвестных элементов, в столбце неизвестных элементы выстроятся в нужном порядке автоматически.

Доказательство исходной гипотезы проведём от противного.
Пусть исходный псевдограф нельзя реконструировать по полной колоде карт. Это значит, что существует ещё один псевдограф, реконструируемый по той же полной колоде и отличный от данного.
Дополним все листы полной колоды неизвестными до матрицы смежности так, как это делали ранее.
Рассмотрим $i$ый лист полной колоды. По неизвестному диагональному элементу оба наши псевдографы
равны, иначе их полные колоды были бы различны.
Возьмём множество неизвестных элементов $n$ой строки $i$го листа, кроме диагонального.
Это множество нам известно, как было установлено ранее, нужно определить их взаимное расположение.
Наши псевдографы имеют различное расположение этих элементов, иначе они совпадают.
Рассчитаем минимальное количество перестановок, которое переводит матрицу смежности первого псевдографа в матрицу смежности второго на всех листах.
Пусть натуральное $l$ - число неизвестных элементов $n$ой строки $i$го листа, которые необходимо поменять, чтобы первый псевдограф перешёл во второй. Тогда $l \in \{2,... ,n-1\}$. При минимуме одной перестановки
участвуют два элемента, а при максимуме числа элементов используются все элементы, кроме диагонального.
Пусть натуральное $k$ - минимальное число перестановок этих элементов для перевода строки неизвестных элементов псевдографа первого в строку неизвестных элементов псевдографа второго. Тогда $\frac{l}{2}\leqslant k\leqslant l-1$. При минимуме количества перестановок каждая пара элементов не на своём месте ставится на своё взаимной перестановкой. При максимуме при каждой перестановке, кроме последней, один из элементов пары не на своём месте ставится на своё.
Эти $l$ неизвестных элементов назовём независимыми в противовес с зависимыми переменными из неизвестного столбца, то есть $n$го столбца $i$го листа.
Рассмотрим отражение перестановок этих независимых элементов на остальных листах полной колоды.
На $n-l$ листах, включая исходный $i$ый, будут отражаться все $k$ перестановок, в то время как
на оставшихся $l$ листах одна перестановка будет выпадать, так как нельзя проводить перестановку с диагональным элементом. Имеем $l$ элементов, которые нужно бы в общем случае с чем-то переставить, но их партнёром по потенциальной перестановке, отражающей соответствующую перестановку в $i$ом листе, выступают диагональные элементы. Такие элементы назовём одинокими. При необходимости одинокий элемент можно переставить только с соответствующей зависимой переменной той же строки. Пусть числом таких перестановок одиноких с зависимыми переменными будет натуральное $s$. Тогда $s \in \{0,1,...,l-1\}$. Минимум перестановок с зависимыми переменными равен нулю, если повезёт.
Покажем, что максимум равен $l-1$, а не $l$. Начнём проводить все перестановки независимых переменных и их отражений на других листах, кроме одной выбранной и её отражений. Проведём все перестановки с зависимыми переменными, кроме двух с отражениями выбранной перестановки. Это состояние полной колоды назовём промежуточным при переходе от первого псевдографа к второму.
По сути у нас осталось сделать ещё $n$ перестановок, из них $n-2$ между независимыми переменными и $2$ одиноких с зависимыми. Однако переход от промежуточного состояния к второму псевдографу является при использовании обеих перестановок одиноких с зависимыми лишь перестановкой двух соседних крестовых множеств. Поэтому оно противоречит нашему переходу от первого псевдографа к второму с использованием минимального количества необходимых перестановок. У нас же получается, что в промежуточном состоянии колода на всех листах уже является матрицей смежности второго псевдографа.
Поэтому максимум перестановок одиноких с зависимыми равен $l-1$.
Общее число перестановок при переходе от первого псевдографа к второму псевдографу на всех листах полной колоды будет равно $(k-1)l+k(n-l)+s$. При этих преобразованиях каждый из дополненных листов полной колоды переводится из матрицы смежности первого псевдографа в матрицу смежности второго. Поэтому число этих перестановок при нашем допущении о возможности реконструирования двух разных псевдографов на основе одной полной колоды должно делиться на $n$, так как матрица смежности однозначно задаёт псевдограф.
Пришли к противоречию. Гипотеза вершинной реконструируемости псевдографа доказана.

[mihaild]

Tot в сообщении #1130277 писал(а):

Рассмотрим отражение перестановок этих независимых элементов на остальных листах полной колоды.

Что такое "отражение перестановки"?

(правда же, что перестановкой вы называете транспозицию?)

Учитываете ли вы, что множество транспозиций не однозначно задается двумя строками ($n$-я строка матрицы смежности старого и нового графов)?

[Tot]

1. Да, можно сказать, что рассматриваем множество транспозиций при учёте множества инвариантов относительно изоморфных преобразований.
2. Да, выбираем множество с минимальным количеством транспозиций. Если взять не минимальное, то его можно разбить на минимальное и на множество перестановок пар туда и обратно. Тогда второе множество для нашей задачи будет уже избыточным. Среди множеств с минимальным количеством разницы нет, так как результат одинаков за одинаковое количество действий, то есть влияния на наличие противоречия нет.

[mihaild]

Что значит "отражение перестановки на листах"?
Для каждого листа $i$ можно найти число $k_i$ - минимальное число транспозиций, отправляющих $n$-ю строку $i$-го листа $1$-го графа в $n$-ю строку $i$-го листа $2$-го графа. Взяли среди всех $k_i$ минимальное, и зафиксировали какой-нибудь соответствующий набор транспозиций.

Дальше, как я понимаю, вы берете какой-то другой лист, и доказываете про него какое-то утверждение. Можете подробнее расписать?

[Tot]

Версия №2.
Доказательство гипотезы вершинной реконструируемости псевдографа, в том числе ориентированного. (обобщения гипотез Келли-Улама и новой гипотезы реконструируемости орграфов (new digraph reconstruction conjecture)).

Терминология:
Мультиграф - граф с кратными рёбрами без петель.
Псевдограф - мультиграф с петлями.
Неориентированный псевдограф задаётся множествами вершин и рёбер.
Ориентированный псевдограф задаётся множествами вершин, рёбер, количеств выходящих из вершин рёбер и количеств входящих в вершины рёбер.

Дан неизвестный псевдограф $G$ с $n$ вершинами, то есть ориентированный или неориентированный граф с кратными рёбрами и петлями. $n>2$. $\{v_1, v_2, ..., v_n\}$ -множество вершин псевдографа $G$. Псевдограф $G-v_i$ - это псевдограф, полученный из $G$ отсечением вершины $v_i$.
Оракул выполняет с каждым из $n$ псевдографов $G-v_i$ следующую работу. Он перенумеровывает вершины $G-v_i$ в произвольном порядке и матрицу смежности псевдографа с новой нумерацией записывает на карту(пустой бланк типа игральной карты).
Псевдограф, матрица смежности которого записана на $i$ой карте, изоморфен соответствующему псевдографу $G-v_i$.
Таким образом оракул получает полную колоду из $n$ карт. Эту колоду он демонстрирует нам.
В случае ориентированного псевдографа множества количеств входных в вершины и выходных из вершин рёбер позволяют оракулу выписать все карты колоды.
Нужно доказать, что любой псевдограф, реконструируемый на основе предложенной полной колоды, изоморфен псевдографу $G$.

Доказательство.
Представим $i$ую карту колоды в виде матрицы, дополненной до матрицы смежности искомого графа с помощью столбца и строки, отражающих связь вершины $v_i$ с другими вершинами псевдографа $G$.
На основе исходных данных это всегда можно сделать.
\begin{bmatrix} a_{i,1,1} & a_{i,1,2} & ... & a_{i,1,i}? & ... & a_{i,1,n-1} & a_{i,1,n} \\ a_{i,2,1} & a_{i,2,2} & ... & a_{i,2,i}? & ... & a_{i,2,n-1} & a_{i,2,n} \\ ... & ... & ... & ... & ... & ... & ...\\ a_{i,i,1}? & a_{i,i,2}? & ... & a_{i,i,i}? & ... & a_{i,i,n-1}? & a_{i,i,n}? \\ ... & ... & ... & ... & ... & ... & ...\\ a_{i,n-1,1} & a_{i,n-1,2} & ... & a_{i,n-1,i}? & ... & a_{i,n-1,n-1} & a_{i,n-1,n} \\ a_{i,n,1} & a_{i,n,2} & ... & a_{i,n,i}? & ... a_{i,n,n-1} & a_{i,n,n} \end{bmatrix}
Вопросом отмечены переменные, которые нужно найти в процессе реконструкции, элементы с вопросом относятся к закрытой части карты, а все остальные находятся в открытой части.
Переменные, стоящие на диагонали с левого верхнего угла в нижний правый, показывают количество петель у вершины с соответствующим номером в нумерации $i$ой карты.
У каждого элемента три нижних индекса: номер карты в колоде, номер строки на карте, номер столбца на карте.
Элементы, находящиеся в строке и столбце, которые пересекаются в числе петель одной из вершин, выделим в отдельное множество.
Возьмём первую строку и первый столбец $i$ой карты. Рассмотрим множество

$$\{ a_{i,1,1}, (a_{i,1,2}, a_{i,2,1}),(a_{i,1,3}, a_{i,3,1}),...,(a_{i,1,n-1}, a_{i,n-1,1}),(a_{i,1,n}, a_{i,n,1}) \}$$

Назовём это множество крестовым первой вершины $i$ой карты колоды.
Выделим и другие крестовые множества на каждой карте. Всего по $n$ крестовых множеств на каждой карте.
Все крестовые множества обладают следующими свойствами:
1) множество содержит один одиночный элемент, характеризующий количество петель у соответствующей вершины;
2) множество содержит $(n-1)$ парных элемента, то есть одинаковые пары не поглощают друг друга;
3) одиночный элемент и пары внутри множества неупорядоченны;
4) внутри пары строгий порядок, в начале стоит элемент строки, а затем элемент столбца;
5) пары множества отражают взаимодействие вершины графа с данным номером в нумерации данной карты со всеми другими вершинами графа;
6) множество является инвариантом относительно синхронного перемещения строк и столбцов матрицы смежности при подстановке изоморфизма.
Имеем $n$ крестовых множеств, которые одни и те же в каждой карте полной колоды, дополненной строкой и столбцом неизвестных до матрицы смежности графа $G$.
Рассмотрим неизвестные $i$ой карты колоды.
Диагональный элемент $i$ой строки $i$ой карты нам известен. Действительно, посчитаем количество каждого известного диагонального элемента по всем картам колоды, разделим полученные количества на $n-1$ и вычеркнем из полученного множества все известные диагональные элементы $i$ой карты. Получим искомое. Так можно получить неизвестный диагональный элемент у всех карт колоды.

Множество неизвестных $i$ой строки $i$ой карты нам известно. Действительно, посчитаем количество каждой уникальной пары известных элементов по всем картам колоды, разделим полученные количества на $n-1$, вычтем известные пары $i$ой карты. Полученное множество пар определяет множества неизвестных $i$ой строки и множество неизвестных $i$ого столбца $i$ой карты за вычетами из обоих множеств диагонального элемента, определённого ранее.

Предположим, что нам как-то удалось определить расположение всех неизвестных $i$ой строки $i$ого листа. Тогда по парам элементов мы автоматически знаем расположение всех неизвестных $i$ого столбца $i$го листа. Действительного, если есть две пары неизвестных элементов, то значит есть два одинаковых крестовых множества, а значит по свойствам крестовых множеств эти пары неизвестных взаимозаменяемы.
Следовательно, мы можем искать порядок только в строке неизвестных элементов, в столбце неизвестных элементы выстроятся в нужном порядке автоматически.

Доказательство исходной гипотезы проведём от противного.
Пусть исходный псевдограф нельзя реконструировать по полной колоде карт. Это значит, что существует ещё один псевдограф, реконструируемый по той же полной колоде и отличный от данного.
Дополним все листы полной колоды неизвестными до матрицы смежности так, как это делали ранее.
Рассмотрим $i$ый лист полной колоды. По неизвестному диагональному элементу оба наши псевдографы
равны, иначе их полные колоды были бы различны.
Возьмём множество неизвестных элементов $i$ой строки $i$го листа, кроме диагонального.
Это множество нам известно, как было установлено ранее, нужно определить их взаимное расположение.
Наши псевдографы имеют различное расположение этих элементов, иначе они совпадают.
Рассматривать будем только перестановку в строке элементов, держа в уме синхронную перестановку в соответствующем столбце.
При неориентированных графах соответствующие перестановки в строке и в столбце происходят синхронно, при ориентированных графах соответствующие перестановки в строке и в столбце производят синхронно принудительно, так как если два различных псевдографа реконструируются из одной полной колоды карт, то переход от одного псевдографа к другому происходит и при синхронных перестановках соответствующих элементов строк и столбцов. Это следует из того, что любой парный элемент любого крестового множества изначально определён на $n-1$ой картах колоды, а значит в итоге должен сохраниться при любой группе преобразований из первого псевдографа во второй.
Рассмотрим минимальное количество транспозиций в перестановке, которое переводит матрицу смежности первого псевдографа в матрицу смежности второго на $i$ом листе.
Пусть натуральное $l$ - число неизвестных элементов , которые необходимо поменять, чтобы первый псевдограф перешёл во второй.

$$l \in \{2,... ,n-1\}$$

При минимуме в перестановке из одной транспозиции участвуют два элемента, а при максимуме числа элементов используются все элементы, кроме диагонального.
Пусть натуральное $k$ - минимальное число транспозиций этих элементов для перевода строки неизвестных элементов псевдографа первого в строку неизвестных элементов псевдографа второго.

$$\frac{l}{2}\leqslant k\leqslant l-1$$

При минимуме количества транспозиций каждая пара элементов не на своём месте ставится на своё одной транспозицией. При максимуме при каждой транспозиции, кроме последней, только один из элементов пары не на своём месте ставится на своё.
Перевод первого псевдографа во второй на $i$ом листе осуществляется с помощью $k$ транспозиций $l$ элементов в $i$ой строке и соответствующих $k$ транспозиций $l$ элементов в $i$ом столбце.
Другие преобразования на $i$ом листе не требуются, так как элементы, не участвующие в перестановке, уже находятся на своих местах.
Но наши преобразования на $i$ом листе вызвали соответствующие преобразования-отражения на открытых частях всех других карт колоды.
Пусть натуральное $s$ - число элементов открытых частей всех листов, кроме $i$ого, которые участвуют в этих преобразованиях-отражениях.
Все эти элементы изменены, так как число транспозиций $k$ по определению минимально.
Между тем у обоих псевдографов все открытые части всех листов колоды одинаковы.
Поэтому нужно компенсировать эти изменения путём транспозиции между таким элементом и находящимся напротив элементом неизвестной строки на данном листе.
Таким образом имеем $s$ компенсаторных транспозиций, которые возвращают в прежнее положение изменённые элементы на открытых частях карт, кроме $i$ой.
Рассмотрим отражение компенсаторных транспозиций на $i$ый лист.
Но там всё уже в порядке ещё до этих отражений.
Поэтому отражения компенсаторных транспозиций на этом листе должны самокомпенсироваться.
А для этого нужно

$$(2(n-1))\mid s$$

Отражения компенсаторных транспозиций равномерно распределены по открытым частям $n-1$ строк $i$ого листа,
так как на закрытой части их быть не может, а между тем они являются лишь обратным отражением исходной перестановки на каждый из листов колоды, кроме исходного.
Причём для самокомпенсации их должно быть на открытой части каждой из строк чётное число.
Посчитаем $s$.
Рассмотрим первую транспозицию из наших $k$ транспозиций $i$ой строки $i$го листа. Два элемента в ней участвующих отражаются в один элемент на открытой части на двух других листах и в два элемента на открытой части на всех остальных листах.
Значит первая транспозиция, как и любая другая из $k$ транспозиций $i$ой строки $i$го листа, порождает
$2+2(n-3)$ компенсаторных транспозиций. Отсюда

$$s=2(n-2)k$$

Пришли к противоречию, доказывающему гипотезу вершинной реконструируемости псевдографа, так как $2k(n-2)\mod 2(n-1)\neq 0$ при $n>2$.