Теорема Рамсея

[mihaild]

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

Так что при $r=1$ имеем $R(1, t)=t$, то есть $R(1, t)\ne1$.

Нельзя писать "при $r = 1$ что-то там с $R(x, y)$". Потому что $R(x, y)$ не зависит от $r$.
$R(x, y)$ (из википедии, у Холла её вроде бы вообще нет) - это конкретная функция, $R(x, y) = n(x, y, 2)$. Это определение $R$, отношение $r = 1$ там пихать некуда. И никакого "подразумеваемого $r$" там тоже нет.
(единственный важный момент: в определении $n(p, q, r)$ Холл зачем-то требует $p, q \geq r$, хотя определение прекрасно работает и без этого требования, просто тривиально получается $n = 1$)

Вам достаточно для выражения своих сомнений нотации Холла, или нужно что-то еще? У Холла $R$ вообще нет.

[Vladimir Pliassov]

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

$R(x, y)$ ... - это конкретная функция, $R(x, y) = n(x, y, 2)$. Это определение $R$

Теперь понятно, значит, числа Рамсея берутся только для $r=2$. Это странно, почему бы не брать их для любых $r$ (для любых гиперграфов)?

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

в определении $n(p, q, r)$ Холл зачем-то требует $p, q \geq r$, хотя определение прекрасно работает и без этого требования, просто тривиально получается $n = 1$

Не могли бы Вы показать, как оно получается? По-моему, оно не может получаться.

Цитата:

Теоретико-множественная формулировка

Частный случай $N(p, q, r)$

Пусть $p$, $q$ и $r$ — натуральные числа, причём $p,\;q\geqslant r$.

Тогда существует число $N=N(p,\;q,\;r)$, обладающее следующим свойством: если все $r$-элементные подмножества $N$-элементного множества $S$ произвольным образом разбиты на два непересекающихся семейства $\alpha$ и $\beta$, то либо существует $p$-элементное подмножество множества $S$, все $r$-элементные подмножества которого содержатся в $\alpha$, либо существует $q$-элементное подмножество (множества $S$), все $r$-элементные подмножества которого содержатся в $\beta$. (Текст из Википедии, чуть измененный.)

Исключим из этой формулировки условие $p,\;q\geqslant r$.

Возьмем $R(p, q) = n(p, q, r)$ при $p=1$, $q>1$ ($q$ может быть произвольным) и $r=2$, то есть $R(1, q) = n(1, q, 2)$.

Пусть $R(1, q) = n(1, q, 2)=1$,

тогда $N=\vert S\vert=1$. Как же мы можем взять "все $r$-элементные подмножества $N$-элементного множества $S$" ($2$-элементные подмножества $1$-элементного множества) и произвольным образом разбить их на два непересекающихся семейства $\alpha$ и $\beta$? Я думаю, никак, поэтому $\alpha$ и $\beta$ не существуют.

Но даже если бы $\alpha$ и $\beta$ существовали, не существует ни $p$-элементного подмножества множества $S$, все $r$-элементные подмножества которого мы гипотетически могли бы поместить в $\alpha$ или в $\beta$, потому что не существует $r$-элементных подмножеств $p$-элементного множества ($2$-элементных подмножеств $1$-элементного множества),

ни $q$-элементного подмножества множества $S$, все $r$-элементные подмножества которого мы гипотетически могли бы поместить в $\beta$ или в $\alpha$, потому что не существует $q$-элементное подмножество множества $S$ (так как $q>1$, а $\vert S\vert=1$).

Так что имеем противоречие с допущением $R(1, q) = n(1, q, 2)=1$.

Если, конечно, я не ошибаюсь.

[mihaild]

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

Теперь понятно, значит, числа Рамсея берутся только для $r=2$. Это странно, почему бы не брать их для любых $r$ (для любых гиперграфов)?

Да ни почему, берутся и для гиперграфов. Просто обозначаются иначе.
Ну и некоторые авторы вполне могут гиперграфы и не рассматривать, если считают по какой-то причине разумным ограничиться графами.

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

