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

노드에 그래프가 있다고 가정합니다 . 각 노드에 또는 -1 을 할당하려고합니다 . 이것을 구성 \ sigma \ in \ {+ 1, −1 \} ^ n이라고 합니다. 우리가 할당해야 할 +1 의 수 는 정확히 s (따라서 -1 의 수는 n-s) 입니다. \ sigma 설정이 주어지면, 각 노드 i를 보고 인접 노드에 할당 된 값을 합쳐서 호출합니다. 이것은 \ xi_i (\ sigma) 입니다. 그런 다음 \ xi_i (\ sigma) 가 음이 아닌 노드 수를 계산합니다 .
N (\ sigma) : = \ sum_ {i = 1} ^ n 1 \ {\ xi_i (\ sigma) \ ge 0 \}.

n

+1

−1

σ∈{+1,−1}n

+1

s

−1

n−s

σ

i

ξi(σ)

ξi(σ)

N(σ):=∑i=1n1{ξi(σ)≥0}.


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

σ

N(σ)

(maxN)/n

s/n

p (log⁡n)/n

log⁡n

s/n∈(0,1/2)



답변

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

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

log⁡n

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


답변

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

m

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

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

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

σ(Sj)

σ(Sj)

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

s>n/2

G=([n],E)

δ1,…,δn

σ

s

1

σi

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

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

C

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

σ

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

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

s<n/2

σ

σ

s

ξi(σ)

δi(2s/n−1)

δi

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

η(n)

nη(n)=o(n)

취할 수 있습니다 .

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

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

δi

s/n

n/2