Проблема Заранкевича - Википедия - Zarankiewicz problem

В Проблема заранкевича, нерешенная задача в математике, требует максимально возможного числа ребер в двудольный граф который имеет заданное количество вершин, но не имеет полный двудольный подграфы заданного размера.[1] Это относится к области экстремальная теория графов, филиал комбинаторика, и назван в честь польского математика Казимеж Заранкевич, который в 1951 г. предложил несколько частных случаев проблемы.[2]

В Теорема Кевари – Соша – Турана, названный в честь Тамаша Кевари, Вера Т. Сос, и Пал Туран, обеспечивает верхняя граница о решении проблемы Заранкевича. Когда запрещенный полный двудольный подграф имеет одну сторону не более чем с тремя вершинами, эта граница оказалась в пределах постоянного множителя правильного ответа. Для больших запрещенных подграфов она остается наиболее известной и считается точной. Применения теоремы Кевари – Соша – Турана включают ограничение числа инцидентов между различными типами геометрических объектов в дискретная геометрия.

Постановка задачи

А двудольный граф грамм = (UVE) состоит из двух непересекающихся наборов вершины U и V, и набор края каждый из которых соединяет вершину в U к вершине в V. Никакие два ребра не могут соединять одну и ту же пару вершин одновременно. А полный двудольный граф является двудольным графом, в котором каждая пара вершин из U и вершина из V связаны друг с другом. Полный двудольный граф, в котором U имеет s вершины и V имеет т вершины обозначены Ks,т. Если грамм = (UVE) является двудольным графом, и существует множество s вершины U и т вершины V которые все связаны друг с другом, то эти вершины побудить подграф формы Ks,т. (В этой формулировке порядок s и т имеет значение: набор s вершины должны быть из U и набор т вершины должны быть из V, а не наоборот.)

В Функция Заранкевича z(мпsт) обозначает максимально возможное количество ребер в двудольном графе грамм = (UVE), для которых |U| = м и |V| = п, но не содержащий подграфа вида Ks,т. Как сокращение для важного особого случая, z(пт) такой же как z(пптт). Задача Zarankiewicz требует формулы для функции Zarankiewicz или (если это невозможно) для точной асимптотические оценки по темпам роста z(пт) при условии, что т - фиксированная константа в пределе п уходит в бесконечность.

За s = t = 2 эта проблема такая же, как и определение клетки с обхватом шесть. Проблема Заранкевича, клетки и конечная геометрия сильно взаимосвязаны.[3]

Эту же проблему можно сформулировать в терминах цифровая геометрия. Возможные ребра двудольного графа грамм = (UVE) можно представить себе как точки |U| × |V| прямоугольник в целочисленная решетка, а полный подграф - это набор строк и столбцов в этом прямоугольнике, в котором присутствуют все точки. Таким образом, z(мпsт) обозначает максимальное количество точек, которые могут быть помещены в м × п сетка таким образом, чтобы никакое подмножество строк и столбцов не составляло полного s × т сетка.[4] Альтернативное и эквивалентное определение: z(мпsт) - наименьшее целое число k так что каждый (0,1) -матрица размера м × п с k +1 должен иметь набор s ряды и т столбцы такие, что соответствующие s×т подматрица является состоит только из единиц.

Примеры

Двудольный граф с 4 вершинами на каждой стороне, 13 ребрами и без K3,3 подграф и эквивалентный набор из 13 точек в сетке 4 × 4, показывающий, что z(4; 3) ≥ 13.

Номер z(п, 2) запрашивает максимальное количество ребер в двудольном графе с п вершин на каждой стороне, не имеющей 4-цикла (его обхват шесть и более). Таким образом, z(2, 2) = 3 (достигается трехреберным путем), и z(3, 2) = 6 (a шестиугольник ).

