PaperlayerView exact revision on arXiv

Source-linked AI summary

A New Upper Bound for 7-Universal Tournaments

Harshit Verma

arXiv:2610.06891v1cs.DMmath.CO

TL;DR

Whether a 7-universal tournament exists on 13 vertices remained unresolved, after a 15-vertex upper bound and a lower bound excluding 12 vertices. The authors give an explicit 14-vertex tournament and verify universality by checking labelled seven-vertex tournaments against tuples of distinct host vertices. There exists a 7-universal tournament on 14 vertices, improving the previously known upper bound.

  • Problem

    Whether a 7-universal tournament exists on 13 vertices remained unresolved, after a 15-vertex upper bound and a lower bound excluding 12 vertices.

    Source: §1 · p. 1

  • Method

    The authors give an explicit 14-vertex tournament and verify universality by checking labelled seven-vertex tournaments against tuples of distinct host vertices.

    Source: §1 · p. 1, §3.1 · pp. 2–3

  • Results

    There exists a 7-universal tournament on 14 vertices, improving the previously known upper bound.

    Source: §1 · p. 1

  • Takeaways & Limitations

    The minimum order remains t(7) ∈ {13, 14}; whether a 13-vertex example exists is unresolved.

    Source: §4 · p. 3

Abstract

from arXiv · show

We give an explicit tournament on 14 vertices containing every 7-vertex tournament as an induced sub-tournament, and verify this property by exhaustive computation. This improves the previously known upper bound of 15. Together with the known lower bound, it follows that the minimum order of a 7-universal tournament is either 13 or 14.

1 Introduction

The paper gives a completely computationally verified 7-universal tournament on 14 vertices, improving the previous upper bound of 15. The cases of 13 and 14 vertices had been unresolved.

1 Introduction

  • A tournament is k-universal when every tournament on k vertices occurs as a subtournament, and t(k) is the minimum host order.Because both host and pattern are tournaments, each such copy is induced.Source: §1 · p. 1
  • Moon [2, Section 17] gave general bounds, while Alon established an asymptotic formula; exact values for small k are a separate finite problem.Source: §1 · p. 1
  • Zhang and Szeider excluded 12 vertices and gave a 15-vertex upper-bound example, leaving 13 and 14 unresolved.Source: §1 · p. 1
  • A completely computationally verified 7-universal tournament on 14 vertices improves the previously known upper bound.The lower bound in Theorem 1 is due to Zhang and Szeider.Source: §1 · p. 1

2 A tournament on fourteen vertices

The paper specifies a tournament T14 on vertices 1 through 14 by an adjacency matrix. Its universality is verified in Section 3.

2 A tournament on fourteen vertices

  • T14 has vertex set {1, . . . , 14} and is specified by an adjacency matrix.Source: §2 · p. 2
  • An entry Aij = 1 means the arc goes from i to j; diagonal entries are zero and Aij + Aji = 1 for distinct vertices.These conditions make the matrix define a tournament.Source: §2 · p. 2
  • The paper verifies T14's universality in Section 3.Source: §2 · p. 2

3 Verification of universality

The verification establishes that T14 contains every tournament on seven vertices by exhaustively checking labelled copies, with a second check using isomorphism classes. Together with the lower bound, this yields 13 ≤ t(7) ≤ 14.

3.1 Exhaustive labelled coverage

  • The labelled check encodes each ordered tuple of seven distinct T14 vertices as a 21-bit code specifying all arc directions.The code records whether each arc goes from vi to vj; an embedding of each labelled tournament is equivalent to seeing every possible code.Source: §3.1 · p. 2
  • Enumerating all 17,297,280 ordered tuples and marking their codes marks every one of the 2,097,152 possible labelled tournaments.Each tuple is visited exactly once.Source: §3.1 · pp. 2–3
  • 13 ≤ t(7) ≤ 14: the exhaustive computation establishes that T14 is 7-universal, and the known lower bound is 13.The lower bound is due to Zhang and Szeider.Source: §3.1 · p. 3

3.2 Verification up to isomorphism

  • 456 representatives of seven-vertex isomorphism classes account for all 2,097,152 labelled tournaments, independently verifying T14’s universality.The orbit–stabilizer sum counts the labelled tournaments represented by each class, and every representative occurs in T14.Source: §3.2 · p. 3

4 Concluding remark

The 14-vertex example reduces the upper bound for t(7) to 14, leaving t(7) either 13 or 14.

  • The example reduces the upper bound for t(7) from fifteen to fourteen, leaving t(7) ∈ {13, 14}.Source: §4 · p. 3
Loading 2610.06891v1…