pith. sign in

arxiv: 2606.03520 · v1 · pith:GZJMSQGDnew · submitted 2026-06-02 · 🧮 math.CO

Finite palette endpoints and degree-square Tur\'an problems

Jiangdong Ai , Bin Chen , Ming Chen , Zilong Yan , Tianxiao Zhao This is my paper

Pith reviewed 2026-06-28 09:36 UTC · model grok-4.3

classification 🧮 math.CO
keywords palettesTurán densitydigraphstournamentsadmissible triplesdegree sequencesself-conversemajorization
0
0 comments X

The pith

For self-converse tournaments T with at least two vertices, the maximum admissible triples in m-color palettes avoiding left and right T-palettes equals the maximum sum of squared out-degrees in T-free digraphs on m vertices.

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

This paper proves that optimizing the number of admissible triples in finite m-color palettes that avoid both the left and right palettes generated by a self-converse tournament T reduces exactly to maximizing the sum of squared out-degrees in an m-vertex digraph that avoids T. The reduction is achieved by attaching two auxiliary digraphs to each palette. A reader would care because the result gives exact finite values that can be computed from known digraph extremal constructions, and when applied to the cyclic triangle it produces a sequence of finite 3-uniform hypergraphs whose uniform Turán densities approach one third from below.

Core claim

If T is a self-converse tournament with at least two vertices, then for every m ≥ 1 the maximum number of admissible triples in an m-color palette avoiding both P_T^L and P_T^R equals ex_2^+(m,T), the maximum of sum d_D^+(v)^2 over all T-free digraphs D with m vertices. The equality is obtained by attaching two auxiliary digraphs to each palette and thereby converting the optimization into a degree-square Turán problem. A general majorization principle for convex out-degree moments in F-free digraphs is also proved, yielding exact values such as ex_2^+(m, directed C_3) = m(m^2 - 1)/3.

What carries the argument

Attachment of two auxiliary digraphs to each palette that converts the admissible-triple count into the sum of squared out-degrees in a T-free digraph.

If this is right

  • The Brown-Harary and Zhou-Li constructions maximize all convex out-degree moments in directed-cycle-free digraphs.
  • The density avoiding the two cyclic-triangle palettes is exactly 1/3 - 1/(3m^2) for m colors.
  • There exist finite 3-graphs H_m with uniform Turán density satisfying 1/3 - 1/(3m^2) ≤ π_u(H_m) ≤ 1/3, so the densities converge to 1/3 as m grows.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The majorization principle may allow exact computation of other moments or for other forbidden subdigraphs where extremal constructions are known.
  • Finite palette endpoints could be used to construct sequences of hypergraphs with densities approaching other known Turán densities.
  • If the auxiliary digraph attachment works for other families, similar exact reductions might exist beyond tournaments.

Load-bearing premise

Attaching two auxiliary digraphs to each palette converts the admissible triple count exactly into the sum of squared out-degrees of a corresponding T-free digraph.

What would settle it

Finding an m-color palette avoiding P_T^L and P_T^R with more admissible triples than any T-free digraph on m vertices achieves in sum of squared out-degrees would show the equality fails.

read the original abstract

