betaFeedback

WorksMathematics

Minimum outdegree forcing directed cycles

Abstract

The Caccetta-Häggkvist conjecture, one of the best known open problems on oriented graphs, asserts that every oriented graph on nn vertices with minimum outdegree at least n/ℓn/\ell contains a directed cycle of length at most ℓ\ell. Motivated by it, Kelly, Kühn and Osthus asked for the minimum degree condition that forces a directed cycle of length exactly ℓ\ell. The semidegree version of this problem was recently solved, but the methods used there rely on bounding the directed diameter, which requires control over the indegrees. In the setting of the Caccetta-Häggkvist conjecture, where only the outdegrees are bounded, the answer was known only for ℓ\ell not divisible by 33. We determine the optimal minimum outdegree forcing a directed cycle of length ℓ\ell for every sufficiently large ℓ\ell and nn. This establishes the outdegree version of the Kelly-Kühn-Osthus conjecture for all large ℓ\ell, up to a small correction of the additive term, which in general cannot be avoided.

Introduction

One of the best known and most studied open problems concerning oriented graphs is the following conjecture from 1978.

Conjecture 1.1 (Caccetta, Häggkvist [2]). Every oriented graph GG on nn vertices with minimum outdegree δ+(G)≥nℓ\delta^{+}(G) \ge\frac{n}{\ell} contains a directed cycle of length at most ℓ\ell.

Here, by an oriented graph we understand a directed graph without loops and symmetric pairs of directed arcs, that is, an orientation of a simple graph. Furthermore, δ+(G)\delta^{+}(G) and δ−(G)\delta^{-}(G) denote the minimum outdegree and the minimum indegree of an oriented graph GG, respectively.

Numerous partial results towards Conjecture 1.1 are known. These include proofs with an additive error term in the bound on the cycle length, proofs in which the minimum outdegree assumption is strengthened by a multiplicative constant, and results obtained under additional forbidden-subgraph assumptions. For these and related developments concerning the Caccetta–Häggkvist conjecture, we refer the reader to the survey [8].

Even if we strengthen the assumption of Conjecture 1.1 by imposing a lower bound on the minimum semidegree δ±(G)=min⁡(δ+(G),δ−(G))\delta^{\pm}(G) = \min(\delta^{+}(G), \delta^{-}(G)) instead of the minimum outdegree, the essential difficulty seems to persist and the resulting weaker statement is open as well, except the case ℓ=3\ell= 3 recently claimed to be solved by OpenAI [7]. Motivated by this conjecture, Kelly, Kühn and Osthus [5] proposed in 2010 the following problem: for a given integer ℓ≥4\ell\ge4, determine the minimum semidegree that forces an oriented graph to contain a directed cycle of length exactly ℓ\ell. Despite the similar formulation, this problem is substantially different, and the answer depends on the divisibility properties of ℓ\ell. Indeed, Kelly, Kühn and Osthus conjectured the following.

Conjecture 1.2 (Kelly, Kühn, Osthus [5]). Let ℓ≥4\ell\ge4 be an integer and let kk be the smallest integer greater than 2 that does not divide ℓ\ell. Then there exists n0n_0 such that every oriented graph GG on n≥n0n \ge n_0 vertices with minimum semidegree δ±(G)≥⌊nk⌋+1\delta^{\pm}(G) \ge\left\lfloor\frac{n}{k} \right\rfloor+ 1 contains a directed cycle of length ℓ\ell.

Kelly, Kühn and Osthus [5] proved Conjecture 1.2 in the case k=3k=3, that is, for cycle lengths not divisible by 3. They also showed an asymptotic statement (with the semidegree bound (1+ε)nk(1+\varepsilon)\frac{n}{k}) in the cases k=4k=4 and k=5k=5. Later, Kühn, Osthus and Piguet [6] proved a similar asymptotic statement for the remaining values of kk, under the additional assumption that ℓ>107k6\ell> 10^7 k^6. Conjecture 1.2 was then resolved in 2023, up to a slight adjustment of the semidegree bound.

Theorem 1.3 (Grzesik, Volec [4]). Let ℓ≥4\ell\ge4 be an integer and let kk be the smallest integer greater than 2 that does not divide ℓ\ell. Then there exists n0n_0 such that for every oriented graph GG on n≥n0n \ge n_0 vertices:

  • if ℓ≢3(mod12)\ell\not\equiv3 \pmod{12} and δ±(G)≥nk+k−12k\delta^{\pm}(G) \ge\frac{n}{k}+\frac{k-1}{2k}, then GG contains a directed cycle of length ℓ\ell,

  • if ℓ≡3(mod12)\ell\equiv3 \pmod{12} and δ±(G)≥n4+14\delta^{\pm}(G) \ge\frac{n}{4}+\frac{1}{4}, then GG contains a directed cycle of length ℓ\ell.

