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.