Maximizing directed cycles in tournaments

Hao Huang; Yijia Fang

REVIEW 2 major objections 4 minor 22 references

Maximizing directed cycles in tournaments

T0 review · 2 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 The carousel tournament maximizes directed cycles of length divisible by 4.

desk verdict Resolves Bartley-Day for all 4k with a clean reduction, but Lemma 3.3 has a real proof gap that must be fixed before the upper bound is rigorous. read the letter →

arxiv 2608.06238 v1 pith:HHH4TY26 submitted 2026-08-06 math.CO

Yijia Fang , Hao Huang This is my paper · ORCID

classification math.CO MSC 05C2005C3505C3815A18

keywords tournamentsdirectedcyclescarouseltournamentextremalcombinatoricstraceinequalitiesskew-symmetricmatricesweakmajorizationBartley-Dayconjecture

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

This paper tries to settle the extremal question of which n-vertex tournament contains the most directed cycles of a fixed length. It claims that for every cycle length divisible by 4, the asymptotic maximum is achieved by the carousel tournament, with an explicit constant that is strictly larger than the random tournament's count. Combined with earlier work on lengths not divisible by 4, this would complete the Bartley-Day conjecture for all cycle lengths. The proof converts cycle counts into traces of powers of a skew-symmetric ±1 adjacency matrix and reduces the extremal problem to a linear-algebra inequality about those traces.

What carries the argument

The central object is the carousel tournament Car_n, the directed Cayley graph on Z/nZ in which each vertex points to the next (n−1)/2 vertices; for even n it is obtained by deleting one vertex from Car_{n+1}. On the matrix side, the argument runs through T_n, the skew-symmetric matrix with 1 above the diagonal and −1 below, and a closely related symmetric matrix K_n that preserves weak majorization. The mechanism: closed directed walks of length ℓ correspond to diagonal entries of (A+J)^ℓ, so bounding Tr[(A+J)^{4k}] bounds cycle counts; Theorem 1.4 shows the transitive sign matrix maximizes Tr[$A^{{4k}}$] via a weak-majorization comparison (Ax)^* ≺ K_n x^*, and Theorem 1.3 separates the contribution of the all-ones matrix J.

What would settle it

Check the disputed inequality in Lemma 3.3 at n=4 with x=(10,9,8,1), A=T_4, and S={1,3}: the claimed bound would require 36 ≤ 29, which is false. This counterexample does not by itself disprove Theorem 1.2, but it pinpoints the exact step whose repair or replacement is needed for the upper bound.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1.2: for each fixed positive integer k, the maximum number of directed 4k-cycles in an n-vertex tournament satisfies C(n,4k)/R(n,4k) → 1 + 2·Σ_{i≥1}(2/((2i−1)π))^{4k}, where R(n,4k) is the expected count in the random tournament, and the carousel tournament asymptotically attains this value. This confirms the Bartley-Day conjecture for all cycle lengths divisible by 4. The constant is strictly greater than 1, so the random tournament is not asymptotically extremal for these lengths. The proof proceeds through two matrix theorems: Theorem 1.3, which bounds Tr[(A+J)^{4k}] by Tr[$A^{{4k}}$] + Tr[$J^{{4k}}$], and Theorem 1.4, which bounds Tr[$A^{{4k}}$] by Tr[$T_n^{{4k}}$] where T_n is the sign matrix of the transitive tournament, with equality exactly for signed-permutation conjugates of T_n.

Load-bearing premise

The upper bound depends on the technical claim that every tournament sign matrix stretches any vector less aggressively than one fixed matrix K_n, when both are measured by their largest partial sums; if that claim is false, the paper's proof of the maximum does not go through.

Editorial extensions

If this is right

Every cycle length divisible by 4 now has an identified asymptotic extremal tournament: the carousel, which beats the random tournament by the factor 1 + 2·Σ(2/((2i−1)π))^{4k}.
The Bartley-Day dichotomy is confirmed for all cycle lengths: the random tournament is asymptotically optimal when the length is not divisible by 4, and the carousel is optimal when it is.
The carousel's advantage over the random tournament decays like 2(2/π)^{4k} as k grows, so the effect is strongest for short 4k-cycles.
As a by-product, the paper establishes a linear-algebra extremal result: among all ±1 skew-symmetric matrices, the transitive-tournament matrix T_n maximizes the trace of the 4k-th power, with equality only for signed-permutation conjugates of T_n.

Reading between the lines

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

