REVIEW 2 major objections 4 minor 18 references
On the supersaturation of oriented Tur\'an problems
T0 review · 2 major / 4 minor · reviewed 2026-08-02 · deepseek-v4-flash
Pith's one-line read The paper establishes oriented supersaturation: arc density above the oriented Turán threshold forces a positive-density supply of every forbidden oriented subgraph, including an exact one-extra-arc bound for transitive triangles and a rati
desk verdict Solid partial paper: three theorems are good, but the Moon–Moser inequality for transitive tournaments has a false double-counting claim and should not be accepted as is. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The transitive tournament is the workhorse: the acyclic tournament whose vertices can be ordered so every arc points forward. The general supersaturation proof averages over m-vertex induced subgraphs: if too few m-sets were above the extremal density, the total arc count would fall short, while each above-threshold m-set must contain a copy of F; double-counting m-sets against copies of F yields δ. For transitive tournaments, the argument is a pair count of (T,R) where T is a transitive r-tournament and R is a non-transitive r-set sharing r−1 vertices with T. An upper bound on these pairs via Jensen's inequality and a lower bound obtained by counting non-extensions are combined to produce t
What would settle it
The lower bound in the double count assumes that for each transitive r-set Q and each vertex u' whose addition does not make a transitive (r+1)-set, some vertex y in Q makes u', y together with any other r−2 vertices of Q non-transitive. This is false: in the four-vertex tournament with directed triangle a→b→c→a and d dominating a,b,c, take the transitive triple Q={a,b,d} and u'=c; no choice of y gives the claimed property for all remaining vertices. That failure means Theorem 1.9's ratio inequality needs a repaired argument.
Extended reading notes
Core claim
For a fixed oriented graph F, let π_o(F) be the limit of ex_o(n,F)/(n choose 2). The paper's main theorem says that for every ε>0 there is δ>0 such that every sufficiently large oriented graph with at least (π_o(F)+ε)(n choose 2) arcs contains at least δ(n choose h) copies of F. For the transitive triangle, one arc above the balanced complete 3-partite extremal graph forces roughly 2n/3 copies. With N_r the number of transitive r-tournaments, it derives the ratio inequality N_{r+1}/N_r ≥ (r^2 N_r/N_{r-1} − n)/(r^2−1), and from it a supersaturation bound whenever |E(G)| ≥ (1−1/t)n^2/2. It also shows that |E(G)| ≥ e s^{1/t} n^{2−1/t} forces at least (e/t)^t n^t copies of the antidirected compl
Load-bearing premise
The transitive-tournament ratio rests on the assumption that whenever a vertex u' fails to extend a transitive r-tournament Q, some vertex y in Q has the property that u', y together with any r−2 other vertices of Q is non-transitive; that 'any' fails even for r=3, so the inequality as proved needs a repaired count.
Editorial extensions
If this is right
- If the main theorem holds, an n-vertex oriented graph with arc density π_o(F)+ε contains at least a fixed positive fraction δ of all possible h-vertex sets as copies of F; the threshold is truly a phase transition.
- For transitive triangles, one arc beyond the balanced complete 3-partite extremal graph forces at least about 2n/3 copies—an oriented analogue of the sharp triangle-counting result for graphs.
- The ratio inequality N_{r+1}/N_r ≥ (r² N_r/N_{r-1} − n)/(r²−1) links consecutive transitive-tournament counts; if valid, it yields the supersaturation bound N_r ≥ (t choose r)(n/t)^r for oriented graphs with arc count at least (1−1/t)n²/2.
- For antidirected complete bipartite graphs, arc count ≥ e s^{1/t} n^{2−1/t} forces polynomial many copies, extending bipartite supersaturation to oriented settings.
Reading between the lines
- The faulty lower-bound step suggests Theorem 1.9 may still be salvageable by counting only the non-transitive r-sets that do satisfy the required property, possibly with a weaker constant; a natural test is to compute the inequality on the four-vertex counterexample and see which term breaks.
- If a corrected ratio inequality holds, it would imply a local counting stability for transitive tournaments: tournaments with many transitive r-sets must contain many transitive (r+1)-sets, a directed analogue of clique supersaturation that could feed into extremal results for acyclic oriented graphs.
- The exact one-extra-arc result for the transitive triangle invites a full stability-supersaturation classification for all tournaments of order three, including the cyclic triangle, whose extremal behaviour differs because oriented graphs containing a directed cycle can hide copies differently.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper develops supersaturation results for oriented Turán problems. Theorem 1.7 gives a general Erdős–Simonovits-type statement: any oriented graph with edge density above the oriented Turán density of a fixed oriented graph F contains a positive-density number of copies of F. Theorem 1.8 establishes a Rademacher-type bound for transitive triangles: an n-vertex oriented graph with one more arc than the balanced complete 3-partite oriented extremal graph contains about 2n/3 copies of TT3. Theorem 1.9 claims a Moon–Moser-type inequality for transitive tournaments TTr, and Theorem 1.10 derives a supersaturation bound for general r from it. Theorem 1.11 gives a supersaturation result for antidirected complete bipartite graphs K_{s,t}. The proofs of Theorems 1.7, 1.8, and 1.11 are self-contained averaging/induction arguments; the proof of Theorem 1.9, however, contains a false intermediate claim that is load-bearing for both Theorems 1.9 and 1.10.
Significance. If all the results were correct, this would be a meaningful step for oriented Turán supersaturation, especially the first oriented analogue of the Moon–Moser inequality and the explicit supersaturation bound for antidirected complete bipartite graphs. Theorem 1.7 is a clean and correct convergence/density argument, and Theorem 1.8 is a carefully detailed induction with only local technical points. Theorem 1.11 gives explicit constants and is also essentially correct. The main defect is the proof of Theorem 1.9: the double-counting lower bound relies on a false structural assertion, and because Theorem 1.10 is derived from Theorem 1.9, the gap propagates. The paper’s central claims are therefore currently unproven in their full stated generality, though the affected theorem may be repairable. The manuscript is self-contained and does not appear to depend improperly on the authors’ prior work.
major comments (2)
- [Section 4, proof of Theorem 1.9] The lower bound P ≥ (r−1) Σ_j (n−r−b_j) is derived from the assertion: for every non-extension u' of a transitive r-tournament Q_j, there is a vertex y∈V(Q_j) such that u', y together with any r−2 other vertices of Q_j\{y} induce a non-transitive r-set. This assertion is false. For r=3, take the oriented graph G on {1,2,3,4} with arcs 1→2, 2→3, 3→1, and 4→1, 4→2, 4→3. The only non-transitive triple is {1,2,3}. Let Q_j={1,2,4} and u'=3. For y=1, the triple {1,3,4} is transitive; for y=2, {2,3,4} is transitive; for y=4, both {3,4,1} and {3,4,2} are transitive. Thus no y has the claimed property. Consequently, the double-counting inequality P ≥ (r−1)Σ_j(n−r−b_j) is not justified. Since this inequality is used to derive the Moon–Moser inequality in Theorem 1.9 and then Theorem 1.10, those two theorems are not proven by this manuscript. The remaining results (Theorems 1.7, 1.8, 1.11) are unaf
- [Section 4, Theorem 1.10] Theorem 1.10 is derived from Theorem 1.9 via Claim 4.1. Because the proof of Theorem 1.9 has the gap described above, the proof of Theorem 1.10 inherits that gap. The statement of Theorem 1.10 may still be true, but a different argument or a corrected double-counting inequality is needed to establish it.
minor comments (4)
- [Section 4, proof of Theorem 1.9] In the double-counting display, the subscript 's−1' appears in 'Ns−1' where it should be 'r−1'. This is a typo that should be corrected.
- [Section 1, Definition 1.2] The notation π_o(F) is defined as a limit of ex_o(n,F)/binom(n,2). The limit is well-defined by Proposition 2.1, but it would be clearer to write the limit explicitly as n→∞ in the definition.
- [References] Reference [17] (Taylor) appears in the bibliography but is not cited in the body of the paper. Either cite it where relevant (e.g., in the discussion of regular methods for digraphs) or remove it.
- [Section 3, Case 3.2.1] There is a small punctuation typo: 'by Claim 3.2,.' should read 'by Claim 3.2.'.
Circularity Check
No circular reductions found; only a minor non-load-bearing self-citation. The largest issue is a non-circular proof gap in Theorem 1.9.
full rationale
The derivation chains are self-contained against the paper's own inputs. Theorem 1.7 uses the definition of the oriented Turan density to find an m-set above the extremal threshold; this is a standard extremal-counting step, not a fit or a prediction that reduces to its input. Theorem 1.8 is proved by induction and case analysis using only Proposition 3.1; it does not use the self-cited exact value ex_o(n,TT_3)=|E(T(n,3))| from [10] except as motivation. Theorem 1.11 is derived directly from Jensen and Stirling estimates; it does not call on Theorem 1.6 or on any fitted constant. Theorem 1.10 is an algebraic consequence of Theorem 1.9, whose double-counting proof introduces no fitted parameters. The only overlap with the authors' prior work is [10] (Gerbner, Hu, Sun; Hu and Sun are also authors here). It supplies the oriented extremal bounds quoted in the introduction, but the central proofs of Theorems 1.7, 1.8, and 1.11 do not use it, so this is a minor, non-load-bearing self-citation. I therefore keep the circularity score at 2 rather than higher. I do flag a separate correctness issue, not a circularity issue: in the proof of Theorem 1.9, the assertion 'there exists at least one vertex y in V(Q_j) such that the union of u', y and any r-2 vertices of Q_j \ {y} induces an R' is false in general (a non-transitive (r+1)-tournament may contain exactly one non-transitive r-subset), so the lower bound P >= (r-1) sum (n-r-b_j) is unsupported. This threatens Theorems 1.9 and 1.10 but does not make the derivation circular.
Assumptions & free parameters
assumptions (4)
- standard math Jensen's inequality for binomial-coefficient polynomials
- standard math Stirling bounds: (m/k)^k ≤ C(m,k) ≤ (em/k)^k
- domain assumption Valadkhan's oriented Erdős–Stone–Simonovits theorem (Theorem 1.4)
- domain assumption Exact oriented Turán number for tournaments from [10]
Cite this review
Pith. "Pith review of On the supersaturation of oriented Tur\'an problems." pith.science (2026). https://pith.science/paper/GQP7PHS3
@misc{pith2026260214008,
author = {Pith},
title = {Pith review of: On the supersaturation of oriented Tur\'an problems},
year = {2026},
howpublished = {\url{https://pith.science/paper/GQP7PHS3}},
note = {Machine review of arXiv:2602.14008}
}
abstract
The oriented Tur\'{a}n number of a given oriented graph $\overrightarrow{F}$, denoted by $\exo(n,\overrightarrow{F})$, is the largest number of arcs in $n$-vertex $\overrightarrow{F}$-free oriented graphs. This parameter could be seen as a natural oriented version of the classical Tur\'{a}n number. In this paper, we study the supersaturation phenomenon for oriented Tur\'{a}n problems, and prove oriented versions of the famous Erd\H{o}s-Simonovits Supersaturation Theorem and Moon-Moser inequality, and supersaturation theorems for tournaments and antidirected complete bipartite graphs.
Reference graph
Works this paper leans on
-
[1]
Addario-Berry, F
L. Addario-Berry, F. Havet, C. Linhares Sales, B. Reed and S. Thomass´ e, Oriented trees in digraphs, Discrete Math., 313, 2013, 967–974
2013
-
[2]
N. Alon, M. Krivelevich and B. Sudakov, Tur´ an numbers of bipartite graphs and related Ramsey-type questions, Combin. Prob. Comput., 12, 2003, 477–494
2003
-
[3]
Brown and F
W.G. Brown and F. Harary, Extremal digraphs, Combinatorial theory and its applica- tions, Colloq. Math. Soc. J. Bolyai, 4, 1969, 135–198
1969
-
[4]
Burr, Subtrees of directed graphs and hypergraphs, In: Proc
S.A. Burr, Subtrees of directed graphs and hypergraphs, In: Proc. 11th South east- ern Conf. Combinatorics, Graph Theory and Computing, Florida Atlantic Univ., Boca Raton, Fla. I Vol. 28, 1980, 227–239
1980
-
[5]
Erd˝ os, On a theorem of Rademacher-Tur´ an, Illinois J
P. Erd˝ os, On a theorem of Rademacher-Tur´ an, Illinois J. Math., 6, 1962, 122–127
1962
-
[6]
Erd˝ os and M
P. Erd˝ os and M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hun- gar., 1, 1966, 51–57
1966
-
[7]
Erd˝ os and M
P. Erd˝ os and M. Simonovits, Cube-supersaturated graphs and related problems, Progress in graph theory (Waterloo, Ont., 1982), pages 203–218, 1984
1982
-
[8]
Erd˝ os and A
P. Erd˝ os and A. H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc., 52, 1946, 1087–1091
1946
Show all 18 references
-
[9]
F¨ uredi, On a Tur´ an type problem of Erd˝ os, Combinatorica, 11(1), 1991, 75–79
Z. F¨ uredi, On a Tur´ an type problem of Erd˝ os, Combinatorica, 11(1), 1991, 75–79. 18
1991
-
[10]
Gerbner, X
D. Gerbner, X. Hu and Y. Sun, On oriented Tur´ an problems, arXiv:2602.04324v1
-
[11]
Graham, On subtrees of directed graphs with no path of length exceeding one, Canad
R.L. Graham, On subtrees of directed graphs with no path of length exceeding one, Canad. Math. Bull., 13, 1970, 329–332
1970
-
[12]
Grzesik and M
A. Grzesik and M. Skrzypczyk, Antidirected paths in oriented graphs, arXiv:2506.11866
-
[13]
Katona, T
G. Katona, T. Nemetz and M. Simonovits, On a problem of Tur´ an in the theory of graphs, Mat. Lapok, 15, 1964, 228–238
1964
-
[14]
Klimo˘ sov´ a and M
T. Klimo˘ sov´ a and M. Stein, Antipaths in oriented graphs, Discrete Math., 346, 2023, Article 113515
2023
-
[15]
K˝ ov´ ari, V.T
P. K˝ ov´ ari, V.T. S´ os and P. Tur´ an, On a problem of Zarankiewicz, Colloq. Math., 33, 1954, 50–57
1954
-
[16]
Moon and L
J.W. Moon and L. Moser, On cliques in graphs, Israel J. Math., 3, 1965, 23–28
1965
-
[17]
Taylor, The regularity method for graphs and digraphs, arXiv:1406.6531
A. Taylor, The regularity method for graphs and digraphs, arXiv:1406.6531
-
[18]
Valadkhan, Extremal oriented graphs and Erd˝ os-Hajnal conjecture, Master’s thesis, Simon Fraser University, 2009
P. Valadkhan, Extremal oriented graphs and Erd˝ os-Hajnal conjecture, Master’s thesis, Simon Fraser University, 2009. 19
2009
Reviewed August 2, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.