Finite palette endpoints and degree-square Turán problems

Abstract

We study finite palette extremal problems motivated by uniform Turán densities of $3$-uniform hypergraphs. Given a self-converse tournament $T$ with at least two vertices, we determine the largest possible number of admissible triples in an $m$-color palette that avoids the left and right palettes associated with $T$. The answer is the one-sided degree-square Turán number \[ \operatorname{pal}_T(m) = \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\}. \] Thus this palette problem is reduced to an extremal problem for digraph out-degrees. We then prove a prefix-majorization lemma for convex out-degree moments and apply it to directed cycles. In particular, ${\mathrm{ex}}_2^{+}(m,{\overrightarrow{C}}_3)=\frac{m(m^2-1)}{3}$, which gives the sharp $m$-color palette endpoint $\frac{1}{3}-\frac{1}{3m^2}$ for the directed triangle. Combining this endpoint with the palette characterization of uniform Turán density and the palette separation theorem, we show that for every $m\ge 2$ there is a finite $3$-graph $H_m$ such that \[ \frac13-\frac{1}{3m^2}\le π_u(H_m)\le \frac13. \] Hence there is a sequence of individual finite $3$-graphs whose uniform Turán densities converge to $1/3$. We also describe the extremal palettes, prove a qualitative edit-distance stability theorem, and compute the Lagrangian of the endpoint palette ${\mathcal{P}}_m^{\star }$. As a consequence, for every $m\ge 2$ there is a finite family ${\mathcal{F}}_m$ of $3$-graphs with ${\pi }_u({\mathcal{F}}_m)=\frac{1}{3}-\frac{1}{3m^2}$, so $1/3$ is an accumulation point of uniform Turán densities of finite forbidden families.