Improved Bounds for the Ultimate Independence Ratio of Odd Wheels

Basic Information

• Paper ID: 2511.18747
• Title: Improved Bounds for the Ultimate Independence Ratio of Odd Wheels
• Authors: Alexander Clow, Hitesh Kumar, Shivaramakrishna Pragada (Simon Fraser University)
• Classification: math.CO (Combinatorics), math.OC (Optimization and Control)
• Submission Date: Submitted to arXiv on November 24, 2025
• Paper Link: https://arxiv.org/abs/2511.18747

Abstract

This paper investigates the ultimate independence ratio of graphs. For a graph $G$, the ultimate independence ratio is defined as $\mathscr{I}(G) = \lim_{k\rightarrow\infty} \frac{\alpha(G^{\Box k})}{|V(G)|^k}$, where $\alpha(G^{\Box k})$ is the independence number of the $k$-fold Cartesian product of $G$. Hahn, Hell, and Poljak (1995) proved that $\frac{1}{\chi(G)} \leq \mathscr{I}(G) \leq \frac{1}{\omega(G)}$ and conjectured that all wheel graphs $W_n$ satisfy $\mathscr{I}(W_n) = \frac{1}{\chi(W_n)}$. This paper makes significant progress on this 30-year-old unsolved conjecture: it is proved that for odd wheels with $t \geq 3$, $\mathscr{I}(W_{2t+1}) \leq \frac{4t^2+6t}{3(2t+2)^2} < \frac{1}{3}$; for the 5-wheel, the upper bound is improved to $\mathscr{I}(W_5) \leq \frac{1019}{3888} \approx 0.262$ (previous bound was $\frac{11}{41} \approx 0.268$).

Research Background and Motivation

Problem Background

1. Definition and Significance of Ultimate Independence Ratio:
   • The ultimate independence ratio characterizes the asymptotic behavior of maximum independent sets in Cartesian powers of graphs
   • Closely related to Shannon capacity and graph homomorphism theory
   • Hell, Yu, and Zhou (1994) proved that the sequence $\{i(G^{\Box k})\}$ is monotone decreasing and convergent
2. Basic Theoretical Bounds:
   • Hahn, Hell, and Poljak proved: $\frac{1}{\chi(G)} \leq \mathscr{I}(G) \leq \frac{1}{\chi_f(G)} \leq \frac{1}{\omega(G)}$
   • For weakly perfect graphs ($\chi = \omega$), the ultimate independence ratio can be determined
   • Zhu (1996) constructed graphs satisfying $\frac{1}{\chi(G)} < \mathscr{I}(G) < \frac{1}{\chi_f(G)}$, showing that equality does not hold in general
3. Special Properties of Wheel Graphs:
   • Even wheels $W_{2t}$: $\chi(W_{2t}) = \omega(W_{2t}) = 3$, thus $\mathscr{I}(W_{2t}) = \frac{1}{3}$
   • Odd wheels $W_{2t+1}$: $\chi(W_{2t+1}) = 4$, $\omega(W_{2t+1}) = 3$, thus $\frac{1}{4} \leq \mathscr{I}(W_{2t+1}) \leq \frac{1}{3}$
   • Core Conjecture (Conjecture 1.2): $\mathscr{I}(W_{2t+1}) = \frac{1}{4}$

Research Motivation

1. 30-Year-Old Open Problem: Hahn revisited this problem at the Canadian Mathematical Society Winter Conference in 2024
2. Smallest Unknown Case: The 5-wheel $W_5$ is the smallest graph with unknown ultimate independence ratio
3. Theoretical Importance: May provide insights for the general theory of ultimate independence ratio
4. Computational Challenge: Estimating $\mathscr{I}(W_{2t+1})$ to arbitrary precision using known methods is algorithmically infeasible

Core Contributions

The main contributions of this paper include:

1. New General Upper Bound Method (Theorem 1.3):
   • For graphs $G$ containing a $k$-clique, proves $\mathscr{I}(G) \leq \frac{\alpha(G^{\Box \ell} \Box K_k)}{k|V(G)|^\ell}$
   • Generalizes results of Hahn, Hell, and Poljak on vertex-transitive graphs
