2025/06/11 by Penny Haxell, Haxell, Penny, Arpit Mittal +3
Mathematics · Computer Science · Engineering · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2506.09515
Given integers r>d≥ 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-(1)/(q)), provided q= \lfloor (r)/(d+1)\rfloor≥ (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 (r)/(d+1) \rfloor≥ (6r+6d+7)/(6d+7) is odd, we show that n> 2Δ(1-(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.