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 and 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: i. 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’. ii. 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 Q(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 t from each vertex, and extending to more than two colours. The extension to the closed t-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 (a1,..., ak) such that a1 < a2 < ··· < ak, analogous to (b,r) in the two colour case, then if a1 is sufficiently large and ak  a1 + 1 4 a2 1 10a 3 2 1 ⌫ , it is shown that an (a1,..., ak)-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  r2 2 5r3/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, ak need not necessarily be bounded in a1. Formally, there is some positive integer m = m(k) such that for every positive integer N, there exists a k-flip sequence (m, a2,..., ak) such that ak > N. Consequently, when considering four or more colours, there exists constructions where the first colour can locally win against the kth colour, no matter how big of a majority the kth colour has across the entire graph.