Доказательства получены только с помощью теории спектральных графов

28

Я все больше интересуюсь теорией спектральных графов, которая мне кажется интересной, и я начал собирать несколько документов, которые мне еще предстоит прочитать более тщательно, чем то, что я имею до сих пор.

Однако мне любопытно высказывание, которое появилось в нескольких источниках (например, там ), в котором говорится, что некоторые результаты в теории графов были доказаны с использованием только методов, основанных на спектре, и что до сих пор нет доказательств того, что Обход тех приемов известен.

Если я не пропустил это, я не помню, чтобы видел такой пример в литературе, которую я до сих пор читал. Кто-нибудь из вас знает примеры таких результатов?

graph-theory co.combinatorics proofs spectral-graph-theory Энтони Лабарре
источник
Название вопроса предполагает, что вы запрашиваете доказательства, которые можно получить только с помощью теории спектральных графов, но вы запрашиваете доказательства, которые до сих пор были получены только с помощью теории спектральных графов. Это два совершенно разных вопроса. Таким образом, название вводит в заблуждение, поэтому я изменил его.
Дейв Кларк,
@ Дейв, я сделал откат
Суреш Венкат
5
В главе 7 « Спектры графиков » Цветковича, Дуба и Сакса приводится множество примеров теорем, в формулировках которых нет прямого упоминания о спектрах, но которые доказуемы с использованием спектральных методов. Я предполагаю, что многие из них не имеют известных не спектральных доказательств, хотя вам придется проверять это в каждом конкретном случае. Конечно, во многих случаях самое простое или естественное доказательство использует спектры.
Тимоти Чоу
@ Тимоти Чоу: Спасибо, я постараюсь достать это.
Энтони Лабарр
@TimothyChow: думаю, вы должны сделать это ответом.
Суреш Венкат

Ответы:

12

Теорема Хоффмана – Синглтона .

Колин Маккуиллан
источник
Хоффман-Синглтон тоже был моей первой мыслью. Но я не знаю, существуют ли какие-либо неспектральные доказательства, и если их нет, то это потому, что они слишком сложны или потому что никто не пытался. Стандартное доказательство довольно аккуратное и лаконичное, поэтому я не знаю, как это мотивировать, чтобы получить не спектральное доказательство.
Mhum
9

Как насчет этого результата на квантовых вычислениях.

Марио Сегеды. Квантовое ускорение алгоритмов на основе цепей Маркова. В FOCS'04.

Он расширяет цепочки Маркова до квантовых цепей Маркова и показывает, что время квантового удара сверху ограничено квадратным корнем классического времени удара. Он делает это, связывая сингулярные векторы классической цепи Маркова с сингулярными векторами квантовой цепи Маркова. До этой статьи не было никакой известной связи между случайными и квантовыми блужданиями. Я не могу представить, как сделать то же самое, используя не спектральные методы.

Маркос Вильягра
источник
8

Я думаю, что теорема о дружбе (см. Также статью Хунеке ) является хорошим примером, хотя, строго говоря, в настоящее время существуют доказательства теоремы о дружбе, которые избегают собственных значений. Доказательства, которые полностью избегают собственных значений, намного сложнее, чем спектральное доказательство.

(Теорема о дружбе гласит, что если в комнате людей у ​​каждой пары людей есть только один общий друг, то есть кто-то, кто знает всех остальных.)

Тимоти Чоу
источник
8

LGG=(V,E,w)GHx∈RV

xTLHx(1−ϵ)≤xTLGx≤xTLHx(1+ϵ).
O(n/ϵ2)

Несмотря на то, что формулировка теоремы, несомненно, не является «изначально спектральной», я не думаю, что известно, как можно получить этот результат или подобный результат без использования спектральных методов.

Лев Рейзин
источник
Это немного спорно, является ли это утверждение не неотъемлемо Спектральный. В буквальном смысле вы правы, но единственное обоснование, которое я могу придумать, почему квадратичная форма проявляется, это спектрально.
Суреш Венкат
1
F(A)={xTAx:||x||2=1}O(n/ϵ2)
Конечно, - но можно представить, как получить эти спарсификаторы другим способом. Но, да, это может быть не лучшим примером ...
Лев Рейзин