2. Improved Bounds for Large Odd Wheels (Theorem 1.5):
   • For all $t \geq 3$, proves $\mathscr{I}(W_{2t+1}) \leq \frac{4t^2+6t}{3(2t+2)^2}$
   • First non-trivial theoretical bound for large odd wheels (without computer assistance)
3. Exact Computation of Critical Values (Theorem 1.6):
   • Computer-assisted proof that $\alpha(W_5^{\Box 3} \Box K_3) = 170$
   • Combines structural arguments and integer programming
4. Improved Bound for 5-Wheel (Theorem 1.7):
   • Proves $\mathscr{I}(W_5) \leq \frac{1019}{3888}$
   • First improvement of this bound in 30 years
5. Computational Framework:
   • Develops systematic methodology combining theoretical analysis and computational verification
   • All code is publicly available and reproducible

Detailed Methods

Task Definition

Core Task: Establish tighter upper bounds for the ultimate independence ratio $\mathscr{I}(W_{2t+1})$ of odd wheel graphs.

Technical Challenges:

• Direct computation of $\alpha(G^{\Box k})$ is infeasible for large $k$
• Requires combining theoretical estimates with finite computation
• Standard methods fail for odd wheels where chromatic number differs from clique number

Method Architecture

The paper employs a three-level progressive approach:

1. Theoretical Framework: General Upper Bound Theorem (Theorem 1.3)

Core Idea: Utilize clique structure in graphs to improve bounds.

Theorem Statement: If $G$ contains a $k$-clique, then for any $\ell \geq 1$: $\mathscr{I}(G) \leq \frac{\alpha(G^{\Box \ell} \Box K_k)}{k|V(G)|^\ell}$

and $\mathscr{I}(G) = \lim_{\ell \to \infty} \frac{\alpha(G^{\Box \ell} \Box K_k)}{k|V(G)|^\ell}$

Proof Technique:

1. Recurrence Relation: For maximum independent set $I$ in $G^{\Box (p+1)}$, decompose by last coordinate: $\alpha(G^{\Box (p+1)}) \leq \alpha(G^{\Box p} \Box K_k) + (n-k)\alpha(G^{\Box p})$
2. Limit Analysis: $i(G^{\Box (p+1)}) \leq \frac{\alpha(G^{\Box \ell} \Box K_k)}{n^{\ell+1}} \sum_{i=0}^{p-\ell} \left(\frac{n-k}{n}\right)^i + \frac{(n-k)^{p-\ell+1}\alpha(G^{\Box \ell})}{n^{p+1}}$
3. Geometric Series Summation: As $p \to \infty$, the second term vanishes and the first term converges to $\frac{\alpha(G^{\Box \ell} \Box K_k)}{kn^\ell}$

Application to Odd Wheels (Corollary 1.4): Since $W_{2t+1}$ contains $K_3$, taking $k=3$ yields: $\mathscr{I}(W_{2t+1}) \leq \frac{\alpha(W_{2t+1}^{\Box \ell} \Box K_3)}{3(2t+2)^\ell}$

2. Structural Analysis: Independent Sets in Cartesian Products of Odd Wheels (Section 4)

Key Lemma (Lemma 4.2): If $I$ is an independent set in $W_{2t+1}^{\Box 2}$ and $I_*$ is the part involving the central vertex, then if $|I_* \setminus \{(w_*, w_*)\}| = k$: $|I| \leq t(2t+1) + 1 + (1-t)k$

Exact Value (Proposition 4.3): $\alpha(W_{2t+1}^{\Box 2}) = (2t+1)t + 1$

Proof Strategy:

1. Constructive Lower Bound: Explicitly construct an independent set of size $(2t+1)t+1$
2. Upper Bound Proof: Using Lemma 4.2, if $|I| > (2t+1)t+1$, then $k \geq 2$, leading to contradiction

Estimate for Ternary Product: For $W_{2t+1}^{\Box 2} \Box K_3$, let $S_i$ denote the part corresponding to the $i$-th vertex of $K_3$. Through careful counting arguments: $\alpha(W_{2t+1}^{\Box 2} \Box K_3) \leq 4t^2 + 6t$

This directly yields Theorem 1.5.

3. Computational Method: Integer Programming and Branch-and-Bound (Sections 5-6)

Integer Programming Formulation: Standard independent set IP: $\max \sum_{v \in V(G)} x_v \quad \text{s.t.} \quad B(G)^T x \leq \mathbf{1}, \quad x \in \{0,1\}^{|V(G)|}$

