Generalized Tur\'an problem for directed cycles

Andrzej Grzesik; Bart{\l}omiej Kielak; Justyna Jaworska; Piotr Kuc; Tomasz \'Slusarczyk

REVIEW 3 major objections 4 minor 24 references

Generalized Tur\'an problem for directed cycles

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For every k and l, the paper determines how many directed k-cycles an oriented graph can have without a directed l-cycle: order n^k when k does not divide l, order n^{k-1} when it does.

desk verdict Strong, original paper on the directed generalized Turán problem; the stress-test's objection to Claim 16 rests on a misreading of the path notation, and the real soft spots are the unpublished [17] and insufficiently documented computer-assisted steps. read the letter →

arxiv 2505.22189 v1 pith:73J7KMHY submitted 2025-05-28 math.CO

Andrzej Grzesik , Justyna Jaworska , Bart{l}omiej Kielak , Piotr Kuc , Tomasz Ślusarczyk This is my paper · ORCID

classification math.CO MSC 05C2005C3505C38

keywords generalizedTuránproblemdirectedcyclesorientedgraphsextremalgraphtheoryblow-upconstructionsdivisibilitydichotomysparsesettingdense

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

An oriented graph is a directed graph with at most one arc between any two vertices. The paper asks: if such a graph on $n$ vertices contains no directed $\ell$-cycle $\vec C_\ell$, how many directed $k$-cycles $\vec C_k$ can it contain? It proves the order of magnitude for every pair: $\Theta(n^k)$ when $k\nmid \ell$ and $\Theta(n^{k-1})$ when $k\mid \ell$. For large forbidden length $\ell$ it identifies the leading constant, showing that a balanced blow-up of a shorter directed cycle is extremal except in one parity case, where a random orientation of a complete balanced bipartite graph is better. For small $\ell$ the extremal constructions are many and varied, and the paper determines leading constants for several representative pairs, leaving the case $(k,\ell)=(5,4)$ open.

What carries the argument

The argument runs through three devices. First, a clearing step uses the directed regularity lemma and the blow-up lemma to delete $o(n^2)$ arcs so that all homomorphic images of $\vec C_\ell$ (closed directed walks of length $\ell$) disappear, losing only $o(n^k)$ copies of $\vec C_k$. Second, a weighting lemma counts copies of $\vec C_k$ by averaging probabilities of 'good sequences' around each cycle; together with the AM-GM inequality it bounds the count by $\frac nk(\frac nd)^{k-1}$ whenever every vertex has at most $2k/d$ neighbours on any $\vec C_k$, and this neighbourhood bound is forced by forbidding cycles with one arc reversed through a coin-representation theorem. Third, in the bipartite exception, a high-minimum-degree plus no-short-odd-cycle argument forces the extremal graph to be bipartite, and an eigenvalue majorization inequality bounds the cycle count by $\frac2k(\frac n4)^k$.

What would settle it

Check the unpublished inducibility bound by computing, for small $n$, the maximum number of induced copies of each orientation of $C_4$ in an oriented graph and comparing the extremal construction with the iterated blow-up of $\vec C_4$; a higher density or a different extremal construction would invalidate $\mathrm{ex}(n,\vec C_4,\vec C_3)=\frac{n^4}{4^4-1}+o(n^4)$. Equivalently, a computer search for directed-triangle-free oriented graphs whose directed 4-cycle count beats the iterated blow-up on the same vertex set would decide the matter.

Watch

Extended reading notes

Core claim

