WikiSort.ru - Не сортированное

Разреженность

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

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

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

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

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

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

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

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