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

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

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

Формулировка проблемы [ править ]

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

Функция Заранкевича z ( m ,  n ;  s ,  t ) обозначает максимально возможное количество ребер в двудольном графе G  = ( U ,  V ,  E ), для которого | U | =  m и | V | =  n , но не содержит подграфа вида K s , t . Сокращение важного особого случая: z ( n ;  t ) - это то же самое, что z ( n ,  n; т ,  т ). Задача Заранкевича требует формулы для функции Заранкевича или (в противном случае) точных асимптотических оценок скорости роста z ( n ;  t ) в предположении, что t - фиксированная константа, в пределе, когда n стремится к бесконечности.

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

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

Примеры [ править ]

Двудольный граф с 4 вершинами на каждой стороне, 13 ребрами и без подграфа K 3,3 , а также эквивалентный набор из 13 точек в сетке 4 × 4, показывающий, что z (4; 3) ≥ 13.

Число z ( n , 2) требует максимального количества ребер в двудольном графе с n вершинами на каждой стороне, не имеющем 4-цикла (его обхват шесть или более). Таким образом, z (2, 2) = 3 (достигается трехреберным путем) и z (3, 2) = 6 ( шестиугольник ).

В своей первоначальной формулировке задачи Заранкевич запросил значения z ( n ; 3) для n  = 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] и стала известна как теорема Кевари – Соша – Турана :

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

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

и

Нижние границы [ править ]

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

В более общем плане [10]

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

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

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

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

Недвудольные графы [ править ]

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ Bollobás, Бел (2004), "VI.2 Полных подграфы г -дольных графов", Экстремальная Теория графов , Минеол, NY: Dover Publications Inc., стр 309-326,. MR  2078877. Перепечатка 1978 года выпуска Academic Press, MR 0506522 .
  2. ^ Zarankiewicz, К. (1951), "Проблема P 101", коллоквиум. Математика. , 2 : 301. Цитируется по Bollobás (2004) .
  3. ^ http://www.cs.elte.hu/~hetamas/publ/DHSzFIN.pdf
  4. ^ a b Sierpiński, W. (1951), "Sur un problème Concerant un Reseau à 36 points", Ann. Soc. Полон. Математика. , 24 : 173–174, MR 0059876 .
  5. ^ Kővári, T .; Т. Сос, В .; Туран, П. (1954), "Об одной проблеме К. Заранкевича" (PDF) , Colloquium Math. , 3 : 50–57, MR 0065617  .
  6. ^ Hyltén-Cavallius, C. (1958), "О комбинаторных проблемах", коллоквиум Mathematicum , 6 : 59-65, MR 0103158 . Цитируется по Bollobás (2004) .
  7. ^ Znám, Š. (1963), "Об одной комбинаторной проблеме К. Заранкевича", Colloquium Mathematicum , 11 : 81–84, MR 0162733 . Цитируется по Bollobás (2004) .
  8. ^ Рейман, И. (1958), "Убер Ein Проблема фон К. Zarankiewicz", Acta Mathematica Academiae Scientiarum Hungaricae , 9 : 269-273, DOI : 10.1007 / bf02020254 , МР 0101250 . Цитируется по Bollobás (2004) .
  9. ^ Bollobás (2004) , следствие 2.7, стр. 313.
  10. ^ Furedi, Золтан (1996), "Новые асимптотики для двудольных чисел Турана", Журнал комбинаторной теории , Серия А, 75 (1): 141-144, DOI : 10,1006 / jcta.1996.0067 , MR 1395763 .
  11. ^ Браун, WG (1966), «О графах, не содержащих графа Томсена», Canadian Mathematical Bulletin , 9 : 281–285, DOI : 10.4153 / CMB-1966-036-2 , MR 0200182 .
  12. ^ Bollobás (2004) , гипотеза 15, стр. 312.
  13. ^ Алон, Нога ; Роньяи, Лайош; Сабо, Тибор (1999), "Norm-графы: варианты и применение", Журнал комбинаторной теории , Series B, 76 (2): 280-290, DOI : 10,1006 / jctb.1999.1906 , МР 1699238 . Эта работа основывается на более раннем связанно, действительны для больших значений х , в Колларе, Янош; Роньяи, Лайош; Сабо, Тибор (1996), "Norm-графа и двудольное число Турана", Combinatorica , 16 (3): 399-406, DOI : 10.1007 / BF01261323 , МР 1417348 .
  14. ^ Bollobás (2004) , теорема 2.3, стр. 310.
  15. ^ Матушек, Иржи (2002), Лекции по дискретной геометрии , Тексты для выпускников по математике, 212 , Нью-Йорк: Springer-Verlag, стр. 65–68, DOI : 10.1007 / 978-1-4613-0039-7 , ISBN 0-387-95373-6, MR  1899299.