Writing $\mathrm{ex}(n,\vec C_k,\vec C_\ell)$ for the maximum number of directed $k$-cycles in an $n$-vertex oriented graph with no directed $\ell$-cycle, the paper establishes the dichotomy $\mathrm{ex}(n,\vec C_k,\vec C_\ell)=\Theta(n^k)$ if $k\nmid\ell$ and $=\Theta(n^{k-1})$ if $k\mid\ell$ (Theorem 4). In the dense case, for $\ell\ge 2(k-1)^2$ and $k\nmid\ell$, let $d$ be the smallest divisor of $k$ greater than $2$ that does not divide $\ell$; then, when $k$ is odd, $\ell$ is even, or $d\le 4$, the value is $\frac{n}{k}(\frac{n}{d})^{k-1}+o(n^k)$, attained by a balanced blow-up of $\vec C_d$. When $k$ is even, $4\nmid k$, $\ell$ is odd, and $3\nmid k$ or $3\mid\ell$, with $\ell>33k^2$, the value is $\frac{2}{k}(\frac n4)^k+o(n^k)$, attained by a random orientation of a complete balanced bipartite graph. For small $\ell$ the paper computes several exact leading constants: $\frac{n^4}{4^4-1}+o(n^4)$ for $(4,3)$ via an iterated blow-up of $\vec C_4$, $(\frac n4)^4+o(n^4)$ for $(4,6)$, $\frac{n^5}{512}+o(n^5)$ for $(5,3)$, $\frac{27}{16}(\frac n5)^5+o(n^5)$ for $(5,7)$, and $(\frac n5)^5+o(n^5)$ for $(5,8)$ and $(5,13)$. It also solves the sparse example $(3,6)$ with value $\frac14 n^2+o(n^2)$. The directed-graph analogue for large $\ell$ not divisible by $k$ is $\frac nk(\frac nd)^{k-1}+o(n^k)$ with $d$ the smallest positive divisor of $k$ not dividing $\ell$.

Load-bearing premise

The exact constant for the $(k,\ell)=(4,3)$ case rests on an unpublished manuscript's claim about the largest possible density of induced 4-cycles in an oriented graph; if that claim is wrong or does not transfer to counting directed 4-cycles, the stated constant is unsupported.

Editorial extensions

If this is right

The order of magnitude is now known for every pair $(k,\ell)$, closing the directed-cycle version of the generalized Turán problem at the $\Theta$ level.
For large $\ell$, the extremal graph is almost always a balanced blow-up of a shorter cycle: the shortest divisor $d>2$ of $k$ that does not divide $\ell$ determines both the construction and the constant.
In the one parity exception—$k$ even, $\ell$ odd, $d\ge 5$—the extremal graph is a random orientation of a complete balanced bipartite graph, giving $\frac2k(\frac n4)^k+o(n^k)$ copies.
For small $\ell$ no single construction dominates: iterated blow-ups, transitive tournaments inside blobs, and unbalanced blow-ups with bipartite patches each win for different pairs, showing many genuinely different extremal regimes.
The directed-graph version of the problem has the same order of magnitude and the same type of blow-up extremal value for large $\ell$, with $d$ now allowed to be $2$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same divisibility dichotomy should survive when the forbidden object is any fixed orientation of a cycle of length $\ell$: the paper's final remarks show such a cycle is homomorphic to $\vec C_\ell$, so its upper bounds apply, but the extremal constructions may need to be re-optimized for each orientation.
The threshold-orientation construction used for the open case $(5,4)$ suggests that between pure blow-ups and random orientations there is a continuous family of extremal graphs parameterized by monotone functions; testing this family computationally for other unsolved pairs could reveal a general interpolation principle.
The conjectured formula $\mathrm{ex}(n,\vec C_3,\vec C_{3t})\sim \frac{t-1}{4}n^2$ indicates a family of extremal graphs with one small blob and two large parts; verifying $t=3$ would give the first sparse-case constant beyond the $(3,6)$ example and might expose a general sparse construction.
On the open question of $\mathrm{ex}(n,\vec C_5,\vec C_4)$, the paper's lower bound $0.0517\binom n5$ comes from a monotone orientation of a blow-up of a 7-cycle plus chords; a natural testable extension is to optimize the monotone threshold function beyond the form $\min(x+c,1)$ to see whether the constant can be pushed closer to the computer-assisted upper bound.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Bottom line: this is a real contribution, not a repackaging. The directed analogue of the generalized Turán problem for cycles has not been treated before, and the paper settles the order of magnitude for every k and l, gives leading asymptotics for all dense pairs with l large, and finds a genuinely varied set of extremal constructions for small l. The main proof machinery — thick-arc induction, the Král'-Norin-Volec weight argument, and the eigenvalue bound for orientations of complete bipartite graphs — is standard but applied carefully, and most of the heavy lifting is self-contained.