Не могли бы Вы показать, как оно получается? По-моему, оно не может получаться.

И правда, я наврал. Правильно так: если $\min(p, q) < r$, то $n(p, q, r) = \min(p, q)$. Для случая $r = 2$, $\min(p, q) = 1$ получается как я написал изначально.

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

Как же мы можем взять "все $r$-элементные подмножества $N$-элементного множества $S$" ($2$-элементные подмножества $1$-элементного множества)

Как обычно. Получится, что множество двухэлементных подмножеств пусто, но почему это должно нам помешать?

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

и произвольным образом разбить их на два непересекающихся семейства $\alpha$ и $\beta$?

Пустое множество можно разбить на два непересекающихся множества. Правда единственным образом.

[Vladimir Pliassov]

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

если $\min(p, q) < r$, то $n(p, q, r) = \min(p, q)$. Для случая $r = 2$, $\min(p, q) = 1$ получается как я написал изначально.

Искал, как Вы написали изначально, нашел только, что $n=1$.

У Холла $n(p, r, r) =p$ и $n(r, q, r) =q$. Как из этого следует, что если $\min(p, q) < r$, то $n(p, q, r) = \min(p, q)$? Или это следует из чего-то другого?

Либо $p$, либо $q$ должно быть произвольное. Пусть $r=2$, $p=1$. Имеем $n(1, q, 2)$. Почему оно равно $1$?

[mihaild]

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

Как из этого следует, что если $\min(p, q) < r$, то $n(p, q, r) = \min(p, q)$? Или это следует из чего-то другого?

Да. Заметьте, что если $p < r$, то для любого $p$-элементного множества все его $r$-элементные подмножества принадлежат $\alpha$ (и даже неважно, что такое $\alpha$).

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

Почему оно равно $1$?

Потому что:
1. Я могу привести пример $0$-элементного множества $X$ и разбиения всех его $2$-элементных подмножеств на два семейства так, что Вы не сможете найти никакое одноэлементное подмножество $X$, такое что все его двухэлементные подмножества принадлежат одному из этих семейств. Так что $n(1, q, 2) > 0$.
2. С другой стороны, если Вы принесете мне одноэлементное множество $X$ и любое разбиение его $2$-элементных подмножеств на два семейства, то я смогу найти одноэлементное подмножество $X$, все двухэлементные подмножества которого принадлежат одному из этих семейств. Так что $n(1, q, 2) \leq 1$.

[Vladimir Pliassov]

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

Заметьте, что если $p < r$, то для любого $p$-элементного множества все его $r$-элементные подмножества принадлежат $\alpha$ (и даже неважно, что такое $\alpha$).

Думаю, понял! Все $r$-элементные подмножества $p$-элементного множества составляют пустое множество, а оно является подмножеством любого множества. Теперь необходимо понять, как

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

Пустое множество можно разбить на два непересекающихся множества. Правда единственным образом.

Почему единственным образом? Посмотрел, что такое разбиение множества, тут такое определение:

Цитата:

Разбиение множества — это представление его в виде объединения произвольного количества попарно непересекающихся непустых подмножеств. Википедия.

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

Цитата:

Из аксиомы объёмности следует, что есть только одно множество, обладающее таким свойством.

(не содержать ни одного элемента), можно взять сколько угодно его копий? Во всяком случае, существуют объединение, пересечение, симметрическая разность пустых множеств -- в каждом из этих случаев имеется по крайней мере два пустых множества.

Пустое множество является подмножеством пустого множества, но у него ведь только одно подмножество, как же его разбивать: на само пустое множество и его пустое подмножество? А как же оно потом без своего пустого подмножества?

Вообще, если исключить из множества его пустое подмножество, в нем, что, не останется больше пустого подмножества?

Детские вопросы, но должен их задать.

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

1. Я могу привести пример $0$-элементного множества $X$ и разбиения всех его $2$-элементных подмножеств на два семейства так, что Вы не сможете найти никакое одноэлементное подмножество $X$, такое что все его двухэлементные подмножества принадлежат одному из этих семейств. Так что $n(1, q, 2) > 0$.