Editorial inference: the same trace-and-majorization framework may extend to other Cayley or circulant tournaments, potentially identifying carousel-type objects as extremal for other fixed orientations.
Editorial inference: the equality case in Theorem 1.4 suggests a stability version, namely that tournaments nearly extremal for 4k-cycles should be structurally close to a signed-permutation conjugate of the transitive tournament, hence close to a carousel in a suitable cut metric.
Editorial inference: a direct computational check for small n and k (especially k=3, where the paper leaves exact maximization open) could test whether the carousel is the exact finite-n maximizer or only asymptotically optimal.

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

The paper closes the last open case of the Bartley-Day conjecture by proving the exact asymptotic maximum for directed 4k-cycles in tournaments. That is a real result, and the high-level strategy is attractive: the cycle count is reduced to a trace inequality, and the extremal matrix is shown to be the transitive tournament matrix T_n up to signed permutation. The two matrix theorems are new and give a clean explanation of why the carousel tournament beats random for lengths divisible by 4.

What is actually new: the exact constant c(4k) for all k >= 3, previously only known for k = 1, 2. The proof combines a known reduction with two spectral/trace inequalities. Lemma 2.1 is a neat Schur-decomposition argument and looks correct. Lemma 4.2's spectrum of T_n is standard and correctly applied. The carousel lower bound is cited from Bartley's thesis, so the upper bound is the load-bearing part.

The soft spot is Lemma 3.3. The claim that (Ax)^* is weakly majorized by K_n x^* is plausible and probably true, but the proof as written has a gap. The first bound gives r times the sum over the complement of S plus a term involving the entries of x on S. The next line replaces the complement with the n-r largest entries of x, which increases the first term, and replaces the x'_i with the r smallest entries x_{n-r+i}, which decreases the second term. Since the coefficients c_{r,i} are nonnegative, this is not automatically an upper bound. The paper says "It is easy to see that |c_{r,i}| <= r", but that only controls the size of the coefficients, not the net change. A correct proof needs a rearrangement/majorization step showing the increase in the first term dominates the decrease in the second. The reader's specific counterexample does not land, by the way: for n=4, x=(10,9,8,1), S={1,3}, the paper's final RHS is 47, not 29. But the proof gap is genuine. Since Lemma 3.3 feeds Corollary 3.4 and Theorem 1.4, the upper bound in the main theorem is not fully rigorous as written.

The rest of the paper is in good shape: the reduction in Proposition 4.1 is correct, the equality cases in Theorem 1.4 are plausible, and the citations to Grzesik-Kral-Lovasz-Volec and Bartley's thesis are appropriate. The authors acknowledge using ChatGPT for parts of the proof; that is not itself a problem because the work is independently checked, but the referee should ask for the gap to be fixed by a human argument.

Who should read this: anyone working on extremal combinatorics of tournaments, and the matrix inequalities may interest people working on trace majorization. It deserves a serious referee. I would suggest sending it to review with a request to fix Lemma 3.3 or provide a reference; the likely outcome is a correct proof of a significant theorem.

Referee Report

2 major / 4 minor

Summary. The paper claims to settle the remaining case of the Bartley--Day conjecture by showing that, for every fixed positive integer k, the maximum number of directed 4k-cycles in an n-vertex tournament is asymptotically (1 + 2 sum_{i>=1} (2/((2i-1)pi))^{4k} + o(1)) * (4k-1)! / 2^{4k} * binom(n,4k), with the carousel tournament attaining the bound. The proof encodes a tournament as a skew-symmetric +/-1 matrix A, reduces cycle counting to traces of (A+J)^{4k}, and derives two matrix inequalities: Theorem 1.3 bounds Tr[(A+J)^{4k}] in terms of Tr[A^{4k}], and Theorem 1.4 bounds Tr[A^{4k}] by the corresponding trace for the transitive tournament matrix T_n. The eigenvalues of T_n are then computed to obtain the constant.

Significance. If the proof can be completed, this is a substantial result: it confirms the Bartley--Day conjecture for all cycle lengths divisible by 4 and gives the first exact asymptotic constant for those cases, extending the work of Grzesik--Kral'--Lovasz--Volec. The trace-based strategy is attractive, and Theorems 1.3 and 1.4 are potentially of independent interest. The paper is also transparent about the sources of its lower bound and about the use of AI assistance. However, the main upper bound currently rests on Lemma 3.3, whose proof is incomplete at a load-bearing point, and on an unverified hypothesis in the application of Karamata's inequality.

major comments (2)