On the stress-test: the alleged collapse of Lemma 12 does not happen. The test reads p_2 as the number of length-two directed paths, but the paper defines P_r as a path on r vertices, i.e. r-1 arcs, so P_2 is a single arc and p_2 is just the edge count. The induction base is correct: p_1(v) = 1 for all v, so the sum of d^+(v) p_1^2(v) over v equals e(G). The random orientation of K_{n/2,n/2} has p_2 ~ n^2/4, exactly matching the claimed bound, not n^3. Claim 16 is fine, and the subsequent estimates in Claim 17 check out. I could not find a load-bearing internal error in the proof of Theorem 11.

The real soft spots are external dependencies and one compressed optimization. Theorem 23 imports its upper bound from the unpublished manuscript [17], so the exact constant for (k, l) = (4, 3) is not self-contained. Theorem 27 provides a Flagmatic script but no generated certificate, so the verification is not reproducible from the text alone. And Theorem 28's final blob-size optimization is asserted rather than proved. All three are addressable, and none affects the main order-of-magnitude result or the large-l dense asymptotics.

The citation pattern is honest: the self-citations are to results actually used, and the open problem for (5, 4) is stated plainly. This paper deserves a serious referee, not a desk rejection. I would send it out and ask the authors to either resolve the dependence on [17] or mark the (4, 3) theorem explicitly conditional, and to supply certificates or detailed derivations for the two computer-assisted/optimization steps. It is well worth discussing in a reading group.

Referee Report

3 major / 4 minor

Summary. The paper studies the generalized Turán problem for oriented graphs, determining the maximum number of directed k-cycles in an n-vertex oriented graph that contains no directed l-cycle. The main results are an order-of-magnitude classification for all k,l (Theorem 4), asymptotic values in the dense setting for large l (Theorems 8 and 11), several small-cycle cases (Theorems 20, 23, 24, 26, 27, 28, 31, and 33), and an analogous theorem for directed graphs (Theorem 35). Theorems 8 and 11 together are intended to settle the leading constant whenever l is large and k does not divide l, with extremal constructions given by balanced blow-ups of a directed cycle or by a random orientation of a complete bipartite graph.

Significance. If the results were established, they would constitute a substantial contribution to generalized Turán theory for directed graphs: the paper gives a complete order of magnitude for every pair (k,l) and, for large forbidden cycle lengths, identifies the leading constant and the extremal construction. The paper also contains some sound and elegant components, notably the induction proof of Theorem 4, the weight argument of Lemma 9, and the eigenvalue bound of Lemma 13, and it provides a reproducible Flagmatic script for one of the small cases. However, two load-bearing statements in the proof machinery are false as written, and a third main theorem depends on an unpublished external manuscript. These issues leave the paper's headline results unproven in the submitted form.

major comments (3)