Буду очень признателен, если Вы его приведете.

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

2. С другой стороны, если Вы принесете мне одноэлементное множество $X$ и любое разбиение его $2$-элементных подмножеств на два семейства, то я смогу найти одноэлементное подмножество $X$, все двухэлементные подмножества которого принадлежат одному из этих семейств. Так что $n(1, q, 2) \leq 1$.

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

А на три семейства его уже нельзя разбить? Или можно? (Может быть, его можно разбить единственным образом, но на много семейств?)

[mihaild]

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

Посмотрел, что такое разбиение множества, тут такое определение

Вот тут конфликт определений.
То, что приведено в Википедии, имеет право на существование. Но у Холла другое. А именно, пара $\alpha, \beta$ называется разбиением множества $X$, если $\alpha \cup \beta = X$, $\alpha \cap \beta = \varnothing$ (не знаю, прописано ли у него это где-то явно, но "разбиение на два непересекающихся множества" всегда означает именно это, и Холл явно разрешает элементам разбиения быть пустыми).

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

почему нельзя объединить сколько угодно пустых множеств?

Потому что я, вслед за Холлом, говорю о разбиении ровно на два множества.

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

Пустое множество является подмножеством пустого множества, но у него ведь только одно подмножество, как же его разбивать: на само пустое множество и его пустое подмножество? А как же оно потом без своего пустого подмножества?

Подмножества тут вообще не при чем. Берем $\alpha = \beta = \varnothing$, и получаем, что пара $\alpha, \beta$ - разбиение пустого множества.

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

Вообще, если исключить из множества его пустое подмножество, в нем, что, не останется больше пустого подмножества?

Почему не останется, останется.

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

Буду очень признателен, если Вы его приведете

Ну а Вы попробуйте сами догадаться. Начните с какого-нибудь $0$-элементного множества (их не очень много различных), выпишите все его $2$-элементные подмножества, возьмите какое-нибудь разбиение этих подмножеств на два непустых.

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

А на три семейства его уже нельзя разбить? Или можно? (Может быть, его можно разбить единственным образом, но на много семейств?)

Его можно разбить на любое количество семейств, конечно. На любое конкретное количество - единственным образом.

[Vladimir Pliassov]

1.

Давайте разберемся с предложением "существует $p$-элементное подмножество множества $S$, все $r$-элементные подмножества которого содержатся в $\alpha$".

Пусть $r>p$, тогда не существует ни одного $r$-элементного подмножества $p$-элементного множества, и поэтому ни одно из них не содержится ни в каком $\alpha$.Тем не менее, существует множество этих подмножеств -- пустое множество этих подмножеств, -- и оно содержится в любом $\alpha$.

Я хочу сказать, что при $r>p$ выражение "все $r$-элементные подмножества $p$-элементного множества содержатся в $\alpha$" можно считать вольностью речи, если под этим выражением понимать: "(пустое) множество всех $r$-элементных подмножеств $p$-элементного множества содержится в $\alpha$".

Теперь пусть $p>N=\vert S\vert$, тогда уже хуже: мы не можем сказать, что "существует $p$-элементное подмножество $N$-элементного множества $S$", потому что оно не существует.

Как быть с этим?

Можно, конечно, сказать, что существует множество (имея в виду, что оно пустое) $p$-элементных подмножеств $N$-элементного множества $S$, но тогда надо переделать формулировку, либо согласиться, что выражение "существует $p$-элементное подмножество $N$-элементного множества $S$" в определенных обстоятельствах представляет собой вольность речи, под которой следует понимать: "существует (пустое) множество $p$-элементных подмножеств $N$-элементного множества $S$".

2.

Еще один момент.

Цитата:

Теоретико-множественная формулировка

Частный случай $N(p, q, r)$

Пусть $p$, $q$ и $r$ — натуральные числа, причём $p,\;q\geqslant r$.

