pith. sign in

arxiv: 1802.09049 · v2 · pith:HRC6PMS5new · submitted 2018-02-25 · 🧮 math.CO

On 1-factors with prescribed lengths in tournaments

classification 🧮 math.CO
keywords prescribedpossibleresultbestconnectedconstantstronglyclose
0
0 comments X
read the original abstract

K\"uhn, Osthus, and Townsend asked whether there exists a constant $C$ such that every strongly $Ct$-connected tournament contains all possible $1$-factors with at most $t$ components. We answer this question in the affirmative. This is best possible up to constant. In addition, we can ensure that each cycle in the $1$-factor contains a prescribed vertex. Indeed, we derive this result from a more general result on partitioning digraphs which are close to semicomplete. More precisely, we prove that there exists a constant $C$ such that for any $k\geq 1$, if a strongly $Ck^4t$-connected digraph $D$ is close to semicomplete, then we can partition $D$ into $t$ strongly $k$-connected subgraphs with prescribed sizes, provided that the prescribed sizes are $\Omega(n)$. This result improves the earlier result of K\"uhn, Osthus, and Townsend. Here, the condition of connectivity being linear in $t$ is best possible, and the condition of prescribed size being $\Omega(n)$ is also best possible.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.