Tournaments with high complexity contain special subgraphs with long cycles
Digraphs of Large Girth and Dichromatic Number in Tournaments with Large Dichromatic Number
Discrete Mathematics
Summary
The paper looks at a kind of complex network called a tournament, where directions matter in connections. It proves that if a tournament is complicated enough, it must have smaller parts that have both long directed loops and high complexity. This extends an old idea about ordinary networks to these directed ones. The authors also consider cases where loops ignore direction and show this links back to the original problem.
What this means in practice
- •For network architects: Design reliable networks by ensuring highly connected directed structures contain complex feedback loops that prevent simple cyclical failures.
- •For graph algorithm engineers: Use structural properties of large tournaments to optimize algorithms for detecting complex cycles in directed graphs.
A theory result. No direct application yet.
Authors
Pierre Charbit, Samuel Coulomb
Abstract
In the 1960s, Erdős and Hajnal conjectured that every graph with sufficiently large chromatic number contains a subgraph of large girth (size of a smallest cycle) and large chromatic number. In this paper, we prove that every tournament with sufficiently large dichromatic number contains a subdigraph of large digirth (size of a smallest directed cycle) and large dichromatic number. We investigate the same statement when replacing digirth by girth (of the underlying graph). We show that it implies the conjecture of Erdős and Hajnal, and prove it for a particular family of tournaments.