Тогда существует число $N=N(p,\;q,\;r)$, обладающее следующим свойством: если все $r$-элементные подмножества $N$-элементного множества $S$ произвольным образом разбиты на два непересекающихся семейства $\alpha$ и $\beta$, то либо существует $p$-элементное подмножество множества $S$, все $r$-элементные подмножества которого содержатся в $\alpha$, либо существует $q$-элементное подмножество (множества $S$), все $r$-элементные подмножества которого содержатся в $\beta$. (Текст из Википедии, чуть измененный.)

Если в этой формулировке -- для себя -- добавить одно слово: не "Тогда существует число $N=N(p,\;q,\;r)$, обладающее следующим свойством ...", -- а "... минимальное число $N=N(p,\;q,\;r)$, обладающее следующим свойством ..." -- то $N$ не сможет быть насколько угодно большим, и работать будет проще, то есть доказать сначала все для минимального $N$, а потом уже ясно, что если $N$ взять больше, то теорема тем более справедлива.

Также и у Холла читаем:

Цитата:

Тогда существует такое минимальное число $n(p,\;q,\;r)$ ... что если $N\geqslant n(p,\;q,\;r)$, то ...

Я думаю, что если доказывать сначала не для $N\geqslant n(p,\;q,\;r)$, а для $N=n(p,\;q,\;r)$, то это легче (хотя я все еще не освоил его доказательства).

Кстати, не разобравшись с минимальностью $N$ в первой формулировке, я в одном из предыдущих постов написал:

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

Пусть $R(1, q) = n(1, q, 2)=1$, тогда $N=\vert S\vert=1$.

Но это не обязательно так, если $N$ не минимальное.

[mihaild]

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

содержится в любом $\alpha$

Тут стоит избегать выражения "$x$ содержится в множестве $y$", потому что это высказывание можно понимать двояко: как $x \subset y$ и как $x \in y$ (содержится как подмножество и как элемент соответственно).

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

Я хочу сказать, что при $r>p$ выражение "все $r$-элементные подмножества $p$-элементного множества содержатся в $\alpha$" можно считать вольностью речи, если под этим выражением понимать: "(пустое) множество всех $r$-элементных подмножеств $p$-элементного множества содержится в $\alpha$".

Это не вольность речи, это прямое следствие определений. Ничего другого под этим выражением понимать нельзя.

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

Теперь пусть $p>N=\vert S\vert$, тогда уже хуже: мы не можем сказать, что "существует $p$-элементное подмножество $N$-элементного множества $S$", потому что оно не существует.
Как быть с этим?

А зачем с этим как-то быть? Да, не существует.
Поэтому, например, $n(2, 2, 5) = 2$, а не $1$ - нам нужно, чтобы нашлось двухэлементное подмножество с каким-то свойством (что всего его пятиэлементные подмножества лежат в $\alpha$ либо $\beta$).

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

Если в этой формулировке -- для себя -- добавить одно слово: не "Тогда существует число $N=N(p,\;q,\;r)$, обладающее следующим свойством ...", -- а "... минимальное число $N=N(p,\;q,\;r)$, обладающее следующим свойством ..."

Эти варианты тривиально эквивалентны: т.к. любое непустое множество натуральных чисел содержит минимальный элемент, то, если число с нужным свойством вообще есть, то есть и минимальное число с нужным свойством.
Хотя формулировка в википедии и правда не очень хорошая, т.к. она не определяет функцию $N(p, q, r)$. В целом, я бы Вам посоветовал отложить википедию, пока не разберетесь с текстом Холла.

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

Я думаю, что если доказывать сначала не для $N\geqslant n(p,\;q,\;r)$, а для $N=n(p,\;q,\;r)$, то это легче

Это опять же тривиально: если верно для $N = n(p, q, r)$ то для $N > n(p, q, r)$ возьмем первое попавшееся $n(p, q, r)$-элементное подмножество, найдем в нём нужное подмножество, оно и будет ответом.

[Vladimir Pliassov]

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

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

содержится в любом $\alpha$

