Rainbow independent sets in graphs with maximum degree two

Yue Ma, Xinmin Hou, Jun Gao, Boyuan Liu, Zhi YinarXiv 2021 · DOI · arXiv

This paper, published in the field of combinatorial graph theory, explores the conditions under which a collection of "independent sets" in a graph can yield a "rainbow" independent set. It specifically focuses on graphs with a maximum degree of two—essentially collections of paths and cycles.

TL;DR

The authors provide new proofs and bounds for two major conjectures regarding rainbow independent sets in simple graphs (paths and cycles). Most notably, they prove that for sufficiently large cycles, a collection of $n$ independent sets of size $n$ is guaranteed to contain a rainbow independent set of size $n$.

What Problem Does This Paper Address?

In graph theory, an independent set is a collection of vertices where no two vertices are connected by an edge. Think of it as a group of people who are all "socially distanced" from one another.

A rainbow set arises when you have several different collections (or "colors") of vertices. A rainbow set picks exactly one vertex from each collection. The challenge is finding a rainbow independent set: a set that is both "rainbow" (one from each color) and "independent" (no two vertices are neighbors).

The authors tackle two conjectures proposed by Aharoni et al. in 2019:

  1. Conjecture (i): For any graph with a maximum degree of two, if you have $n-1$ independent sets of size $n$, you can always find a rainbow independent set of size $n-1$.
  2. Conjecture (ii): For a cycle graph of length $t$ (where $t \ge 2n+1$), if you have $n$ independent sets of size $n$, you can always find a rainbow independent set of size $n$.

While these graphs (paths and cycles) seem simple, proving these "rainbow" properties is notoriously difficult and sits at the intersection of graph theory and topology.

Methods

The researchers employed several combinatorial strategies to push the boundaries of these conjectures:

  • Greedy Rainbow Independent Set (GRIS) Algorithm: The authors utilize a greedy approach to construct rainbow sets. The algorithm iterates through vertices in a specific order, adding a vertex to the rainbow set if it maintains independence and its "color" (the set it belongs to) hasn't been used yet.
  • Structural Induction: To handle complex graphs consisting of multiple components, the authors used induction on the number of components, breaking the problem down into smaller, manageable sub-graphs.
  • Double-Counting Arguments: In proving the bounds for large cycles, the authors used double-counting to relate the number of available vertices to the number of "colors" required, establishing a contradiction if a rainbow set were not to exist.
  • 2-Jump Analysis: They introduced and analyzed "2-jump independent sets"—a specific configuration where vertices in a cycle are spaced exactly two units apart.

Datasets

As a theoretical mathematics paper, this work does not use external datasets. The "data" consists of the logical structures of graphs (specifically cycles $C_t$ and paths $P_t$) and the formal definitions of independent sets.

Key Insights and Ideas

  • The Quadratic Threshold: One of the most significant insights is the proof of Conjecture (ii) for "large" cycles. While the conjecture suggests it holds for $t \ge 2n+1$, the authors proved it definitively for $t \ge \frac{1}{3}n^2 + \frac{44}{9}n$. This provides a solid upper bound on how large a cycle needs to be to guarantee the rainbow property.
  • 2-Jump Sets as a Base Case: The authors realized that in a cycle of length $2n+1$, any independent set of size $n$ must be a 2-jump set. By proving the conjecture for 2-jump sets specifically, they provided a bridge to understanding the more general cases.
  • Linking the Conjectures: The paper demonstrates a formal link between the two conjectures. They proved that if the cycle conjecture (ii) is true, then the general degree-2 graph conjecture (i) must also be true for graphs with a limited number of even-length cycles.

Key Results

  • Theorem 1.4: Proved that for 2-regular graphs (collections of cycles) with a total vertex count of $2n-1$ or $2n$, the minimum number of sets needed to find a rainbow $(n-1)$-set is indeed $n-1$.
  • Theorem 1.6: Established that the cycle conjecture holds whenever the cycle length $t$ is at least roughly $n^2/3$.
  • Theorem 1.7: Proved that the conjecture holds for any cycle $t \ge 2n+1$ if we restrict the family of sets to "2-jump" independent sets.

Limitations and Future Work

The primary limitation is the gap between the conjectured bound ($t \ge 2n+1$) and the proven bound ($t \approx n^2/3$). While the authors proved the conjecture for "large" cycles, the behavior for "medium-sized" cycles remains an open question.

Additionally, the proof linking the two conjectures (Theorem 1.5) is currently limited to graphs with four or fewer even cycles. Extending this to an arbitrary number of even cycles remains a promising direction for future research in combinatorial optimization and graph theory.

Summary updated

Abstract

Given a graph $G$, let $f_{G}(n,m)$ be the minimal number $k$ such that every $k$ independent $n$-sets in $G$ have a rainbow $m$-set. Let $\mathcal{D}(2)$ be the family of all graphs with maximum degree at most two. Aharoni et al. (2019) conjectured that (i) $f_G(n,n-1)=n-1$ for all graphs $G\in\mathcal{D}(2)$ and (ii) $f_{C_t}(n,n)=n$ for $t\ge 2n+1$. Lv and Lu (2020) showed that the conjecture (ii) holds when $t=2n+1$. In this article, we show that the conjecture (ii) holds for $t\ge\frac{1}{3}n^2+\frac{44}{9}n$. Let $C_t$ be a cycle of length $t$ with vertices being arranged in a clockwise order. An ordered set $I=(a_1,a_2,\ldots,a_n)$ on $C_t$ is called a $2$-jump independent $n$-set of $C_t$ if $a_{i+1}-a_i=2\pmod{t}$ for any $1\le i\le n-1$. We also show that a collection of 2-jump independent $n$-sets $\mathcal{F}$ of $C_t$ with $|\mathcal{F}|=n$ admits a rainbow independent $n$-set, i.e. (ii) holds if we restrict $\mathcal{F}$ on the family of 2-jump independent $n$-sets. Moreover, we prove that if the conjecture (ii) holds, then (i) holds for all graphs $G\in\mathcal{D}(2)$ with $c_e(G)\le 4$, where $c_e(G)$ is the number of components of $G$ isomorphic to cycles of even lengths.
BibTeX
@misc{ma2021rainbow,
  author = {Yue Ma and Xinmin Hou and Jun Gao and Boyuan Liu and Zhi Yin},
  title = {{Rainbow independent sets in graphs with maximum degree two}},
  year = {2021},
  eprint = {2108.02520},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2108.02520},
}

Loading related content...

Figure