this is for holding javascript data
ZoƩ Christoff edited section_Colorability_and_unanimity_In__.tex
about 8 years ago
Commit id: bb9e27363a08339a69079fe7750dbafee4c05949
deletions | additions
diff --git a/section_Colorability_and_unanimity_In__.tex b/section_Colorability_and_unanimity_In__.tex
index 17de44d..a18effb 100644
--- a/section_Colorability_and_unanimity_In__.tex
+++ b/section_Colorability_and_unanimity_In__.tex
...
Recall that a graph is properly two-colored if no node has a successor of the same color. The above result can be reformulated as follows: if for some $j$, $O$ properly colors $G_{p_j}$, then $O$ does not converge. In fact, it is easy to see that in such a case, all agents will change their opinion on $p_j$ at every step, entering an oscillation of size $2$. Note that this limit case of opinion distribution is yet another special case of DeGroot processes, another intersection between the frameworks propositional opinion diffusion and DeGroot.
The possibility of this extreme distribution of opinions relies on the graph $G_{p_j}$ being
$2$-colorable. $2$-colorable, which is equivalent to $G_{p_j}$ not containing any cycle of odd length. However,
this non $2$-colorability is not a necessary condition for non-convergence of
UPs: UPs in general: a simple cycle of three agents, for instance, is not $2$-colorable but (as we have shown above with BDPs) does not
necessarily converge. guarantee convergence.
Nevertheless, there is a class of (non-necessarily functional) influence profiles for which begin $2$-colorable is a necessary condition of
non-convergence: non-convergence, the
class of \emph{symmetric} influence
graphs. profiles:
\begin{proposition}
Let $\G=(G_{p_1},\dots,G_{p_m})$ be a symmetric
(and non-necessarily functional) influence profile and $\O=(O_1,\dots,O_n)$ be an opinion profile.
The opinion diffusion under the unanimity rule converges for $\O$ on $\G$ iff:
\begin{itemize}
\item[] For all $j\in\{1,\ldots,m\}$, $G_pj$ is not $2$-colorable, OR