*** Welcome to piglix ***

Sumner's conjecture


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. 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 . Thus, if true, Sumner's conjecture would give the best possible size of a universal graph for polytrees.


...
Wikipedia

...