Two questions on Kneser colorings
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910984472363008 |
|---|---|
| author | Inozemtsev, Eduard Kupavskii, Andrey |
| author_facet | Inozemtsev, Eduard Kupavskii, Andrey |
| contents | In this paper, we investigate two questions on Kneser graphs $KG_{n,k}$. First, we prove that the union of $s$ intersecting families in ${[n]\choose k}$ has size at most ${n\choose k}-{n-s\choose k}$ for all sufficiently large $n$ that satisfy $n>(2+ε)k^2+s$ with $ε>0$. We provide an example that shows that this result is essentially tight for the number of colors close to $χ(KG_{n,k})=n-2k+2$. We also improve the result of Bulankina and Kupavskii on the choice chromatic number, showing that it is at least $\frac 1{25} n\log n$ for all $k<\sqrt n$ and $n$ sufficiently large. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_08797 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Two questions on Kneser colorings Inozemtsev, Eduard Kupavskii, Andrey Combinatorics Discrete Mathematics In this paper, we investigate two questions on Kneser graphs $KG_{n,k}$. First, we prove that the union of $s$ intersecting families in ${[n]\choose k}$ has size at most ${n\choose k}-{n-s\choose k}$ for all sufficiently large $n$ that satisfy $n>(2+ε)k^2+s$ with $ε>0$. We provide an example that shows that this result is essentially tight for the number of colors close to $χ(KG_{n,k})=n-2k+2$. We also improve the result of Bulankina and Kupavskii on the choice chromatic number, showing that it is at least $\frac 1{25} n\log n$ for all $k<\sqrt n$ and $n$ sufficiently large. |
| title | Two questions on Kneser colorings |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2405.08797 |