ZoĆ© Christoff edited section_Unanimity_and_2_colorability__.tex  about 8 years ago

Commit id: 9ba80f59efcdb317052f5fb56af1f4a1ba57f553

deletions | additions      

       

Let $p\in\Atoms$ and $C$ be connected component of $G_p$ with diameter $k$. Let $C$ contain a cycle of length $c$, with $c$ odd. Let $O$ be an arbitrary opinion profile. Since $c$ is odd, there exist $i,j\in S$ such that $j\in R_p(i)$ and $O_i(p)=O_j(p).$ By definition of UP, this implies that $O_i(p)$ is stable, and that all agents with distance $\leq k$ will be stable after at most $k$ steps. The other direction follows from \ref{lemma:symm.opinionUP}.   \end{proof}  The above characterizes the influence profiles which guarantee that any opinion profile converge, but, as we have done above for the BDPs, we can also characterize the pairs of(symmetric and serial)  influence profiles and opinion profiles which converge: \begin{theorem}\label{thm:fullUP}  Let $\G$ be a symmetric (serial and non-necessarily functional) influence profile and $\O$ be an opinion profile.  The UP converges for $\O$ on $\G$ iff: iff, for all $p\in\Atoms$, and all connected component $C$ of $G_p$:  \begin{itemize}  \item[] For all $p\in\Atoms$, $G_p$ $C$  is not $2$-colorable, or \item[] There It  is no $p\in\Atoms$, such that: not the case that  for all $i,j\in\N$ if $i,j\in\C$ such that  $j\in R_p(i)$, $O_i(p)\neq O_j(p)$. \end{itemize}  \end{theorem}  \begin{proof}