Свободный от биклик граф

В теории графов свободный от $\text{[math]}$ t-биклик граф — это граф, в котором нет полных двудольных графов с 2 $\text{[math]}$ t вершинами $\text{[math]}$ K_t,t в качестве подграфов. Семейство графов является свободным от биклик, если существует число $\text{[math]}$ t, такое, что все графы в семействе свободны от $\text{[math]}$ t-биклик. Семейства свободных от бициклов графов образуют одно из наиболее общих типов семейств разреженных графов. Они возникают в задачах инцидентности в комбинаторной геометрии, а также используются в теории параметрической сложности^[en].

СвойстваПравить

РазреженностьПравить

Согласно теореме Ковари – Сос – Турана^[en] любой свободный от $\text{[math]}$ t-бициклов граф с $\text{[math]}$ n вершинами имеет $\text{[math]}$ O(n^{2 − 1/t}) рёбер, т.е. граф существенно более редкий, чем плотный граф^[1]. В обратную сторону, если семейство графов определено запрещёнными подграфами или замкнуто по отношению к операции взятия подграфа и не включает плотные графы произвольно большого размера, оно должно быть свободным от $\text{[math]}$ t-биклик для некоторого $\text{[math]}$ t, в противном случае, семейство должно включать произвольно большие плотные полные двудольные графы.

В качестве нижней границы Эрдёш, Хайнал и Муун^[2] высказали предположение, что любой максимальный свободный от $\text{[math]}$ t-биклик двудольный граф (к которому нельзя добавить ребро без создания $\text{[math]}$ t-биклики) имеет по меньшей мере $\text{[math]}$ (t − 1)(n + m − t + 1) рёбер, где $\text{[math]}$ n и $\text{[math]}$ m — число вершин на каждой из долей графа^[3].

Связь с другими типами семейств разреженных графовПравить

Граф с вырождением $\text{[math]}$ d является обязательно свободным от $\text{[math]}$ (d + 1)-биклик. Кроме того, семейство свободных от биклик графов должно быть нигде не плотным, что означает, что для любого числа $\text{[math]}$ k существует граф, который не является $\text{[math]}$ k-неглубоким минором какого-либо графа из семейства. В частности, если существует граф с $\text{[math]}$ n вершинами, не являющийся 1-неглубокими минором, то семейство должно быть свободным от $\text{[math]}$ n-биклик, поскольку все графы с $\text{[math]}$ n вершинами являются 1-неглубокими минорами графа $\text{[math]}$ K_n,n. Таким образом, свободные от биклик семейства графов унифицируют два из наиболее общих классов разреженных графов^[4].

ПриложенияПравить

Дискретная геометрияПравить

В комбинаторной геометрии многие типы графов инцидентности заведомо свободны от биклик. В качестве простого примера граф инцидентности конечного множества точек и прямых на евклидовой плоскости заведомо не содержит $\text{[math]}$ K_2,2 подграфа^[5].

Параметризованная сложностьПравить

Свободные от биклик графы используются в теории параметрической сложности^[en] для разработки алгоритмов, эффективных для разреженных графов с достаточно малыми входными параметрами. В частности, поиск доминирующего множества размером $\text{[math]}$ k на свободных от $\text{[math]}$ t-биклик графах является фиксированно-параметрически разрешимой задачей, если использовать параметр $\text{[math]}$ k + t, даже хотя существуют веские основания, что это невозможно, если использовать только параметр $\text{[math]}$ k без $\text{[math]}$ t. Те же результаты верны для многих вариантов задачи о доминирующем множестве^[4]. Проверка, имеет ли доминирующее множество размер не более $\text{[math]}$ k, может быть также преобразована в другую проверку с той же параметризацией путём цепочки вставок и удалений вершин, сохраняя свойство доминирования^[6].

ПримечанияПравить

↑ Kővári, T. Sós, Turán, 1954. Эта работа рассматривает число рёбер свободных от биклик графов, но стандартное приложение вероятностного метода переносит те же границы на произвольные графы.
↑ Erdős, Hajnal, Moon, 1964.
↑ Erdős, Hajnal, Moon, 1964, с. 1107–1110.
↑ ¹ ² Telle, Villanger, 2012, с. 802–812.
↑ Kaplan, Matoušek, Sharir, 2012, с. 499–517.
↑ Lokshtanov, Mouawad, Panolan, Ramanujan, Saurabh, 2015, с. 506–517.

ЛитератураПравить

T. Kővári, V. T. Sós, P. Turán. On a problem of K. Zarankiewicz // Colloquium Math.. — 1954. — Т. 3. — С. 50–57.
P. Erdős, A. Hajnal, J. W. Moon. A problem in graph theory // The American Mathematical Monthly. — 1964. — Т. 71. — С. 1107–1110. — doi:10.2307/2311408.
Jan Arne Telle, Yngve Villanger. Algorithms – ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenia, September 10–12, 2012, Proceedings / Leah Epstein, Paolo Ferragina. — Springer, 2012. — Т. 7501. — С. 802–812. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-642-33090-2_69.
Haim Kaplan, Jiří Matoušek, Micha Sharir. Simple proofs of classical theorems in discrete geometry via the Guth–Katz polynomial partitioning technique // Discrete and Computational Geometry. — 2012. — Т. 48, вып. 3. — С. 499–517. — doi:10.1007/s00454-012-9443-3. — arXiv:1102.5391.. See in particular Lemma 3.1 and the remarks following the lemma.
Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, M. S. Ramanujan, Saket Saurabh. Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015, Proceedings / Frank Dehne, Jörg-Rüdiger Sack, Ulrike Stege. — Springer, 2015. — Т. 9214. — С. 506–517. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-319-21840-3_42.

[1] Kővári, T. Sós, Turán, 1954. Эта работа рассматривает число рёбер свободных от биклик графов, но стандартное приложение вероятностного метода переносит те же границы на произвольные графы.

[_f640c5db00324cb2-2] Erdős, Hajnal, Moon, 1964.

[_9b44ccce137c2d45-3] Erdős, Hajnal, Moon, 1964, с. 1107–1110.

[_6409eb028a87e990-4] ¹ ² Telle, Villanger, 2012, с. 802–812.

[_a2329b1ddb57f9c2-5] Kaplan, Matoušek, Sharir, 2012, с. 499–517.

[_9f900ad53970b591-6] Lokshtanov, Mouawad, Panolan, Ramanujan, Saurabh, 2015, с. 506–517.

[1]

[2]

[3]

[4]

[5]

[6]