[3.2.1] Claim 16 is false. It asserts p_{2j} ≤ n(n/4)^{2j-1} for every positive integer j. In the proof, the displayed base equality reads Σ_v d^+(v)p_1^2(v) = e(G), but p_1(v) is defined as the number of directed P_1 ending at v, so p_1(v) = d^-(v); the left-hand side is therefore Σ_v d^+(v)d^-(v)^2, not e(G). This is not a harmless typo: in a balanced random orientation of K_{n/2,n/2}, the expected number of directed P_2 subgraphs is n^3/16 + o(n^3), while the claimed bound for j=1 is n(n/4) = n^2/4. The inequality fails already at j=1. Since Claim 17 uses p_{k-4} ≤ n(n/4)^{k-5} to control the number of ways to complete a k-cycle through a low-degree vertex, the proof of the minimum-degree bound δ(ẽG) > 2n/23 collapses. Consequently Lemma 12, which is the entire proof of Theorem 11, is unsupported, and the large-ℓ random-bipartite case is not proved.
[1.1] Observation 1 is false as stated. Let F = C_6 and let H be the oriented graph consisting of two directed triangles sharing one vertex. Under the paper's definition, H is a homomorphic image of C_6: map the six vertices of C_6 to the sequence a,b,c,a,d,e, where a,b,c and a,d,e are the two triangles. A balanced blow-up of H contains no C_6, because the underlying undirected graph has no cycle of length 6. However, deleting o(n^2) arcs cannot destroy all copies of H: to eliminate H one must delete all arcs of at least one of the two directed triangles, which requires Θ(n^2) deletions. Thus the reduction used at the start of Section 3 — 'remove o(n^2) arcs using Observation 1 to delete from G all homomorphic images of C_ℓ' — is not valid. This clearing step is used in the proofs of Theorems 8, 11, 24, 26, 28, 31, and 35, so those upper-bound proofs lack a valid foundation and would need a substantially different reduction.
[3.3.2] The upper bound for ex(n,C_4,C_3) is imported entirely from the unpublished manuscript [17] (Hu–Lidický–Volec, 'Inducibility of orientations of C_4'). No proof of the relevant inducibility result is given in this paper, and no public version of [17] is referenced. The stated constant n^4/(4^4-1) + o(n^4) is therefore conditional on an external result that the present manuscript does not make available to the reader. For a main theorem, this dependency should be removed or the external result should be published and cited in a verifiable form.

minor comments (4)

[3.3.3, Theorem 27] The flag-algebra proof is presented only as a Flagmatic script; the generated certificate is not included, and the target bound 15/64 is not reconciled with the claimed constant 1/512 n^5. Without the certificate or an explanation of the normalization, the proof is not independently verifiable from the manuscript.
[2, Lemma 9] The same symbol w(D) is used for both the forward and reverse sampling weights in the proof of Lemma 9; renaming the second weight would improve readability.
[1] The text contains numerous formatting artifacts and typos, such as missing spaces in the abstract, 'forex(n,C_4,C_3)' in Section 3.3.2, and inconsistent arrow/bold notation for cycles. A careful copyedit is needed.
[3.3.3, Theorem 28] The final optimization step in the proof of Theorem 28 is only sketched ('Optimizing the sizes of the six blobs ... gives in both cases the same blob sizes ...'); the computation should be shown to confirm the claimed constant 27/16.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivations are self-contained or rely on external benchmarks, and the self-citations are not load-bearing.

full rationale

The paper contains no fitted parameters and no prediction that is defined in terms of the target quantity. The order-of-magnitude bounds in Theorem 4 are proved directly: the lower bounds come from explicit blow-up constructions, and the upper bounds follow from a thick-arc argument together with the Frobenius-type Corollary 3. In the dense setting, Theorem 8 derives the upper bound from Lemma 9, whose proof is a self-contained adaptation of the Král'-Norin-Volec weighting method, and the required neighborhood bound is established inside the proof using Corollary 3 and the definition of d; the extremal construction is a balanced blow-up of C_d, but its size is not inserted as an input to the upper-bound calculation. Theorem 11 similarly derives the random-bipartite bound from the Andrásfai-Erdős-Sós theorem and an eigenvalue estimate (Lemma 13) that is proved in full, including the inequality whose proof is credited to [15] but also included inline. The self-citations to [13], [14], and [15] cite published, externally checkable results (e.g., the maximum number of pentagons in triangle-free graphs) that do not contain the present theorem as an assumption. Theorem 23's use of the unpublished manuscript [17] for the inducibility of orientations of C4 is an external dependency rather than a circular reduction, and the cited result is about induced copies of C4, not about ex(n,C4,C3) itself. A suspected error in Claim 16 or the reliance on [17] would be a correctness risk, not a circularity, because neither reduces the claimed result to its own inputs by definition or by a fitted parameter. Overall, the derivation chain is not circular.

Assumptions & free parameters 0 free parameters · 10 assumptions · 0 invented entities

