Есть много примеров в комбинаторике и информатике, где мы можем проанализировать теоретико-графическую проблему, но для ее гиперграфа у нас отсутствуют инструменты. Как вы думаете, почему проблемы с 3-равномерными гиперграфами часто становятся намного сложнее, чем с 2-равномерными графами? Каковы основные трудности?
Одна из проблем заключается в том, что у нас пока нет удовлетворительного понимания теории спектральных гиперграфов. Пожалуйста, не стесняйтесь пролить больше света на эту проблему. Но я также ищу другие причины, которые делают гиперграфы более сложными объектами.
Ответы:
В этом вопросе я понимаю, что «сложность» относится не к «сложным вычислениям», а к «трудным для изучения».
Графические проблемы легче (по крайней мере для меня) изучить, поскольку некоторые концепции оказываются эквивалентными. Другими словами, если вы хотите обобщить вопросы для графиков на вопросы для гиперграфов, вам нужно обратить внимание на «правильное» обобщение, чтобы получить желаемое следствие.
Например, рассмотрим дерево. Для графов граф - это дерево, если он связан и не содержит циклов. Это эквивалентно соединению и наличию n-1 ребер (где n - количество вершин), а также эквивалентно отсутствию цикла и наличию n-1 ребер. Однако для 3-равномерных гиперграфов, скажем, 3-равномерный гиперграф является деревом, если он связан и не содержит циклов. Но это не эквивалентно соединению и наличию гиперчетов n-1, а также отсутствию цикла и наличию гипер-граней n-1.
Я слышал, что основная трудность доказательства леммы регулярности для равномерных гиперграфов состояла в том, чтобы придумать правильные определения регулярности и связанных понятий.
Если вы хотите рассмотреть «теорию спектральных гиперграфов», вы можете попытаться заглянуть в тензоры или в гомологии, если вы увидите k-равномерный гиперграф как (k-1) -мерный симплициальный комплекс, из которого естественным образом возникает линейная алгебра. Я не знаю, какое «правильное» обобщение для вашей цели, или возможно, что ни то, ни другое не верно.
источник
Я думаю, что это в значительной степени связано с «мистической силой двойственности» Лоулера (наблюдение, что многие параметризованные задачи находятся в P для param = 2 и NP-полные для param≥3). Граф - это вещь, которая соединяет 2 набора вершин, а гиперграф - это вещь, которая соединяет k наборов вершин для k≥3.
Так, например, 2-SAT находится в P и является по существу проблемой графа, тогда как 3-SAT является проблемой на 3-равномерных гиперграфах и является NP-полной.
источник
Другая причина состоит в том, что у нас гораздо больше знаний о бинарных отношениях, чем о любых других n-арных отношениях для n больше 2.
Естественно, мы рассматриваем бинарные отношения между объектами, такие как смежность, непустое пересечение, эквивалентность и т. Д. Таким образом, мы можем определить графы в терминах бинарных отношений и даже определить граф на основе некоторого бинарного отношения на другом графе. (Например, линейные графики, клики, разложения деревьев ...)
Но что касается других российских отношений, мы не очень понимаем. Например, требуется некоторое время, чтобы придумать интересное троичное соотношение; (Ладно, частично из-за моего невежества) свойства слабее, а инструменты гораздо меньше при изучении троичных отношений. (Как мы определяем симметричные или транзитивные троичные отношения? Оба они являются одними из самых важных отношений, которые можно изучить.)
Но все же я не знаю, почему это происходит между бинарными и троичными отношениями. Возможно, как сказала туркистанина, этот вопрос сложен и может быть связан с пониманием проблемы P / NP.
источник
Сначала я собирался ответить на неправильный вопрос: «Какой пример проблем гораздо сложнее в гиперграфах, чем в графах». Я был особенно впечатлен различием в работе с проблемой максимального соответствия на графах, а также с гиперграфами (набором попарно непересекающихся ребер), которые очень легко могут моделировать раскраску, максимальное независимое множество, максимальное клик ...
Тогда я заметил, что это был не твой вопрос: «Каковы основные трудности между ними?».
Ну, на это я бы ответил, что до сих пор я не видел много общих точек между графиками и гиперграфами. За исключением самого названия. И то, что многие люди пытаются «распространить» результаты с первого на другое.
У меня была возможность пролистать страницы «Гиперграфов» Берге и «Систем множеств» Боллобаса: они содержат много вкусных результатов, и те, которые я нашел наиболее интересными, мало что могли сказать о графиках. Например, теорема Бараньи (в книге Юкны есть хорошее доказательство).
Я не знаю многих из них, но сейчас я думаю о проблеме с гиперграфами, и все, что я могу сказать по этому поводу, - это то, что я не чувствую, чтобы где-то вокруг скрывался график. Возможно, мы думаем о них как о «трудных», потому что мы просто пытаемся изучить их с помощью неправильных инструментов. Я не ожидаю, что проблемы с графами, над которыми я работаю, сразу исчезнут, если использовать теорию чисел (хотя иногда это случается).
Ох, и что-то еще. Возможно, им труднее учиться, потому что они комбинаторно намного ... больше ?!
«попробуй их все и посмотри, как это работает» - иногда хорошая идея для графиков, но с гиперграфами один быстро смиряется с числами. :-)
источник