Вариация расхождения с участием случайных графов

Предположим, у нас есть график $n$ узлы. Мы хотели бы назначить каждому узлу либо $+1$ или $−1$ , Назовите это конфигурацией $\sigma \in \{+1,−1\}^n$ , Номер $+1$ с, что мы должны назначить точно $s$ (отсюда количество $−1$ с это $n−s$ .) Учитывая конфигурацию $\sigma$ Смотрим на каждый узел $i$ и суммировать значения, присвоенные его соседям, вызовите это $\xi_i(\sigma)$ , Затем мы посчитаем количество узлов, для которых $\xi_i(\sigma)$ неотрицательно:

N (σ) := \sum_{i = 1}^{n} 1 {ξ_{i} (σ) \geq 0} .

$N(\sigma):=\sum_{i=1}^n 1\{\xi_i(\sigma) \ge 0\}.$ Вопрос в том, что такое конфигурация.

σ

$\sigma$ что максимизирует

N (σ)

$N(\sigma)$ ? Что еще более важно, мы можем дать оценку

(max N) / n

$(\max N)/n$ с точки зрения . Мне интересно, выглядит ли эта проблема знакомой кому-либо или ее можно свести к какой-то известной проблеме в теории графов. Если это помогает, можно считать, что граф случайный типа Эрдеша-Реньи (скажем, G (n, p) с вероятностью фронта , т.е. средняя степень растет как ). Основной инстрест в том случае, когда .

s / n

$s/n$

p (\log n) / n

$p ~ (\log n)/n$

\log n

$\log n$

s / n \in (0, 1 / 2)

$s/n \in (0,1/2)$

graph-theory co.combinatorics optimization passerby51
источник

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

Суреш Венкат

простая граница: произвольно взять ; , где - степень вершины а - некоторая постоянная. Итак, . Если, скажем, и граф является -регулярным, то существует такая , что .

σ

$\sigma$

Pr [ξ_{i} (σ) < 0] \leq \exp (- C δ_{i} (s / n - 1 / 2)^{2})

$\Pr[\xi_i(\sigma) < 0] \leq \exp(-C\delta_i (s/n - 1/2)^2)$

δ_{i}

$\delta_i$

i

$i$

C

$C$

E [N (σ)] \geq \sum_{i} 1 - \exp (- C δ_{i} (s / n - 1 / 2)^{2})

$E[N(\sigma)] \geq \sum_i{1-\exp(-C\delta_i (s/n - 1/2)^2)}$

s = 3 n / 4

$s = 3n/4$

(16 / C) \log n

$(16/C)\log n$

σ

$\sigma$

N (σ) \geq n - O (1)

$N(\sigma) \geq n - O(1)$

Сашо Николов

@ Суреш: Спасибо. Это то, что мне нравится спрашивать у компьютерных ученых, вы узнаете что-то новое! Так, где хорошее место, чтобы узнать о проблемах несоответствия в пространстве диапазона? (Может быть, краткая краткая газета?)

passerby51

@Sasho: Спасибо. По какой-то причине я не могу видеть уравнения должным образом (они столкнулись с окружающим текстом.) Я постараюсь прочитать его и вернуться к вам. Но я должен упомянуть, что интересный для меня режим - это и проблема, похоже, усложняется, когда приближается к . (Это связано с рассмотрением симметрии в исходной задаче, из которой это произошло.) Я не думаю, что рассмотрение случайной сделало бы это для .

s / n \in (0, 1 / 2)

$s/n \in (0,1/2)$

s / n

$s/n$

1 / 2

$1/2$

σ

$\sigma$

s / n \in (0, 1 / 2)

$s/n \in (0,1/2)$

passerby51

Предположение / надежда состоит в том, что для, скажем, G (n, p) с или . Я только что понял опечатку в моем первоначальном посте относительно . Прости за это. Средняя степень растет, так как не .

(max N) / n = o (1)

$(\max N)/n = o(1)$

p (\log n) / n

$p ~ (\log n) / n$

p (\log n)^{1 + ϵ} / n

$p ~ (\log n)^{1+\epsilon} /n$

p

$p$

\log n

$\log n$

p

$p$

passerby51

Ответы:

Вы можете подойти к этому с помощью метода «второго момента», аналогичного тому, который я использовал в «Остром пороге» для задачи удовлетворения случайных ограничений , Discrete Matmatics 285 / 1-3 (2004), 301-305.

Когда средняя степень растет как достаточно большие постоянные времена , такого подхода часто бывает достаточно, чтобы точно найти порог выполнимости. Это может также показать часть предложений, которые могут быть выполнены в неудовлетворительном случае, хотя я не исследовал это. $\log n$

Чтобы ваша проблема выглядела как моя общая проблема, вы можете рассматривать ее как «MAX-AT-LEAST-HALF-SAT» со специальной графической структурой, лежащей в основе предложений в формуле CNF. Однако я не думаю, что эта специальная структура поможет в анализе наихудшего случая, и поскольку размер вашего предложения неоднороден, а ваш «плохой» набор назначений растет, вам придется пройти расчет и посмотреть, будет ли он еще работает.

Авраам Д Flaxman
источник

смотреть на это как на CSP кажется действительно более подходящим, чем смотреть на это как на проблему несоответствия

