랜덤 그래프와 관련된 불일치의 변형 노드에 할당 된 값을

노드에 그래프가 있다고 가정합니다 . 각 노드에 또는 을 할당하려고합니다 . 이것을 구성 합니다. 우리가 할당해야 할 의 수 는 정확히 (따라서 의 수는 입니다. 설정이 주어지면, 각 노드 보고 인접 노드에 할당 된 값을 합쳐서 호출합니다. 이것은 입니다. 그런 다음 가 음이 아닌 노드 수를 계산합니다 .
$n$

$+ 1$

$- 1$

−1

$σ \in {+ 1, - 1}^{n}$

σ∈{+1,−1}n

$+ 1$

$s$

$- 1$

−1

$n - s$

n−s

$σ$

$i$

$ξ_{i} (σ)$

ξi(σ)

$ξ_{i} (σ)$

ξi(σ)

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

문제는 를 최대화 하는 구성 는 무엇 입니까? 더 중요한 것은 관점 에서 에 제한을 줄 수 ? 이 문제가 다른 사람에게 친숙해 보이는지 또는 그래프 이론에서 알려진 문제로 줄일 수 있는지 궁금합니다. 그것이 도움이된다면, 그래프는 Erdős-Renyi 유형 (예 : 가장자리 확률 , 즉 평균 정도가 증가하는 G (n, p))의 임의 인 것으로 가정 할 수 있습니다 . 주요 근심은 입니다. $σ$

$N (σ)$

N(σ)

$(max N) / n$

(maxN)/n

$s / n$

s/n

$p (\log n) / n$

p (log⁡n)/n

$\log n$

log⁡n

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

s/n∈(0,1/2)

답변

임의 제약 조건 만족 문제 에 대한 날카로운 임계 값 , Discrete Mathematics 285 / 1-3 (2004), 301-305 에서 사용한 것과 비슷한 “두 번째 모멘트 방법”계산으로이 방법에 접근 할 수 있습니다.

평균 정도가 충분히 큰 상수 시간 과 같이 증가 할 때 ,이 접근법은 종종 만족도의 임계 값을 정확하게 찾기에 충분했습니다. 나는 그것을 조사하지 않았지만 만족스럽지 않은 인스턴스에서 만족할 수있는 조항의 일부를 보여줄 수도 있습니다. $\log n$

log⁡n

문제를 내 일반적인 문제처럼 보이게하려면 CNF 수식의 절을 기본으로하는 특수한 그래픽 구조를 사용하여 “MAX-AT-LEAST-HALF-SAT”로 볼 수 있습니다. 그러나이 특수 구조가 최악의 경우 분석에 도움이 될 것이라고 생각하지는 않지만 절 크기가 균일하지 않고 “나쁜”할당 세트가 커지기 때문에 계산을 수행하고 계산 해야하는지 확인해야합니다. 여전히 작동합니다.

답변

내 의견에 대해 자세히 설명하겠습니다. 첫째, 이것은 불일치와 유사하지만 물론 여러 가지면에서 다릅니다. 세트 시스템 의 시스템의 불일치는 . 하자 나타낸다. 정의는 당신이 가 얼마나 많은 세트인지 알고 불일치는 최악의 경우 가 얼마나 큰지 묻습니다 . 빠른 소개를 위해 내 서기 메모 가 도움이 될 수 있습니다. Chazelle에는 많은 세부 사항이 담긴 멋진 책 이 있습니다. $m$

$S_{1}, \dots, S_{m} \subseteq {1, \dots n} = [n]$

S1,…,Sm⊆{1,…n}=[n]

$min_{σ : [n] \to {\pm 1}} max_{j} | \sum_{i \in S_{j}} σ (i) |$

minσ:[n]→{±1}maxj|∑i∈Sjσ(i)|

$σ (S_{j}) = | \sum_{i \in S_{j}} σ (i) |$

σ(Sj)=|∑i∈Sjσ(i)|

$σ (S_{j})$

σ(Sj)

$σ (S_{j})$

σ(Sj)

내 의견과 같이 일 때 쉬운 확률 론적 하한을 위해 그래프 순서가 인 그래프 사용 하면 무작위로 균일하게 선택할 수 있습니다 의 모든 시퀀스에서 ( 는 독립적이지 않지만이 경우에도 Chernoff 바운드를 증명할 수 있어야합니다). 우리는 을 가지며 Chernoff 경계에 의해 일정한 상수 . 따라서 입니다. 그래서 약간의 $s > n / 2$

s>n/2

$G = ([n], E)$

G=([n],E)

$δ_{1}, \dots, δ_{n}$

δ1,…,δn

$σ$

$s$

$1$

$σ_{i}$

σi

$E [ξ_{i} (σ)] = δ_{i} s / n$

E[ξi(σ)]=δis/n

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

Pr[ξi(σ)<0]≤exp⁡(−Cδi(s/n−1/2)2)

$C$

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

E[N(σ)]≥n−∑iexp⁡(−Cδi(s/n−1/2)2)

$σ$

그것은이 한계를 달성합니다.

편집 : 당신이 사건에 관심이있는 것 같습니다 . 이전 단락과 같은 방식으로 를 무작위로 봅시다 . 대체없이 샘플링을 위해 중앙 한계 정리의 버전을 사용하면 ( 는 그래프의 꼭짓점에서 대체하지 않고 크기 의 샘플입니다 ), 는 평균을 가진 가우스처럼 행동 한다는 것을 보여줄 수 있어야합니다 및 에 대한 분산 이므로 일부 및 C 중심 극한 정리에서 에러 파라미터. 이어야합니다 $s < n / 2$

s<n/2

$σ$

$s$

$ξ_{i} (σ)$

ξi(σ)

$δ_{i} (2 s / n - 1)$

δi(2s/n−1)

$δ_{i}$

δi

$Pr [ξ_{i} (σ) \geq 0] = \exp (- C δ_{i} (2 s / n - 1)^{2}) \pm η (n)$

Pr[ξi(σ)≥0]=exp⁡(−Cδi(2s/n−1)2)±η(n)

$η (n)$

η(n)

$n η (n) = o (n)$

nη(n)=o(n)

취할 수 있습니다 . $N (σ) \geq \sum_{i} \exp (- C δ_{i} (2 s / n - 1)^{2}) - o (n)$

N(σ)≥∑iexp⁡(−Cδi(2s/n−1)2)−o(n)

면책 조항 : 가 상수 / 작거나 이 매우 가까운 경우에만 의미가 있습니다. 또한 계산은 다소 추론 적이며 매우 신중하게 수행되지 않습니다. $δ_{i}$

δi

$s / n$

s/n

$n / 2$

n/2

How IT

언제든지 물어보세요.

랜덤 그래프와 관련된 불일치의 변형 노드에 할당 된 값을

답변

답변

답변