Введение

Графы, не содержащие больших полных двудольных подграфов. Проблема Заранкевича — нерешённая задача в математике, которая спрашивает о максимально возможном числе рёбер в двудольном графе с заданным числом вершин, не имеющем полных двудольных подграфов заданного размера. Она относится к области экстремальной теории графов, являющейся частью комбинаторики, и названа в честь польского математика Казимежа Заранкевича, который в 1951 году предложил несколько частных случаев этой задачи.

Заявление о проблеме

Двудольный граф состоит из двух непересекающихся множеств вершин, и , и множества ребер, каждое из которых соединяет вершину из с вершиной из . Не существует двух ребер, соединяющих одну и ту же пару вершин. Полный двудольный граф — это двудольный граф, в котором каждая пара вершин из и вершина из соединены между собой. Если — двудольный граф, и существует множество из вершин из и вершин из , которые все соединены друг с другом, то эти вершины индуцируют подграф вида (В этой формулировке порядок и существенен: множество вершин должно быть из и множество вершин должно быть из , а не наоборот.) Функция Заранкевича обозначает максимальное возможное число ребер в двудольном графе таком, что и , но который не содержит подграф вида . В качестве сокращения для важного частного случая, то же самое, что и . Проблема Заранкевича состоит в поиске формулы для функции Заранкевича или (если это не удается) для точных асимптотических ограничений скорости роста при условии, что — фиксированная константа, в пределе при стремящемся к бесконечности. Для эта проблема эквивалентна определению клеток с длиной окружности шесть. Проблема Заранкевича, клетки и конечная геометрия тесно взаимосвязаны. Ту же проблему можно сформулировать и в терминах цифровой геометрии. Возможные ребра двудольного графа можно представить как точки прямоугольника в целочисленной решетке, а полный подграф — как набор строк и столбцов в этом прямоугольнике, в котором присутствуют все точки. Таким образом, обозначает максимальное количество точек, которые можно разместить в сетке таким образом, чтобы никакое подмножество строк и столбцов не образовывало полный подграф. Случай относительно прост: двудольный граф с 13 ребрами, имеющий четыре вершины на каждой стороне двудольного разбиения и не содержащий подграф, можно получить, добавив одну из длинных диагоналей к графу куба. И наоборот, если двудольный граф с 14 ребрами имеет четыре вершины на каждой стороне, то две вершины на каждой стороне должны иметь степень четыре. Удаление этих четырех вершин и их 12 инцидентных ребер оставляет непустое множество ребер, любое из которых вместе с четырьмя удаленными вершинами образует подграф.

Графики наклона в конечной геометрии

Для , двусторонний граф с вершинами на каждой стороне, ребрами и без может быть получен как граф Леви, или граф инцидентности точка-линия, проективной плоскости порядка , системы точек и линий, в которой любые две точки определяют единственную линию, и любые две линии пересекаются в единственной точке. Мы строим двусторонний граф, связанный с этой проективной плоскостью, у которого одна часть вершин представляет точки, а другая – линии, так что точка и линия соединены тогда и только тогда, когда они инцидентны в проективной плоскости. Это приводит к свободному графу с вершинами и ребрами. Поскольку эта нижняя граница совпадает с верхней границей, полученной И. Рейманом, мы имеем асимптотическое.

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

Приложения

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