Тут стоит избегать выражения "$x$ содержится в множестве $y$", потому что это высказывание можно понимать двояко: как $x \subset y$ и как $x \in y$ (содержится как подмножество и как элемент соответственно).

Понял: элемент содержится в множестве, а подмножество содержится в множестве и входит в множество -- однако это когда оно содержится в множестве в качестве его подмножества, если же $\alpha$ это множество $r$-элементных подмножеств, то каждое $r$-элементное подмножество это элемент $\alpha$, и потому оно не "входит" в него, а "содержится" в нем.

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

Это не вольность речи, это прямое следствие определений. Ничего другого под этим выражением понимать нельзя.

Не могли бы Вы сказать, каких именно определений? Потому что я здесь мало что знаю, и просто не понимаю, о чем идет речь.

Я написал :

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

Пусть $r>p$, тогда не существует ни одного $r$-элементного подмножества $p$-элементного множества,

Уверен, что с этим Вы согласны.

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

и поэтому ни одно из них не содержится ни в каком $\alpha$

ни в качестве элемента, ни в качестве подмножества.

То есть нет такого множества $\alpha$, в котором содержались бы несуществующие элементы или несуществующие подмножества.

Согласны ли Вы с этим?

При этом я считаю, что существует пустое множество вещей, которые не существуют (или вообще существуют, но отсутствуют в рассматриваемом построении): дальше я написал (с исправлением "входит" вместо "содержится"):

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

Тем не менее, существует множество этих подмножеств -- пустое множество этих подмножеств, -- и оно входит в любое $\alpha$.

Кроме того, оно может содержаться в некотором множестве в качестве элемента -- потому что оно существует.

Но сами $r$-элементные подмножества $p$-элементного множества при $r>p$ не могут содержаться ни в каком множестве в качестве элементов, потому что они не существуют.

Дальше я написал:

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

при $r>p$ выражение "все $r$-элементные подмножества $p$-элементного множества содержатся в $\alpha$" можно считать вольностью речи, если под этим выражением понимать: "(пустое) множество всех $r$-элементных подмножеств $p$-элементного множества содержится в $\alpha$".

Здесь под "содержится в $\alpha$" я имел в виду "входит в $\alpha$" (в качестве подмножества множества $\alpha$), и это так и есть, но тут я не разобрался: то, что пустое множество всех $r$-элементных подмножеств входит в $\alpha$ не значит, что в $\alpha$ содержится в качестве элемента хоть одно $r$-элементное подмножество.

(Пустое множество всех $r$-элементных подмножеств является подмножеством $\alpha$, но не может быть элементном $\alpha$, так как $\alpha$ это множество $r$-элементных подмножеств, а пустое множество всех $r$-элементных подмножеств не является $r$-элементным подмножеством.)

Так что при $r>p$ выражение "все $r$-элементные подмножества $p$-элементного множества содержатся в $\alpha$" нельзя оправдать даже тем, что это вольность речи. Это просто неверное выражение: при $r>p$ не существует $r$-элементных подмножеств $p$-элементного множества, которые содержатся в $\alpha$

(просто потому, что при $r>p$ не существует $r$-элементных подмножеств $p$-элементного множества).

[mihaild]

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

Не могли бы Вы сказать, каких именно определений?

Самых стандартных.

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

все $r$-элементные подмножества $p$-элементного множества содержатся в $\alpha$

Означает
1. Взяли $X$ - $p$-элементое множество.
2. Взяли $\mathcal P(X)$ - множество всех подмножеств $X$.
3. Взяли $Y$ - множество элементов $\mathcal P(x)$, состоящих ровно из. $r$ элементов. Оно пусто.
4. И теперь оказывается, что любой элемент $Y$ является одновременно элементом $\alpha$.

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

То есть нет такого множества $\alpha$, в котором содержались бы несуществующие элементы или несуществующие подмножества.