Improved Formulation for Cartesian Products (Program 7): For $G \Box H$, introduce variable vectors $x_v$ ($v \in V(H)$): $\max \sum_{v \in V(H)} \mathbf{1}^T x_v$$\text{s.t.} \quad B(G)^T x_v \leq \mathbf{1} \quad \forall v \in V(H)$$x_u + x_v \leq \mathbf{1} \quad \forall uv \in E(H)$

Advantages: Allows convenient addition of structural constraints (e.g., $\mathbf{1}^T x_v \geq k$) to study specific types of independent sets.

Branch-and-Bound Strategy (Lemma 6.2-6.4): For $W_5^{\Box 3}$, systematically enumerate possible independent set size distributions:

• Let $I_i$ denote the part in the $i$-th coordinate layer
• Build decision tree by sizes $|I_*|, |I_0|, \ldots, |I_4|$
• Verify feasibility at each node using IP

Key Computational Results:

• Lemma 6.2(v): If $|I| = 58$ in $W_5^{\Box 3}$, then (WLOG) $\mathbf{i} \in \{(9,11,9,11,9,9), (8,11,9,10,10,10)\}$
• Lemma 6.4: Eliminates existence of independent sets of size 171 in $W_5^{\Box 3} \Box K_3$

Technical Innovations

1. Theoretical Innovation:
   • Theorem 1.3 provides new methodology utilizing clique structure, independent of vertex-transitivity
   • Limit equality $\mathscr{I}(G) = \lim_{\ell \to \infty} \frac{\alpha(G^{\Box \ell} \Box K_k)}{k|V(G)|^\ell}$ provides new computational pathway
2. Structural Insights:
   • Lemma 4.2 establishes precise relationship between independent set size and central vertex usage
   • Identifies key structural patterns of independent sets in $W_{2t+1}^{\Box 2} \Box K_3$
3. Computational Methodology:
   • Organically combines theoretical bounds with finite computation
   • Hybrid strategy of branch-and-bound + IP effectively handles exponential search space
   • Utilizes automorphism group to simplify fractional chromatic number computation (Theorem 5.1)
4. Reproducibility:
   • All computational steps have corresponding code file links
   • Provides detailed verification pathways

Experimental Setup

Computational Environment

• Hardware: Authors' personal laptop
• Software:
  • Python with Gurobi optimization solver (integer programming)
  • SageMath (basic graph theory computation)
  • Open source code: https://github.com/Shivaramkratos/Ultimate_Independence_ratio_Python_Gurobi_code

Computational Tasks

1. Independence Number Computation:
   • $\alpha(W_5^{\Box 2}) = 11$
   • $\alpha(W_5^{\Box 3}) = 58$
   • $\alpha(W_5^{\Box 2} \Box K_3) = 29$
   • $\alpha(W_5^{\Box 3} \Box K_3) = 170$ (main contribution)
2. Fractional Chromatic Number Computation:
   • Use linear programming to compute $\chi_f(W_{2t+1}^{\Box 2})$
   • Simplify constraints through orbits of maximum independent sets
3. Upper Bound Verification:
   • $\alpha(W_5^{\Box 4}) \leq 343$
   • $\alpha(W_5^{\Box 4} \Box K_3) \leq 1019$

Verification Strategy

Branch-and-Bound Tree:

• For example, verification of Lemma 6.2(v) involves 9 leaf nodes
• Each leaf node corresponds to an independent IP instance
• All infeasible cases have corresponding code file verification

Case Analysis:

• Symmetry Utilization: Reduce cases to check via automorphism group of $W_{2t+1}$
• Structural Pruning: Use $\alpha(W_{2t+1}^{\Box 2} \Box K_3) = 29$ to eliminate certain size combinations

Experimental Results

Main Results

1. Theoretical Bounds for Large Odd Wheels (Table 1 & Theorem 1.5)

Key Observations:

• All new bounds significantly improve previous bounds $\frac{t}{3t+1}$
• For $t \geq 3$, general bound $\frac{4t^2+6t}{3(2t+2)^2}$ asymptotically approaches $\frac{1}{3}$ from below
• Still has gap with conjectured value $\frac{1}{4}$

