Talk:Tournament (graph theory)

This is the talk page for discussing improvements to the Tournament (graph theory) article.
This is not a forum for general discussion of the article's subject.

Put new text under old text. Click here to start a new topic.
New to Wikipedia? Welcome! Learn to edit; get help.

Article policies

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL

"undirected"

The intro says the graph is undirected, but the image directly below that statement shows a directed graph. Please fix. --AlanH (talk) 18:36, 22 February 2008 (UTC)[reply]

Nope, the intro says that a tournament is a graph obtained by assigning direction to edges of a complete undirected graph, thus making it a directed graph. --Rulatir (talk) 20:21, 5 July 2009 (UTC)[reply]

largest transitive subtournament

"Every tournament on n vertices has a transitive subtournament on log2n vertices. Reid and Parker showed that this is the best possible result: there exist n-vertex tournaments whose largest transitive subtournament is of size log2n."

This comes with no reference, and is apparently simply wrong. I belive the best known upper bound is ~2log2n. —Preceding unsigned comment added by 132.64.140.208 (talk) 11:46, 24 November 2010 (UTC)[reply]

Last Sentence Paths and Cycles

It reads: "Moreover, if the tournament is 4‑connected, each pair of vertices can be connected with a Hamiltonian path (Thomassen 1980)."

Aren't all tournaments complete graphs? Isn't a complete graph with k vertices always k-connected? Therefore wouldn't it be simpler to write, "Moreover, if the tournament has 4 or more vertices, each pair of vertices can be connected with a Hamiltonian path (Thomassen 1980)." —Preceding unsigned comment added by Recurve7 (talk • contribs) 19:28, 25 November 2010 (UTC)[reply]

It's a directed form of connectivity. I imagine that it means that it remains strongly connected after the removal of any three vertices, but I'd have to check the source to be sure. —David Eppstein (talk) 19:49, 25 November 2010 (UTC)[reply]

A UCI ICS grad's question fielded by a UCI CS professor on a random obscure Wikipedia Talk page. That's almost a graph theory connectedness anomaly in itself. -Recurve7

Transitivity

The graph shown on the right is not transitive (at least not according to the definition given in this article). It says a graph with n vertices should have as score sequence {0, 1, ..., n-1}, which means, every outdegree exists exactly once. Nodes 3 and 4 both have the same outdegree (ie. 4: 3->4, 3->5, 3->6, 3->7 and 4->5, 4->6, 4->7, 4->8). — Preceding unsigned comment added by 141.44.28.72 (talk) 10:51, 16 August 2012 (UTC)[reply]

You missed 3 → 8. In fact, the tournament has an extremely simple description: i → j iff i < j. Since < is a linear order, it is clearly transitive.—Emil J. 12:28, 16 August 2012 (UTC)[reply]

Definition

Tournaments can also be defined by means of an irreflexive, antisymmetric and total binary relation R. That is, for each x, y in a set E, either x = y, either x R y, either y R x. R can be seen as the domination relation. Would that be worth saying in the article?

Other topics that might be added include number of non-isomorphic tournaments over n vertices, and tournament matrix. --MathsPoetry (talk) 09:42, 27 January 2013 (UTC)[reply]

Please see WP:BOLD. —David Eppstein (talk) 21:57, 14 February 2013 (UTC)[reply]

Nope. I decided not to contribute anymore on WP:en, sorry. --MathsPoetry (talk) 14:55, 17 February 2013 (UTC)[reply]

History

"Many of the important properties of tournaments were first investigated by Landau in order to model dominance relations in flocks of chickens."

I would remove "first", as we have other important results from 1934, that is before 1953, date of Landau's article. --MathsPoetry (talk) 09:44, 27 January 2013 (UTC)[reply]

Please see WP:BOLD. —David Eppstein (talk) 21:58, 14 February 2013 (UTC)[reply]

Nope. I decided not to contribute anymore on WP:en, sorry. --MathsPoetry (talk) 14:56, 17 February 2013 (UTC)[reply]

Theorem about Hamiltonian paths

