Local v. global majority : an edge colouring approach

Abstract

We introduce a new problem on local v. global majority in graphs, concerning edge-colourings. In particular, we ask for which positive integers b, r, such that b < r, does a b + r regular graph G exist with an edge colouring f : E(G) 鈫� {blue, red} satisfying the following: The subgraphs induced by the blue and red edges are b and r regular respectively, resulting in a global majority ordering since b < r, where across the entire graph 'red' wins against 'blue'. On the other hand, for every vertex v, the number of blue edges in the closed neighbourhood of v is greater than the number of red edges, resulting in a locally opposite majority ordering where locally 'blue' wins against 'red'. We term such a graph as a (b, r)-flip graph, due to the local v. global majority flip they demonstrate. We show that such edge-coloured graphs do exist, namely for when the difference between b and r is not too great, as intuition would suggest. In particular we show that a (b, r)-flip graph exists if, and only if, 3 鈮� b < r < 鈱�(b + 1)/2鈱�. We also establish a number of bounds on the number of vertices h(b, r) of the smallest (b, r)-flip graph. Somewhat surprisingly, we establish that such graphs can be very small, illustrating cases where h(b, r) is 螛(b + r). To establish these results, we provide a number of different construction techniques using: edge-coloured graph products, graph packings, and Cayley graphs. Two natural extensions of this problem are considered: extending the local flip up to the closed neighbourhood at a distance f from each vertex, and extending to more than two colours. The extension to the closed f-neighbourhood is considered briefly, offering two distinct techniques of constructing such graphs. The extension to more than two colours is considered more exhaustively. Given a colour-degree sequence (a鈧�, ..., a鈧�) such that a鈧� < a鈧� < ... < a鈧�, analogous to (b, r) in the two-colour case, then if a鈧� is sufficiently large and a鈧� 鈮� a鈧� + 鈱�1/4 (a鈧伮� - 10a鈧乛(3/2))鈱�, it is shown that an (a鈧�, ..., a鈧�)-flip graph exists. The proof is constructive, and relates to another (existence) problem of interest which we briefly consider. We show that for every integer r 鈮� 1 and integer c, 0 鈮� c 鈮� r虏/2 - 5r^(3/2), there exists an r-regular graph with the property that for every vertex v, the open neighbourhood of v contains precisely c edges. Here we outline a number of connections with other well-known families of graphs, such as those with constant link and (r, b)-regular graphs. We conclude with a somewhat surprising result, namely that unlike the case of two colours, for k 鈮� 4 colours, a鈧� need not necessarily be bounded in a鈧�. Formally, there is some positive integer m = m(k) such that for every positive integer N, there exists a k-flip sequence (m, a鈧�, ..., a鈧�) such that a鈧� > N. Consequently, when considering four or more colours, there exists constructions where the first colour can locally win against the k岬検� colour, no matter how big of a majority the k岬検� colour has across the entire graph.