Moreover, the above bounds are best possible.

As with the Caccetta–Häggkvist conjecture, Conjecture 1.2 seems to hold in a stronger form, where the minimum semidegree is replaced by the minimum outdegree. However, the techniques used in the aforementioned results cannot be easily adapted to this stronger setting, as they heavily rely on bounding the directed diameter, which cannot be done without an assumption on the indegrees.

As a first step towards the outdegree version of Conjecture 1.2, Czygrinow, Molla, Nagle and Oursler [3] proved that for every integer ℓ≥4\ell\ge4, there exists n0n_0 such that every oriented graph GG on n≥n0n \ge n_0 vertices with minimum outdegree δ+(G)≥n3+13\delta^+(G) \ge\frac{n}{3}+\frac{1}{3} contains a directed cycle of length ℓ\ell. In particular, the outdegree version of Conjecture 1.2 holds whenever ℓ\ell is not divisible by 3.

In this paper, we improve the above result for large ℓ\ell divisible by 3, providing an optimal outdegree bound. In particular, this shows that the outdegree version of Conjecture 1.2 holds for every sufficiently large ℓ\ell, up to the same kind of slight adjustment of the degree bound as in Theorem 1.3.

Theorem 1.4. Let ℓ\ell be an integer divisible by 3 and let kk be the smallest integer greater than 2 that does not divide ℓ\ell. If ℓ>20k2\ell> 20k^2, then there exists n0n_0 such that every oriented graph GG on n≥n0n \ge n_0 vertices with δ+(G)≥nk+k−1k\delta^+(G) \ge\frac{n}{k}+\frac{k-1}{k} contains a directed cycle of length ℓ\ell. Moreover, this outdegree bound is best possible if ℓ≢3,6(mod12)\ell\not\equiv3,6 \pmod{12} and ℓ≢24,48(mod60)\ell\not\equiv24,48 \pmod{60}.

Note that kk is always a prime power, and so k>9k>9 forces k≥11k\ge11. In particular, when k>9k>9, the assumption ℓ>20k2\ell>20k^2 of Theorem 1.4 is redundant, as every such ℓ\ell satisfies it: all of the integers 3,4,…,k−13,4,\ldots,k-1 divide ℓ\ell, and hence ℓ≥lcm⁡(3,4,…,k−1)>20k2\ell\ge\operatorname{lcm}(3,4,\ldots,k-1)>20k^2. Thus, the assumption ℓ>20k2\ell>20k^2 can be replaced by ℓ>1620\ell>1620. A more careful analysis of our proof would reduce this bound even further, to ℓ>180\ell>180, if needed.

Observe that the outdegree bound in Theorem 1.4 is slightly larger than the semidegree bound in Theorem 1.3. At an intuitive level, this is because a larger family of extremal constructions is available when only the outdegree condition has to be maintained.

However, similarly as with ℓ≡3(mod12)\ell\equiv3 \pmod{12} in Theorem 1.3, there are cases in which the best known construction does not match the general bound in Theorem 1.4. It turns out that in these cases the outdegree bound can indeed be improved, and the following theorem determines its optimal value.

Theorem 1.5. Let ℓ\ell be an integer divisible by 33 and let kk be the smallest integer greater than 22 that does not divide ℓ\ell. Assume that ℓ>20k2\ell> 20k^2, GG is an oriented graph on nn vertices, with nn large enough, and one of the following assumptions is satisfied:

  • ℓ≡3(mod12)\ell\equiv3 \pmod{12} and δ+(G)≥n4+14\delta^{+}(G) \ge\frac{n}{4} + \frac{1}{4};

  • ℓ≡6(mod12)\ell\equiv6 \pmod{12} and δ+(G)≥n4+24\delta^{+}(G) \ge\frac{n}{4} + \frac{2}{4};

  • ℓ≡24(mod60)\ell\equiv24 \pmod{60} and δ+(G)≥n5+35\delta^{+}(G) \ge\frac{n}{5} + \frac{3}{5};

  • ℓ≡48(mod60)\ell\equiv48 \pmod{60} and δ+(G)≥n5+25\delta^{+}(G) \ge\frac{n}{5} + \frac{2}{5};

Then GG contains a directed cycle of length ℓ\ell. Moreover, these bounds are best possible.

The rest of the paper is organized as follows. In Section 2, we introduce our notation and several lemmas we will use in the subsequent proofs. In Section 3, we present the extremal constructions for all values of ℓ\ell. Sections 4 and 5 contain the proofs of Theorems 1.4 and 1.5, respectively.

Notation and Preliminaries

Notation

