Sumner's conjecture

Unsolved problem in mathematics
Does every 
  
    
      
        (
        2
        n
        −
        2
        )
      
    
    {\displaystyle (2n-2)}
  
-vertex tournament contain as a subgraph every 
  
    
      
        n
      
    
    {\displaystyle n}
  
-vertex oriented tree?
<a href="/facts/List_of_unsolved_problems_in_mathematics/RroxGPpP">More unsolved problems in mathematics</a>

<p>Sumner's conjecture (also called Sumner's universal tournament conjecture) is a conjecture in <a href="/facts/Extremal_graph_theory/mdkBX6yN">extremal graph theory</a> on oriented <a href="/facts/Tree_(graph_theory)/TCWk4Joy">trees</a> in <a href="/facts/Tournament_(graph_theory)/SVj5jWWE">tournaments</a>. It states that every <a href="/facts/Orientation_(graph_theory)/GV2KdNtn">orientation</a> of every 
  
    
      
        n
      
    
    {\displaystyle n}
  
-vertex <a href="/facts/Tree_(graph_theory)/TCWk4Joy">tree</a> is a <a href="/facts/Glossary_of_graph_theory/W0MqKkyE">subgraph</a> of every 
  
    
      
        (
        2
        n
        −
        2
        )
      
    
    {\displaystyle (2n-2)}
  
-vertex tournament. 
<a href="/facts/David_Sumner/QxNqG0YX">David Sumner</a>, a <a href="/facts/Graph_theory/VVPCd4TX">graph theorist</a> at the <a href="/facts/University_of_South_Carolina/C6YRanR1">University of South Carolina</a>, <a href="/facts/Conjecture/oPWUb7SF">conjectured</a> in 1971 that <a href="/facts/Tournament_(graph_theory)/SVj5jWWE">tournaments</a> are <a href="/facts/Universal_graph/ETvMS7NB">universal graphs</a> for <a href="/facts/Polytree/pcJa4qeS">polytrees</a>. The conjecture was proven for all large 
  
    
      
        n
      
    
    {\displaystyle n}
  
 by <a href="/facts/Daniela_K%25C3%25BChn/mgN9N5yQ">Daniela Kühn</a>, Richard Mycroft, and <a href="/facts/Deryk_Osthus/8KIb5Vur">Deryk Osthus</a>.
</p>

Sumner's conjecture open-in-new

Sumner's conjecture