Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn 1-factors with prescribed lengths in tournaments
100
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Kuhn, 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 $kgeq 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 Kuhn, 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.
rate research
Read More
We prove that there exists $C>0$ such that any $(n+Ck)$-vertex tournament contains a copy of every $n$-vertex oriented tree with $k$ leaves, improving the previously best known bound of $n+O(k^2)$ vertices to give a result tight up to the value of $C$. Furthermore, we show that, for each $k$, there exists $n_0$, such that, whenever $ngeqslant n_0$, any $(n+k-2)$-vertex tournament contains a copy of every $n$-vertex oriented tree with at most $k$ leaves, confirming a conjecture of Dross and Havet.
In this short note we prove that every tournament contains the $k$-th power of a directed path of linear length. This improves upon recent results of Yuster and of Gir~ao. We also give a complete solution for this problem when $k=2$, showing that there is always a square of a directed path of length $lceil 2n/3 rceil-1$, which is best possible.
We consider a generalisation of Kellys conjecture which is due to Alspach, Mason, and Pullman from 1976. Kellys conjecture states that every regular tournament has an edge decomposition into Hamilton cycles, and this was proved by Kuhn and Osthus for large tournaments. The conjecture of Alspach, Mason, and Pullman asks for the minimum number of paths needed in a path decomposition of a general tournament $T$. There is a natural lower bound for this number in terms of the degree sequence of $T$ and it is conjectured that this bound is correct for tournaments of even order. Almost all cases of the conjecture are open and we prove many of them.
In 1976, Alspach, Mason, and Pullman conjectured that any tournament $T$ of even order can be decomposed into exactly ${rm ex}(T)$ paths, where ${rm ex}(T):= frac{1}{2}sum_{vin V(T)}|d_T^+(v)-d_T^-(v)|$. We prove this conjecture for all sufficiently large tournaments. We also prove an asymptotically optimal result for tournaments of odd order.
Let $S_k(n)$ be the maximum number of orientations of an $n$-vertex graph $G$ in which no copy of $K_k$ is strongly connected. For all integers $n$, $kgeq 4$ where $ngeq 5$ or $kgeq 5$, we prove that $S_k(n) = 2^{t_{k-1}(n)}$, where $t_{k-1}(n)$ is the number of edges of the $n$-vertex $(k-1)$-partite Turan graph $T_{k-1}(n)$, and that $T_{k-1}(n)$ is the only $n$-vertex graph with this number of orientations. Furthermore, $S_4(4) = 40$ and this maximality is achieved only by $K_4$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
