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

$m$

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

$S_1,\dots ,S_m\subseteq \{1,\dots n\}=[n]$

$S_1, \ldots, S_m \subseteq \{1, \ldots n\} = [n]$minσ:[n]→{±1}maxj|∑i∈Sjσ(i)|

$\underset{\sigma :[n]\to \{\pm 1\}}{min}\underset{j}{max}|\sum _{i\in S_j}\sigma (i)|$

$\min_{\sigma:[n] \rightarrow \{\pm 1\}}{\max_{j}{|\sum_{i \in S_j}{\sigma(i)}|}}$σ(Sj)=|∑i∈Sjσ(i)|

$\sigma (S_j)=|\sum _{i\in S_j}\sigma (i)|$

$\sigma(S_j) = |\sum_{i \in S_j}{\sigma(i)}|$σ(Sj)

$\sigma (S_j)$

$\sigma(S_j)$σ(Sj)

$\sigma (S_j)$

$\sigma(S_j)$

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

$s>n/2$

$s > n/2$G=([n],E)

$G=([n],E)$

$G = ([n], E)$δ1,…,δn

${\delta }_1,\dots ,{\delta }_n$

$\delta_1, \ldots, \delta_n$σ

$\sigma$

$\sigma$s

$s$

$s$ 1

$1$

$1$σi

${\sigma }_i$

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

$E[{\xi }_i(\sigma )]={\delta }_{i}s/n$

$E[\xi_i(\sigma)] = \delta_i s/n$Pr[ξi(σ)<0]≤exp(−Cδi(s/n−1/2)2)

$Pr[{\xi }_i(\sigma )<0]\le \exp (-C{\delta }_i(s/n-1/2{)}^2)$

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

$C$

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

$E[N(\sigma )]\ge n-\sum _i\exp (-C{\delta }_i(s/n-1/2{)}^2)$

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

$\sigma$

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

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

$s<n/2$

$s < n/2$σ

$\sigma$

$\sigma$σ

$\sigma$

$\sigma$s

$s$

$s$ξi(σ)

${\xi }_i(\sigma )$

$\xi_i(\sigma)$δi(2s/n−1)

${\delta }_i(2s/n-1)$

$\delta_i (2s/n - 1)$δi

${\delta }_i$

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

$Pr[{\xi }_i(\sigma )\ge 0]=\exp (-C{\delta }_i(2s/n-1{)}^2)\pm \eta (n)$

$\Pr[\xi_i(\sigma) \geq 0] =\exp(-C\delta_i(2s/n - 1)^2) \pm \eta(n)$η(n)

$\eta (n)$

$\eta(n)$nη(n)=o(n)

$n\eta (n)=o(n)$

$n\eta(n) = o(n)$ 취할 수 있습니다 .N(σ)≥∑iexp(−Cδi(2s/n−1)2)−o(n)

$N(\sigma )\ge \sum _i\exp (-C{\delta }_i(2s/n-1{)}^2)-o(n)$

$N(\sigma) \geq \sum_{i}{\exp(-C\delta_i(2s/n - 1)^2)} - o(n)$

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

${\delta }_i$

$\delta_i$s/n

$s/n$

$s/n$n/2

$n/2$

$n/2$

---

답변