The proofs rest on standard extremal graph theory tools plus four external or computational ingredients: the unpublished inducibility result [17], the Flagmatic computation in Theorem 27, the known maximum of C5 in triangle-free graphs, and the K4-free triangle bound. No free parameters or invented entities are introduced; all constants in the theorems are derived from the constructions and optimization.

assumptions (10)

standard math Directed Szemeredi regularity lemma and blow-up lemma: a subgraph-free oriented graph can be made free of all homomorphic images by deleting o(n^2) arcs (Observation 1).
Used throughout Section 3 to pass to (k,l)-cleared graphs while losing only o(n^k) copies of C_k.
standard math Brauer's theorem and Corollary 3 (Frobenius coin problem): sufficiently large multiples of the gcd are nonnegative integer combinations of given integers.
Invoked repeatedly to force a forbidden homomorphic image of C_l from smaller structures, for example in Theorem 8, Claim 15, and Theorem 35.
standard math Mantel's theorem: a triangle-free graph on n vertices has at most n^2/4 edges.
Used in Claim 16 to bound path counts and in Theorem 33 to bound thin arcs.
standard math The Andrasfai-Erdos-Sos theorem, in the form used by the authors to conclude bipartiteness from the minimum degree and short odd cycle conditions.
Used in the proof of Lemma 12 to conclude the extremal graph is bipartite.
standard math Perron-Frobenius theorem for nonnegative matrices and Ky Fan's eigenvalue inequality (Proposition 18).
Used in Lemma 13 to bound the trace of the k-th power of the adjacency matrix of an orientation of a complete bipartite graph.
standard math The complex-number inequality Re(z^k) <= k|z|^(k-1) Re(z) for Re(z) >= 0 and k = 2 mod 4.
Used in step (c) of Lemma 13; the paper includes a proof and credits [15].
standard math Erdos' theorem: a K4-free undirected graph on n vertices has at most (n/3)^3 + O(n^2) triangles, attained by a balanced blow-up of K3.
Used in Claim 21 to bound the number of directed triangles in a transitive-triangle-free oriented graph.
standard math The maximum number of C5 in a triangle-free undirected graph is (n/5)^5 + o(n^5) (Grzesik [13], Hatami et al. [16]).
Used in Theorem 26 to transfer triangle-freeness to the bound on C5 copies.
domain assumption The inducibility of orientations of C4 is maximized by the iterated blow-up of C4, claimed in the unpublished manuscript [17] (see also [6]).
The upper bound in Theorem 23 for ex(n,C4,C3) is taken from this external result; no proof appears in the present paper.
domain assumption The flag algebra method with Flagmatic is a valid and complete proof system, and the script in Theorem 27 generates a verifiable certificate.
Theorem 27's upper bound rests on this computer-assisted proof; the paper supplies the script but not the certificate.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Generalized Tur\'an problem for directed cycles." pith.science (2026). https://pith.science/paper/73J7KMHY

