Let $C_{2s}^{\mathrm{ad}}$ be the anti-directed cycle of length $2s$, where $s\geq2$. We prove that, for every $\mu>0$, every sufficiently large $n$-vertex oriented graph $D$ with $2s\mid n$, \[ \delta^0(D)\geq\left(\frac14+\mu\right)n \qquad\text{and}\qquad \alpha(D)=o(n) \] contains a $C_{2s}^{\mathrm{ad}}$-factor. The minimum semidegree threshold is asymptotically tight. The proof develops Ramsey--Tur\'an-type lattice-absorption lemmas with a transferral arising from the small-independence condition by virtue of a fork-type structure.
For every $q\ge2$, we prove that every oriented graph $G$ on $n\ge45q-8$ vertices whose minimum semidegree satisfies \[ \delta^0(G)\ge \left\lceil\frac n3\right\rceil \] contains a directed cycle of length $3q$ through every vertex. The semidegree bound is sharp. This closes the one-unit gap left by the prescribed-vertex theorem of Kelly, K\"uhn and Osthus when $3\mid n$. We also prove that if an oriented graph $H$ has order $N$, minimum semidegree $d\ge3$, and $7d\ge2N+3$, then every ordered pair of distinct vertices is joined by a path of length three, four, or five. The constant $+3$ is best possible. As a consequence, the order hypothesis $n\ge10^{10}\ell$ in the general prescribed-vertex theorem of Kelly, K\"uhn and Osthus can be replaced by $n\ge15\ell-60$ for $\ell\ge7$.
Let $\Cvec$ be a fixed orientation of the cycle $C_\ell$, $\ell\ge3$, which is not directed. For an oriented graph $D$, let $d_D^*(v):=\max\{d_D^+(v),d_D^-(v)\},$ and let \[ \sigore(D):=\min\bigl\{d_D^*(x)+d_D^*(y):x\ne y,\ xy,yx\notin A(D)\bigr\}, \] with $\sigore(D)=\infty$ if the underlying graph of $D$ is complete. We prove that, for every $\mu>0$, there exist $\gamma>0$ and $n_0$ such that every $n\ge n_0$ with $\ell\mid n$ and every $n$-vertex oriented graph $D$ satisfying \[ \alpha(D)\le\gamma n \text{ and } {\sigore(D)\ge\left(\frac34+\mu\right)n} \] contains a $\Cvec$-factor. {Additionally, for every fixed $s\ge2$ and every fixed real constant $C$, we construct arbitrarily large oriented graphs with $\sigore(D)\ge \frac34n+C$ that contain no $C_{2s}^{\ad}$-factor. More precisely, $C:=\frac34\alpha(D)-2$ for $s=2$ and $C:=\frac14\alpha(D)-\frac32$ for $s\ge3$.} This paper develops a weighted reduction framework adapted to dominant degree condition, proves the absorption lemma via closed-cluster merging with even-walk, and derives almost-perfect tiling structures by virtue of Farkas-lemma-based fractional decomposition.
For an oriented graph $G$ the oriented chromatic number of $G$, written $\chi_o(G)$, is the least integer $t$ such that $G$ has a homomorphism to a tournament on $t$ vertices. The oriented chromatic number of a simple graph $H$ is the maximum oriented chromatic number over all orientations of $H$. Borodin, Kostochka, Ne{\v{s}}et{\v{r}}il, Raspaud, and Sopena proved in 1999 that for all $\epsilon>0$, graphs with maximum average degree less than $4-\epsilon$ have bounded oriented chromatic number. This is in some sense optimal, because $1$-subdivisions of cliques demonstrate that there exists graphs with maximum average degree strictly less than $4$ and oriented chromatic number $\Omega(\sqrt{n})$. We prove that for every positive integer $d$, every $d$-degenerate graph $G$ with sufficiently large order satisfies $\chi_o(G) \leq 6(1+\frac{9d^2}{4})^{\frac{1}{2}}d 8^{d}\sqrt{n}$. This implies for a fixed $r\geq 4$, the optimal bound for the oriented chromatic number of graphs with maximum average degree less than $r$ is $\Theta(\sqrt{n})$. This complements a bound of Wood, who showed that for all $n$ vertex graphs $\chi_o \leq 2\Delta\sqrt{n-1}$ where $\Delta$ is the maximum degree.
A graph $\Gamma$ is $(c,t)$-sparse for $c>0$ and $t \ge 1$ if for every pair of vertex subsets $A, B \subseteq V(\Gamma)$ with $|A|, |B| \ge t$, the number of edges $e(A,B)$ between them satisfies $ e(A,B) \le (1 - c)|A||B|$. In this paper, we prove that for every integer $\ell\ge2$, there are $\varepsilon>0, C, C'>0$ such that if an $n$-vertex graph $\Gamma$ is $(1-\varepsilon,t)$-sparse for some $t$, and has at least $Ct^{1-1/\ell}n^{1+1/\ell}$ edges, then $\Gamma$ contains at least $C'n^2t^{2\ell-2}$ induced copies of $C_{2\ell}$. This partially resolves a problem of Ding, Gao, Liu, Luan, and Sun.
Adam Džavoronok, Ole Gabsdil, Alexander Mylet et al.· 1 citation
The codegree Tur\'an density $\pi_{\mathrm{co}}(F)$ is the supremum over all $\gamma \in [0,1)$ such that, for arbitrarily large $n$, there exists an $n$-vertex $F$-free $k$-graph $H$ whose every $(k-1)$-subset of vertices lies in at least $\gamma n$ edges. Ding, Lamaison, Liu, Wang, and Yang (JLMS, 2025) studied the problem of what 3-graphs $F$ satisfy $\pi_{\mathrm{co}}(F) = 0$. They introduced layered $3$-graphs and conjectured that a $3$-graph has zero codegree Tur\'an density if and only if it is layered and has zero uniform Tur\'an density. For $k\ge 3$, a $k$-graph is called layered if its vertices can be labelled so that every edge has a unique maximum label and two edges with the same maximum label have the same label multiset. In this paper, we show that every non-layered $k$-graph $F$ on $m$ vertices satisfies \[ \pi_{\mathrm{co}}(F)\ge q_{k,m}^{-q_{k,m}}>0, \quad \text{where}\quad q_{k,m}=\frac{(k-1)^{m+1}-1}{k-2}, \] which implies any $k$-graph with zero $\ell$-degree Tur\'an density is layered, and the case $k=3$ confirms the conjecture of Ding, Lamaison, Liu, Wang, and Yang.
A famous conjecture of Erd\H{o}s and Hajnal (1969) states that for every integer $g\ge 4$ there is a smallest function $f_g:\mathbb{N}\to\mathbb{N}$ such that every graph of chromatic number at least $f_g(k)$ contains a subgraph of chromatic number $k$ and girth at least $g$. So far, this has only been proved for $g=4$ by R\"odl (1977), with $f_4(k)$ bounded by a tower of height $\Theta(k^2\log k)$. We exhibit a surprising connection between finding high-chromatic subgraphs of large odd-girth (avoiding short odd cycles) and lower-bounding multicolor Ramsey numbers of odd cycles. Using this connection, we prove that for every odd $g\ge 5$ there is a function $h_g:\mathbb{N}\to\mathbb{N}$ growing as a power tower of height $\frac{g-3}{2}$ such that every graph of chromatic number at least $h_g(k)$ contains a subgraph of chromatic number at least $k$ and odd-girth at least $g$. This proves a conjecture of Mohar and Wu (2018), addresses a question of Erd\H{o}s and Hajnal (1975), and for $g=5$ improves R\"odl's bound on $f_4(k)$ to a single-exponential. We extend this to a much more general meta-theorem which applies to many graph parameters: if $f$ is the fractional chromatic number, the Hall ratio, or the strict vector chromatic number (Lov\'{a}sz-Theta-function of the complement), then for every $k,g\in\mathbb{N}$, every graph $G$ with sufficiently large $f(G)$ contains a subgraph $G'$ of odd-girth at least $g$ with $f(G')\ge k$. The key Ramsey-theoretic ingredient is a new lower bound on Ramsey numbers of odd cycles. For $p\ge 1$, let $\mathcal{O}_p=\{C_3,C_5,\ldots,C_{2p+1}\}$. We show that $R_k(\mathcal{O}_p)\ge(\log^{(p-1)}k)^{k/3-o(k)}$ for every fixed $p$, where $\log^{(p-1)}$ denotes the $(p-1)$-fold iterated logarithm. This yields the first superexponential lower bound on multicolor Ramsey numbers of fixed odd cycles, and extends the recent breakthrough by OpenAI for triangles.
Raphael Steiner· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