We study finite extremal problems for palettes, which arise from the palette framework for the uniform Tur\'an densities of $3$-uniform hypergraphs. Recent work has developed reductions from palette colorability questions to extremal problems for digraphs. In this paper we prove an exact degree-square refinement of these reductions for a natural family of left and right tournament palettes. For a tournament $T$, let $P_T^L$ and $P_T^R$ denote the left and right palettes generated by $T$. We prove that if $T$ is self-converse and has at least two vertices, then for every $m\ge 1$ the maximum number of admissible triples in an $m$-color palette avoiding both $P_T^L$ and $P_T^R$ is \[ \operatorname{ex}_2^+(m,T) = \max\left\{ \sum_{v\in V(D)} d_D^+(v)^2: |V(D)|=m,\; D\text{ is }T\text{-free} \right\}. \] The proof attaches two auxiliary digraphs to each palette and converts the palette optimization into a degree-square Tur\'an problem. We also prove a general majorization principle for convex out-degree moments in $F$-free digraphs. Whenever an ordinary Tur\'an extremal construction has extremal initial segments, the same construction maximizes every nondecreasing convex function of the out-degree sequence. Applying this to the Brown--Harary and Zhou--Li extremal digraphs for directed cycles gives exact formulas for all convex out-degree moments in $\overrightarrow{C}_{\ell}$-free digraphs. In particular, $\operatorname{ex}_2^+(m,\overrightarrow{C}_{3}) =\frac{m(m^2-1)}{3}.$ Consequently, for $m$ color the sharp density avoiding the two cyclic-triangle palettes is $\frac13-\frac1{3m^2}.$ Combining this exact finite endpoint with the palette classification theorem, we obtain finite $3$-graphs $H_m$ satisfying \[ \frac13-\frac1{3m^2} \le \pi_{\mathrm u}(H_m) \le \frac13. \] Thus the densities of these finite hypergraphs converge to $\frac13$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper proves that if T is a self-converse tournament on at least two vertices, then for every m ≥ 1 the maximum number of admissible triples in an m-color palette avoiding both the left and right palettes generated by T equals ex_2^+(m,T), defined as the maximum of ∑ d_D^+(v)^2 over all T-free digraphs D on m vertices. The proof proceeds by attaching two auxiliary digraphs to each palette, converting the optimization exactly into a degree-square Turán problem. A general majorization principle is established showing that, under suitable conditions on extremal constructions, the same digraphs maximize all nondecreasing convex functions of the out-degree sequence; this is applied to the Brown–Harary and Zhou–Li constructions to obtain the exact value ex_2^+(m, C_3) = m(m^2−1)/3 and the consequent finite 3-graphs H_m with uniform Turán densities satisfying 1/3 − 1/(3m^2) ≤ π_u(H_m) ≤ 1/3.

Significance. If the auxiliary-digraph reduction is exact, the result supplies the first explicit finite-palette endpoints for a natural family of tournament palettes and yields a sequence of 3-uniform hypergraphs whose uniform densities converge to the known limit 1/3. The majorization principle for convex out-degree moments in F-free digraphs is a reusable tool that strengthens existing extremal constructions without introducing new parameters. The explicit formula for the directed-triangle case and the resulting density bounds are concrete, falsifiable outputs.

major comments (1)
  1. [the reduction step described in the abstract and the proof of the main equality] The central equality rests on the claim that attaching two auxiliary digraphs to each palette induces a precise, bijective correspondence under which the admissible-triple count equals the sum of squared out-degrees and avoidance of both P_T^L and P_T^R translates exactly to T-freeness. The abstract identifies this attachment as the proof method, but the manuscript must supply the explicit attachment rules together with a verification that every valid palette maps to a T-free digraph recovering the count and conversely that every T-free digraph arises from some admissible palette without additional constraints.
minor comments (2)
  1. [Introduction] Notation for the left and right palettes P_T^L and P_T^R should be introduced with a short diagram or explicit definition before the main statement.
  2. [the majorization section] The statement of the majorization principle would benefit from an explicit list of the required hypotheses on the extremal construction (e.g., “extremal initial segments”) so that readers can check applicability to other forbidden digraphs.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thorough reading and for identifying the need to strengthen the presentation of the central reduction. We will revise the manuscript to address this point explicitly.

read point-by-point responses

  1. Referee: [the reduction step described in the abstract and the proof of the main equality] The central equality rests on the claim that attaching two auxiliary digraphs to each palette induces a precise, bijective correspondence under which the admissible-triple count equals the sum of squared out-degrees and avoidance of both P_T^L and P_T^R translates exactly to T-freeness. The abstract identifies this attachment as the proof method, but the manuscript must supply the explicit attachment rules together with a verification that every valid palette maps to a T-free digraph recovering the count and conversely that every T-free digraph arises from some admissible palette without additional constraints.

    Authors: We agree that the attachment rules and bijective verification require a more self-contained and explicit treatment. In the revised manuscript we will insert a new subsection (immediately following the definition of P_T^L and P_T^R) that (i) gives the precise construction of the two auxiliary digraphs D_L(P) and D_R(P) from an m-color palette P, including the vertex set, the directed edges, and the out-degree formulas; (ii) proves that the number of admissible triples in P equals sum_v d^+(v)^2 in the associated digraph; and (iii) establishes the two directions of the correspondence: every admissible palette avoiding both palettes yields a T-free digraph, and conversely every T-free digraph on m vertices arises from an admissible palette with no extra constraints. The revised text will contain the full verification rather than relying on the earlier sketch. revision: yes

Circularity Check

0 steps flagged

No significant circularity in reduction or majorization

full rationale

