Sumner's conjecture

☆ Save On Wikipedia ↗
Unsolved problem in mathematics
Does every ( 2 n − 2 ) {\displaystyle (2n-2)} {\displaystyle (2n-2)}-vertex tournament contain as a subgraph every n {\displaystyle n} {\displaystyle n}-vertex oriented tree?
More unsolved problems in mathematics
A 6-vertex tournament, and copies of every 4-vertex oriented tree within it.

Sumner's conjecture (also called Sumner's universal tournament conjecture) is a conjecture in extremal graph theory on oriented trees in tournaments. It states that every orientation of every n {\displaystyle n} {\displaystyle n}-vertex tree is a subgraph of every ( 2 n − 2 ) {\displaystyle (2n-2)} {\displaystyle (2n-2)}-vertex tournament.[1] David Sumner, a graph theorist at the University of South Carolina, conjectured in 1971 that tournaments are universal graphs for polytrees. The conjecture was proven for all large n {\displaystyle n} {\displaystyle n} by Daniela Kühn, Richard Mycroft, and Deryk Osthus.[2]

Examples

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

However, in every tournament of 2 n − 2 {\displaystyle 2n-2} {\displaystyle 2n-2} vertices, the average outdegree is n − 3 2 {\displaystyle n-{\frac {3}{2}}} {\displaystyle n-{\frac {3}{2}}}, and the maximum outdegree is an integer greater than or equal to the average. Therefore, there exists a vertex of outdegree ⌈ n − 3 2 ⌉ = n − 1 {\displaystyle \left\lceil n-{\frac {3}{2}}\right\rceil =n-1} {\displaystyle \left\lceil n-{\frac {3}{2}}\right\rceil =n-1}, which can be used as the central vertex for a copy of P {\displaystyle P} {\displaystyle P}.

Partial results

The following partial results on the conjecture have been proven.

  • There is a function f ( n ) {\displaystyle f(n)} {\displaystyle f(n)} with asymptotic growth rate f ( n ) = 2 n + o ( n ) {\displaystyle f(n)=2n+o(n)} {\displaystyle f(n)=2n+o(n)} with the property that every n {\displaystyle n} {\displaystyle n}-vertex polytree can be embedded as a subgraph of every f ( n ) {\displaystyle f(n)} {\displaystyle f(n)}-vertex tournament. Additionally and more explicitly, f ( n ) ≤ 3 n − 3 {\displaystyle f(n)\leq 3n-3} {\displaystyle f(n)\leq 3n-3}.[4]
  • There is a function g ( k ) {\displaystyle g(k)} {\displaystyle g(k)} such that tournaments on n + g ( k ) {\displaystyle n+g(k)} {\displaystyle n+g(k)} vertices are universal for polytrees with k {\displaystyle k} {\displaystyle k} leaves.[5]
  • There is a function h ( n , Δ ) {\displaystyle h(n,\Delta )} {\displaystyle h(n,\Delta )} such that every n {\displaystyle n} {\displaystyle n}-vertex polytree with maximum degree at most Δ {\displaystyle \Delta } {\displaystyle \Delta } forms a subgraph of every tournament with h ( n , Δ ) {\displaystyle h(n,\Delta )} {\displaystyle h(n,\Delta )} vertices. When Δ {\displaystyle \Delta } {\displaystyle \Delta } is a fixed constant, the asymptotic growth rate of h ( n , Δ ) {\displaystyle h(n,\Delta )} {\displaystyle h(n,\Delta )} is n + o ( n ) {\displaystyle n+o(n)} {\displaystyle n+o(n)}.[6]
  • Every "near-regular" tournament on 2 n − 2 {\displaystyle 2n-2} {\displaystyle 2n-2} vertices contains every n {\displaystyle n} {\displaystyle n}-vertex polytree.[7]
  • Every orientation of an n {\displaystyle n} {\displaystyle n}-vertex caterpillar tree with diameter at most four can be embedded as a subgraph of every ( 2 n − 2 ) {\displaystyle (2n-2)} {\displaystyle (2n-2)}-vertex tournament.[7]
  • Every ( 2 n − 2 ) {\displaystyle (2n-2)} {\displaystyle (2n-2)}-vertex tournament contains as a subgraph every n {\displaystyle n} {\displaystyle n}-vertex arborescence.[8]

Rosenfeld (1972) conjectured that every orientation of an n {\displaystyle n} {\displaystyle n}-vertex path graph (with n ≥ 8 {\displaystyle n\geq 8} {\displaystyle n\geq 8}) can be embedded as a subgraph into every n {\displaystyle n} {\displaystyle n}-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 n + k − 1 {\displaystyle n+k-1} {\displaystyle n+k-1} vertices contains as a subgraph every polytree with at most k {\displaystyle k} {\displaystyle k} leaves. This has been confirmed for almost every tree by Mycroft and Naia (2018).

Burr (1980) conjectured that, whenever a graph G {\displaystyle G} {\displaystyle G} requires 2 n − 2 {\displaystyle 2n-2} {\displaystyle 2n-2} or more colors in a coloring of G {\displaystyle G} {\displaystyle G}, then every orientation of G {\displaystyle G} {\displaystyle G} contains every orientation of an n {\displaystyle n} {\displaystyle n}-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 n {\displaystyle n} {\displaystyle n} are universal for polytrees.

Notes

  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. Kühn, Mycroft & Osthus (2011b).
  3. This example is from Kühn, Mycroft & Osthus (2011a).
  4. Kühn, Mycroft & Osthus (2011a) and El Sahili (2004). For earlier weaker bounds on f ( n ) {\displaystyle f(n)} {\displaystyle f(n)}, 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. 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).

References