Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCycles of a given length in tournaments
89
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We study the asymptotic behavior of the maximum number of directed cycles of a given length in a tournament: let $c(ell)$ be the limit of the ratio of the maximum number of cycles of length $ell$ in an $n$-vertex tournament and the expected number of cycles of length $ell$ in the random $n$-vertex tournament, when $n$ tends to infinity. It is well-known that $c(3)=1$ and $c(4)=4/3$. We show that $c(ell)=1$ if and only if $ell$ is not divisible by four, which settles a conjecture of Bartley and Day. If $ell$ is divisible by four, we show that $1+2cdotleft(2/piright)^{ell}le c(ell)le 1+left(2/pi+o(1)right)^{ell}$ and determine the value $c(ell)$ exactly for $ell = 8$. We also give a full description of the asymptotic structure of tournaments with the maximum number of cycles of length $ell$ when $ell$ is not divisible by four or $ellin{4,8}$.
rate research
Read More
Let $L$ be subset of ${3,4,dots}$ and let $X_{n,M}^{(L)}$ be the number of cycles belonging to unicyclic components whose length is in $L$ in the random graph $G(n,M)$. We find the limiting distribution of $X_{n,M}^{(L)}$ in the subcritical regime $M=cn$ with $c<1/2$ and the critical regime $M=frac{n}{2}left(1+mu n^{-1/3}right)$ with $mu=O(1)$. Depending on the regime and a condition involving the series $sum_{l in L} frac{z^l}{2l}$, we obtain in the limit either a Poisson or a normal distribution as $ntoinfty$.
We compute the limiting distribution, as n approaches infinity, of the number of cycles of length between gamma n and delta n in a permutation of [n] chosen uniformly at random, for constants gamma, delta such that 1/(k+1) <= gamma < delta <= 1/k for some integer k. This distribution is supported on {0, 1, ... k} and has 0th, 1st, ..., kth moments equal to those of a Poisson distribution with parameter log (delta/gamma). For more general choices of gamma, delta we show that such a limiting distribution exists, which can be given explicitly in terms of certain integrals over intersections of hypercubes with half-spaces; these integrals are analytically intractable but a recurrence specifying them can be given. The results herein provide a basis of comparison for similar statistics on restricted classes of permutations.
In 2006, Barat and Thomassen posed the following conjecture: for each tree $T$, there exists a natural number $k_T$ such that, if $G$ is a $k_T$-edge-connected graph and $|E(G)|$ is divisible by $|E(T)|$, then $G$ admits a decomposition into copies of $T$. This conjecture was verified for stars, some bistars, paths of length $3$, $5$, and $2^r$ for every positive integer $r$. We prove that this conjecture holds for paths of any fixed length.
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.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