Так от нас не требуется, чтобы в $\alpha$ содержались несуществующие элементы. От нас требуется, чтобы любой несуществующий элемент содержался в $\alpha$. Т.е. если нам принесут несуществующее множество, то мы сможем показать, где оно в $\alpha$. И мы действительно можем это пообещать и спать со спокойной душой, потому что поймать нас за руку - принести несуществующее множество - всё равно никто не сможет.
(это не слишком хорошее рассуждение, и вообще о "несуществующих элементах" лучше не говорить, но, возможно, так будет понятнее)

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

при $r>p$ не существует $r$-элементных подмножеств $p$-элементного множества, которые содержатся в $\alpha$

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

просто потому, что при $r>p$ не существует $r$-элементных подмножеств $p$-элементного множества

Одно другому не мешает. $r$-элементных подмножеств не существует, и именно поэтому любое $r$-элементное подмножество является элементом $\alpha$.

[Vladimir Pliassov]

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

1. Взяли $X$ - $p$-элементное множество.
2. Взяли $\mathcal P(X)$ - множество всех подмножеств $X$.
3. Взяли $Y$ - множество элементов $\mathcal P(x)$, состоящих ровно из. $r$ элементов. Оно пусто.
4. И теперь оказывается, что любой элемент $Y$ является одновременно элементом $\alpha$.

Наверное, в п. 3 должно быть $\mathcal P(X)$.

$Y$ это пустое множество $r$-элементных множеств. Поскольку $Y\subset \alpha$, все элементы $Y$ являются элементами $\alpha$.

Ура! Найдено юридическое обоснование, по которому $r$-элементные множества принадлежат $\alpha$, -- через пустое множество. Но если бы не пустое множество, то я не вижу, как бы можно было обосновать.

[mihaild]

Да всё так же. "Если $x$ - $r$-элементный элемент $\mathcal P(X)$, то $x \in \alpha$". Т.к. посылка ложна для любого $x$, то вся импликация истинна для любого $x$.

[Vladimir Pliassov]

В общем как будто разобрался с доказательством теоремы Рамсея у Холла (http://mathscinet.ru/files/HallM.pdf стр.79 - 81).

Поставил на листке бумаги $11$ точек и произвольно соединил каждую с каждой частью сплошными, частью пунктирными линиями. На произвольную точку $a_0$ кладу гайку поменьше ($4$ мм), а потом кладу гайки покрупнее ($6$ мм) (чтобы видно было, где $a_0$, а где остальные точки) на точки, соединяющиеся с $a_0$ сплошными (либо пунктирными) линиями, то есть сплошными (либо пунктирными) ребрами получившегося полного, так сказать, двухцветного графа. Можно, конечно, класть пуговицы или монеты, желательно не слишком крупные. Затем прохожу доказательство по книге и все вижу на своем девайсе. Когда надо, кладу гайки на другие точки, это гораздо удобнее, чем отмечать их, рисуя на бумаге (не нужно стирать метки, когда меняешь точки).

Почему $11$ точек? Это чтобы рассмотреть все на конкретном примере, но не на $n(3, 3, 2)$ -- чтобы не было $p=q$. Я взял $n(4, 3, 2)$. Из известных примеров можно, конечно, взять $n(3, 5, 2)$ или $n(4, 5, 2)$, но там больше точек -- тогда желательно листок побольше, а зачем? $11$ точек хватает.

У Холла написано:

Цитата:

Пусть $S$ -- множество из $N\geqslant n(p_1, q_1, r-1)+1$ элементов

где $p_1=n(p-1, q, r)$, $q_1=n(p, q-1, r)$.

Доказывается, что $n(p, q, r)\leqslant n(p_1, q_1, r-1)+1$. При $p=4, q=3, r=2$ будет $n(p, q, r)=n(4, 3, 2)=9$,

$p_1=n(3, 3, 2)=6$, $q_1=n(4, 2, 2)=4$, так что $n(p_1, q_1, r-1)+1=n(6, 4, 1)+1=9+1=10$. Но поскольку $N\geqslant n(p_1, q_1, r-1)+1$, то есть $N\geqslant 10$, взять уж $11$ точек.

Это, разумеется, для случая $r=2$, но сначала пройти доказательство так (мне это очень помогло), а потом снова -- уже для $r>2$.