2. Exact Computation for W₅ (Theorem 1.6)

Core Result: $\alpha(W_5^{\Box 3} \Box K_3) = 170$

Proof Structure:

• Lower Bound: Figure 4 exhibits explicit independent set of size 170
• Upper Bound: Lemmas 6.2-6.5 systematically eliminate possibility of size ≥ 171

Key Lemma Verification:

• Lemma 6.2: 5 assertions involving approximately 15 IP instances
• Lemma 6.3: Handles size 57 case, 6 cases
• Lemma 6.4: Handles boundary case of size 170-171, approximately 15 IP instances
• Lemma 6.5: Final synthesis, confirms only two possible size distributions

3. Recursive Upper Bounds for W₅ (Theorems 6.6-6.7)

Theorem 6.6: $\alpha(W_5^{\Box 4}) \leq 343$

Proof Strategy:

• Assume $|I| = 344$, decompose by coordinate layers
• Use $\alpha(W_5^{\Box 3} \Box K_3) = 170$ to establish constraints
• Derive contradiction: requires $|I_*| = 54$ and all $|I_i| = 58$
• But this requires certain layers to satisfy impossible size combinations (Lemma 6.4)

Theorem 6.7: $\alpha(W_5^{\Box 4} \Box K_3) \leq 1019$

Proof Strategy:

• Assume $|S| = 1020$, implying all 6 coordinate layers achieve maximum value 170
• Use Lemma 6.5, each layer must be specific size distribution
• By pigeonhole principle, at least one coordinate has two different $K_3$ parts not achieving maximum
• Results in total $\leq 1019$

Final Upper Bound: $\mathscr{I}(W_5) \leq \frac{1019}{3888} \approx 0.26217$

This improves the 1995 bound $\frac{11}{41} \approx 0.26829$ by approximately 2.3%.

Fractional Chromatic Number Computation

Method (Section 5.2): Compute $\frac{1}{\chi_f(G)}$ via LP: $\min z \quad \text{s.t.} \quad \sum_v x_v = 1, \quad \sum_{v \in I} x_v \leq z \quad \forall I \in \mathcal{I}_{\max}(G)$

Automorphism Group Simplification (Theorem 5.1): Optimal solution exists that is constant on vertex orbits, so only need to consider profiles of maximum independent sets.

Profiles for W₅² (from 7): $(1, 0, 10), (0, 2, 8), (0, 3, 6), (0, 4, 5)$ where $(p_1, p_2, p_3)$ denotes number of vertices in three orbits $T_1, T_2, T_3$.

Computational Results:

• $\chi_f(W_7^{\Box 2}) = \frac{39}{11}$
• $\chi_f(W_9^{\Box 2}) = \frac{127}{37}$
• $\chi_f(W_5^{\Box 3}) = \frac{722}{189}$ (computationally intensive)

Observed Pattern (Conjecture 7.3): $\chi_f(W_{2t+1}^{\Box 2}) = \frac{6t^2 + 7t + 3}{2t^2 + t + 1}$

This would yield $\mathscr{I}(W_{2t+1}) \geq \frac{2t^2+t+1}{6t^2+7t+3}$ (asymptotically $\frac{1}{3}$).

Visualization Results

Appendix A: Shows maximum independent sets in $W_{2t+1}^{\Box 2} \Box K_3$ (as 3-colorings of $W_{2t+1}^{\Box 2}$):

• Figure 5: $W_5^{\Box 2} \Box K_3$, size 29
• Figure 6: $W_7^{\Box 2} \Box K_3$, size 54
• Figure 7: $W_9^{\Box 2} \Box K_3$, size 87
• Figure 8: $W_{11}^{\Box 2} \Box K_3$, size 128

Structural Observation (Conjecture 7.1): $\alpha(W_{2t+1}^{\Box 2} \Box K_3) = (2t+2)\alpha(W_{2t+1}) - (t-1) = 4t^2 + 5t + 3$

That is, the order of maximum 3-colorable subgraph is $4t^2 + 5t + 3$.

Related Work

Ultimate Independence Ratio Theory

1. Foundational Work:
   • Hell, Yu, Zhou (1994): Formalize definition, prove limit existence
   • Hahn, Hell, Poljak (1995): Establish basic bounds $\frac{1}{\chi} \leq \mathscr{I} \leq \frac{1}{\omega}$