[Section 3, Lemma 3.3] The proof of Lemma 3.3 omits a decisive rearrangement argument. After the reduction to X <= r sum_{j not in S} x_j + sum_{i<j, i,j in S} |epsilon_i x_j - epsilon_j x_i|, the manuscript asserts two inequalities: (i) sum_{i<j, i,j in S} |epsilon_i x_j - epsilon_j x_i| <= sum_i c_{r,i} x'_i, and (ii) r sum_{j not in S} x_j + sum_i c_{r,i} x'_i <= r sum_{j=1}^{n-r} x_j + sum_i c_{r,i} x_{n-r+i}. Both are true but genuinely nontrivial. In particular, (ii) is not a consequence of the stated observation '|c_{r,i}| <= r': passing from x'_i to the smaller entries x_{n-r+i} decreases the second sum, while the first sum increases. The proof needs the sharper bound c_{r,i} <= r-1 together with an exchange argument showing that the maximum over S is attained when S is the set of the r smallest coordinates. Since Lemma 3.3 is the only bridge from arbitrary tournaments to K_n, and it is used to prove Corollary 3.4 and Theorem 1.4, the upper bound in Theorem 1.2 is not rigorously established as written.
[Section 3, proof of Theorem 1.4] Proposition 3.1 is applied to u = (A^{2k} e_j)^* and v = K_n^{2k} e_1, but Proposition 3.1 is stated only for pairs of nonnegative non-increasing vectors. The manuscript does not prove that K_n^{2k} e_1 is nonnegative or non-increasing. This is not automatic because K_n has negative entries. The authors should either prove that K_n^{2k} e_1 has these properties (for instance, by showing that K_n^2 preserves the cone of non-increasing nonnegative vectors) or state and prove the real-vector version of Karamata's inequality that the argument actually requires. Without this, the chain leading to (A^{4k})_{jj} <= (K_n^{4k})_{11} is missing a hypothesis.

minor comments (4)

[Section 4, Lemma 4.2] In the definition of z_j, the text writes z_j = e^{(2j-1)pi/n}; the imaginary unit i is missing and should be z_j = e^{i(2j-1)pi/n}, the roots of z^n = -1.
[Section 4, proof of Theorem 1.2] The lower bound for the number of 4k-cycles in the carousel tournament is cited only to Bartley's PhD thesis [1]. Since this bound is half of the equality statement in the main theorem, the paper would be more self-contained if the computation were included in an appendix or at least stated with a precise pointer to the relevant result in the thesis.
[Section 3, proof of Theorem 1.4, equality case] The equality-case proof is very compressed. In particular, the assertion that the first two entries of (B * 1)^* being n-2 forces an all-1 row and an all-(-1) row, and the subsequent induction, should be written out in full.
[Section 3, Lemma 3.2] The sentence 'Notice that w_{n-r,r} - w_{n-r+1,r} = r - (r-1) = 1 for r = 1, ..., n' has an index error: for r = n the term w_{0,n} is undefined. The range should be r = 1, ..., n-1, together with the separate statement for w_{n,2} - w_{n+1,2}.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the upper bound is derived from parameter-free trace inequalities and an explicit eigen-computation, and the carousel lower bound is cited from external work.

full rationale

The central claim (Theorem 1.2) is established by an upper bound and a matching lower bound that are logically independent of each other and of the statement being proved. The upper bound follows from Theorem 1.3 and Theorem 1.4, both proved internally with no fitted constants and no appeal to the conjectured formula; the asymptotic constant is then obtained by computing eigenvalues of the explicit matrix T_n in Lemma 4.2, which is parameter-free and independent of the lower bound. The lower bound for the carousel tournament is cited from Bartley's external PhD thesis [1] and matches the upper bound; this is not a self-citation and not a fitted input. There are no load-bearing self-citations by the present authors, no uniqueness theorem imported from their own prior work, and no ansatz smuggled in via citation. The potentially invalid inequality flagged by the reader in Lemma 3.3 concerns a rearrangement step whose proof may be incomplete; that is a correctness or rigor issue, not circularity, because the lemma is not defined in terms of the target result and the final theorem does not assume what it proves. No equation renames a known result or fits a parameter and then calls the fit a prediction. Under the stated circularity criteria, the honest finding is no significant circularity, so the score is 0.

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

The paper introduces no fitted parameters or new postulated entities. It relies on standard linear algebra and majorization facts, plus the standard cycle-to-walk reduction. The main unstated dependency is the validity of Lemma 3.3, which is currently unproved due to the flawed proof step.

assumptions (3)