The paper defines ex_2^+(m,T) explicitly as the maximum out-degree-square sum over T-free digraphs on m vertices. It then proves equality to the palette maximum by exhibiting an explicit attachment of two auxiliary digraphs to each palette (and the converse mapping), which converts the admissible-triple count into the degree-square sum while preserving T-freeness. This is a direct constructive equivalence, not a self-definition or parameter fit. The majorization principle for convex out-degree moments is derived inside the paper from first principles and then applied to externally published extremal constructions (Brown-Harary, Zhou-Li), yielding closed forms without internal fitting. No load-bearing self-citation, ansatz smuggling, or renaming of known results occurs; the derivation remains self-contained against the stated external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

No free parameters or invented entities are introduced. The work relies on the majorization principle (a domain assumption) and on the extremal constructions of Brown-Harary and Zhou-Li.

axioms (1)
  • domain assumption If an ordinary Turán extremal construction for F-free digraphs has extremal initial segments, then the same construction maximizes every nondecreasing convex function of the out-degree sequence.
    Invoked to lift ordinary Turán results to convex out-degree moments; stated in the abstract as the general majorization principle.

pith-pipeline@v0.9.1-grok · 5968 in / 1421 out tokens · 39188 ms · 2026-06-28T09:36:34.109415+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

15 extracted references · 7 canonical work pages · 2 internal anchors

  1. [1]

    W. G. Brown and F. Harary. Extremal digraphs. InCombinatorial Theory and Its Ap- plications, volume 4 ofColloq. Math. Soc. János Bolyai, pages 135–198. North-Holland, 1970

    1970

  2. [2]

    Bućić, J

    M. Bućić, J. W. Cooper, D. Král’, S. Mohr, and D. Munhá Correia. Uniform Turán density of cycles.Trans. Amer. Math. Soc., 376(7):4765–4809, 2023

    2023

  3. [3]

    Erdős and M

    P. Erdős and M. Simonovits. A limit theorem in graph theory.Studia Sci. Math. Hungar., 1:51–57, 1966

    1966

  4. [4]

    Erdős and V

    P. Erdős and V. T. Sós. On Ramsey-Turán type theorems for hypergraphs.Combinatorica, 2(3):289–295, 1982

    1982

  5. [5]

    Erdős and A

    P. Erdős and A. H. Stone. On the structure of linear graphs.Bull. Amer. Math. Soc., 52:1087–1091, 1946

    1946

  6. [6]

    Glebov, D

    R. Glebov, D. Král’, and J. Volec. A problem of Erdős and Sós on 3-graphs.Israel J. Math., 211(1):349–366, 2016

    2016

  7. [7]

    D. King, S. Piga, M. Sales, and B. Schülke. On possible uniform Turán densities. arXiv:2504.21220v2, 2025

    work page arXiv 2025

  8. [8]

    Král’, F

    D. Král’, F. Kučerák, A. Lamaison, and G. Tardos. Uniform Turán density—palette clas- sification.arXiv:2505.17325, 2025

    work page arXiv 2025

  9. [9]

    Lamaison

    A. Lamaison. Palettes determine uniform Turán density.arXiv:2408.09643v1, 2024

    work page arXiv 2024

  10. [10]

    Lamaison and Z

    A. Lamaison and Z. Wu. The uniform Turán density of large stars.arXiv:2409.03699v1, 2024

    work page arXiv 2024

  11. [11]

    H. Lin, G. Sun, G. Wang, and W. Zhou. Uniform Turán densities ofk-uniform hypergraphs. arXiv:2605.15105v1, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  12. [12]

    H. Lin, G. Wang, W. Zhou, and Y. Zhou. Extremal problems in uniformly dense hyper- graphs and digraphs.arXiv:2603.10766v1, 2026

    work page arXiv 2026

  13. [13]

    Tur\'an density of stars in uniformly dense hypergraphs

    H. Lin and W. Zhou. Turán density of stars in uniformly dense hypergraphs. arXiv:2510.12576v2, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  14. [14]

    Reiher, V

    C. Reiher, V. Rödl, and M. Schacht. On a Turán problem in weakly quasirandom 3-uniform hypergraphs.J. Eur. Math. Soc., 20(5):1139–1159, 2018

    2018

  15. [15]

    Zhou and B

    W. Zhou and B. Li. The Turán number of directed paths and oriented cycles.Graphs Combin., 39:Article 47, 2023. 12

    2023