Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2509.22026 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916971590713344 |
|---|---|
| author | Daneshpajouh, Hamid Reza |
| author_facet | Daneshpajouh, Hamid Reza |
| contents | One of the key unsolved conjectures in hypergraph coloring is about the chromatic number of $s$-stable $r$-uniform Kneser hypergraphs $\mathrm{KG}^r(n,k)_{s\textup{-stab}}$. The problem remains largely open, particularly in the case where $s > r\geq 3$. To the best of our knowledge, no information is available except a limited number of computations conducted for the instances when $r=3, 4$, $s=4, 5$, $k=2,3$ with some $n$ does not exceed 14. In this study, we verify the conjecture for infinity many values of the parameters $n$ and $k$. In particular, we demonstrate: (i) the validity of the conjecture for $r = 4$, $s = 6$ under the condition that $3 \mid n$ or $k=2$, and (ii) for $r = 4$, $k = 2$, $s = 5$ given $3 \nmid n$. As far as we are aware, this provides the first rigorous theoretical proof of the conjecture (for the case $s > r\geq 3$) for infinitely many parameter values, extending beyond finite computational verification. Furthermore, our methods rely on a detailed study of vector-stable Kneser graphs, an approach that not only yields these results but also provides a deeper understanding of their chromatic numbers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_22026 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Chromatic Number of Stable Kneser Hypergraphs: Verifying the Conjecture for New Families Daneshpajouh, Hamid Reza Combinatorics One of the key unsolved conjectures in hypergraph coloring is about the chromatic number of $s$-stable $r$-uniform Kneser hypergraphs $\mathrm{KG}^r(n,k)_{s\textup{-stab}}$. The problem remains largely open, particularly in the case where $s > r\geq 3$. To the best of our knowledge, no information is available except a limited number of computations conducted for the instances when $r=3, 4$, $s=4, 5$, $k=2,3$ with some $n$ does not exceed 14. In this study, we verify the conjecture for infinity many values of the parameters $n$ and $k$. In particular, we demonstrate: (i) the validity of the conjecture for $r = 4$, $s = 6$ under the condition that $3 \mid n$ or $k=2$, and (ii) for $r = 4$, $k = 2$, $s = 5$ given $3 \nmid n$. As far as we are aware, this provides the first rigorous theoretical proof of the conjecture (for the case $s > r\geq 3$) for infinitely many parameter values, extending beyond finite computational verification. Furthermore, our methods rely on a detailed study of vector-stable Kneser graphs, an approach that not only yields these results but also provides a deeper understanding of their chromatic numbers. |
| title | On the Chromatic Number of Stable Kneser Hypergraphs: Verifying the Conjecture for New Families |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2509.22026 |