Число Турана - Turán number

В математике Число Турана Т (п,k,р) за р-униформа гиперграфы порядка п наименьшее количество р-ребра такие, что каждый индуцированный подграф на k vertices содержит ребро. Это число было определено для р = 2 по Туран (1941), и проблема для общего р был представлен в Туран (1961). Бумага (Сидоренко 1995 г. ) дает обзор чисел Турана.

Определения

Исправить набор Икс из п вершины. Для данного р, р-край или же блокировать это набор р вершины. Набор блоков называется Туран (п,k,р) система (п ≥ k ≥ р) если каждые k-элементное подмножество Икс содержит блок. Число Турана Т (п,k,р) - минимальный размер такой системы.

Пример

Дополнения строк Самолет Фано образуют (7,5,4) -систему Турана. Т (7,5,4) = 7.[1]

Связь с другими комбинаторными планами

Можно показать, что

Равенство имеет место тогда и только тогда, когда существует Система Штейнера S (п - k, п - р, п).[2]

An (п,р,k,р) -лотто дизайн является (п, k, р) -Турановая система. Таким образом, T (п,k, р) = L (п,р,k,р).[3]

Смотрите также

Рекомендации

  1. ^ Колборн и Диниц 2007, стр. 649, Пример 61.3
  2. ^ Колборн и Диниц 2007, стр. 649, замечание 61.4
  3. ^ Колборн и Диниц 2007, стр. 513, Предложение 32.12

Библиография

  • Колборн, Чарльз Дж .; Диниц, Джеффри Х. (2007), Справочник по комбинаторным схемам (2-е изд.), Бока-Ратон: Chapman & Hall / CRC, ISBN  1-58488-506-8
  • Годбол, А.П. (2001) [1994], «Число Турана», Энциклопедия математики, EMS Press
  • Сидоренко, А. (1995), "Что мы знаем и чего не знаем о числах Турана", Графы и комбинаторика, 11 (2): 179–199, Дои:10.1007 / BF01929486
  • Туран, П. (1941), "Egy gráfelméleti szélsőértékfeladatról (Венгерский. Экстремальная задача в теории графов.)", Мат. Физ. Лапок (на венгерском), 48: 436–452
  • Туран, П. (1961), "Проблемы исследования", Мадьяр Туд. Акад. Мат. Kutato Int. Közl., 6: 417–423