A directed graph GG is a pair (V(G),E(G))(V(G), E(G)), where E(G)⊆V(G)×V(G)E(G) \subseteq V(G) \times V(G). Elements of E(G)E(G) are called arcs. When (u,v)∈E(G)(u,v) \in E(G), we say there is an arc from uu to vv. We often write uvuv instead of (u,v)(u,v) for brevity. In all directed graphs we consider, loops, i.e., arcs of the form vvvv, are not allowed.

Oriented graphs are directed graphs with an additional restriction – for u,v∈V(G)u,v \in V(G), if uv∈E(G)uv \in E(G), then vu∉E(G)vu \notin E(G) (this in particular implies there are no loops). As we are mostly concerned with oriented graphs, we refer to them simply as graphs whenever this is clear from the context.

In a directed graph, an outneighbor of a vertex vv is a vertex uu such that vuvu is an arc. Similarly, uu is an inneighbor of vv if uvuv is an arc.

The outneighborhood N+(v)N^{+}(v) of a vertex vv is the set of its outneighbors. Symmetrically, the inneighborhood N−(v)N^{-}(v) is the set of the inneighbors of vv. The outdegree and indegree of vv are d+(v):=∣N+(v)∣d^{+}(v) := |N^{+}(v)| and d−(v):=∣N−(v)∣d^{-}(v) := |N^{-}(v)|, respectively. Whenever the underlying graph is not clear from the context, we indicate it by a subscript, writing NG+(v)N_G^{+}(v), dG+(v)d_G^{+}(v), and so on. Define:

δ+(G)=min⁡v∈V(G)d+(v)minimum outdegreeΔ+(G)=max⁡v∈V(G)d+(v)maximum outdegreeδ−(G)=min⁡v∈V(G)d−(v)minimum indegreeΔ−(G)=max⁡v∈V(G)d−(v)maximum indegreeδ±(G)=min⁡(δ+(G),δ−(G))minimum semidegree\begin{aligned} \delta^{+}(G) &= \min_{v \in V(G)} d^{+}(v) && \text{minimum outdegree} \\ \Delta^{+}(G) &= \max_{v \in V(G)} d^{+}(v) && \text{maximum outdegree} \\ \delta^{-}(G) &= \min_{v \in V(G)} d^{-}(v) && \text{minimum indegree} \\ \Delta^{-}(G) &= \max_{v \in V(G)} d^{-}(v) && \text{maximum indegree} \\ \delta^{\pm}(G) &= \min(\delta^{+}(G),\delta^{-}(G)) && \text{minimum semidegree} \end{aligned}

We extend the notion of out- and inneighborhood to sets of vertices – for A⊆V(G)A \subseteq V(G), we set N+(A):=⋃a∈AN+(a)N^{+}(A) := \bigcup_{a\in A} N^{+}(a), and define N−(A)N^{-}(A) analogously.

For A,B⊆V(G)A, B \subseteq V(G), we set E(A,B):=E(G)∩(A×B)E(A,B) := E(G) \cap(A \times B) (the set of arcs from AA to BB in the graph GG) and e(A,B):=∣E(A,B)∣e(A,B) := |E(A,B)|.

References

  1. [1]Noga Alon and Asaf Shapira. Testing subgraphs in directed graphs. Journal of Computer and Systems Sciences, 69:354–382, 2004.
  2. [2]Louis Caccetta and Roland Häggkvist. On minimal digraphs with given girth. Congressus Numerantium, XXI:181–187, 1978.
  3. [3]Andrzej Czygrinow, Theodore Molla, Brendan Nagle, and Roy Oursler. On even rainbow or nontriangular directed cycles. Journal of Combinatorics, 12(4):589–662, 2021.arxiv.org/abs/1912.02049
  4. [4]Andrzej Grzesik and Jan Volec. Degree conditions forcing directed cycles. International Mathematics Research Notices, 2023(11):9711–9753, 2023.arxiv.org/abs/2102.12830
  5. [5]Luke Kelly, Daniela Kühn, and Deryk Osthus. Cycles of given length in oriented graphs. Journal of Combinatorial Theory, Series B, 100(3):251–264, 2010.arxiv.org/abs/0806.0933
  6. [6]Daniela Kühn, Deryk Osthus, and Diana Piguet. Embedding cycles of given length in oriented graphs. European Journal of Combinatorics, 34(2):495–501, 2013.DOI
  7. [7]OpenAI. A proof of Seymour’s second-neighborhood conjecture. OpenAI Math Release preprint OAI:A-proof-of-Seymours-second-neighborhood-conjecture-September-23-2026, 2026.
  8. [8]Blair D. Sullivan. A summary of results and problems related to the Caccetta-Häggkvist conjecture. arXiv preprint math/0605646, 2006.

Paper details

vlnc:W_nf96rg4z
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
  • Mathematics

Claude Opus 5.5

View statement
Looking for related papers…
Contents