Вопросы с тегом «co.combinatorics»

22
Социальный выбор, теорема стрелы и открытые проблемы?

В последние несколько месяцев я начал читать лекции о социальном выборе, теореме стрелы и связанных с ней результатах. Прочитав об исходных результатах, я спросил себя о том, что происходит с предпочтениями частичного порядка, ответ в статье Pini et al. : Агрегирование частично упорядоченных...

22
Количество отдельных узлов в случайной прогулке

Время коммутирования в связанном графе определяется как ожидаемое количество шагов в случайном блуждании, начиная с , до посещения узла и затем достижения узла снова. В основном это сумма двух времен удара и .G = ( V, E)гзнак равно(В,Е)G=(V,E)яяiJJjяяiЧАС( я , j )ЧАС(я,J)H(i,j)ЧАС( J , I...

21
Консенсусная кластеризация с использованием множества объединений

Я уже публиковал этот вопрос некоторое время назад в MathOverflow , но, насколько мне известно, он все еще открыт, поэтому я публикую его здесь в надежде, что кто-то мог о нем слышать. Постановка задачи Пусть , Q и R - три разбиения на p непустых частей (обозначаемых через P h 's, Q i ' и R j 's)...

21
Являются ли реберно-вершинные графы многогранников (приличных) экспандерами?

Этот вопрос вдохновлен полиномиальной гипотезой Хирша (PHC). Учитывая гранный многогранник в , ограничена ли спектральная щель графа вершин и вершин (назовем его ) снизу ? Обратите внимание, что граф циклов на вершинах показывает, что даже при спектральная щель может быть такой маленькой, как ; так...

21
Количество различных отличий целых чисел выбранных из

Я столкнулся со следующим результатом во время моего исследования. limn→∞E[#{|ai−aj|,1≤i,j≤m}n]=1limn→∞E[#{|ai−aj|,1≤i,j≤m}n]=1\lim\limits_{n\to \infty} \mathbb{E}\left[ \frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n} \right] = 1 где m=ω(n−−√)m=ω(n)m=\omega(\sqrt n) и a1,⋯,ama1,⋯,ama_1,\cdots,a_m...

21
полнота распознавания разности двух перестановок

Шор заявил в своем комментарии к ответу анонимного лося на этот вопрос. Можете ли вы определить сумму двух перестановок за полиномиальное время? То , что он является полным, чтобы определить разницу двух перестановок. К сожалению, я не вижу прямого сокращения от проблемы суммы перестановок, и было...

21
Причины, по которым график может быть не

Рассуждая немного об этом вопросе , я попытался определить все различные причины, по которым граф может не быть k раскрашиваемым. Это единственные две причины, которые я смог определить до сих пор:G=(VG,EG)G=(VG,EG)G = (V_G,E_G)kkk содержит клику размером k + 1 . Это очевидная причина.GGGk+1k+1k+1...

21
Раскраски планарных графиков

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

20
Для чего нужны бесконечные графики?

Я только что прочитал в немецкой Википедии, что бесконечный граф - это граф с бесконечным числом узлов или бесконечным числом ребер. Я знаю только приложения и алгоритмы для конечных графов. Для чего нужны бесконечные графики? Каковы приложения тех? Я не могу представить алгоритмы, которые будут...

20
Явная сбалансированная матрица

Можно ли построить явное 0 / 1 -матрица с N 1,5 из них таким образом, что каждый N 0,499 × N 0,499 подматрица содержит менее N 0,501 из них?N×NN×NN \times N 0/10/10/1N1.5N1.5N^{1.5}N0.499×N0.499N0.499×N0.499N^{0.499} \times N^{0.499}N0.501N0.501N^{0.501} Или, возможно, для такого свойства можно...

19
Построение графов, в которых каждая пара вершин имеет единого общего соседа

Позволять граммграммG быть простым графиком на NNn вершины ( n > 3 )(N>3)(n > 3) без вершины степени n - 1N-1n − 1, Предположим, что для любых двух вершинграммграммG, есть уникальная вершина, смежная с ними обоими. Ван Линт и Уилсон - это курс из курса по комбинаторике , чтобы доказать, что...

19
Модели случайных графов, для реальных компьютерных сетей

Меня интересуют модели случайных графов, которые похожи на графы реальных компьютерных сетей. Я не уверен, что общая хорошо изученная модель ( n вершин, каждое возможное ребро выбрано с вероятностью p ) подходит для изучения реальных компьютерных сетей (не так ли?).G ( n , p )G(n,p)G(n,p)Nnnпpp...

19
Линейно независимые коэффициенты Фурье

Основное свойство векторных пространств состоит в том, что векторное пространство размерности может характеризоваться линейно независимыми линейными ограничениями, то есть существуют линейно независимых векторов , ортогональных .В⊆ FN2В⊆F2NV \subseteq \mathbb{F}_2^nн - дN-dn-dddddddвес1, … , Шd∈...

19
Какое количество языков принимается DFA размера

Вопрос прост и прям: для фиксированного , сколько (разных) языков принято DFA размером n (то есть nnnnnnnnnn состояний)? Я официально заявлю это: Определите DFA как , где все как обычно и δ : Q × Σ → Q (возможно, частичная) функция. Нам нужно установить это, поскольку иногда только полные функции...

19
Аксиомы для кратчайших путей

Предположим, у нас есть неориентированный взвешенный граф G=(V,E,w)G=(V,E,w)G = (V, E, w) (с неотрицательными весами). Предположим, что все кратчайшие пути в GGG единственны. Предположим, у нас есть эти пути (последовательности невзвешенных ребер), но мы не знаем саму G. Можем ли мы создать G ,...

19
Math talk: Теорема о системе контроля версий git?

Я хотел бы выступить с математикой о системе контроля версий git . В настоящее время он широко используется в математике, а также в индустрии компьютерных наук. Например, сообщество HoTT (Homotopy Type Theory) использует его, и это система перехода к совместному редактированию текстовых файлов,...

18
Можно ли проверить, является ли вычислимое число рациональным или целым?

Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...

18
Какое наилучшее приближение для большинства голосов?

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

18
Кратчайший эквивалент формулы CNF

Пусть F1F1F_1 - выполнимая формула CNF с nnn переменными и mmm предложениями. Пусть SF1SF1S_{F_1} - пространство решений F1F1F_1 . Рассмотрим проблему определения для данной F1F1F_1 другой формулы CNF F2F2F_2с тем же набором переменных, что и для F1F1F_1 , с SF2=SF1SF2=SF1S_{F_2} = S_{F_1} (то же...