Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.09515 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911000110825472 |
|---|---|
| author | Haxell, Penny Mittal, Arpit Zhao, Yi |
| author_facet | Haxell, Penny Mittal, Arpit Zhao, Yi |
| contents | Given integers $r>d\ge 0$ and an $r$-partite graph, an independent $(r-d)$-transversal or $(r-d)$-IT is an independent set of size $r-d$ that intersects each part in at most one vertex. We show that every $r$-partite graph with maximum degree $Δ$ and parts of size $n$ contains an $(r-d)$-IT if $n> 2Δ(1-\frac{1}{q})$, provided $q= \lfloor \frac{r}{d+1}\rfloor\ge \frac{4r}{4d+5}$. This is tight when $q$ is even and extends a classical result of Haxell in the $d=0$ case. When $q= \lfloor \frac{r}{d+1} \rfloor\ge \frac{6r+6d+7}{6d+7}$ is odd, we show that $n> 2Δ(1-\frac{1}{q-1})$ guarantees an $(r-d)$-IT in any $r$-partite graph. This is also tight and extends a result of Haxell and Szabó in the $d=0$ case. In addition, we show that $n> 5Δ/4$ guarantees a $5$-IT in any $6$-partite graph and this bound is tight, answering a question of Lo, Treglown and Zhao. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_09515 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Partial independent transversals in multipartite graphs Haxell, Penny Mittal, Arpit Zhao, Yi Combinatorics Given integers $r>d\ge 0$ and an $r$-partite graph, an independent $(r-d)$-transversal or $(r-d)$-IT is an independent set of size $r-d$ that intersects each part in at most one vertex. We show that every $r$-partite graph with maximum degree $Δ$ and parts of size $n$ contains an $(r-d)$-IT if $n> 2Δ(1-\frac{1}{q})$, provided $q= \lfloor \frac{r}{d+1}\rfloor\ge \frac{4r}{4d+5}$. This is tight when $q$ is even and extends a classical result of Haxell in the $d=0$ case. When $q= \lfloor \frac{r}{d+1} \rfloor\ge \frac{6r+6d+7}{6d+7}$ is odd, we show that $n> 2Δ(1-\frac{1}{q-1})$ guarantees an $(r-d)$-IT in any $r$-partite graph. This is also tight and extends a result of Haxell and Szabó in the $d=0$ case. In addition, we show that $n> 5Δ/4$ guarantees a $5$-IT in any $6$-partite graph and this bound is tight, answering a question of Lo, Treglown and Zhao. |
| title | Partial independent transversals in multipartite graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2506.09515 |