Cтраница 2
Недавно Ловас [5] предложил удивительно простое решение чрезвычайно трудной комбинаторной задачи ( нахождение емкости пятиугольника), поставленной Шенноном [8] в 1956 г. В этой работе мы покажем, что идеи Ловаса в сочетании с некоторыми нашими идеями приводят к очень мощному и общему методу решения комбинаторных задач упаковки, который мы изложим на языке теории графов В частности, граница линейного программирования Дельсарта [3] для клик в ассоциативных схемах окажется специальным случаем границы Ловаса. [16]
Доказательство этого результата не представляет труда и опускается. Ловас ( 1979Ь), где дано доказательство для частного случая. [17]
Несмотря на это возрастающее признание комбинаторики ( включая теорию графов) как части математики, следы полемики о ее значении все еще сохраняются. Ловас очень правильно реагирует на эту полемику, указывая на увеличивающееся многообразие методов и унифицирующую теорию, приобретаемые данной ветвью математики. Тем не менее, несколько дальнейших замечаний могут оказаться уместными. Как считает другой мой бывший коллега Дж. Шихан [4], могут существовать довольно важные разделы комбинаторики, которые невозможно заключить ни в какие унифицирующие рамки. Есть, несомненно, удовлетворение от решения просто формулируемой, естественной в своей постановке, но строптивой, неподдающейся задачи, даже если найденное решение представляется, по крайней мере в настоящее время, стоящим особняком. Если ( как иногда, кажется, считают) теорема может быть важна только в том случае, когда она полезна при доказательстве или разъяснении других теорем, то следует далее поинтересоваться, чем важны эти другие теоремы, а это может повлечь гес1ис11о ас. Разве для того, чтобы доказать, что некая ветвь математики интересна, обязательно демонстрировать ее полное подобие другим ветвям математики. А может быть, доля привлекательности математики - в разнообразии ее направлений. [18]
Сначала мы приводим очень простую границу для 0 ( G), которая применима к любым регулярным графам. Затем вычисляем границу Ловаса для двух бесконечных семейств графов: циклических графов CN и квадратично-вычет-ных графов Qp, которые являются двумя различными обобщениями графа Сб - Нам не удалось вычислить емкости графов С для нечетных Л /, N 7, но для любого простого р, р гэ 1 mod 4, мы покажем, что 0 ( QP) д / Р - Далее рассматриваются три специальных графа: граф Петерсена, графы икосаэдра и додекаэдра. Мы также рассматриваем очень интересный регулярный граф на 7 вершинах. [19]
В частности, мы получим первоначальный результат Ловаса о емкости графа С и границу линейного программирования Дельсарта для клик в ассоциативных схемах. [20]
Сделаем несколько дополнительных замечаний относительно обобщения рассматриваемой задачи об / - факторе. Ловас ( 1972с) показал, что возможность раскраски ребер тремя цветами сводима к случаю, когда I ( v) 1 или 0, 3 в каждой вершине. Из этого, согласно результату Холиера ( 1981), следует, что данная задача для произвольных множеств I ( v ] является N Р - полной. Однако в частном случае, когда допускается, чтобы множество I ( v) содержало только одноэлементные промежутки, большая часть рассмотрений, представленных в этом разделе, может быть опущена. [21]
Ловас также указал много других следствий из (1.5), которые мы сейчас не приводим. Ловаса и были получены им ранее. [22]
Настоящая статья возникла из попыток перенести результаты Ловаса на более общий случай. Думаем, что нам это удалось, но в нашем решении ортонормированные представления полностью исчезли. Тем не менее все границы, которые мы получили ( по крайней мере границы для 6 ( G)), могут быть получены из ортонормированного представления, поэтому мы и называем их границами Ловаса. В приложении А содержатся доказательства эквивалентности нашего метода и метода Ловаса. [23]
Настоящая статья возникла из попыток перенести результаты Ловаса на более общий случай. Думаем, что нам это удалось, но в нашем решении ортонормированные представления полностью исчезли. Тем не менее все границы, которые мы получили ( по крайней мере границы для 6 ( G)), могут быть получены из ортонормированного представления, поэтому мы и называем их границами Ловаса. В приложении А содержатся доказательства эквивалентности нашего метода и метода Ловаса. [24]