2. Tightness of General Bounds:
   • Zhu (1996): Constructs examples with $\frac{1}{\chi} < \mathscr{I} < \frac{1}{\chi_f}$
   • Introduces star chromatic number for new bounds
3. Related Limit Problems:
   • Shannon Capacity: $\lim_{k \to \infty} \sqrt[k]{\alpha(G^{\boxtimes k})}$ (strong product)
   • Fractional Independence Ratio (Albert et al. 2001)
   • Tensor Graph Powers (Alon & Lubetzky 2007)

Properties of Wheel Graphs

1. Chromatic and Clique Numbers:
   • Even wheels: $\chi = \omega = 3$ (perfect graphs)
   • Odd wheels: $\chi = 4$, $\omega = 3$ (4-critical graphs)
2. Fractional Chromatic Number:
   • $\chi_f(W_{2t+1}) = 3 + \frac{1}{t}$ (by connectivity properties)
   • $\chi_f(C_{2t+1}) = 2 + \frac{1}{t}$ (known)
3. Independence Numbers of Cartesian Products:
   • Proposition 2.1: $\alpha(G \Box H) \leq \min\{|V(G)|\alpha(H), |V(H)|\alpha(G)\}$

Computational Methods

1. Integer Programming:
   • Standard independent set IP (Program 6)
   • Improved formulation for Cartesian products (Program 7)
2. Fractional Chromatic Number Computation:
   • LP formulation (Program 8)
   • Symmetry utilization (Theorem 5.1)
3. Graph Homomorphisms:
   • Theorem 1.1: If homomorphism $G \to H$ exists, then $\mathscr{I}(H) \leq \mathscr{I}(G)$
   • Provides proof of basic bounds

Conclusions and Discussion

Main Conclusions

1. Theoretical Contributions:
   • Proposes new upper bound method utilizing clique structure (Theorem 1.3)
   • Establishes non-trivial theoretical bounds $\frac{4t^2+6t}{3(2t+2)^2}$ for all $t \geq 3$
2. Computational Breakthrough:
   • Exactly determines $\alpha(W_5^{\Box 3} \Box K_3) = 170$
   • Improves 30-year-old bound for 5-wheel
3. Methodology:
   • Demonstrates effective combination of theoretical analysis and computational verification
   • Provides complete reproducible framework

Limitations

1. Gap with Conjecture:
   • New bound $\frac{1019}{3888} \approx 0.262$ still has ~5% gap from conjectured value $\frac{1}{4} = 0.25$
   • Bound for large odd wheels $\frac{4t^2+6t}{3(2t+2)^2}$ asymptotically approaches $\frac{1}{3}$, not $\frac{1}{4}$
2. Computational Limitations:
   • Cannot directly compute $\alpha(W_5^{\Box 4})$ (estimated at 338)
   • Higher-order computations (e.g., $\chi_f(W_7^{\Box 3})$) are extremely intensive
3. Theoretical Tools:
   • Bound in Lemma 4.2 may not be tight
   • Requires deeper structural understanding
4. Generalization:
   • Methods highly dependent on special structure of wheel graphs
   • Applicability to other non-perfect graphs unknown

Future Directions

Authors propose multiple conjectures in Section 7:

1. Conjecture 7.1 (Structural Conjecture): $\alpha(W_{2t+1}^{\Box 2} \Box K_3) = 4t^2 + 5t + 3$
   If true, would yield $\mathscr{I}(W_{2t+1}) \leq \frac{4t^2+5t+3}{3(2t+2)^2}$ (slight improvement).
2. Conjecture 7.2: $\alpha(W_5^{\Box 4}) = 338$
   Heuristic search supports this value. If correct, could further improve bound for $\mathscr{I}(W_5)$.
3. Conjecture 7.3 (Fractional Chromatic Number Pattern): $\chi_f(W_{2t+1}^{\Box 2}) = \frac{6t^2 + 7t + 3}{2t^2 + t + 1}$
   Would yield lower bound $\mathscr{I}(W_{2t+1}) \geq \frac{2t^2+t+1}{6t^2+7t+3}$.