В своей первоначальной формулировке проблемы Заранкевич запросил значения z(п; 3) для п = 4, 5 и 6. Вскоре ответы были предоставлены Вацлав Серпинский: z(4; 3) = 13, z(5; 3) = 20 и z(6; 3) = 26.[4] Случай z(4; 3) относительно прост: двудольный граф с 13 ребрами с четырьмя вершинами по обе стороны от двудольного графа, и нет K3,3 подграф, может быть получен добавлением одной из длинных диагоналей к графику куб. С другой стороны, если двудольный граф с 14 ребрами имеет четыре вершины на каждой стороне, то две вершины на каждой стороне должны иметь степень четыре. Удаление этих четырех вершин и их 12 инцидентных ребер оставляет непустой набор ребер, любое из которых вместе с четырьмя удаленными вершинами образует K3,3 подграф.

Верхняя граница

Следующая верхняя граница была установлена ​​Тамашом Коувари: Вера Т. Сос и Пал Туран вскоре после того, как проблема была поставлена,[5] и стал известен как Теорема Кевари – Соша – Турана:

Фактически Кевари, Сош и Туран доказали аналогичное неравенство для z(пт), но вскоре после этого Хильтен-Каваллиус заметил, что, по существу, тот же аргумент может быть использован для доказательства указанного неравенства.[6]Улучшение постоянного множителя во втором члене этой формулы в случае z(пт), был дан Штефан Знам:[7]

Если s и т считаются постоянными, то асимптотически, используя нотация большой O эти формулы можно представить в виде

и

Нижние границы

За т = 2, и для бесконечного числа значений п, двудольный граф с п вершины на каждой стороне, Ω (п3/2) края, а нет K2,2 может быть получен как Граф Леви конечного проективная плоскость, система п точки и линии, в которых каждые две точки принадлежат уникальной линии, и каждые две прямые пересекаются в уникальной точке. Граф, образованный из этой геометрии, имеет вершину на одной стороне его двудольного деления для каждой точки, вершину на другой стороне его двудольность для каждой линии и ребро для каждого угла между точкой и прямой. Проективные плоскости, определенные из конечных полей порядка п привести к K2,2-свободные графы с п = п2 + п + 1 и с (п2 + п + 1)(п + 1) ребра. Например, граф Леви Самолет Фано дает начало График Хивуда, двудольный граф с семью вершинами на каждой стороне, 21 ребром и без 4-циклов, показывая, что z(7; 2) ≥ 21. Нижняя оценка функции Заранкевича, данная этим семейством примеров, совпадает с верхней оценкой, данной И. Рейманом.[8] Таким образом, для т = 2 и для этих значений п для которого это построение может быть выполнено, оно дает точный ответ на проблему Заранкевича. Для других значений п, из этих оценок сверху и снизу следует, что асимптотически[9]

В более общем смысле,[10]

За т = 3, и для бесконечного числа значений п, двудольные графы с п вершины на каждой стороне, Ω (п5/3) края, а нет K3,3 снова может быть построен из конечная геометрия, позволяя вершинам представлять точки и сферы (тщательно выбранного фиксированного радиуса) в трехмерном конечном аффинном пространстве и позволяя ребрам представлять инцидентности точечной сферы.[11]

Было высказано предположение, что

для всех постоянных значений т, но это известно только для т = 2 и т = 3 по приведенным выше построениям.[12] Также известны узкие границы для пар (sт) с сильно различающимися размерами (в частности, s ≥ (т - 1)!). Для таких пар

подтверждая вышеприведенную гипотезу.[13]

Недвудольные графы

С точностью до постоянных факторов, z(пт) также ограничивает количество ребер в п-вершинный граф (не обязательно двудольный), не имеющий Kт,т подграф. Для двудольного графа в одном направлении с z(пт) края и с п вершины на каждой стороне его двудольного деления могут быть сведены к графу с п вершины и (в ожидании) z(пт) / 4 ребра, выбрав п/ 2 вершины равномерно случайным образом с каждой стороны. В обратном направлении график с п вершины и нет Kт,т можно преобразовать в двудольный граф с п вершин на каждой стороне его двудольного, вдвое больше ребер, и все еще нет Kт,т взяв его двусторонняя двойная обложка.[14]

Приложения

