Отношение эквивалентности

[Vladimir Pliassov]

mihaild в сообщении #1579225 писал(а):

Это же неправда. После изъятия $ad$ и $cf$ пара $be$ разрушает 4 тройки.

Правда, что это неправда. Тут возникает вопрос: почему каждая из пар $\lbrace a, d\rbrace$, $\lbrace c, f\rbrace$ и $\lbrace b, e\rbrace$ разрушает по четыре тройки? Я думаю, это потому что они не пересекаются. Я брал $\lbrace a, d\rbrace$, $\lbrace c, f\rbrace$ и $\lbrace b, f\rbrace$ (две последние пары пересекаются), и у меня получалось, что две первые пары разрушают по четыре тройки, а третья только три. Для того, чтобы разрушать как можно больше полных троек, будем брать тройки непересекающихся пар.

Но здесь обнаруживается непонятная вещь.

Разобьем множество $G$ всех $15$ пар элементов множества $X=\lbrace a, b, c, d, e, f\rbrace$ на два подмножества двумя способами:

1) $G=A_1\cup B_1$, где $A_1=\big\lbrace \lbrace a, d\rbrace,\lbrace a, e\rbrace, \lbrace d, e\rbrace\big \rbrace \cup \big\lbrace \lbrace b, c\rbrace, \lbrace b, f\rbrace, \lbrace c, f\rbrace \big \rbrace$, а $B_1=\big\lbrace \lbrace a, b\rbrace,\lbrace c, d\rbrace, \lbrace e, f\rbrace\big \rbrace \cup \big\lbrace \lbrace a, c\rbrace, \lbrace b, e\rbrace, \lbrace d, f\rbrace\big \rbrace \cup \big\lbrace \lbrace a, f\rbrace, \lbrace b, d\rbrace, \lbrace c, e\rbrace \big \rbrace$;

2) $G=A_2\cup B_2$, где $A_2=\big\lbrace \lbrace a, c\rbrace,\lbrace a, e\rbrace, \lbrace b, c\rbrace, \lbrace b, f\rbrace, \lbrace d, e\rbrace, \lbrace d, f\rbrace \big \rbrace$, а $B_2=\big\lbrace \lbrace a, b\rbrace,\lbrace c, d\rbrace, \lbrace e, f\rbrace \big \rbrace \cup \big\lbrace \lbrace a, d\rbrace, \lbrace b, e\rbrace, \lbrace c, f\rbrace \big \rbrace \cup \big\lbrace \lbrace a, f\rbrace, \lbrace b, d\rbrace, \lbrace c, e\rbrace \big \rbrace$.

Как $B_1$, так и $B_2$ состоят из троек непересекающихся пар, но разбиения 1) и 2) существенно отличаются друг от друга.

Заметим, что $B_1$ и $B_2$ отличаются в своих средних подмножествах $\big\lbrace \lbrace a, c\rbrace, \lbrace b, e\rbrace, \lbrace d, f\rbrace\big \rbrace\subset B_1$ и $\big\lbrace \lbrace a, d\rbrace, \lbrace b, e\rbrace, \lbrace c, f\rbrace \big \rbrace \subset B_2$ только тем, что в них $c$ меняется с $d$. Это приводит к тому, что $A_1$ разбивается на две непересекающиеся тройки пар $\big\lbrace \lbrace a, d\rbrace,\lbrace a, e\rbrace, \lbrace d, e\rbrace\big \rbrace$ и $\big\lbrace \lbrace b, c\rbrace, \lbrace b, f\rbrace, \lbrace c, f\rbrace \big \rbrace$ (которые к тому же представляют собой полные тройки элементов из $X$), а $A_2$ нет. (Или же, с другой стороны, то, что $A_1$ разбивается на две непересекающиеся тройки, а $A_2$ нет, приводит к тому, что $B_1$ и $B_2$ отличаются в своих средних подмножествах тем, что в них $c$ меняется с $d$.)

Хотелось бы понять, отчего это так.

Как бы там ни было, это, в свою очередь, приводит к следующему.

Пусть $G$ будет множеством пар незнакомых, а $H$ множеством пар знакомых, и пусть они будут переменными множествами, то есть, несмотря на то, что мы будем добавлять в каждое из них новые элементы или удалять из них элементы, они будут называться $G$ и $H$.

Пусть первоначально $G$ состоит из всех $15$, а $H$ из $0$ пар. Будем переводить из $G$ в $H$ по одной паре (то есть не так, как раньше, а наоборот: будем разрушать полные тройки незнакомых, другими словами, будем знакомить тех, кто незнаком, -- это, чтобы было соответствие с тем, как все излагалось раньше).

Сначала будем делать это в соответствии с первым разбиением (этот случай я уже разбирал).

1) Пока мы не переведем в знакомые все $B_1$ (мы сначала переводим $B_1$, потому что сначала переводим (произвольно выбранные) тройки непересекающихся пар, чтобы разрушить как можно больше полных троек незнакомых), среди незнакомых будет все $A_1$ (которое состоит из двух полных троек незнакомых), а как только мы переведем в знакомые любую пару из $A_1$, среди знакомых появится полная тройка.

Теперь -- в соответствии со вторым разбиением.

2) Первая тройка пар $\big\lbrace \lbrace a, b\rbrace,\lbrace c, d\rbrace, \lbrace e, f\rbrace \big \rbrace$ разрушает $12$ полных троек незнакомых (по четыре тройки каждая пара), вторая тройка пар $ \big\lbrace \lbrace a, d\rbrace, \lbrace b, e\rbrace, \lbrace c, f\rbrace \big \rbrace$ разрушает только $6$ до того нетронутых полных троек незнакомых (по две тройки каждая пара), остается две последние нетронутые тройки, их разрушает третья тройка пар $\big\lbrace \lbrace a, f\rbrace, \lbrace b, d\rbrace, \lbrace c, e\rbrace \big \rbrace$, то есть две из этих трех пар разрушают по одной из оставшихся троек, а третья пара, так сказать, только усугубляет разрушение четырех уже частично разрушенных троек незнакомых, при этом две тройки незнакомых (можно проследить, какие именно тройки) разрушаются полностью, и, таким образом, появляется две полные тройки знакомых.

Оба разбиения $G$ производятся в пропорции $6/9$, но есть вопрос: не может ли быть других разбиений в той же пропорции, но принципиально отличающихся по отношениям между элементами? Например, $A_1=\big\lbrace \lbrace a, d\rbrace,\lbrace a, e\rbrace, \lbrace d, e\rbrace\big \rbrace \cup \big\lbrace \lbrace b, c\rbrace, \lbrace b, f\rbrace, \lbrace c, f\rbrace \big \rbrace$ разбивается на две непересекающиеся тройки, а $A_2=\big\lbrace \lbrace a, c\rbrace,\lbrace a, e\rbrace, \lbrace b, c\rbrace, \lbrace b, f\rbrace, \lbrace d, e\rbrace, \lbrace d, f\rbrace \big \rbrace$ -- нет. Может быть, можно найти еще какие-то структуры для $A_1$ и $A_2$ и, соответственно, для $B_1$ и $B_2$?

(Я понимаю, что это еще не доказательство.)

[mihaild]

Vladimir Pliassov в сообщении #1579380 писал(а):

Тут возникает вопрос: почему каждая из пар $\lbrace a, d\rbrace$, $\lbrace c, f\rbrace$ и $\lbrace b, e\rbrace$ разрушает по четыре тройки? Я думаю, это потому что они не пересекаются.

Да, это легко видеть. Если мы взяли пару $x, y$ и потом $x, z$, то тройка $x, y, z$ уже разрушена первой парой, и соответственно вторая пара её не разрушит, а разрушит максимум три тройки.

Я не очень понимаю, что Вы тут хотите накопать, но очень советую вместо операций с символами попробовать порисовать на бумажке картинки (6 точек, некоторые из которых соединены) - это ИМХО гораздо более наглядная модель.

[Vladimir Pliassov]

mihaild в сообщении #1579667 писал(а):

очень советую вместо операций с символами попробовать порисовать на бумажке картинки (6 точек, некоторые из которых соединены) - это ИМХО гораздо более наглядная модель.

