Flip Colouring of Graphs II

Basic Information

• Paper ID: 2401.02315
• Title: Flip Colouring of Graphs II
• Author: Xandru Mifsud (University of Malta)
• Classification: math.CO (Combinatorics)
• Publication Date/Conference: arXiv preprint, latest version (v3) November 4, 2025
• Paper Link: https://arxiv.org/abs/2401.02315

Abstract

This paper investigates two core problems in flip colouring of graphs. For positive integers $b, r$ (where $b < r$), a $(b,r)$-flip graph is a $(b+r)$-regular graph admitting a red/blue edge colouring such that each vertex has red degree $r$ and blue degree $b$, but the number of blue edges in each vertex's closed neighbourhood exceeds the number of red edges. The paper proves: (1) For integers $b, r$ satisfying $4 \leq b < r < b + 2\lfloor\frac{b+2}{6}\rfloor^2$, there exist small-scale $(b,r)$-flip graphs with $\Theta(b+r)$ vertices; (2) There exist $k$-flip sequences $(a_1, \ldots, a_k)$ (for $k > 4$) where $a_k$ can be arbitrarily large while $a_i$ remains constant for $1 \leq i < \frac{k}{4}$.

Research Background and Motivation

Problem Definition

Flip Colouring represents a new example of local-global phenomenon contrast in graph theory. Given positive integers $b < r$, a $(b,r)$-flip graph is a $(b+r)$-regular graph whose edge colouring satisfies:

1. Global Majority: Blue edges induce a $b$-regular subgraph, red edges induce an $r$-regular subgraph, so globally "red wins"
2. Local Flip: For each vertex $v$, the number of blue edges in its closed neighbourhood $N[v]$ exceeds the number of red edges, so locally "blue wins"

This local-global "flip" phenomenon exemplifies counterintuitive properties in graph theory.

Research Significance

1. Theoretical Importance: Flip colouring belongs to the study of local-global phenomena in graph theory, related to majority consensus problems and local majority effects
2. Combinatorial Structures: Explores existence and construction methods for regular graphs with special properties
3. Parameter Relationships: Investigates existence boundaries and minimum sizes of flip graphs under different parameters

Limitations of Prior Work

Previous work 4 established foundational theory:

• Theorem 1.1: Completely characterizes the existence of 2-flip graphs, proving $(b,r)$-flip graphs exist when $3 \leq b < r \leq \binom{b+1}{2}-1$
• Theorem 1.2: Provides an upper bound for minimum order $h(b,r)$, but this bound is relatively loose
• Theorem 1.3: Proves for 3-flip graphs that $a_3 < 2(a_1)^2$, i.e., maximum colour degree is quadratically bounded by minimum colour degree
• Theorem 1.4: Proves no such polynomial bounding relationship exists for $k > 3$

Paper Motivation

1. Improved Bounds: Seek tighter $h(b,r)$ bounds, particularly for specific parameter ranges
2. Quantifying Unboundedness: Precisely characterize $q(k)$—the maximum index such that the first $q(k)$ parameters in a $k$-flip sequence can remain constant while the last parameter grows arbitrarily

Core Contributions

The main contributions of this paper include:

1. Improved Construction Bound (Theorem 3.1): For $4 \leq b < r < b + 2\lfloor\frac{b+2}{6}\rfloor^2$, prove $h(b,r) \leq 8\lambda_{b,r}\left(2 + \lfloor\frac{r}{2}\rfloor + \lfloor\frac{b+2}{2}\rfloor - 2\lfloor\frac{b+2}{6}\rfloor\right)$ where $\lambda_{b,r} = \max\{1, (b \bmod 2) + (r \bmod 2)\}$. This significantly improves upon prior work.
2. Precise Bounds on $q(k)$ (Theorems 4.1 and 4.4): Prove for $k > 3$, $\max\left\{1, \lceil\frac{k}{4}\rceil - 1\right\} \leq q(k) < \begin{cases} \frac{k}{3} & \text{if } k \equiv 0 \pmod{3}\\ \lceil\frac{k}{2}\rceil & \text{otherwise} \end{cases}$
3. Development of Technical Tools:
   • Systematized products and packing operations on edge-coloured graphs (Section 2)
   • Established connections between Cayley graph constructions and sum-free sets
   • Developed construction methods based on additive combinatorics
