1
$\begingroup$

This is a somewhat vague question, but I'm interested in ways to create a strong tournament from one or more smaller tournaments. Obviously, the disjoint union of two tournaments is a new tournament, but more interestingly, the idea of a transitive blowup of a tournament has been studied. Given a tournament $T$, form a new tournament by expanding each vertex into a transitive tournament with some specified number of vertices, with the edges between two of the inserted tournaments drawn in the same direction as the edge between vertices they replaces. Of course, this concept can be varied so that the inserted subtournaments are non-transitive.

My general questions are:

  1. What other ways are there to create large tournaments from small ones?

  2. Is there any collection of tools that one can use to inductively generate all tournaments?

My instinct is that question 2 is a pipe dream - the number of tournaments on $n$ vertices grows pretty quickly, so the procedures used to generate them would have to be pretty robust. Thanks for the help!

$\endgroup$
1
  • $\begingroup$ You can pretty easily reduce the problem to constructing all strongly connected tournaments. Not sure how to efficiently generate all of those, though... $\endgroup$ Commented May 8, 2017 at 15:56

0

You must log in to answer this question.

Browse other questions tagged .