@misc{pith2026250522189,
  author       = {Pith},
  title        = {Pith review of: Generalized Tur\'an problem for directed cycles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/73J7KMHY}},
  note         = {Machine review of arXiv:2505.22189}
}

abstract

For integers $k, \ell \geq 3$, let $\mathrm{ex}(n, \overrightarrow{C_k}, \overrightarrow{C_\ell})$ denote the maximum number of directed cycles of length $k$ in any oriented graph on $n$ vertices which does not contain a directed cycle of length $\ell$. We establish the order of magnitude of $\mathrm{ex}(n, \overrightarrow{C_k}, \overrightarrow{C_\ell})$ for every $k$ and $\ell$ and determine its value up to a lower error term when $k \nmid \ell$ and $\ell$ is large enough. Additionally, we calculate the value of $\mathrm{ex}(n, \overrightarrow{C_k}, \overrightarrow{C_\ell})$ for some other specific pairs $(k, \ell)$ showing that a diverse class of extremal constructions can appear for small values of $\ell$.

Figures

Figures reproduced from arXiv: 2505.22189 by the authors.

**Figure 2.** Examples for k = 4 and t = 3, t = 4 respectively. 3 The dense setting When determining ex(n, −→Ck, −→Cℓ) in the dense setting, our usual framework is to take any extremal graph G and remove o(n 2 ) arcs using Observation 1 to delete from G all homomorphic images of −→Cℓ, that is, closed directed walks of length ℓ. Note that this way we remove only o(n k ) copies of −→Ck. Finally, we delete from G all arcs and vertic… view at source ↗

**Figure 3.** For k = 4, existence of −→T3 implies existence of homomorphic images of −→C5 and −→C7. Observation 7. For any integers m ≥ 3, x ≥ 1 and y ≥ 0, a (k, mx + ky)-cleared graph does not contain −→Cm. Proof. Since every vertex of a (k, mx + ky)-cleared graph occurs in a −→Ck, if the graph contains a −→Cm, it also contains a −→Ck and a −→Cm joint by a vertex, which is a forbidden homomorphic image of −→Cmx+ky. 5 [PITH_FUL… view at source ↗

Figures from the paper (8 more)

**Figure 4.** Figure 4: Example for ℓ = 8, m = 1 This claim shows that graph G satisfies the assumptions of part a) of the theorem, hence ex(n, −→C3, −→Cℓ) ≤ n 3 27 + O(n 2 ). 3.3.2 Maximizing −→C4 In contrast to the case of −→C3, when we maximize the number of copies of −→C4, an extremal con…

**Figure 5.** Figure 5: An iterated blow-up of −→C4. Theorem 23. The value of ex(n, −→C4, −→C3) is achieved in the iterated blow-up of −→C4. In particular, ex(n, −→C4, −→C3) = n 4 4 4 − 1 + o(n 4 ). Proof. In any graph not containing −→C3, each copy of −→C4 is induced, thus the number of copi…

**Figure 6.** Figure 6: Forbidden configurations when w belongs to two different sets A1. i ∈ {0, 1, 2, 3}, and the same holds for A2 and, by symmetry, for A3. This implies that the contribution of w can be at most 3 and the claim follows. Combining this result with the previous inequality gi…

**Figure 7.** Figure 7: The extremal graph for ex(n, −→C5, −→C3). from fl a gm a ti c . a l l import ∗ problem = OrientedGraphProblem ( 5 , f o r b i d=" 3: 1 2 2 3 3 1 " , d e n si t y =[" 5: 1 2 2 3 3 4 4 5 5 1 " , " 5: 1 2 2 3 3 4 4 5 5 1 1 3 " , " 5: 1 2 2 3 3 4 4 5 5 1 1 3 2 4 " ] , t y …

**Figure 8.** Figure 8: An extremal graph for ex(n, −→C5, −→C7). Clearly, all the vertices in one blob are contained in the same number of −→C5. Assume that for two different blobs x and y there is no −→C5 in G′ containing both x and y and say that the number of copies of −→C5 in G containing…

**Figure 9.** Figure 9: Optimizing the sizes of the six blobs of [PITH_FULL_IMAGE:figures/full_fig_p018_9.png]

**Figure 9.** Figure 9: Possible placements of arcs in G′ . They correspond to adjacent groups (but without the useless dashed arc), or opposite groups in the conjectured extremal construction. Theorem 31. ex(n, −→C5, −→C8) = n 5 5 + o(n 5 ) and ex(n, −→C5, −→C13) = n 5 5 + o(n 5 ). Proof. …

**Figure 10.** Figure 10: The extremal graph for ex(n, −→C3, −→C6). 20 [PITH_FULL_IMAGE:figures/full_fig_p020_10.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 23 canonical work pages

[17]

Inducibility of orientations ofC4

Ping Hu, Bernard Lidický, and Jan Volec. Inducibility of orientations ofC4. Manuscript

work page
[1]

Testing subgraphs in directed graphs.Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 700–709, 2003

Noga Alon and Asaf Shapira. Testing subgraphs in directed graphs.Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 700–709, 2003

work page 2003
[2]

ManyTcopies inH-free graphs.Journal of Combinatorial Theory, Series B, 121:146–172, 2016

Noga Alon and Clara Shikhelman. ManyTcopies inH-free graphs.Journal of Combinatorial Theory, Series B, 121:146–172, 2016

work page 2016
[3]

Béla Andrásfai, Paul Erdős, and Vera T. Sós. On the connection between chromatic number, maximal clique and minimal degree of a graph.Discrete Mathematics, 8(3):205–218, 1974

work page 1974
[4]

On the generalized Turán problem for odd cycles.SIAM Journal on Discrete Mathematics, 38(3):2416–2428, 2024

Csongor Beke and Oliver Janzer. On the generalized Turán problem for odd cycles.SIAM Journal on Discrete Mathematics, 38(3):2416–2428, 2024

work page 2024
[5]

On a problem of partitions.American Journal of Mathematics, 64(1):299–312, 1942

Alfred Brauer. On a problem of partitions.American Journal of Mathematics, 64(1):299–312, 1942

work page 1942
[6]

Inducibility of 4-vertex tournaments.arXiv:2103.07047, 2021

Dalton Burke, Bernard Lidick` y, Florian Pfender, and Michael Phillips. Inducibility of 4-vertex tournaments.arXiv:2103.07047, 2021

arXiv 2021
[7]

On the number of complete subgraphs contained in certain graphs.Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei, 7(3):459–464, 1962

Paul Erdős. On the number of complete subgraphs contained in certain graphs.Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei, 7(3):459–464, 1962. 22

work page 1962

Show all 24 references

[8]

On some problems in graph theory, combinatorial analysis and combinatorial number theory.Graph Theory and Combinatorics, pages 1–17, 1984

Paul Erdős. On some problems in graph theory, combinatorial analysis and combinatorial number theory.Graph Theory and Combinatorics, pages 1–17, 1984

1984
[9]

On the structure of linear graphs.Bulletin of the American Mathematical Society, 52:1087–1091, 1946

Paul Erdős and Arthur Harold Stone. On the structure of linear graphs.Bulletin of the American Mathematical Society, 52:1087–1091, 1946

1946
[10]

On a theorem of Weyl concerning eigenvalues of linear transformations: II.Proceed- ings of the National Academy of Sciences, 36(1):31–35, 1950

Ky Fan. On a theorem of Weyl concerning eigenvalues of linear transformations: II.Proceed- ings of the National Academy of Sciences, 36(1):31–35, 1950

1950
[11]

Generalized Turán prob- lems for even cycles.Journal of Combinatorial Theory, Series B, 145:169–213, 2020

Dániel Gerbner, Ervin Győri, Abhishek Methuku, and Máté Vizer. Generalized Turán prob- lems for even cycles.Journal of Combinatorial Theory, Series B, 145:169–213, 2020

2020
[12]

AgeneralizedTuránproblemanditsapplications.Proceed- ings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 760–772, 2018

LiorGishbolinerandAsafShapira. AgeneralizedTuránproblemanditsapplications.Proceed- ings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 760–772, 2018

2018
[13]

On the maximum number of five-cycles in a triangle-free graph.Journal of Combinatorial Theory, Series B, 102(5):1061–1066, 2012

Andrzej Grzesik. On the maximum number of five-cycles in a triangle-free graph.Journal of Combinatorial Theory, Series B, 102(5):1061–1066, 2012

2012
[14]

On the maximum number of odd cycles in graphs without smaller odd cycles.Journal of Graph Theory, 99(2):240–246, 2022

Andrzej Grzesik and Bartłomiej Kielak. On the maximum number of odd cycles in graphs without smaller odd cycles.Journal of Graph Theory, 99(2):240–246, 2022

2022
[15]

Lovász, and Jan Volec

Andrzej Grzesik, Daniel Král’, László M. Lovász, and Jan Volec. Cycles of a given length in tournaments.Journal of Combinatorial Theory, Series B, 158:117–145, 2023

2023
[16]

On the number of pentagons in triangle-free graphs.Journal of Combinatorial Theory, Series A, 120(3):722–732, 2013

Hamed Hatami, Jan Hladk` y, Daniel Král’, Serguei Norine, and Alexander Razborov. On the number of pentagons in triangle-free graphs.Journal of Combinatorial Theory, Series A, 120(3):722–732, 2013

2013
[18]

Sárközy, and Endre Szemerédi

János Komlós, Gábor N. Sárközy, and Endre Szemerédi. Blow-up lemma.Combinatorica, 17:109–123, 1997

1997
[19]

A bound on the inducibility of cycles.Journal of Combinatorial Theory, Series A, 161:359–363, 2019

Daniel Král’, Sergey Norin, and Jan Volec. A bound on the inducibility of cycles.Journal of Combinatorial Theory, Series A, 161:359–363, 2019

2019
[20]

Wiley New York, 1988

Henryk Minc.Nonnegative matrices, volume 170. Wiley New York, 1988

1988
[21]

A note on the Turán function of even cycles.Proceedings of the American Mathematical Society, 140(11):3687–3692, 2012

Oleg Pikhurko. A note on the Turán function of even cycles.Proceedings of the American Mathematical Society, 140(11):3687–3692, 2012

2012
[22]

Sylvester

James J. Sylvester. On subvariants, i.e. semi-invariants to binary quantics of an unlimited order.American Journal of Mathematics, 5(1):79–136, 1882
[23]

On an extremal problem in graph theory (in Hungarian).Középiskolai Matem- atikai és Fizikai Lapok, 48:436–452, 1941

Paul Turán. On an extremal problem in graph theory (in Hungarian).Középiskolai Matem- atikai és Fizikai Lapok, 48:436–452, 1941

1941
[24]

Flagmatic software package, further developed by Jakub Sliačan, available at https://github.com/jsliacan/flagmatic

Emil Vaughan. Flagmatic software package, further developed by Jakub Sliačan, available at https://github.com/jsliacan/flagmatic. 23

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [17]

Inducibility of orientations ofC4

Ping Hu, Bernard Lidický, and Jan Volec. Inducibility of orientations ofC4. Manuscript

work page

[2] [1]

Testing subgraphs in directed graphs.Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 700–709, 2003

Noga Alon and Asaf Shapira. Testing subgraphs in directed graphs.Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 700–709, 2003

work page 2003

[3] [2]

ManyTcopies inH-free graphs.Journal of Combinatorial Theory, Series B, 121:146–172, 2016

Noga Alon and Clara Shikhelman. ManyTcopies inH-free graphs.Journal of Combinatorial Theory, Series B, 121:146–172, 2016

work page 2016

[4] [3]

Béla Andrásfai, Paul Erdős, and Vera T. Sós. On the connection between chromatic number, maximal clique and minimal degree of a graph.Discrete Mathematics, 8(3):205–218, 1974

work page 1974

[5] [4]

On the generalized Turán problem for odd cycles.SIAM Journal on Discrete Mathematics, 38(3):2416–2428, 2024

Csongor Beke and Oliver Janzer. On the generalized Turán problem for odd cycles.SIAM Journal on Discrete Mathematics, 38(3):2416–2428, 2024

work page 2024

[6] [5]

On a problem of partitions.American Journal of Mathematics, 64(1):299–312, 1942

Alfred Brauer. On a problem of partitions.American Journal of Mathematics, 64(1):299–312, 1942

work page 1942

[7] [6]

Inducibility of 4-vertex tournaments.arXiv:2103.07047, 2021

Dalton Burke, Bernard Lidick` y, Florian Pfender, and Michael Phillips. Inducibility of 4-vertex tournaments.arXiv:2103.07047, 2021

arXiv 2021

[8] [7]

On the number of complete subgraphs contained in certain graphs.Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei, 7(3):459–464, 1962

Paul Erdős. On the number of complete subgraphs contained in certain graphs.Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei, 7(3):459–464, 1962. 22

work page 1962