Как в задачу привлечь числа Рамсея?

s4d3v2g

На плоскости расположены n точек, являющихся вершинами правильного n-угольника,
вершины попарно соединены отрезком, покрашенным либо в красный либо в голубой цвет.
Понятно, что будут образовываться монохромные треугольники из этих отрезков.
Вопрос: как оценить количество монохромных треугольников сверху в зависимости от n?
Вроде как задача на теорию Рамсея, но никак не могу понять, как тут затесать числа Рамсея...

Sanych

В смысле сверху? Максимальное число - когда все треугольники монохромные.
А числа Рамсея вроде бы, не совсем об этом. Они говорят только, при каком n может быть 0 треугольников, а при каком - уже обязательно появится одноцветный полный подграф.
Так что это около чисел Рамсея, но не совсем они. Впрочем - скажем, взяв максимальные k точек, среди которых нет монохромных треугольников, можно добавлением ещё одной вершины получать монохромные треугольники с основанием в этих k точках и с вершиной в каждой из оставшихся. При этом k не больше, чем 5, из-за соответствующего число Рамсея. Последовательное применение такой конструкции даёт может быть довольно грубую оценку снизу [n/5]*(n-5)/2 ~ (n^2)/10.

s4d3v2g

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

Sanych

Ещё одна оценка. Пусть мы знаем, что среди 20 треугольников в полном графе из 6 вершин есть хотя бы t монохромных треугольников. Тогда сложив эти неравенства по всем полным подграфам из 6 вершин, мы получим, что во всём графе доля монохромных треугольников тоже не меньше, чем t/20. Аналогичные рассуждения показывают, что минимальная возможная доля монохромных треугольников среди всех треугольников - монотонно неубывающая функция числа вершин. Из чисел Рамсея ясно, что f(6)>=1/20, на самом деле f(6)=1/10, и это даёт оценку для n>=6 - а именно, число монохромных треугольников не меньше, чем n*(n-1)*(n-2)/60
PS. И ещё, кстати, если вспомнить теорию случайных графов, то получается f(x)<1/4, потому что каждый треугольник монохромен в 1/4 от всех возможных раскрасок, и значит средняя доля 1/4, а минимальная естественно меньше.

s4d3v2g

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

igor196505

Фига ты ботан ... Курсач што-ли?
Оставить комментарий
Имя или ник:
Комментарий: