🔢 mathematics

$L_2$ Turán Problems for Small Tournaments and Stability

This paper determines the exact maximum $L_2$ norm squared of out-degree sequences for digraphs avoiding specific small tournaments like $TT_4$ and $R_4$ , identifies the corresponding extremal structures, and establishes a stability result for $\vec{C}_3$ -free digraphs.

Original authors: Daniel Iľkovič

Published 2026-09-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Daniel Iľkovič

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of mathematics, there is a branch dedicated to understanding how things can be arranged before they inevitably break a specific rule. Imagine a room full of people where everyone is shaking hands with some others, but not everyone shakes hands with everyone. Mathematicians ask: what is the most "connected" this room can be without forming a specific, forbidden pattern? This question, known as a Turán problem, has been a central puzzle for decades. It is not just about counting handshakes; it is about finding the precise tipping point where a structure becomes so dense that it accidentally creates a shape it was trying to avoid. For a long time, researchers focused on the total number of connections. However, a newer, more subtle way of measuring these networks has emerged. Instead of just counting every connection equally, this new method looks at how unevenly the connections are distributed. It asks: if we square the number of connections each person has and add them all up, what is the highest possible total we can reach without creating the forbidden shape? This approach reveals a different kind of order, one that favors networks where a few individuals are extremely popular while others are less so, rather than a perfectly even spread.

A researcher has now taken a deep dive into this specific question, focusing on small, intricate networks called tournaments. In these networks, every pair of points is connected by an arrow, which can be a one-way arrow or a two-way connection (arcs in both directions), much like a round-robin sports league where every team plays every other team, but ties are represented by mutual connections. The researcher was particularly interested in networks that avoid certain small, specific patterns, such as a four-team sequence where the results flow in a straight line without any loops, or a four-team group that is tightly interlocked in a cycle. They wanted to know the exact mathematical limit for the "unevenness" score in these forbidden-pattern-free networks. By combining the power of advanced computer simulations with rigorous human logic, they have mapped out the precise maximum values for these small networks. Their work does more than just provide a number; it reveals the exact shape of the network that achieves this maximum. They found that for one type of forbidden pattern, the best structure is a perfectly balanced three-part division where every group is connected to the others in both directions. For another, slightly more complex pattern, the best structure is almost the same, but with a tiny adjustment: if the total number of points leaves a specific remainder when divided by three, the optimal shape requires peeling off a single terminal sink vertex to form a specific graph structure where the main balanced group points to this isolated point.

The researcher also turned their attention to a five-point network where every point has the exact same number of outgoing arrows. While they could not prove the final answer for this specific case with absolute certainty, they have calculated the values for small examples and proposed a highly likely formula that fits the pattern perfectly. This suggests that the same balanced, multi-part structure that works for the other cases likely holds true here as well. Beyond finding these maximum values, the researcher investigated the concept of stability. In many mathematical problems, if you are very close to the maximum possible score, your structure must look very similar to the perfect solution. The researcher proved that this is indeed true for networks that avoid a simple three-point cycle. They showed that any network that comes close to the theoretical limit must be structurally almost identical to a specific, ordered chain of connections, differing from the perfect shape by only a tiny, predictable number of changes. This means that the path to the maximum is not a chaotic scramble of possibilities, but a narrow, well-defined corridor.

The journey to these answers was a collaboration between human intuition and artificial intelligence. The researcher began by using computers to generate and test millions of small networks, calculating their scores to spot patterns that human eyes might miss. Once the computers identified the likely formulas and shapes, the human mathematician stepped in to build the rigorous proofs that confirm these patterns hold true for networks of any size, not just the small ones they could simulate. This partnership allowed them to solve problems that had remained open for some time, turning vague guesses into precise mathematical laws. The results provide a clearer picture of how complex networks organize themselves when they are forced to avoid certain local structures. It shows that even in the chaotic world of directed connections, there are strict, predictable rules governing how much "clustering" or "unevenness" a system can sustain before it is forced to create the very pattern it is trying to avoid. The work stands as a testament to how modern tools can illuminate the hidden architecture of mathematical space, revealing that the most extreme cases are often the most beautifully simple.

Technical Summary: L2 Turán Problems for Small Tournaments and Stability

Problem Statement
This paper investigates the $L_2$ Turán problem for directed graphs (digraphs). Specifically, it seeks to determine the maximum possible squared $L_2$ norm of the out-degree sequence, denoted as $\text{ex}^+_{L_2}(m, H)$ , for a digraph on $m$ vertices that avoids a specific forbidden subdigraph $H$ . The quantity is defined as:
$\text{ex}^+_{L_2}(m, H) = \max \left\{ \sum_{v \in V(D)} (d^+_D(v))^2 : |V(D)| = m, D \text{ is } H\text{-free} \right\}$
The study focuses on small tournaments, particularly self-converse tournaments, and extends to stability versions of these problems. The work is motivated by the connection between uniform Turán densities in hypergraphs and palette extremal problems, where $L_2$ Turán problems on auxiliary digraphs serve as a critical refinement for establishing tight density bounds.

Methodology
The research employs a hybrid human-AI collaborative approach, utilizing the Google DeepMind AI co-mathematician. The methodology proceeds in three stages:

Computational Exploration: Extensive calculations were performed to compute the maximum sum of squared out-degrees for small cases of forbidden subdigraphs. This data was used to formulate precise conjectures regarding the extremal structures.
Structural Analysis: The author utilizes structural graph theory, including symmetrization arguments, the analysis of semicomplete quotients, and properties of strongly connected components (SCCs). Key tools include Camion's Theorem (regarding Hamiltonian cycles in strongly connected semicomplete digraphs) and Moon's Theorem (regarding subtournaments in strongly connected tournaments).
Algebraic Optimization and Stability: For exact results, the author optimizes algebraic formulas derived from partitioning vertices into independent sets (blow-ups). For stability results, they employ a global structural majorization argument on the out-degree sequence, utilizing Abel summation and telescoping identities to bound the "structural deficit" between a near-extremal graph and the exact extremal construction.

Key Contributions and Results

1. Exact $L_2$ Turán Numbers for Small Tournaments
The paper resolves three specific open problems regarding the exact values of $\text{ex}^+_{L_2}(m, H)$ :

Transitive Tournament ( $TT_4$ ):
The author proves that the complete directed 3-partite Turán graph, $T_3(m)$ , uniquely maximizes the objective.
- Theorem 3.1: For all $m \ge 1$ , $\text{ex}^+_{L_2}(m, TT_4) = \|d^+_{T_3(m)}\|^2_2$ .
- Proof Strategy: The proof establishes that any $TT_4$ -free digraph can be bounded by a function $F(a,b,c)$ corresponding to a 3-partite structure. It is shown that balancing the partition sizes (making them as equal as possible) strictly increases the $L_2$ norm, leading to the unique extremal graph $T_3(m)$ .
Strongly Connected Self-Converse Tournament ( $R_4$ ):
$R_4$ is the unique strongly connected self-converse tournament on four vertices (out-degree sequence 1, 1, 2, 2).
- Theorem 3.2: The extremal graph is uniquely isomorphic to a structure $E(m)$ . This structure consists of a complete 3-partite directed graph $T_3(k)$ followed by a transitive tournament $TT_{m-k}$ , with all edges directed from $T_3(k)$ to $TT_{m-k}$ .
- Modulo Condition: The parameter $k$ $k$ depends on $m \pmod 3$ $m (mod 3)$ :
  - If $m \equiv 0, 2 \pmod 3$ , then $k = m$ (the graph is purely $T_3(m)$ ).
  - If $m \equiv 1 \pmod 3$ , then $k = m-1$ . In this case, "peeling off" a terminal sink vertex to form $T_3(m-1) \to v$ strictly increases the objective compared to $T_3(m)$ .
- The paper provides exact algebraic formulas for $\text{ex}^+_{L_2}(m, R_4)$ based on $m = 3q + r$ .
Regular Tournament ( $Reg_5$ ):
- Conjecture 3.3: Based on computational evidence for small $m$ , the author conjectures that the Turán graph $T_4(m)$ (complete directed 4-partite graph) uniquely maximizes the $L_2$ norm for $Reg_5$ -free digraphs. Exact algebraic formulas are proposed for $m = 4q + r$ .

2. Stability for $\vec{C}_3$ -Free Digraphs
The paper addresses the stability version of the $L_2$ Turán problem for the directed triangle $\vec{C}_3$ .

Theorem 3.4: If a loopless $\vec{C}_3$ -free digraph $D$ on $n$ vertices has an $L_2$ norm squared of the out-degree sequence satisfying $\sum (d^+(v))^2 \ge \frac{n^3}{3} - \delta n^3$ , then the edit distance from $D$ to the ordered digon-chain $\vec{F}_{n,2}$ is at most $O(\delta^{1/2})n^2$ .
Corollary 3.5: A corresponding stability result is proven for palette densities. If an $m$ -color palette avoiding the left and right palettes of $\vec{C}_3$ has density at least $\frac{1}{3} - \frac{1}{3m^2} - \delta$ , its auxiliary digraphs are within edit distance $O(\delta^{1/2})m^2$ of the ordered digon-chain extremal construction.

Significance and Claims
The paper claims to provide a comprehensive resolution to specific degree-square Turán problems that were previously open.

Exactness: It determines the exact maximum $L_2$ norm squared for $TT_4$ and $R_4$ -free digraphs, settling open questions from recent literature.
Structural Insight: It reveals that for $R_4$ -free digraphs, the extremal structure is not always a pure Turán graph; a specific "peeling" operation is required when $m \equiv 1 \pmod 3$ to achieve the maximum.
Stability: It establishes a quantitative stability theorem for $\vec{C}_3$ -free digraphs, demonstrating that near-extremal graphs must be structurally close (in terms of edit distance) to the ordered digon-chain.
Methodological Demonstration: The work highlights the efficacy of human-AI collaboration in bridging computational exploration with formal mathematical proof, particularly in generating conjectures for complex extremal structures.

The author notes that while the results for $Reg_5$ are currently conjectural, the framework established suggests that similar algebraic reductions could potentially lead to a formal proof in the future. The paper does not claim to solve the general $L_2$ Turán problem for all forbidden subdigraphs but focuses on these specific small tournaments as a foundational step.

Technical Summary: L2 Turán Problems for Small Tournaments and Stability

More like this