There is a fascinating array of interrelated questions studying which structures can be guaranteed in digraphs of large minimum out-degree. These often have intriguingly simple statements, yet seem surprisingly difficult to approach. A well-known example is Lichiardopol's conjecture (2014), stating that there exists a function $g:\mathbb{N}\rightarrow \mathbb{N}$ such that every digraph with minimum out-degree at least $g(k)$ contains $k$ vertex-disjoint directed cycles of distinct lengths. In this paper, building on earlier work of the second author, we confirm this conjecture in full generality. We also generalise this result to a weighted setting. Our proof uses and combines many ingredients from structural digraph theory such as butterfly minors, directed tangles, a directed analogue of the Tangle-Wall Theorem due to Robertson and Seymour as well as a local variant of the Directed Flat Wall Theorem due to Giannopoulou, Kawarabayashi, Kreutzer and Kwon. These techniques, which are somewhat atypical in the study of minimum degree conditions, may be of independent interest and may find further applications.
The celebrated conjecture of Lov\'asz from 1969 asks whether every connected vertex-transitive graph has a Hamiltonian path. Buci\'c, Christoph, Pokrovskiy and Steiner recently proved that every such graph on $n$ vertices contains a cycle of length $n^{2/3-o(1)}$. In this paper, we improve this bound to $n^{1-o(1)}$. O...
In 1965, D. H. Lehmer conjectured that the permutations of every multiset admit an imperfect Hamiltonian traversal by adjacent swaps: a walk in the neighbor-swap graph that visits every word, with some words visited twice in order to reach a neighbor and return. The question is posed as an unsolved research problem in...
A finite simple graph $G$ is called a cograph if it does not contain the path on four vertices $P_4$ as an induced subgraph. It is classically known that the family of cographs are well-quasi-ordered by the induced subgraph relation \cite{D}. In preceding work of Knudsen and the third author \cite[Theorem 7.2]{KR}, it...
Adityo Mamun, Jonathan Nalikka, Eric Ramos· 0 citations
Tutte's flow conjectures ask when a graph has a nowhere-zero flow with small integer values. We approach these questions through spanning-tree packing and an analytic minimization argument of Alon, Buci\'c, and Davies. For every integer $q\ge2$, we prove that $q$ edge-disjoint spanning trees suffice to realize every co...
We prove that for every finite connected simple graph $G$ on $n$ vertices with minimum degree $k\geq 2$, there is a coupling of its uniform spanning tree and its random $1$-out subgraph under which the expected number of differing edges is $O(n\log (k)/\sqrt{k})$. More generally, we establish analogous couplings betwee...
Let f:N→D$f:\mathbb {N}\rightarrow \mathbb {D}$ be a multiplicative function. Under the merely necessary assumption that f$f$ is nonpretentious (in the sense of Granville and Soundararajan), we show that for any pair of distinct integer shifts h1,h2$h_1,h_2$ , the two‐point correlation 1x∑n⩽xf(n+h1)f¯(n+h2)$$\begin{equ...
O. Klurman, Alexander P. Mangerel, Joni Teravainen· Proceedings of the London Ma...· 10 citations· ⚡5
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