Я сейчас пытаюсь понять теорему Рамсея и, в связи с этим, читаю Ф. Харари "ТЕОРИЯ ГРАФОВ" (https://stugum.files.wordpress.com/2014 ... theory.pdf), там на стр. 28 - 30 на графах доказывается теорема о шестерых знакомых-незнакомых (наверное, Вы это имеете в виду?), я было обрадовался, думал, что это другое доказательство, чем здесь, но оно то же самое. Я подозреваю, что других доказательств просто нет (не считая перебора всех вариантов), но может быть, я ошибаюсь, и они есть?

mihaild в сообщении #1579667 писал(а):

Я не очень понимаю, что Вы тут хотите накопать

Я хотел найти другое доказательство, и не такое, когда перебираются все варианты, но на выбранном пути тоже столкнулся с многовариантностью.

Кажется, не сразу -- по-моему, есть что-то однозначное, а именно, критическая пропорция $9/6$ между парами знакомых и незнакомых: пока она не достигнута (начиная с $15/0$), видно, что либо там, либо там есть полная тройка. А когда она достигнута, начинается многовариантность:

1) когда шестерка пар разбивается на две полные тройки так, что эти тройки не пересекаются по составу элементов из $X$, например, если она разбивается на тройки пар $\big\lbrace \lbrace a, d\rbrace,\lbrace a, e\rbrace, \lbrace d, e\rbrace\big \rbrace$ и $\big\lbrace \lbrace b, c\rbrace, \lbrace b, f\rbrace, \lbrace c, f\rbrace \big \rbrace$, то доказывается легко;

2) когда шестерка пар, например, $\big\lbrace \lbrace a, c\rbrace,\lbrace a, e\rbrace, \lbrace b, c\rbrace, \lbrace b, f\rbrace, \lbrace d, e\rbrace, \lbrace d, f\rbrace \big \rbrace$, не разбивается на две полные тройки, то либо надо доказывать для каждого варианта такой шестерки, либо надо найти для таких шестерок общий принцип;

Да еще и шестерка пар может разбиваться на две полные тройки так, что эти тройки пересекаются по составу элементов из $X$, например, $\big\lbrace \lbrace a, d\rbrace,\lbrace a, e\rbrace, \lbrace d, e\rbrace\big \rbrace$ и $\big\lbrace \lbrace a, c\rbrace, \lbrace a, f\rbrace, \lbrace c, f\rbrace \big \rbrace$ -- тут тоже много вариантов.

Так что я пока прекращаю свои попытки (если не будет каких-то предложений) и иду дальше.

Кстати, в предыдущем посте я неправильно написал:

Vladimir Pliassov в сообщении #1579380 писал(а):

Например, $A_1=\big\lbrace \lbrace a, d\rbrace,\lbrace a, e\rbrace, \lbrace d, e\rbrace\big \rbrace \cup \big\lbrace \lbrace b, c\rbrace, \lbrace b, f\rbrace, \lbrace c, f\rbrace \big \rbrace$ разбивается на две непересекающиеся тройки, а $A_2=\big\lbrace \lbrace a, c\rbrace,\lbrace a, e\rbrace, \lbrace b, c\rbrace, \lbrace b, f\rbrace, \lbrace d, e\rbrace, \lbrace d, f\rbrace \big \rbrace$ -- нет.

Конечно же, и $A_1$, и $A_2$ разбивается на две непересекающиеся тройки пар (потому что и там, и там все пары разные), я имел в виду, что тройки пар $\big\lbrace \lbrace a, d\rbrace,\lbrace a, e\rbrace, \lbrace d, e\rbrace\big \rbrace$ и $\big\lbrace \lbrace b, c\rbrace, \lbrace b, f\rbrace, \lbrace c, f\rbrace \big \rbrace$ не пересекаются по составу элементов из $X$, а из $A_2=\big\lbrace \lbrace a, c\rbrace,\lbrace a, e\rbrace, \lbrace b, c\rbrace, \lbrace b, f\rbrace, \lbrace d, e\rbrace, \lbrace d, f\rbrace \big \rbrace$ невозможно выбрать две такие тройки пар, чтобы они не пересекались по составу элементов из $X$ (и поэтому $A_2$ не разбивается на две полные тройки).

[mihaild]

Vladimir Pliassov в сообщении #1579769 писал(а):

Я подозреваю, что других доказательств просто нет (не считая перебора всех вариантов), но может быть, я ошибаюсь, и они есть?

Я ничего про другие доказательства не знаю. Наверное можно придумать какие-то методы для сокращения перебора вариантов, но это не особо интересно. Для данного конкретного случая доказательство слишком уж простое получается, чтобы как-то улучшать. А общей теории нет, все известные числа Рамсея получались с большим трудом.