Теорема Кевари – Соша – Турана использовалась в дискретная геометрия для ограничения количества столкновений между геометрическими объектами различных типов. В качестве простого примера, набор п очки и м строки в Евклидова плоскость обязательно не имеет K2,2, поэтому согласно Кевари – Сош – Турану О(нм1/2 + м) точечные инциденты. Эта граница жесткая, когда м намного больше, чем п, но не когда м и п почти равны, и в этом случае Теорема Семереди – Троттера. обеспечивает более жесткий О(п2/3м2/3 + п + м) граница. Однако теорема Семереди – Троттера может быть доказана путем разделения точек и прямых на подмножества, для которых оценка Кевари – Соша – Турана является точной.[15]

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

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

  1. ^ Bollobás, Béla (2004), "VI.2 Полные подграфы р-дольные графы », Экстремальная теория графов, Mineola, NY: Dover Publications Inc., стр. 309–326, МИСТЕР  2078877. Перепечатка издания Academic Press 1978 года, МИСТЕР0506522.
  2. ^ Заранкевич, К. (1951), «Проблема P 101», Коллок. Математика., 2: 301. Как цитирует Боллобаш (2004).
  3. ^ http://www.cs.elte.hu/~hetamas/publ/DHSzFIN.pdf
  4. ^ а б Серпинский, В. (1951), «Sur un problème Concerant un Reseau à 36 points», Анна. Soc. Полон. Математика., 24: 173–174, МИСТЕР  0059876.
  5. ^ Kővári, T .; Т. Сос, В.; Туран, П. (1954), «К проблеме К.Заранкевича» (PDF), Коллоквиум по математике., 3: 50–57, МИСТЕР  0065617.
  6. ^ Хильтен-Каваллиус, К. (1958), "Об одной комбинаторной проблеме", Математический коллоквиум, 6: 59–65, МИСТЕР  0103158. Как цитирует Боллобаш (2004).
  7. ^ Znám, Š. (1963), «Об одной комбинаторной проблеме К.Заранкевича», Математический коллоквиум, 11: 81–84, МИСТЕР  0162733. Как цитирует Боллобаш (2004).
  8. ^ Рейман, И. (1958), "Уберская проблема фон К. Заранкевича", Acta Mathematica Academiae Scientiarum Hungaricae, 9: 269–273, Дои:10.1007 / bf02020254, МИСТЕР  0101250. Как цитирует Боллобаш (2004).
  9. ^ Боллобаш (2004), Следствие 2.7, с. 313.
  10. ^ Фюреди, Золтан (1996), "Новая асимптотика для двудольных чисел Турана", Журнал комбинаторной теории, Серия А, 75 (1): 141–144, Дои:10.1006 / jcta.1996.0067, МИСТЕР  1395763.
  11. ^ Браун, В. Г. (1966), «О графах, не содержащих графа Томсена», Канадский математический бюллетень, 9: 281–285, Дои:10.4153 / CMB-1966-036-2, МИСТЕР  0200182.
  12. ^ Боллобаш (2004), Гипотеза 15, с. 312.
  13. ^ Алон, Нога; Роньяи, Лайош; Сабо, Тибор (1999), «Норм-графы: варианты и приложения», Журнал комбинаторной теории, Серия B, 76 (2): 280–290, Дои:10.1006 / jctb.1999.1906, МИСТЕР  1699238. Эта работа основана на более ранней оценке, действительной для больших значений s, из Коллар, Янош; Роньяи, Лайош; Сабо, Тибор (1996), "Норм-графы и двудольные числа Турана", Комбинаторика, 16 (3): 399–406, Дои:10.1007 / BF01261323, МИСТЕР  1417348.
  14. ^ Боллобаш (2004), Теорема 2.3, с. 310.
  15. ^ Матушек, Иржи (2002), Лекции по дискретной геометрии, Тексты для выпускников по математике, 212, Нью-Йорк: Springer-Verlag, стр. 65–68, Дои:10.1007/978-1-4613-0039-7, ISBN  0-387-95373-6, МИСТЕР  1899299.