Graph-theory open problems

Induced-saturated infinite tournament existence

AX_induced_saturated_infinite_tournament_perturbation

Source: arXiv:2506.08810 — Infinite induced-saturated graphs

Conjecture 24 · arXiv:2506.08810

arXiv Conjecture high confidence— first stated 2025-09-01
Authors: Marthe Bonamy, Carla Groenland, Tom Johnston, Natasha Morrison, Alex Scott

Status ai-disproved high confidence

The five-vertex tournament C3[TT2,TT2,1] is a counterexample: every countable tournament avoiding it has a distinct locally finite perturbation that still avoids it.

Auto-reviewed 2026-09-17 with gpt-6-astra.

AI-generated write-up ai-disproved

Open the PDF write-up

This is a model-generated research artifact, not a peer-reviewed publication or a formally verified proof.

Conjecture. Let $T$ be a finite tournament. If $T$ is not transitive, then there exists a countably infinite $T$-free tournament $S_{T}$ such that every locally finite perturbation of $S_{T}$ has an induced copy of $T$.

Context

This is proposed as the tournament analogue of the paper's main Theorem 1. The non-transitivity condition is necessary because any tournament on $2^n$ elements contains a transitive subtournament on $n$ elements, so a transitive $T$ cannot be avoided in an infinite structure under locally finite perturbations.

Source paper

Infinite induced-saturated graphs
Marthe Bonamy, Carla Groenland, Tom Johnston, Natasha Morrison, Alex Scott · 2025-09-01
https://arxiv.org/abs/2506.08810

Related conjectures

  • implies Arc-reversal induced saturation in tournaments open Checked against the paper (Problem 23, Conjecture 24). A locally finite perturbation is defined as perturbing a nonempty (possibly single) locally finite set of pairs, so one arc reversal qualifies; and in tournaments subtournament containment equals induced containment. Hence Conjecture 24's S_T is a countable H-free tournament where every single arc reversal creates H, answering Problem 23 affirmatively for every non-transitive H. Caveat: it settles only the non-transitive side; for transitive H no infinite example exists (Ramsey footnote in the paper) and a finite example is noted only for TT_3, so finite transitive cases remain outside the source's scope. Direction is correct.

View in the relation graph — relations are AI-reviewed, not formally verified.