Проблема заранкевича - Zarankiewicz problem - Wikipedia

Эта статья о графах без большого полного двудольного подграфа. О числах пересечений полных двудольных графов см. Гипотеза о числе пересечения заранкевича.

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

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

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

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

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

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

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

Примеры

Двудольный граф с 4 вершинами на каждой стороне, 13 ребрами и без K_3,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 ребрами с четырьмя вершинами по обе стороны от двудольного графа, и нет K_3,3 подграф, может быть получен добавлением одной из длинных диагоналей к графику куб. С другой стороны, если двудольный граф с 14 ребрами имеет четыре вершины на каждой стороне, то две вершины на каждой стороне должны иметь степень четыре. Удаление этих четырех вершин и их 12 инцидентных ребер оставляет непустой набор ребер, любое из которых вместе с четырьмя удаленными вершинами образует K_3,3 подграф.

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

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

${\displaystyle z(m,n;s,t)<(s-1)^{1/t}(n-t+1)m^{1-1/t}+(t-1)m.}$

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

${\displaystyle z(n,t)<(t-1)^{1/t}n^{2-1/t}+{\frac {1}{2}}(t-1)n.}$

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

${\displaystyle z(m,n;s,t)=O(nm^{1-1/t}+m)}$

и

${\displaystyle z(n;t)=O(n^{2-1/t}).}$

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

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

${\displaystyle z(n;2)=n^{3/2}(1+o(1)).}$

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

${\displaystyle z(n,n;2,t+1)=n^{3/2}t^{1/2}(1+o(1)).}$

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

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

${\displaystyle z(n;t)=\Theta (n^{2-1/t})}$

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

${\displaystyle z(n,n;s,t)=\Theta (n^{2-1/t}),}$

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

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

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

Приложения

Теорема Кевари – Соша – Турана использовалась в дискретная геометрия для ограничения количества столкновений между геометрическими объектами различных типов. В качестве простого примера, набор п очки и м строки в Евклидова плоскость обязательно не имеет K_2,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.