In case it interests you, I made an illustration of the proof of the theorem about Hamiltonian paths in tournaments. Please notice that $v_{0}$ is renamed $a$ for clarity purposes. --MathsPoetry (talk) 09:56, 27 January 2013 (UTC)[reply]

Please see WP:BOLD. —David Eppstein (talk) 21:58, 14 February 2013 (UTC)[reply]

Nope. I decided not to contribute anymore on WP:en, sorry. --MathsPoetry (talk) 14:56, 17 February 2013 (UTC)[reply]

No winner example

"as the above example shows, there might not be such a player"

Which example above? I assume the 4-vertices graph drawn on top of the article. If correct, that should be made clear in the article IMHO. --MathsPoetry (talk) 09:45, 27 January 2013 (UTC)[reply]

This has since been clarified. —David Eppstein (talk) 21:58, 14 February 2013 (UTC)[reply]

OK. --MathsPoetry (talk) 14:57, 17 February 2013 (UTC)[reply]

Paradoxical vs. Transitive

Sorry for the newbye question, but what is the relationship between a paradoxical tournament and a transitive tournament? My first impression is that a paradoxical tournament is the same as a non-transitive tournament.

Whatever the exact relation, it would be a good idea to make it explicit in the article, because paradoxical tournaments are explained under the section about transitivity. --MathsPoetry (talk) 09:47, 27 January 2013 (UTC)[reply]

I believe the exact relation is that the paradoxical tournaments and the transitive tournaments are disjoint from each other: it is not possible for a tournament to be both paradoxical and transitive. However there exist tournaments that are neither paradoxical nor transitive. —David Eppstein (talk) 21:57, 14 February 2013 (UTC)[reply]

The article would probably benefit from these sentences, and even better, an example of a tournament that is neither paradoxical nor transitive. --MathsPoetry (talk) 15:06, 17 February 2013 (UTC)[reply]

Wrong Diagram?

The diagram in the intro seems to say that the number of edges is "n choose 2", whereas in general it is n*(n-1)/2, the same as K(n). In the case of n=4, these values are the same, but it seems pointless and unhelpful to give the former. I'd be bold and change it if I knew how, though I fear I've missed something..:-) John Wheater (talk) 10:35, 17 September 2014 (UTC)[reply]

They are always the same. And "n choose 2" describes why it has that form rather than just being a random and arbitrary quadratic polynomial. See triangular number. —David Eppstein (talk) 16:31, 17 September 2014 (UTC)[reply]

That's really helpful David, thanks. I now see that "n choose 2" is the same as n*(n-1)/2 for all even n - and a tournament must have an even number of players....John Wheater (talk) 14:15, 19 September 2014 (UTC)[reply]

There is no requirement of having an even number. (This is not like an actual sports tournament that has to proceed in rounds, and n choose 2 is meaningful for odd numbers as well as even.) —David Eppstein (talk) 14:57, 19 September 2014 (UTC)[reply]

Oops, yes, thanks, and thanks for the reversion. Sloppy pencil & paper work, and brain-softening. Mind you, I think it a bit unkind to call n*(n-1)/2 'random and arbitrary', it is intuitive for the complete graph, and a limiting case of the famous handshake. John Wheater (talk) 06:57, 20 September 2014 (UTC)[reply]

"n over 2" (binomial coefficient) isn't even defined for n less than 2, not to mention it is the wrong expression for the number of undirected edges in a complete graph (and thus number of edges in a tournament). If something else is meant by "edges" or by the given expression, than this should be pointed out. As it stood, it was plain wrong. -- ManDay — Preceding unsigned comment added by 88.217.234.135 (talk) 09:11, 9 May 2018 (UTC)[reply]

It's not n over 2, it's n choose 2. And it's perfectly well defined for n less than 2, equalling zero for those n. And it is always the correct number of edges. There is no mistake. —David Eppstein (talk) 16:00, 9 May 2018 (UTC)[reply]

Landau?