4. Existence Results: Prove that for $k \geq 4$, there exist $k$-flip sequences where the first $\lfloor k/4 \rfloor$ parameters can remain constant while the last parameter grows arbitrarily

Methods in Detail

Task Definition

$k$-Flip Graph Problem: Given $k \geq 2$, a $d$-regular graph $G$, and an increasing sequence of positive integers $a_1 < a_2 < \cdots < a_k$ (satisfying $d = \sum_{j=1}^k a_j$), does there exist a $k$-edge colouring such that:

1. Edges of colour $j$ induce an $a_j$-regular subgraph (i.e., $\deg_j(v) = a_j$ for all $v \in V$)
2. For each vertex $v$, $e_k[v] < e_{k-1}[v] < \cdots < e_1[v]$ (colour edge counts in closed neighbourhood are decreasing)

Notation:

• $N_G(v)$: open neighbourhood of vertex $v$
• $N_G[v]$: closed neighbourhood of vertex $v$ ($N_G(v) \cup \{v\}$)
• $E_j^G(S)$: set of colour $j$ edges in the subgraph induced by $S$
• $e_j^G[v]$: number of colour $j$ edges in $N_G[v]$
• $\deg_j(v)$: number of colour $j$ edges incident to $v$

Core Technical Framework

1. Cayley Graphs and Sum-Free Set Construction (Section 3)

Cayley Graph Definition: Given a group $\Gamma$ and a connection set $S \subseteq \Gamma$ (inverse-closed and not containing the identity), the Cayley graph $\text{Cay}(\Gamma; S)$ has vertex set $\Gamma$ and edge set $\{\{g, gs\} : s \in S, g \in \Gamma\}$.

Sum-Free Set: For an abelian group $\Gamma$ and subset $A \subseteq \Gamma$, $A$ is sum-free if $2A \cap A = \emptyset$ (where $2A = A + A$).

Key Lemma (Proposition 2.3): Let $\Gamma$ be an abelian group and $R, B$ be disjoint inverse-closed subsets (not containing the identity). If $G = \text{Cay}(\Gamma; B)$ and $H = \text{Cay}(\Gamma; R)$ are monochromatic with colours 1 and 2 respectively, then in $\text{Cay}(\Gamma; B \cup R)$:

• $\deg_1(v) = \deg_G(v)$, $\deg_2(v) = \deg_H(v)$
• $e_1[v] - e_2[v] = (e_1^G[v] - e_2^H[v]) + (e_2^H(N_G(v)) - e_1^G(N_H(v)))$
• Key Property: If $(R + B) \cap R = \emptyset$ and $e_1^G[v] > e_2^H[v]$, then $e_1[v] > e_2[v]$

Construction Strategy (Theorem 3.1 Proof):

1. Choose modulus $n = 8(2 + \lfloor r/2 \rfloor + \lfloor(b+2)/2\rfloor - 2\lfloor(b+2)/6\rfloor)$
2. In the interval $(n/8, n/4)$ of $\mathbb{Z}_n$, select two disjoint integer intervals $R_0$ and $T_0$
3. Construct sets:
   • $R_1 = R_0 \cup R_0^{-1}$ (size $\lfloor r/2 \rfloor$)
   • $T_1 = T_0 \cup T_0^{-1}$, $B_1 = T_1 \cup 2T_2 \cup 2T_2^{-1}$ (where $T_2 \subseteq T_0$ has size $\lfloor(b+2)/6\rfloor$)
