Improved bound for partitioning graphs into independent transversals

An asymptotic bound for Yuster's independent transversal factor conjecture

Discrete Mathematics

Summary

There is a special kind of graph with multiple groups of points where connections exist between groups, and a question about how to break these graphs into neat parts was posed by Yuster. The authors proved that for large enough groups, such a partition always exists with a size that is very close to the number of groups. Their work provides a near-final answer to Yuster's conjecture by showing the size needed grows almost exactly with the number of groups.

What this means in practice

  • For network schedulers: Design scheduling algorithms that ensure conflict-free resource allocation with nearly minimal group sizes in complex bipartite systems.
  • For distributed system architects: Optimize the partitioning of tasks or data sets across independent subsystems while preserving balanced matching properties.

A theory result. No direct application yet.

Authors

Xin Zhang

Abstract

An $[r,n,1]$-graph has $r$ independent parts of size $n$, with a matching between each pair of parts. Yuster conjectured in 2021 that every such graph has a partition into independent transversals whenever $n\ge 2\lceil r/2\rceil$. We prove that there is an absolute constant $A>0$ such that, for all sufficiently large $r$, this partition exists whenever $n\ge\lceil r+A r^{20/21}\rceil$. Thus $f(r)\le r+O(r^{20/21})$, where $f(r)$ is the least $n_0$ such that every $[r,n,1]$-graph has such a partition whenever $n\ge n_0$. In particular, $f(r)/r\to1$, giving an asymptotic form of the conjecture.