Papers With

← All papers
First page of Random Tournaments Are Asymptotically Almost Surely Link-irregular

Random Tournaments Are Asymptotically Almost Surely Link-irregular

Lily Zhang

math.CO Oct 17, 2026 · v1
formalization combinatorics probability
Read PDF arXiv abstract Code
TL;DR
Both main results, existence of link-irregular tournaments for n≥9 and the a.a.s. link-irregularity of random tournaments, are formalized in Lean 4 (GitHub).
Abstract
Bastien and Khormali (2025) conjectured that a nontrivial link-irregular tournament with $n$ vertices exists if and only if $n \ge 6$. Their work establishes the conjecture for $n \le 100$. We present a probabilistic argument for the existence of link-irregular tournaments with $n$ vertices when $n \ge 9$ to resolve the conjecture. In fact, we show that a random tournament is asymptotically almost surely link-irregular.
Problem

Bastien and Khormali conjectured that a nontrivial link-irregular tournament on n vertices exists if and only if n ≥ 6, and verified it for n ≤ 100. A tournament is link-irregular when no two vertex-deleted subtournaments are isomorphic.

Approach

A probabilistic argument bounds the probability that a bijection φ is an isomorphism between T_n−u and T_n−v by 2^{-C(n-1,2)+o_2(σ_φ)}, where o_2 counts orbits of the cyclic part of φ on vertex pairs. Summing these bounds, using counts of unlabeled graphs (OEIS A000088), shows that link-irregular tournaments exist for n ≥ 9. Both main results are formalized in Lean 4.

Results

Link-irregular tournaments exist for every n ≥ 9, which together with prior computations resolves the conjecture. A uniformly random tournament is asymptotically almost surely link-irregular.