standard math Karamata's inequality for weak majorization and convex functions, Proposition 3.1
Used in the proof of Theorem 1.4 to compare squared norms of vectors under weak majorization.
standard math Real Schur decomposition and spectral theorem for Hermitian matrices
Used in the proof of Lemma 2.1 to bound eigenvalues of a rank-one perturbation of a skew-symmetric matrix.
domain assumption Asymptotic equivalence between directed cycles and closed directed walks in tournaments
Used in Proposition 4.1; walks that revisit vertices contribute only O(n^(ell-1)), which is asymptotically negligible after normalization.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Maximizing directed cycles in tournaments." pith.science (2026). https://pith.science/paper/HHH4TY26

@misc{pith2026260806238,
  author       = {Pith},
  title        = {Pith review of: Maximizing directed cycles in tournaments},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HHH4TY26}},
  note         = {Machine review of arXiv:2608.06238}
}

abstract

Determining the combinatorial structures that maximize the number of prescribed substructures is a central theme in extremal combinatorics. Grzesik, Kr\'al', Lov\'asz and Volec showed that when $\ell$ is not divisible by $4$, the random tournament contains asymptotically the most directed cycles of length $\ell$ among all $n$-vertex tournaments. In the paper, we resolve the remaining cases where $\ell$ is divisible by $4$. We show that, in this regime, the so-called carousel tournament asymptotically maximizes the number of directed $\ell$-cycles among all $n$-vertex tournaments, and in particular contains strictly more such cycles than the random tournament. This confirms the conjecture of Bartley and Day.

Figures

Figures reproduced from arXiv: 2608.06238 by the authors.

**Figure 1.** The 7-vertex carousel tournament Car7 Based on these results, Bartley [1] and Day [8] conjectured that when ℓ is not divisible by 4, the random tournament is asymptotically optimal, while for ℓ divisible by 4, the asymptotic maximizer is the carousel tournament. The first part of their conjecture was confirmed in 2023 by Grzesik, Kr´al’, Lov´asz, and Volec [11]. In other words, they proved that c(ℓ) = 1 when ℓ is no… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 20 canonical work pages

[1]

Bartley,Topics in extremal and probabilistic combinatorics, Ph.D

Jack P. Bartley,Topics in extremal and probabilistic combinatorics, Ph.D. thesis, Queen Mary University of London, 2018

work page 2018
[2]

Beineke and Frank Harary, The maximum number of strongly connected subtournaments, Canadian Mathematical Bulletin8(1965), no

Lowell W. Beineke and Frank Harary, The maximum number of strongly connected subtournaments, Canadian Mathematical Bulletin8(1965), no. 4, 491–498

work page 1965
[3]

Dalton Burke, Bernard Lidick´ y, Florian Pfender, and Michael Phillips, Inducibility of 4-vertex tourna- ments, preprint available at arXiv: 2103.07047

arXiv
[4]

On Tournament Anti-Sidorenko Orientations of Trees

Hao Chen, Felix Christian Clemen, and Jonathan A. Noel, On Tournament Anti-Sidorenko Orientations of Trees, preprint available at arXiv:2605.14138v1, 2026

work page Pith review arXiv 2026
[5]

Colombo, Sui circuiti nei grafi completi,Boll

U. Colombo, Sui circuiti nei grafi completi,Boll. Un. Mat. Ital.,19(3) (1964), 153–170

work page 1964
[6]

Coregliano, Roberto F

Leonardo N. Coregliano, Roberto F. Parente, and Cristiane M. Sato, On the maximum density of fixed strongly connected subtournaments ,Electronic Journal of Combinatorics26(1) (2019), #P1.44, 491–498

work page 2019
[7]

Coregliano and Alexander A

Leonardo N. Coregliano and Alexander A. Razborov, On the density of transitive tournaments,J. Graph Theory85(1) (2017), 12–21

work page 2017
[8]

Day,A collection of problems in extremal combinatorics, Ph.D

Alan N. Day,A collection of problems in extremal combinatorics, Ph.D. thesis, Queen Mary University of London, 2017

work page 2017

Show all 22 references

[9]

of Graph Theory

Jacob Fox, Zoe Himwich, Nitya Mani and Yunkun Zhou, Variations on Sidorenko’s conjecture in tournaments, to appear inJ. of Graph Theory
[10]

Jacob Fox, Zoe Himwich, Nitya Mani and Yunkun Zhou, A note on directed analogues of the Sidorenko and forcing conjectures,Electronic Journal of Combinatorics32(2025), P3.38

