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

В Проблема заранкевича, нерешенная задача в математике, требует максимально возможного числа ребер в двудольный граф который имеет заданное количество вершин, но не имеет полный двудольный подграфы заданного размера.^[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 (м, n; s, t) = O (нм ^ {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 г (п; т) = тета (п ^ {2-1 / т})}$

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

${ Displaystyle г (п, п; s, т) = тета (п ^ {2-1 / т}),}$

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

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

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

Приложения

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

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

• График без биклик, разреженные графы, разреженность которых контролируется решением задачи Заранкевича
• Проблема запрещенного подграфа, недвудольное обобщение проблемы Заранкевича
• Характеристика запрещенного графа, семейства графов, определяемые запрещенными подграфами различных типов
• Теорема Турана, оценка количества ребер графа с запрещенным полным подграфом

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