4. Sum-Free Verification (Lemma 3.2): By carefully choosing interval positions, ensure $(R_1 + B_1) \cap R_1 = \emptyset$
5. Edge Count Calculation: Using the fact that $2T_2$ is a sumset with $|2T_2| = 2|T_2| - 1$, precisely achieve $e_1^G[v] \geq b + 2\lfloor\frac{b+2}{6}\rfloor^2 > r = e_2^H[v]$
6. Parity Handling: Adjust parity of $|R|$ and $|B|$ by adding involutions (such as $n/2$) or using direct products $\mathbb{Z}_2 \times \mathbb{Z}_n$

2. Graph Products and Packing (Section 2)

Strong Product: $G \boxtimes H$ has vertex set $V(G) \times V(H)$, with edge $\{(u,v), (u',v')\}$ existing if and only if:

• $u = u'$ and $v \sim v'$ in $H$, or
• $v = v'$ and $u \sim u'$ in $G$, or
• $u \sim u'$ in $G$ and $v \sim v'$ in $H$

Lemma 2.1 (Strong Product Properties): In $G \boxtimes H$, $\deg_j((u,v)) = \deg_j^H(v) + \deg_j^G(u)(1 + \deg^H(v))$$e_j[(u,v)] = e_j^H[v](1 + \deg^G(u)) + e_j^G[u]\left(1 + \deg^H(v) + 2\sum_{i=1}^k e_i^H[v]\right)$

Cartesian Product: $G \square H$ contains only "coordinate-parallel" edges (no diagonal edges).

Lemma 2.2 (Cartesian Product Properties): $\deg_j((u,v)) = \deg_j^G(u) + \deg_j^H(v)$$e_j[(u,v)] = e_j^G[u] + e_j^H[v]$

3. Lower Bound Construction (Section 4.2)

Core Idea: Combine multiple small flip graphs to construct large flip graphs, keeping the first $q$ parameters fixed while allowing the last parameter to grow arbitrarily.

Lemma 4.3 (Combination Lemma): If there exists an $(a_1, \ldots, a_q)$-flip graph $F$ satisfying $e_j^F[v] = D_j$ for all $v$ and $1 \leq j \leq q$, and $D_q(k - 4q) > 1 + \xi q(q-1) + 5\binom{k-q}{2}$ where $\xi = \max_{1 \leq j < q}\{D_j - D_{j+1}\}$, then for any $N$, there exists an $(a_1, \ldots, a_k)$-flip graph with $a_k > N$.

Construction Steps:

1. Construct Cayley graph $K = \text{Cay}(\Gamma; S)$ where $S = \bigcup_{j=1}^{k-q-1} S_j$ is sum-free
2. Compute Cartesian product $F \square K$
3. Construct bipartite graph $H$ and compute strong product $H \boxtimes (F \square K)$
4. By choosing sufficiently large parameter $t$, ensure colour degrees and closed neighbourhood edge counts satisfy flip conditions

Theorem 4.4 (Existence Theorem): For $k > 3$ and $q = 1$ or $q < k/4$, there exist $a_1, \ldots, a_q \in \mathbb{N}$ such that for any $N$, there exists an $(a_1, \ldots, a_k)$-flip graph with $a_k > N$.

The proof utilizes Theorem 4.2 (existence of flip intervals) and Lemma 4.3 combinatorially.

4. Upper Bound Proof (Section 4.1)

Theorem 4.1 (Recolouring Argument): By regrouping $k$ colours into 2 or 3 colours and using known bounds for 2-flip and 3-flip graphs, prove:

• When $k \equiv 0 \pmod{3}$, merge every $k/3$ colours, obtaining a 3-flip graph, and by Theorem 1.3 get $a_k \leq 2k^2(a_{k/3})^2$
• Otherwise, merge the first $\lceil k/2 \rceil$ colours into one and remaining colours into another, obtaining a 2-flip graph, and by Theorem 1.1 get a quadratic bound

Technical Innovations

