Sumner's conjecture

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Question dropshade.png Unsolved problem in mathematics:
Does every -vertex tournament contain as a subgraph every -vertex oriented tree?
(more unsolved problems in mathematics)

David Sumner (a graph theorist at the University of South Carolina) conjectured in 1971 that tournaments are universal graphs for polytrees. More precisely, Sumner's conjecture (also called Sumner's universal tournament conjecture) states that every orientation of every -vertex tree is a subgraph of every -vertex tournament.[1] The conjecture remains unproven; Kühn, Mycroft & Osthus (2011a) call it "one of the most well-known problems on tournaments."


Let polytree be a star , in which all edges are oriented outward from the central vertex to the leaves. Then, cannot be embedded in the tournament formed from the vertices of a regular -gon by directing every edge clockwise around the polygon. For, in this tournament, every vertex has indegree and outdegree equal to , while the central vertex in has larger outdegree .[2] Thus, if true, Sumner's conjecture would give the best possible size of a universal graph for polytrees.

However, in every tournament of vertices, the average outdegree is , and the maximum outdegree is an integer greater than or equal to the average. Therefore, there exists a vertex of outdegree , which can be used as the central vertex for a copy of .

Partial results[edit]

The following partial results on the conjecture are known.

  • It is true for all sufficiently large values of .[3]
  • There is a function with asymptotic growth rate with the property that every -vertex polytree can be embedded as a subgraph of every -vertex tournament. Additionally and more explicitly, .[4]
  • There is a function such that tournaments on vertices are universal for polytrees with leaves.[5]
  • There is a function such that every -vertex polytree with maximum degree at most forms a subgraph of every tournament with vertices. When is a fixed constant, the asymptotic growth rate of is .[6]
  • Every "near-regular" tournament on vertices contains every -vertex polytree.[7]
  • Every orientation of an -vertex caterpillar tree with diameter at most four can be embedded as a subgraph of every -vertex tournament.[7]
  • Every -vertex tournament contains as a subgraph every -vertex arborescence.[8]

Related conjectures[edit]

Rosenfeld (1972) conjectured that every orientation of an -vertex path graph (with ) can be embedded as a subgraph into every -vertex tournament.[7] After partial results by Thomason (1986) this was proven by Havet & Thomassé (2000a).

Havet and Thomassé[9] in turn conjectured a strengthening of Sumner's conjecture, that every tournament on vertices contains as a subgraph every polytree with at most leaves.

Burr (1980) conjectured that, whenever a graph requires or more colors in a coloring of , then every orientation of contains every orientation of an -vertex tree. Because complete graphs require a different color for each vertex, Sumner's conjecture would follow immediately from Burr's conjecture.[10] As Burr showed, orientations of graphs whose chromatic number grows quadratically as a function of are universal for polytrees.


  1. ^ Kühn, Mycroft & Osthus (2011a). However the earliest published citations given by Kühn et al. are to Reid & Wormald (1983) and Wormald (1983). Wormald (1983) cites the conjecture as an undated private communication by Sumner.
  2. ^ This example is from Kühn, Mycroft & Osthus (2011a).
  3. ^ Kühn, Mycroft & Osthus (2011b).
  4. ^ Kühn, Mycroft & Osthus (2011a) and El Sahili (2004). For earlier weaker bounds on , see Chung (1981), Wormald (1983), Häggkvist & Thomason (1991), Havet & Thomassé (2000b), and Havet (2002).
  5. ^ Häggkvist & Thomason (1991); Havet & Thomassé (2000a); Havet (2002).
  6. ^ Kühn, Mycroft & Osthus (2011a).
  7. ^ a b c Reid & Wormald (1983).
  8. ^ Havet & Thomassé (2000b).
  9. ^ In Havet (2002), but jointly credited to Thomassé in that paper.
  10. ^ This is a corrected version of Burr's conjecture from Wormald (1983).


External links[edit]