Сашо Николов

Спасибо. Это выглядит очень интересно. Я буду смотреть в него.

passerby51

Позвольте мне уточнить мой комментарий. Во-первых, это похоже на расхождение, но, конечно, отличается по нескольким причинам. Для системы из множеств несоответствие системы равно . Обозначим, Ваше определение отличается тем, что вы хотите узнать, сколько наборов является положительным, и расхождение спрашивает, насколько велика величина в худшем случае. Для быстрого вступления, возможно, могут помочь мои заметки писца . У Шазель есть хорошая книга , в которой много деталей. $m$ $S_1, \ldots, S_m \subseteq \{1, \ldots n\} = [n]$ $\min_{\sigma:[n] \rightarrow \{\pm 1\}}{\max_{j}{|\sum_{i \in S_j}{\sigma(i)}|}}$ $\sigma(S_j) = |\sum_{i \in S_j}{\sigma(i)}|$ $\sigma(S_j)$ $\sigma(S_j)$

Для легкой вероятностной нижней границы, когда , как в моем комментарии, учитывая граф с последовательностью степеней , вы можете равномерно выбрать случайным образом из всех последовательностей с ( не являются независимыми, но в этом случае также должна быть возможность доказать границу Чернова). У нас есть и, по черновой границе, для некоторой константы . Так что . Так что существует какая-то $s > n/2$ $G = ([n], E)$ $\delta_1, \ldots, \delta_n$ $\sigma$ $s$ $1$ $\sigma_i$ $E[\xi_i(\sigma)] = \delta_i s/n$ $\Pr[\xi_i(\sigma) < 0] \leq \exp(-C\delta_i (s/n - 1/2)^2)$ $C$ $E[N(\sigma)] \geq n - \sum_i{\exp(-C\delta_i (s/n - 1/2)^2)}$ $\sigma$ это достигает этой границы.

РЕДАКТИРОВАТЬ: Кажется, что вы заинтересованы в случае . Давайте случайным образом выберем же, как и в предыдущем абзаце. Используя версию центральной предельной теоремы для выборки без замены ( - выборка размера без замены из вершин графа), вы должны показать, что ведет себя как гауссиан со средним и дисперсия относительно , поэтому для некоторых C и параметр ошибки из центральной предельной теоремы. Мы должны иметь $s < n/2$ $\sigma$ $\sigma$ $s$ $\xi_i(\sigma)$ $\delta_i (2s/n - 1)$ $\delta_i$ $\Pr[\xi_i(\sigma) \geq 0] =\exp(-C\delta_i(2s/n - 1)^2) \pm \eta(n)$ $\eta(n)$ $n\eta(n) = o(n)$ , так что вы можете взять . $N(\sigma) \geq \sum_{i}{\exp(-C\delta_i(2s/n - 1)^2)} - o(n)$

Отказ от ответственности: это имеет смысл, только если постоянны / малы или очень близко к . Также вычисления несколько эвристичны и не очень тщательно выполнены. $\delta_i$ $s/n$ $n/2$

Сашо Николов
источник

Спасибо за хорошие ссылки и аргумент. Мне нравится вероятностный аргумент, но я думаю, что с вашей границей что-то не так. Вы можете увидеть это, установив , для которого мы должны иметь . Похоже, это то, что пошло не так: если вы случайным образом выбираете из набора, указанного в задаче, у каждого есть . быть и вероят. из бытия . Следовательно, который отрицателен для ...

s = 0

$s = 0$

P r [ξ_{i} (σ) < 0] = 1

$Pr[\xi_i(\sigma) < 0] = 1$

σ

$\sigma$

σ_{j}

$\sigma_j$

γ := s / n

$\gamma := s/n$

+ 1

$+1$

1 - γ

$1-\gamma$

- 1

$-1$

E [ξ_{i} (σ)] = (2 γ - 1) δ_{i}

$E[ \xi_i(\sigma)] = (2\gamma-1) \delta_i$

γ \in (0, 1 / 2)

$\gamma \in (0,1/2)$

passerby51

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

{σ_{j}}

$\{\sigma_j\}$

P r [\frac{1}{δ_{i}} ξ_{i} (σ) < - t + 2 γ - 1) \leq \exp (- δ_{i} t^{2} / 2)

$Pr[ \frac{1}{\delta_i} \xi_i(\sigma) < -t + 2\gamma - 1) \le \exp ( -\delta_i t^2/2)$

t \geq 0

$t \ge 0$

t = 2 γ - 1 < 0

$t = 2\gamma - 1 < 0$

P r [ξ_{i} (σ) < 0]

$Pr[\xi_i(\sigma) <0]$

passerby51

извините, я должен был указать это: предположение здесь было, что . в противном случае это не имеет смысла, и вам нужно что-то более сильное, например, Берри-Эссеен. я думаю, что можно считать по существу независимым

s > n / 2

$s > n/2$

σ_{j}

$\sigma_j$

Сашо Николов

@ passerby51 добавил набросок того, как вы можете попытаться использовать количественную версию центральной предельной теоремы, чтобы расширить вероятностную оценку до .

s / n < 1 / 2

$s/n < 1/2$

Сашо Николов