1. Deep Integration of Cayley Graphs and Sum-Free Sets: First systematic use of sum-free set theory from additive combinatorics to construct flip graphs, achieving $(R+B) \cap R = \emptyset$ through precise interval positioning
2. Multi-Level Graph Product Framework: Innovatively combines Cartesian and strong products, controlling closed neighbourhood edge counts through precise formulas in Lemmas 2.1 and 2.2
3. Parameter Optimization: In Theorem 3.1, by choosing $|T_2| = \lfloor(b+2)/6\rfloor$ and utilizing sumset property $|2T_2| = 2|T_2| - 1$, precisely achieve required edge count lower bounds
4. Parity Handling: Cleverly manages parity combinations of $b, r$ through involutions and direct product groups
5. Recolouring Technique: Theorem 4.1's proof demonstrates the power of colour merging in establishing upper bounds

Experimental Setup

This is a pure theoretical mathematics paper with no experiments or numerical computations. All results are rigorous mathematical proofs.

Theoretical Verification Methods

1. Constructive Proofs: Theorems 3.1 and 4.4 prove existence through explicit construction
2. Counting Arguments: Verify edge count conditions using combinatorial counting and group theory
3. Comparative Analysis: Figure 6 shows comparison between new and old bounds (for $b=11$ and $b=25$)

Numerical Examples

The paper provides concrete examples:

• Figure 1: Smallest known $(3,4)$-flip graph with 7 vertices
• Figure 5: Cayley graph construction sketch for $(b,r) = (6,7)$ with $n=56$

Experimental Results

Main Results

1. Improved Upper Bound (Theorem 3.1)

For $4 \leq b < r < b + 2\lfloor(b+2)/6\rfloor^2$, the new bound is: $h(b,r) \leq 8\lambda_{b,r}\left(2 + \lfloor\frac{r}{2}\rfloor + \lfloor\frac{b+2}{2}\rfloor - 2\lfloor\frac{b+2}{6}\rfloor\right) = O(b+r)$

In contrast, the old bound from Theorem 1.2 is: $h(b,r) \leq 2\left(r + b + 1 - \lfloor\frac{5+\sqrt{1+8(r-b)}}{2}\rfloor\right)\lfloor\frac{5+\sqrt{1+\sqrt{1+8(r-b)}}}{2}\rfloor$

Figure 6 Comparison ($b=11$ and $b=25$):

• For $b=11$, $r \in [13, 18]$: new bound approximately 50-250, old bound approximately 100-300
• For $b=25$, $r \in [30, 55]$: new bound approximately 200-800, old bound approximately 400-1400
• Improvement Magnitude: approximately 30%-50% reduction

Significance: First proof that $h(b,r) = \Theta(b+r)$ in this parameter range, achieving optimal asymptotic order.

2. Bounds on $q(k)$ (Equation 1)

$\max\left\{1, \lceil\frac{k}{4}\rceil - 1\right\} \leq q(k) < \begin{cases} \frac{k}{3} & \text{if } k \equiv 0 \pmod{3}\\ \lceil\frac{k}{2}\rceil & \text{otherwise} \end{cases}$

Concrete Examples:

• $k=4$: $0 \leq q(4) < 2$, so $q(4) \in \{0, 1\}$
• $k=5$: $1 \leq q(5) < 3$, so $q(5) \in \{1, 2\}$
• $k=6$: $1 \leq q(6) < 2$, so $q(6) = 1$
• $k=12$: $2 \leq q(12) < 4$, so $q(12) \in \{2, 3\}$

Significance:

• Lower bound shows at least the first $\lceil k/4 \rceil - 1$ parameters can remain constant
• Upper bound shows cannot exceed $k/3$ (or $\lceil k/2 \rceil$) parameters remaining constant
• Reveals essential constraint relationships between flip graph parameters

Theoretical Findings

1. Phase Transition Phenomenon:
   • For $k=2,3$: $h(a_1, \ldots, a_k)$ is quadratically bounded by $a_1$
   • For $k \geq 4$: $h(a_1, \ldots, a_k)$ cannot be polynomially bounded by $a_1, \ldots, a_{\lfloor k/4 \rfloor}$
