Skip to content
Preprint

Optimal path decompositions of sparse random graphs

Oct 2026 · 0 citations · 15 references
Mathematics

TL;DR

The proof combines a local pairing argument based on the lopsided Lov\'asz local lemma with cycle decompositions of random graphs with cycle decompositions of random graphs.

Abstract

Let $\operatorname{odd}(G)$ be the number of odd-degree vertices of a graph $G$. We prove that, if $p=o(1)$ and $np/\log n\to\infty$, then with probability tending to one the random graph $G(n,p)$ has an edge decomposition into exactly $\operatorname{odd}(G)/2$ paths. This confirms a conjecture of Glock, K\"uhn and Osthus from 2016. The proof combines a local pairing argument based on the lopsided Lov\'asz local lemma with cycle decompositions of random graphs.

View source

Similar papers

Preprint Oct 2026

The terminal leave in random greedy hypergraph matching

Let $G$ be the terminal graph of the random triangle-removal process started from $K_n$. We prove that $e(G)/n^{3/2}\to1/(2\sqrt2)$ in $L^2$. More generally, we obtain the analogous result for any fixed strictly $k$-balanced $k$-graph. Our main tool is a more general theorem on random greedy matchings in nearly regular...

Peter Keevash · 1 citation
Preprint Oct 2026

The singularity probability of dense random regular graphs

Let $G_{n,d}$ be a uniformly random simple $d$-regular graph on $n$ vertices, and let $A_n$ be its adjacency matrix. For every fixed $\lambda\in(0,1/2)$, we prove that for any $\lambda(n-1)\le d\le(1-\lambda)(n-1)$, $\mathbb P(A_n\text{ is singular})\le e^{-cn}$, where $c>0$ depends only on $\lambda$, and $n$ is suffic...

Ze-Yan Song, Han-Chao Wang, Sheng-Yan Yin et al. · 0 citations
Preprint Oct 2026

Optimal Bounds on Spanning Tree Embeddings

We prove that the number of labelled embeddings of any $n$-vertex tree $T$ into an $n$-vertex graph $G$ of maximum degree $d$ satisfies $$ \mathrm{inj}(T,G) \leq (d/e)^n \exp(o_d(1) n). $$ The bound is sharp up to determining $o_d(1)$, even for paths, and the dependence of the error $\exp(o_d(1)n)$ on $d$ is necessary....

Csongor Beke, V. Boskovic, Nina Kamčev et al. · 0 citations
Preprint Sep 2026

Range of Clique Counts in Graphs

Let $\gamma(G)$ denote the number of cliques in a graph $G$ and let $\Gamma(n):= \{\gamma(G):|V(G)|=n\}$ be the set of values of $\gamma(G)$ that can be attained on $n$ vertices. We improve on a result by Erd\H{o}s and Ern\'e to show that $| \Gamma(n)| \geq 2^{n-4\ln(2)\log^3(n)}$ for sufficiently large $n$.

Mihir Neve, Alexey Pokrovskiy, A. Shapiro · 0 citations
Preprint Oct 2026

Normal approximation for subgraph counts in random intersection graphs: the case of cliques

Let $X^{(r)}_n$ denote the number of copies of a complete graph $K_r$ in the random intersection graph model on $n$ vertices. We derive upper bounds on the distance between the standardized version of $X^{(r)}_n$ and the standard normal distribution, measured in both the Kolmogorov and Wasserstein metrics. We complemen...

K. Rybarczyk, G. Serafin · 0 citations
Preprint Oct 2026

The lower tail of triangle counts in sparse random graphs

Let $T_n$ be the number of triangles in the Erd\H{o}s-R\'enyi random graph $G(n,p)$ with $n^{-1/2}\ll p\ll1$ and fix $\eta\in(0,1)$. We study the large deviation rate of the lower tail event $T_n\le\eta\mathbb{E}[T_n]$, and the typical structure of $G(n,p)$ conditioned on this event. By earlier work [16,19,21,49], both...

Dong Huang, Shuang-Ping Li · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.