Spectral radius and rainbow Hamiltonicity in bipartite graphs

This paper establishes tight sufficient conditions based on spectral radius and completely characterizes the corresponding extremal graphs for the existence of rainbow Hamilton paths and cycles in families of bipartite graphs using the bi-shifting technique.

The Gist

Here is an explanation of the paper "Spectral radius and rainbow Hamiltonicity in bipartite graphs," translated into simple language with creative analogies.

The Big Picture: The "Rainbow" Puzzle

Imagine you are organizing a massive party with 2n guests. You want to seat them all in a single, long line (a path) or a circle (a cycle) so that everyone is included exactly once. This is called a Hamiltonian path or cycle.

Now, imagine you have k different groups of friends (let's call them Team Red, Team Blue, Team Green, etc.). Each team has a list of who they are willing to sit next to.

• Team Red might say, "Alice can sit next to Bob."
• Team Blue might say, "Bob can sit next to Charlie."
• Team Green might say, "Charlie can sit next to Dave."

A Rainbow Hamilton Path is a seating arrangement where every single guest is included, and no two neighbors in the line come from the same team's list. It's like a rainbow: every step in the line uses a different color (team).

The big question the authors ask is: How "popular" or "connected" do these teams need to be to guarantee that such a perfect rainbow line exists?

The Secret Weapon: The "Spectral Radius"

To answer this, the authors don't just count the number of connections. They use a mathematical tool called the Spectral Radius.

Think of the Spectral Radius as a "Popularity Score" or a "Vibrancy Meter" for a group of friends.

• If a group has very few connections, the score is low.
• If everyone knows everyone, the score is high.
• Mathematically, it's calculated using a giant grid of numbers (a matrix) representing who knows whom. The "Spectral Radius" is the biggest number hidden inside that grid.

The paper's main discovery is: If every single team has a high enough "Popularity Score," you are guaranteed to find a rainbow line.

The Rules of the Game (Bipartite Graphs)

The paper focuses on a specific type of party: a Bipartite Graph.
Imagine the guests are split into two distinct rooms: Room X and Room Y.

• People in Room X can only sit next to people in Room Y.
• People in Room X cannot sit next to each other.
• People in Room Y cannot sit next to each other.

This is like a dance where partners must always be from opposite sides of the room. The authors figure out the exact "Popularity Score" needed for these two-room parties to guarantee a rainbow dance line.

The "Magic" Trick: Bi-Shifting

How did they prove this? They used a clever technique called "Bi-Shifting."

Imagine you have a messy pile of connections.

• Shifting is like tidying up the room. You take a connection between a "less popular" person and a "more popular" person and move it so the "more popular" person gets even more connections, while the "less popular" one loses some.
• The Magic: The authors proved that doing this "tidying up" never lowers the Popularity Score. In fact, it usually makes it higher!

By repeatedly "shifting" the connections until the graph is perfectly organized (a "shifted" graph), they could easily see if a rainbow line existed. If the organized version had a rainbow line, the original messy version did too. If the organized version didn't have one, they knew exactly what the "worst-case scenario" looked like.

The Results: When Does it Work?

The authors found the "tipping point" for the Popularity Score.

1. For Balanced Parties (Equal size rooms):
   If you have $2n$guests split evenly, and every team's Popularity Score is higher than a specific benchmark (related to a graph called$K_{n,n-1} \cup K_1$), then a rainbow line will exist.

   • The Exception: The only time it fails is if every single team is exactly the same, and that specific team is missing just enough connections to break the pattern.

2. For Nearly Balanced Parties (One room has one extra person):
   Similar rules apply, but the benchmark score is slightly different.

3. For Circles (Cycles):
   They also solved the problem for forming a circle (where the last person sits next to the first). They found the specific score needed to guarantee a rainbow circle, which is slightly higher than the score needed for a line.

The "Extremal" Graphs (The Losers)

The paper also identifies the "worst-case" scenarios. These are the specific graph shapes that have the highest possible Popularity Score without having a rainbow line.

• Think of these as the "Almost-Perfect" teams. They are so close to being able to form a rainbow line that they have the highest possible score, but they are missing just one tiny connection to make it work.
• The authors completely described what these "Almost-Perfect" teams look like.

Summary in One Sentence

If you have a group of teams trying to form a rainbow line of guests in a two-room dance, and every team is "popular" enough (based on a specific mathematical score), you are guaranteed to succeed—unless every team is identical and missing just the right connection to fail.

Why does this matter?
This helps mathematicians understand the limits of connectivity. It tells us exactly how much "social energy" (edges/connections) is required to guarantee complex structures (like visiting everyone exactly once) in a network, which has applications in computer science, logistics, and network design.

Technical Summary

Here is a detailed technical summary of the paper "Spectral radius and rainbow Hamiltonicity in bipartite graphs" by Meng Chen, Ruifang Liu, and Qixuan Yuan.

1. Problem Statement

The paper addresses Problem 1.1 (proposed by Joos and Kim) within the specific context of bipartite graphs. The core problem is to determine sufficient conditions, based on the spectral radius ($\rho(G)$), under which a family of graphs $\mathcal{G} = \{G_1, G_2, \dots, G_k\}$ sharing the same vertex set admits a rainbow Hamilton path or rainbow Hamilton cycle.

• Rainbow Subgraph: A subgraph is "rainbow" if its edges are selected such that no two edges belong to the same graph in the family $\mathcal{G}$.
• Context: While spectral conditions for rainbow matchings and Hamiltonicity in general graphs have been studied, this paper focuses specifically on the bipartite case, extending previous results by Li and Ning regarding single bipartite graphs to families of bipartite graphs.

The authors investigate two specific scenarios:

1. Balanced Bipartite Graphs: Graphs with partitions $(X, Y)$ where $|X| = |Y| = n$.
2. Nearly Balanced Bipartite Graphs: Graphs where $|X| - |Y| = 1$.

2. Methodology

The authors employ a combination of spectral graph theory and extremal combinatorics, utilizing the following key techniques:

• Bi-shifting (Kelmans Operation):

  • The paper adapts the classical "shifting" technique to bipartite graphs. A $(x, y)$-shift moves edges from a vertex $y$ to a vertex $x$ (where $x < y$) if $x$ and $y$ are in the same partition set.
  • Lemma 2.1 (Csikvári): The shifting operation does not decrease the spectral radius ($\rho(S_{xy}(G)) \ge \rho(G)$).
  • Lemma 2.2: If the graph is connected and the shift changes the graph structure, the spectral radius strictly increases.
  • This allows the authors to transform any family of graphs into a bi-shifted family (where edges are "packed" towards lower-indexed vertices) without losing the spectral radius condition. If the shifted family has a rainbow Hamilton path/cycle, the original family does too (Lemmas 2.3 and 2.4).

• Extremal Graph Characterization:

  • The authors identify specific extremal graphs that serve as thresholds. These are constructed using the operation $G_1 \sqcup G_2$, which adds all possible edges between the partitions of two bipartite graphs.
  • Key extremal graphs include:
    • $Q_n^0 = K_{n, n-1} \cup K_1$ (for balanced paths).
    • $T_n^0 = K_{n-1, n-1} \cup K_1$ (for nearly balanced paths).
    • $B_n^1 = K_{1, n-1} \sqcup K_{n-1, 1}$ (for balanced cycles).

• Spectral Inequalities:

  • The proof relies on comparing the spectral radius of the input graphs against the spectral radii of these extremal graphs.
  • Lemma 2.5 (Nosal): For bipartite graphs, $\rho(G) \le \sqrt{|E(G)|}$.
  • Quotient Matrices: Used to calculate exact spectral radii of the constructed extremal graphs (Lemma 2.6).

• Longest Path/Cycle Arguments:

  • The proofs assume the non-existence of a rainbow Hamilton path/cycle and derive a contradiction by constructing a longer rainbow path or cycle using the high degree properties implied by the spectral radius lower bounds.

3. Key Contributions and Results

The paper provides tight sufficient conditions for the existence of rainbow Hamilton structures in families of bipartite graphs.

A. Rainbow Hamilton Paths

Theorem 1.3 (Balanced Case):
Let $\mathcal{G} = \{G_1, \dots, G_{2n-1}\}$ be a family of balanced bipartite graphs on $2n$vertices. If$\rho(G_i) \ge \rho(K_{n, n-1} \cup K_1)$for all$i$, then$\mathcal{G}$admits a rainbow Hamilton path, **unless** all graphs are identical to the extremal graph$K_{n, n-1} \cup K_1$.

Theorem 1.4 (Nearly Balanced Case):
Let $\mathcal{G} = \{G_1, \dots, G_{2n-2}\}$ be a family of nearly balanced bipartite graphs on $2n-1$vertices. If$\rho(G_i) \ge \rho(K_{n-1, n-1} \cup K_1)$for all$i$, then$\mathcal{G}$admits a rainbow Hamilton path, **unless** all graphs are identical to$K_{n-1, n-1} \cup K_1$.

B. Rainbow Hamilton Cycles

Theorem 1.6 (Balanced Case):
Let $\mathcal{G} = \{G_1, \dots, G_{2n}\}$ be a family of balanced bipartite graphs on $2n$vertices. If$\rho(G_i) \ge \rho(K_{1, n-1} \sqcup K_{n-1, 1})$for all$i$, then$\mathcal{G}$admits a rainbow Hamilton cycle, **unless** all graphs are identical to$K_{1, n-1} \sqcup K_{n-1, 1}$.

Note: The paper does not provide a corresponding theorem for nearly balanced cycles, focusing instead on the balanced case for cycles.

4. Significance and Impact

1. Extension of Single-Graph Theory: The results generalize the classical spectral conditions for Hamiltonicity in single bipartite graphs (specifically the work of Li and Ning) to the rainbow setting involving families of graphs.
2. Tightness of Conditions: The conditions are tight. The authors explicitly characterize the extremal graphs (the "unless" cases) where the spectral radius condition is met, but the rainbow Hamilton structure fails. This provides a complete characterization of the spectral extremal graphs.
3. Methodological Advancement: The successful application of bi-shifting to rainbow problems in bipartite graphs demonstrates a powerful technique for handling spectral constraints in multi-graph families. It bridges the gap between structural extremal graph theory and spectral graph theory.
4. Solving Open Problems: The paper directly answers Problem 1.2 and Problem 1.3 posed in the introduction, providing definitive spectral answers for rainbow Hamiltonicity in bipartite settings.

5. Conclusion

This paper establishes that if the spectral radius of each graph in a family of bipartite graphs exceeds a specific threshold determined by a known extremal graph, the family is guaranteed to contain a rainbow Hamilton path or cycle. The only exceptions occur when every graph in the family is structurally identical to that specific extremal graph. This work significantly advances the understanding of rainbow subgraphs in spectral graph theory.