{"ID":2837316,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.18747","arxiv_id":"2511.18747","title":"Improved Bounds for the Ultimate Independence Ratio of Odd Wheels","abstract":"The ultimate independence ratio of a graph $G$ is defined as $\\mathscr{I}(G) = \\lim_{k\\rightarrow\\infty } \\frac{α(G^{\\Box k})}{|V(G)|^k},$ where $α(G^{\\Box k})$ is the independence number of the Cartesian product of $k$ copies of $G$. For all graphs $G$, Hahn, Hell, and Poljak (1995) proved that $\\frac{1}{χ(G)} \\leq \\mathscr{I}(G) \\leq \\frac{1}{ω(G)}$ where $χ(G)$ is the chromatic number, and $ω(G)$ is the clique number of $G$. So all graphs $G$ with $χ(G) = ω(G)$ satisfy $\\mathscr{I}(G) = \\frac{1}{χ(G)} = \\frac{1}{ω(G)}$. A construction of Zhu demonstrates that there exists a graph $G$ with $\\frac{1}{χ(G)} \u003c \\mathscr{I}(G) \u003c \\frac{1}{ω(G)}$, so neither equality holds in general. In response, Hahn, Hell, and Poljak conjectured that all wheel graphs $W_n$ satisfy $\\mathscr{I}(W_n) = \\frac{1}{χ(W_n)}$. For even wheels $W_{2t}$ this follows from the fact $χ(W_{2t}) = ω(W_{2t}) = 3$. Odd wheels of length at least $5$ present a more challenging case, since $χ(W_{2t+1}) = 4$ and $ω(W_{2t+1}) = 3$. First, we prove that odd wheels of length at least $7$ satisfy $\\mathscr{I}(W_{2t+1})\\leq \\frac{4t^2+6t}{3(2t+2)^2}\u003c\\frac{1}{3}$, which provides the best upper bound for large odd wheels. Next, we prove that $\\mathscr{I}(W_5) \\leq \\frac{1019}{3888}$, improving an upper bound of Hahn, Hell, and Poljak that $\\mathscr{I}(W_5) \\leq \\frac{11}{41}$. Our proofs combine counting arguments, recursive bounds on $α(W^{\\Box k}_{2t+1})$, and computer-assisted calculation in the $W_5$ case.","short_abstract":"The ultimate independence ratio of a graph $G$ is defined as $\\mathscr{I}(G) = \\lim_{k\\rightarrow\\infty } \\frac{α(G^{\\Box k})}{|V(G)|^k},$ where $α(G^{\\Box k})$ is the independence number of the Cartesian product of $k$ copies of $G$. For all graphs $G$, Hahn, Hell, and Poljak (1995) proved that $\\frac{1}{χ(G)} \\leq \\m...","url_abs":"https://arxiv.org/abs/2511.18747","url_pdf":"https://arxiv.org/pdf/2511.18747v1","authors":"[\"Alexander Clow\",\"Hitesh Kumar\",\"Shivaramakrishna Pragada\"]","published":"2025-11-24T04:17:29Z","proceeding":"math.CO","tasks":"[\"math.CO\",\"math.OC\"]","methods":"[]","has_code":false}