2. Construction Tightness: Theorem 3.1's construction achieves $\Theta(b+r)$ order, possibly near-optimal
3. Parameter Dependency: Bounds on $q(k)$ show that as colour count increases, the proportion of fixable parameters decreases (from $1/2$ to $1/3$ to $1/4$)

Related Work

Origins of Flip Colouring

• 4 Caro, Lauri, Mifsud, Yuster, Zarb (2024): Introduced flip colouring concept, established foundational theory (Theorems 1.1-1.4)
• 8 Sheffield & Xi (2025): Investigated related problems

Local-Global Phenomena

• 1 Abdullah & Draief (2015): Global majority consensus from local majority voting on graphs
• 5 Caro & Yuster (2018): Impact of local majority on global majority in connected graphs
• 6 Fishburn, Hwang, Lee (1986): Whether local majority forces global majority

Additive Combinatorics

• 2 Alon & Kleitman (1990): Research on sum-free subsets
• 7 Green & Ruzsa (2005): Sum-free sets in abelian groups
• 9 Tao & Vu (2016): Survey on sum-free sets in groups

Advantages of this paper over prior work:

1. Significantly improves $h(b,r)$ bounds (in specific ranges)
2. First precise characterization of $q(k)$ (prior work only knew $q(k) \geq 1$)
3. Develops systematic Cayley graph construction methodology

Conclusions and Discussion

Main Conclusions

1. Small-Scale Constructions: For $4 \leq b < r < b + 2\lfloor(b+2)/6\rfloor^2$, there exist $(b,r)$-flip graphs with $O(b+r)$ vertices
2. Parameter Unboundedness: For $k > 4$, one can construct $k$-flip sequences where the first $\lfloor k/4 \rfloor$ parameters remain constant while the last parameter grows arbitrarily
3. Bound Tightness: $q(k)$ is sandwiched between $\Omega(k/4)$ and $O(k/2)$ (or $O(k/3)$)

Limitations

1. Parameter Range Restrictions: Theorem 3.1 applies only to $r < b + 2\lfloor(b+2)/6\rfloor^2$; for larger $r$ (approaching $\binom{b+1}{2}-1$), Theorem 1.2's bound remains superior
2. Gap in $q(k)$: Significant gap remains between lower bound $\lceil k/4 \rceil - 1$ and upper bound $\lceil k/2 \rceil$; exact value unknown
3. Non-Abelian Groups: Current constructions primarily rely on abelian groups; non-abelian cases insufficiently explored
4. Computational Complexity: Paper does not discuss algorithmic complexity of determining whether a given graph is a flip graph

Future Directions

The paper explicitly poses two open problems:

Problem 1: For $k \geq 4$, does there exist a minimum integer $p(k)$ ($k/4 \leq p(k) \leq k$) such that $h(a_1, \ldots, a_k)$ is polynomially bounded by $a_{p(k)}$?

Problem 2: For $3 \leq b < r \leq \binom{b+1}{2}-1$, what is the maximum value of $r$ for which $h(b,r) = \Theta(b+r)$?

Other potential directions:

• Improve bounds using non-abelian group constructions
• Precisely determine values of $q(k)$
• Study structural properties of flip graphs (diameter, connectivity)
• Algorithmic problems: efficient recognition and construction of flip graphs

In-Depth Evaluation

Strengths

1. Theoretical Depth:
   • Cleverly combines Cayley graphs, sum-free sets, graph products and other tools from multiple areas
   • Rigorous proof techniques with verifiable constructive proofs
   • Fine analysis of sum-free sets in Lemma 3.2 demonstrates deep combinatorial expertise
2. Result Significance:
   • Theorem 3.1 improves $h(b,r)$ from $O((r-b)^2)$ to $O(b+r)$ with substantial improvement
   • First two-sided bounds on $q(k)$, filling theoretical gaps
   • Figure 6's numerical comparison intuitively demonstrates improvements
