An unavoidable mismatch
Every pair of tournaments with at least two vertices has an intersection discrepancy that cannot fall below a fixed n to the three-halves scale under the paper's relabelling comparison, according to a proof-based combinatorial study. Across the possible vertex matchings, the largest departure from the random-relabelling baseline is at least on that scale. The result quantifies over every qualifying tournament pair rather than a selected example.
Here, discrepancy measures how far the overlap of two graphs moves from the average overlap produced by a uniformly random relabelling of their vertices. It is the larger of the biggest excess above that average and the biggest deficit below it. The bound can therefore reflect either an unusually high overlap or an unusually low overlap relative to the same random baseline.
The central tournament theorem gives a product bound as well as an overall bound. It says the positive discrepancy multiplied by the negative discrepancy is at least a positive absolute constant times n cubed. As a result, the overall discrepancy is at least the square root of that constant times n to the three-halves power. The supplied analysis does not give the constant a numerical value, so the theorem fixes the scale of the guarantee without specifying its exact size.
How the proof builds the bound
This is not a simulation. The proof uses centered matrices, estimates over random permutations, transposition-amplification arguments, structural decompositions and conditioning on relabellings. A supporting lemma examines the expected absolute change in correlation when a fixed transposition swaps two labels, then turns that quantity into a lower bound on the discrepancy product. The stated lemma uses a factor of 10 to the minus 4 times n squared and the square of that expected change.
A separate structural theorem applies to every pair of oriented graphs with n at least 4. It ties their discrepancy product to residual matrix components: the squared Frobenius norms of symmetric and skew-symmetric residuals are combined, the result is cubed, and the whole term is divided by n to the ninth power. For tournaments with n at least 4, triangle circulation provides a uniform lower bound on the squared Frobenius norm of the skew-symmetric residual component.
Beyond tournaments
The result extends beyond tournaments to pairs of oriented graphs with edge-density parameters p and q. It requires both parameters to lie between 16 divided by n and 1 minus 16 divided by n. Within that range, the overall discrepancy is bounded below on the n to the three-halves scale, multiplied by the cube of the density factor p(1 minus p)q(1 minus q) and the square root of an absolute positive constant. The corresponding product bound uses the sixth power of the same density factor and n cubed. The supplied analysis does not give that constant a numerical value.
Fixed families are covered too. For r tournaments, where r is at least 2 and each tournament has order n at least 2, the r-way discrepancy product is at least c1 times n cubed divided by 4 to the power r minus 2. The stated form therefore becomes weaker as more tournaments are included, but it remains a universal lower bound for every qualifying family. For r oriented graphs, an extension applies when at least one pair has both densities between 16 divided by n and 1 minus 16 divided by n; it also incorporates the densities of the remaining graphs.
What the theorem does not say
The result does not supply exact discrepancy values for individual graph pairs. It gives lower bounds for the graph classes and order conditions covered by the theorems, while the main absolute constants c, c1 and c2 are generally not specified numerically in the supplied analysis. The oriented-graph result is limited to its moderate-density range, and the fixed-family extension requires the stated qualifying pair. Nothing in the supplied evidence establishes the same guarantees outside those graph classes, order conditions or density assumptions.
The document is an arXiv mathematics preprint, version 2 dated 7 September 2026. Its evidence is mathematical rather than empirical, and it does not establish an empirical or causal effect. The authors report support from the National Key R&D Program of China under Grant No. 2023YFA1010202 and the National Natural Science Foundation of China under Grant No. 12371342.
Paper data and sources
Original title: Intersections of Tournaments
Authors: Zhanping Yang, Qinghou Zeng
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-28
DOI: Not available
Original paper · Full text