Source author record

Michel Bode

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.PR

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Local majority dynamics on preferential attachment graphs

Suppose in a graph $G$ vertices can be either red or blue. Let $k$ be odd. At each time step, each vertex $v$ in $G$ polls $k$ random neighbours and takes the majority colour. If it doesn't have $k$ neighbours, it simply polls all of them, or all less one if the degree of $v$ is even. We study this protocol on the preferential attachment model of Albert and Barabási, which gives rise to a degree distribution that has roughly power-law $P(x) \sim \frac{1}{x^{3}}$ , as well as generalisations which give exponents larger than $3$ . The setting is as follows: Initially each vertex of $G$ is red independently with probability $α< \frac{1}{2}$ , and is otherwise blue. We show that if $α$ is sufficiently biased away from $\frac{1}{2}$ , then with high probability, consensus is reached on the initial global majority within $O(\log_d \log_d t)$ steps. Here $t$ is the number of vertices and $d \geq 5$ is the minimum of $k$ and $m$ (or $m-1$ if $m$ is even), $m$ being the number of edges each new vertex adds in the preferential attachment generative process. Additionally, our analysis reduces the required bias of $α$ for graphs of a given degree sequence studied by the first author (which includes, e.g., random regular graphs).

preprint2012arXiv

Good edge-labelings and graphs with girth at least five

A good edge-labeling of a graph [Araújo, Cohen, Giroire, Havet, Discrete Appl. Math., forthcoming] is an assignment of numbers to the edges such that for no pair of vertices, there exist two non-decreasing paths. In this paper, we study edge-labeling on graphs with girth at least 5. In particular we verify, under this additional hypothesis, a conjecture by Araújo et al. This conjecture states that if the average degree of G is less than 3 and G is minimal without an edge-labeling, then G \in {C_3,K_{2,3}}. (For the case when the girth is 4, we give a counterexample.)

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.