3. Method Innovation:
   • Proposition 2.3's Cayley graph packing framework has broad applicability
   • Systematic treatment of graph products (Lemmas 2.1-2.2) applicable to other problems
   • Recolouring technique (Theorem 4.1) provides new upper bound proof strategy
4. Writing Clarity:
   • Clear structure with hierarchical organization from tools to applications
   • Figures (Figures 1-5) aid understanding of abstract constructions
   • Comprehensive notation system facilitates tracking complex proofs

Weaknesses

1. Limited Scope:
   • Theorem 3.1's parameter restriction $r < b + 2\lfloor(b+2)/6\rfloor^2$ is strict, not covering cases where $r$ approaches upper bound $\binom{b+1}{2}-1$
   • New results inapplicable when $b < 4$
2. Gap Issues:
   • Gap between lower and upper bounds for $q(k)$ remains $O(k/4)$; exact value unknown
   • No conjecture or numerical examples provided for exact $q(k)$ values
3. Construction Complexity:
   • Cayley graph construction requires careful group and connection set selection, potentially difficult in practice
   • Algorithm efficiency not discussed
4. Insufficient Non-Abelian Exploration:
   • Paper primarily relies on abelian group commutativity; non-abelian potential insufficiently explored
   • Lemma 3.2's proof crucially depends on commutativity; generalization to non-abelian groups requires new approaches
5. Limited Concrete Examples:
   • Beyond $(3,4)$ and $(6,7)$, few concrete small-parameter flip graph instances provided
   • No specific examples of $k \geq 4$ flip sequences given

Impact

1. Field Contributions:
   • Solidifies foundations of flip colouring theory, resolving core problems from prior work
   • Introduced Cayley graph methods may inspire research on other local-global problems
   • Bounds on $q(k)$ reveal essential complexity of multi-colour flipping
2. Practical Value:
   • Flip graphs may have applications in network design and consensus algorithms (though paper does not explore)
   • Construction methods provide new approaches for generating regular graphs with specific properties
3. Reproducibility:
   • All proofs are constructive, in principle fully reproducible
   • Lack of code or concrete algorithms; actual construction may require additional work
4. Follow-Up Research:
   • Problems 1 and 2 indicate clear research directions
   • Determining exact $q(k)$ values may require novel techniques
   • Extensions to non-regular graphs, directed graphs, etc. merit exploration

Applicable Scenarios

1. Theoretical Research:
   • Extremal combinatorics: studying regular graphs with special properties
   • Algebraic graph theory: colouring properties of Cayley graphs
   • Additive combinatorics: applications of sum-free sets in graph theory
2. Potential Applications:
   • Distributed systems: designing contradictions between local voting and global decisions
   • Network topology: network structures with local-global contrast properties
   • Coding theory: error-correcting codes based on regular graphs
3. Educational Value:
   • Exemplifies synthesis of multiple mathematical branches (group theory, combinatorics, graph theory)
   • Model for constructive proofs

Key References

4 Y. Caro, J. Lauri, X Mifsud, R. Yuster, and C. Zarb. Flip colouring of graphs. Graphs and Combinatorics, 40(106), 2024.

• Introduced flip colouring, established foundational theory

2 N. Alon and D. J. Kleitman. Sum-free subsets. In A Tribute to Paul Erdős, page 13–26. Cambridge University Press, 1990.

• Classical results on sum-free sets

7 B. Green and I. Z. Ruzsa. Sum-free sets in abelian groups. Israel Journal of Mathematics, 147(1):157–188, 2005.

• In-depth study of sum-free sets in abelian groups

Overall Assessment: This is a high-quality theoretical combinatorics paper that significantly advances flip colouring theory through clever constructions and refined analysis. The combination of Cayley graphs and sum-free sets demonstrates the power of cross-disciplinary methods, with improved bounds on $h(b,r)$ and $q(k)$ having important theoretical value. Despite parameter range restrictions and remaining gaps, the paper establishes solid foundations for subsequent research with challenging open problems. Recommended for researchers interested in extremal graph theory, algebraic graph theory, and additive combinatorics.