4. Conjecture 7.4 (Method Advantage): For all $t \geq 3$ and $\ell \geq 1$, $\frac{\alpha(W_{2t+1}^{\Box \ell} \Box K_3)}{3(2t+2)^\ell} < \frac{1}{\chi_f(W_{2t+1}^{\Box \ell})}$
5. Conjecture 7.5 (Generalization): For graphs $G$ with $\chi > \omega$, if $H$ is maximum induced subgraph with $\chi(H) \leq \omega(G)$, then constant $c$ exists such that $\chi_f(G) < c \cdot \frac{\omega(G)|V(G)|}{|V(H)|}$

In-Depth Evaluation

Strengths

1. Theoretical Novelty:
   • Theorem 1.3 provides new theoretical tool independent of special graph class assumptions
   • Limit equality establishes computational pathway
   • Lemma 4.2 reveals deep structure of odd wheel Cartesian products
2. Methodological Rigor:
   • Theoretical proofs clear and complete
   • Computational part has complete verification pathways
   • Each computational assertion has corresponding code file
3. Practical Breakthrough:
   • First improvement of $\mathscr{I}(W_5)$ bound in 30 years
   • Provides unified theoretical bound for all large odd wheels
4. Reproducibility:
   • Code completely open source
   • Detailed computational framework explanation (Section 5)
   • Visualization aids understanding (Appendix A)
5. Writing Quality:
   • Clear structure, rigorous logic
   • Appropriate background introduction
   • Good balance between technical details and intuitive explanation

Weaknesses

1. Distance from Conjecture:
   • New bound insufficient to prove or disprove Conjecture 1.2
   • Asymptotic behavior of theoretical bound (approaching 1/3) mismatches conjectured value (1/4)
2. Computational Bottlenecks:
   • Depends on personal computer computational power
   • Cannot handle higher-order cases (e.g., $W_5^{\Box 5}$)
   • Fractional chromatic number computation extremely difficult for large graphs
3. Limitations of Theoretical Tools:
   • Bound in Lemma 4.2 may not be tight (gap approximately $t$)
   • No exact formula provided for $\alpha(W_{2t+1}^{\Box 2} \Box K_3)$
4. Insufficient Generalization:
   • Methods highly customized for wheel graphs
   • Applicability to other $\chi > \omega$ graphs unclear
5. Limited Lower Bound Work:
   • Primarily focuses on upper bounds
   • Less investigation of lower bounds (e.g., via construction)

Impact

1. Contribution to Field:
   • Reactivates 30-year-old open problem
   • Provides new theoretical tool (Theorem 1.3)
   • May inspire research on other non-perfect graphs
2. Practical Value:
   • Computational framework applicable to other graphs' ultimate independence ratio research
   • Integer programming method has general applicability
3. Theoretical Significance:
   • Reveals role of clique structure in ultimate independence ratio
   • Connects independence number, chromatic number, and fractional chromatic number
4. Openness:
   • Proposes 5 specific conjectures
   • Provides clear research directions

Applicable Scenarios

1. Direct Applications:
   • Non-homomorphism proofs in graph homomorphism theory
   • Shannon capacity-related problems in network coding
2. Methodological Reference:
   • Hybrid method combining theoretical bounds and finite computation
   • Branch-and-bound + IP strategy
   • Symmetry utilization for computational simplification
3. Generalization Directions:
   • Ultimate independence ratio of other critical graphs
   • Similar problems for other graph products (strong product, lexicographic product)

Key References

1. Hahn, Hell, Poljak (1995): Foundational paper establishing basic theoretical framework
2. Zhu (1996): Proves tightness of general bounds
3. Hell, Yu, Zhou (1994): Formal definition of ultimate independence ratio
4. Scheinerman & Ullman (2011): Fractional graph theory textbook
5. Hammack et al. (2011): Graph products handbook

Summary

This paper makes substantial progress on the 30-year-old problem of ultimate independence ratio of odd wheels. Through innovative theoretical tools (Theorem 1.3), deep structural analysis (Lemma 4.2), and systematic computational verification, the authors improve bounds for all odd wheels, particularly improving the 5-wheel bound from 0.268 to 0.262. Although still distant from the conjectured value 0.25, this represents important progress in the field. The paper is methodologically rigorous, highly reproducible, and provides solid foundation for subsequent research. The main challenge lies in further narrowing the gap between theoretical bounds and conjectured value, which likely requires deeper understanding of independent set structure in odd wheel Cartesian products.