2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Ограничение на одноцветные решения
Сообщение12.01.2008, 08:46 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Придумать функцию $n(k)$ такую, что при любой раскраске натурального ряда в $k$ цветов уравнение $x+y=z$ имеет одноцветное решение, для которого $x,y,z \leqslant n(k)$ (в этой задаче считается, что натуральный ряд начинается с единицы).

P. S. Я знаю, как доказать существование такой функции, однако это доказательство неконструктивно и ничего не даёт в плане построения $n(k)$ в явном виде.

 Профиль  
                  
 
 
Сообщение12.01.2008, 13:25 
Модератор
Аватара пользователя


11/01/06
5710
Минимальное такое n(k) называется числом Шура: http://mathworld.wolfram.com/SchurNumber.html

Добавлено спустя 11 минут 31 секунду:

вот тут когда-то похожие задачи обсуждали: http://www.nsu.ru/phorum/read.php?f=29&t=2564&a=1

 Профиль  
                  
 
 
Сообщение12.01.2008, 15:20 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
maxal писал(а):
вот тут когда-то похожие задачи обсуждали: http://www.nsu.ru/phorum/read.php?f=29&t=2564&a=1


Да, действительно... Я уже забыл то обсуждение. Память девичья :(

Походил по указанным ссылкам, странная какая-то вещь вырисовывается. Если $S(k)$ --- число Шура (наименьшее из всех возможных $n(k)$), то

\[
\frac{3^k-1}{2} \leqslant S(k) < R(3,k) \leqslant c\frac{k^2}{\ln k}
\]

для некоторой константы $c$ и всех $k \in \mathbb{N}$. Как такое возможно?

 Профиль  
                  
 
 
Сообщение12.01.2008, 15:45 
Модератор
Аватара пользователя


11/01/06
5710
MathWorld не на те числа Рамсея ссылку дает. Нужные там только всколзь упоминаются как "обобщенные числа Рамсея". Если переводить "R(3,k)" на язык MathWorld, то это R(3,3,...,3;2), где количество троек равно k.
Или вот в этой статье они называются k-color Ramsey numbers.
Вот они же в OEIS: A003323

 Профиль  
                  
 
 
Сообщение12.01.2008, 18:11 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Цитата:
A generalized Ramsey number is written

\[
R(m_1, \ldots, m_k;n)
\]

and is the smallest integer $r$ such that, no matter how each $n$-element subset of an $r$-element set is colored with $k$ colors, there exists an $i$ such that there is a subset of size $m_i$, all of whose $n$-element subsets are color $i$.


Ну да, понятно. Существование таких чисел должно следовать из теоремы Рамсея: если для бесконечного множества $I$ множество всех его $n$-элементных подмножеств $I^{[n]}$ поделено на конечное число частей, то найдётся бесконечное $J \subseteq I$, для которого все элементы $J^{[n]}$ принадлежат одной и той же части. Знаком также с доказательством этой теоремы (через ультрафильтры). Но доказательство это неконструктивно и не даёт никакой верхней оценки для обобщённых чисел Рамсея.

Так что вопрос всё равно остаётся: получить верхнюю оценку для чисел Шура в виде какой-нибудь "хорошей функции" (например, выражающейся через степени, сложение и умножение).

 Профиль  
                  
 
 
Сообщение13.01.2008, 01:05 
Модератор
Аватара пользователя


11/01/06
5710
В статье Upper bounds for ramsey numbers R(3, 3, ...,3) and Schur numbers доказывается, что

$$R(3,\dots,3)\leq \frac{e-e^{-1}+3}{2}n!+1$$ для всех $n\geq 4$, что также дает оценку для $S(n)$.

Там же в случае чётного $n$ дана чуть более лучшая оценка для чисел Шура:

$$S(n) \leq \frac{e-e^{-1}+3}{2}n!-n+2$$ для всех чётных $n\geq 6$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group