2025
[11]

Lov´ asz, and Jan Volec, Cycles of a given length in tournaments, J

Andrzej Grzesik, Daniel Kr´ al’, L´ aszl´ o M. Lov´ asz, and Jan Volec, Cycles of a given length in tournaments, J. Combin. Theory Ser. B158(2023), 117–145

2023
[12]

Xiaoyu He, Nitya Mani, Jiaxi Nie, Nathan Tung, and Fan Wei, New Sidorenko-type inequalities in tournaments, preprint available at arXiv:2512.11222v1, 2025. 12

2025
[13]

Maurice Kendall and Babington Smith, On the method of paired comparisons,Biometrika31(3/4) (1940), 324–345

1940
[14]

Natasha Komarov and John Mackey, On the number of 5-cycles in a tournament,Journal of Graph Theory86(3) (2017), 341–356

2017
[15]

Marshall and Ingram Olkin,Inequalities: Theory of majorization and its applications, Academic Press, New York, 1979

Albert W. Marshall and Ingram Olkin,Inequalities: Theory of majorization and its applications, Academic Press, New York, 1979

1979
[16]

Hermann Weyl, Inequalities between the Two Kinds of Eigenvalues of a Linear Transformation,Proc. Natl. Acad. Sci. U.S.A., 35 (7) 408-411, 1949

1949
[17]

2, Paper No

Ashwin Sah, Mehtaab Sawhney, and Yufei Zhao, Paths of given length in tournaments,Combinatorial Theory3(2023), no. 2, Paper No. 5

2023
[18]

S. V. Savchenko, On 5-cycles and 6-cycles in regularn-tournaments,J. Graph Theory,83(1) (2016), 44–77

2016
[19]

2, 201–204

Alexander Sidorenko, A correlation inequality for bipartite graphs,Graphs Combin.9(1993), no. 2, 201–204

1993
[20]

Mikl´ os Simonovits, Extremal graph problems, degenerate extremal problems, and supersaturated graphs, inProgress in graph theory (Waterloo, Ont., 1982), Academic Press, Toronto, 1984, pp. 419–437

1982
[21]

Miodrag Tomi´ c, Th´ eor` eme de Gauss relatif au centre de gravit´ e et son application,Bull. Soc. Math. Phys. Serbie, 1:31–40, 1949

1949
[22]

6, 875–896

Yufei Zhao and Yunkun Zhou, Impartial digraphs,Combinatorica40(2020), no. 6, 875–896. 13

2020

Pith tools

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

[1] [1]

Bartley,Topics in extremal and probabilistic combinatorics, Ph.D

Jack P. Bartley,Topics in extremal and probabilistic combinatorics, Ph.D. thesis, Queen Mary University of London, 2018

work page 2018

[2] [2]

Beineke and Frank Harary, The maximum number of strongly connected subtournaments, Canadian Mathematical Bulletin8(1965), no

Lowell W. Beineke and Frank Harary, The maximum number of strongly connected subtournaments, Canadian Mathematical Bulletin8(1965), no. 4, 491–498

work page 1965

[3] [3]

Dalton Burke, Bernard Lidick´ y, Florian Pfender, and Michael Phillips, Inducibility of 4-vertex tourna- ments, preprint available at arXiv: 2103.07047

arXiv

[4] [4]

On Tournament Anti-Sidorenko Orientations of Trees

Hao Chen, Felix Christian Clemen, and Jonathan A. Noel, On Tournament Anti-Sidorenko Orientations of Trees, preprint available at arXiv:2605.14138v1, 2026

work page Pith review arXiv 2026

[5] [5]

Colombo, Sui circuiti nei grafi completi,Boll

U. Colombo, Sui circuiti nei grafi completi,Boll. Un. Mat. Ital.,19(3) (1964), 153–170

work page 1964

[6] [6]

Coregliano, Roberto F

Leonardo N. Coregliano, Roberto F. Parente, and Cristiane M. Sato, On the maximum density of fixed strongly connected subtournaments ,Electronic Journal of Combinatorics26(1) (2019), #P1.44, 491–498

work page 2019

[7] [7]

Coregliano and Alexander A

Leonardo N. Coregliano and Alexander A. Razborov, On the density of transitive tournaments,J. Graph Theory85(1) (2017), 12–21

work page 2017

[8] [8]

Day,A collection of problems in extremal combinatorics, Ph.D

Alan N. Day,A collection of problems in extremal combinatorics, Ph.D. thesis, Queen Mary University of London, 2017

work page 2017