English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Suppose in a graph $G$ vertices can be either red or blue. Let $k$ be odd. Ateach time step, each vertex $v$ in $G$ polls $k$ random neighbours and takesthe majority colour. If it doesn't have $k$ neighbours, it simply polls all ofthem, or all less one if the degree of $v$ is even. We study this protocol ongraphs of a given degree sequence, in the following setting: initially eachvertex of $G$ is red independently with probability $\alpha < \frac{1}{2}$, andis otherwise blue. We show that if $\alpha$ is sufficiently biased, then withhigh probability consensus is reached on the initial global majority within$O(\log_k \log_k n)$ steps if $5 \leq k \leq d$, and $O(\log_d \log_d n)$ stepsif $k > d$. Here, $d\geq 5$ is the effective minimum degree, the smallestinteger which occurs $\Theta(n)$ times in the degree sequence. We further showthat on such graphs, any local protocol in which a vertex does not changecolour if all its neighbours have that same colour, takes time at least$\Omega(\log_d \log_d n)$, with high probability. Additionally, we demonstratehow the technique for the above sparse graphs can be applied in astraightforward manner to get bounds for the Erd\H{o}s-R\'enyi random graphs inthe connected regime.

Global Majority Consensus by Local Majority Polling on Graphs of a Given Degree Sequence