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

задан 18 Июн '19 14:55

@falcao, @navacho, а правильно ли я понимаю, что кликовое число устроено следующим образом: вот у нас максимальное число ребер, такое что кликовое число <=3 и далее мы добавляем одно ребро и у нас от этого кликовое число увеличится РОВНО на единицу, т.е. станет равным 4? Или кликовое число может прыгнуть, например, на 2 и стать равным 5?

Если оно увеличивается ровно на 1, то тогда по теореме Турана: рассмотрим три доли мощности 4, 3, 3. Тогда число ребер в таком полном трехдольном графе равно 4 * (3+3) + 3 * 3 = 33. И мы добавляем еще одно ребро и получаем 34.

(18 Июн '19 15:11) worker
1

@worker: первый абзац я не понимаю, к сожалению. Но конструкция именно такая: разбиваем 10 на три примерно одинаковые части, соединяем рёбрами точки из разных частей. Рёбер 33, подграфа K4 нет, так как из 4 точек две попадут в одну часть по принципу Дирихле, а там соединений нет. Если рёбер больше, то их не меньше 34, а это число строго больше оценки из теоремы: (1-1/r)n^2/2=100/3, где n=10, r=3. Формула простая и удобная, её нетрудно запомнить.

(18 Июн '19 15:41) falcao

@falcao, спасибо!

(18 Июн '19 15:47) worker
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×624

задан
18 Июн '19 14:55

показан
333 раза

обновлен
18 Июн '19 15:47

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru