Réunion d'hiver SMC 2026
Montréal, 11 - 14 décembre 2026
Chercheurs en début de carrière en théorie des graphes
Org: Kathie Cameron (Wilfrid Laurier University), Cicely Henderson (University of Waterloo) et Taite LaGrange (University of Waterloo)
Org: Kathie Cameron (Wilfrid Laurier University), Cicely Henderson (University of Waterloo) et Taite LaGrange (University of Waterloo)
- ALEXANDER CLOW, Simon Fraser University
Ultimately, How Independent is the 5-Wheel? [PDF]
-
The ultimate independence ratio of a graph $G$ is defined as $\mathcal{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 Cartesian product of $k$ copies of $G$. For all graphs $G$, Hahn, Hell, and Poljak (1995) proved that $\frac{1}{\chi(G)} \leq \mathcal{I}(G) \leq \frac{1}{\omega(G)}$ where $\chi(G)$ is the chromatic number, and $\omega(G)$ is the clique number of $G$.
Motivated by this, the same authors conjectured that for all odd wheels $\mathcal{I}(W_{2t+1}) = \frac{1}{4}$.
By combine counting arguments, novel recursive bounds on $\alpha(G^{\Box k})$ which yield
generalized inequalities for $\mathcal{I}(G)$, and computer-assisted calculation in the $W_5$ case
we provide the first progress on this conjecture in three decades.
This is joint work with Hitesh Kumar and Shivaramakrishna Pragada.
- JULIEN CODSI, Princeton
- XINYUE FAN, University of Waterloo
- CICELY HENDERSON, University of Waterloo
- LORA HREISH, University of Toronto
- SEAN KIM, Simon Fraser University
- SEOKBEOM KIM, Korea Advanced Institute of Science & Technology (KAIST)
- TAITE LAGRANGE, University of Waterloo
- KYNE SANTOS, Toronto Metropolitan University
- AGNES TOTSCHNIG, Massachusetts Institute of Technology
- XINYUE FAN, University of Waterloo