Who is Landau? Can we have a first initial or link? Lena Key (talk) 20:01, 13 May 2016 (UTC)[reply]

His initials were already given in the references section. Apparently he was Hyman G. Landau, a mathematician at the University of Chicago. —David Eppstein (talk) 20:38, 13 May 2016 (UTC)[reply]

Transitivity - acyclic

The first shown graph is stated as being a tournament graph but is cyclic: 1->2->4->3->1 Condition (3) states: T is asyclic. What is the source of that condition, and which one is correct (graph or condition)? Dominikmorgen (talk) 12:24, 16 July 2016 (UTC)[reply]

Transitive tournaments are the same thing as acyclic tournaments, but they are a special case among all tournaments. This example is not one of these special cases. It is a tournament, but not transitive and not acyclic. —David Eppstein (talk) 17:17, 16 July 2016 (UTC)[reply]

Paths and cycles

The proof is incorrect. It says:

suppose that the statement holds for $n$ , and consider any tournament $T$ on $n+1$ vertices. Choose a vertex $v_{0}$ of $T$ and consider a directed path $v_{1},v_{2},\ldots ,v_{n}$ in $T\setminus \{v_{0}\}$ . Now let $i\in \{0,\ldots ,n\}$ be maximal such that for every $j\leq i$ there is a directed edge from $v_{j}$ to $v_{0}$ .

v_{1},\ldots ,v_{i},v_{0},v_{i+1},\ldots ,v_{n}

is a directed path as desired.

First, it's missing the ground case of n=2, which has a Hamiltonian path by inspection.

In addition, no such i exists if all edges between v0 and v1 ... vn point away from v0. (One cannot say that 0 is the biggest such i, because there is no edge v0->v0.) Nevertheless, a Hamiltonian path still exists, v0, v1, ..., vn.

More generally, I think this proof should be written without mathematical notation. It's a fantastic inductive proof because it's so simple, and it would be great to make it accessible to the general public.

The proof would go something like:

We show that a tournament of any size has a Hamilton path. Clearly a tournament with 2 nodes has one. We prove that a trournament of any size must have a Hamilton path because if any tournament with n nodes has such a path then any tournament of size n+1 containing the tournament of size n must have a Hamilton path.

Imagine that a tournament with n nodes has a Hamilton path. Label the nodes in the path v1, v2, ..., vn. Add another node X to the graph and connect it to all the existing nodes with directed edges. Then there are 3 cases:

All the edges between X and v1, v2, ..., vn point from X. Then X, v1, v2, ..., vn is a Hamiltonian Path.

All the edges between X and v1, v2, ..., vn point to X. Then v1, v2, ..., vn, X is a Hamiltonian Path.

Some of the edges connecting X to the existing graph point from X, while others point to X. Suppose vi is the first node in v1, v2, ... that X points to. Then v1, v2, v(i-1), X, vi, v(i+1), ..., vn is a Hamiltonian Path.

(I realize that cases 1 & 3 could be combined, but I like the symmetry of 1 & 2.)

I know that the proof needs to found elsewhere to publish this in WP. Sorry, I don't have time to do that.

Diagrams would be nice, of course.

Arthur.Goldberg (talk) 17:00, 24 June 2017 (UTC) ArthurG — Preceding unsigned comment added by Arthur.Goldberg (talk • contribs) 16:53, 24 June 2017 (UTC)[reply]

Solvability

The group of isomorphisms on any tournament graph is solvable. This should be mentioned somewhere. — Preceding unsigned comment added by 141.20.50.37 (talk) 16:53, 2 March 2020 (UTC)[reply]

Paul Erdős showed that for any fixed value of k, if (maths), then almost every tournament on V is k-paradoxical

Is it correct for this to say "almost every" per the mathematical definition of "almost"? Isn't the linked proof only proving existence? Given that, for a fixed V, there are a finite number of tournaments, of which at least some are not k-paradoxical (e.g. one player wins every match), surely that's a non-zero measure of non-paradoxical tournaments?

Rawling (talk) 11:09, 29 October 2024 (UTC)[reply]