词条 | 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.[1] The conjecture remains unproven; {{harvtxt|Kühn|Mycroft|Osthus|2011a}} call it "one of the most well-known problems on tournaments." ExamplesLet 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 resultsThe following partial results on the conjecture are known.
Related conjectures{{harvtxt|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 {{harvtxt|Thomason|1986}} this was proven by {{harvtxt|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. {{harvtxt|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.Notes1. ^{{harvtxt|Kühn|Mycroft|Osthus|2011a}}. However the earliest published citations given by Kühn et al. are to {{harvtxt|Reid|Wormald|1983}} and {{harvtxt|Wormald|1983}}. {{harvtxt|Wormald|1983}} cites the conjecture as an undated private communication by Sumner. 2. ^This example is from {{harvtxt|Kühn|Mycroft|Osthus|2011a}}. 3. ^{{harvtxt|Kühn|Mycroft|Osthus|2011b}}. 4. ^{{harvtxt|Kühn|Mycroft|Osthus|2011a}} and {{harvtxt|El Sahili|2004}}. For earlier weaker bounds on , see {{harvtxt|Chung|1981}}, {{harvtxt|Wormald|1983}}, {{harvtxt|Häggkvist|Thomason|1991}}, {{harvtxt|Havet|Thomassé|2000b}}, and {{harvtxt|Havet|2002}}. 5. ^{{harvtxt|Häggkvist|Thomason|1991}}; {{harvtxt|Havet|Thomassé|2000a}}; {{harvtxt|Havet|2002}}. 6. ^{{harvtxt|Kühn|Mycroft|Osthus|2011a}}. 7. ^1 2 {{harvtxt|Reid|Wormald|1983}}. 8. ^{{harvtxt|Havet|Thomassé|2000b}}. 9. ^In {{harvtxt|Havet|2002}}, but jointly credited to Thomassé in that paper. 10. ^This is a corrected version of Burr's conjecture from {{harvtxt|Wormald|1983}}. References
| last = Burr | first = Stefan A. | author-link = Stefan Burr | contribution = Subtrees of directed graphs and hypergraphs | series = Congressus Numerantium | mr = 608430 | pages = 227–239 | title = Proceedings of the Eleventh Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1980), Vol. I | volume = 28 | year = 1980}}.
| last = Chung | first = F.R.K. | author-link = Fan Chung | publisher = Bell Laboratories | series = Internal Memorandum | title = A note on subtrees in tournaments | year = 1981}}. As cited by {{harvtxt|Wormald|1983}}.
| last = El Sahili | first = A. | doi = 10.1016/j.jctb.2004.04.002 | issue = 1 | journal = Journal of Combinatorial Theory | series = Series B | mr = 2078502 | pages = 183–187 | title = Trees in tournaments | volume = 92 | year = 2004}}.
| last1 = Häggkvist | first1 = Roland | last2 = Thomason | first2 = Andrew | doi = 10.1007/BF01206356 | issue = 2 | journal = Combinatorica | mr = 1136161 | pages = 123–130 | title = Trees in tournaments | volume = 11 | year = 1991}}.
| last = Havet | first = Frédéric | doi = 10.1016/S0012-365X(00)00463-5 | issue = 1-3 | journal = Discrete Mathematics | mr = 1874730 | pages = 121–134 | title = Trees in tournaments | volume = 243 | year = 2002}}.
| last1 = Havet | first1 = Frédéric | last2 = Thomassé | first2 = Stéphan | doi = 10.1006/jctb.1999.1945 | issue = 2 | journal = Journal of Combinatorial Theory | series = Series B | mr = 1750898 | pages = 243–273 | title = Oriented Hamiltonian paths in tournaments: a proof of Rosenfeld's conjecture | volume = 78 | year = 2000a}}.
| last1 = Havet | first1 = Frédéric | last2 = Thomassé | first2 = Stéphan | doi = 10.1002/1097-0118(200012)35:4<244::AID-JGT2>3.0.CO;2-H | issue = 4 | journal = Journal of Graph Theory | mr = 1791347 | pages = 244–256 | title = Median orders of tournaments: a tool for the second neighborhood problem and Sumner's conjecture | volume = 35 | year = 2000b}}.
| last1 = Kühn | first1 = Daniela | author1-link = Daniela Kühn | last2 = Mycroft | first2 = Richard | last3 = Osthus | first3 = Deryk | doi = 10.1016/j.jctb.2010.12.006 | issue = 6 | journal = Journal of Combinatorial Theory | series = Series B | mr = 2832810 | zbl=1234.05115 | pages = 415–447 | title = An approximate version of Sumner's universal tournament conjecture | volume = 101 | year = 2011a}}.
| last1 = Kühn | first1 = Daniela | author1-link = Daniela Kühn | last2 = Mycroft | first2 = Richard | last3 = Osthus | first3 = Deryk | arxiv = 1010.4430 | doi = 10.1112/plms/pdq035 | issue = 4 | journal = Proceedings of the London Mathematical Society | series = Third Series | mr = 2793448 | zbl=1218.05034 | pages = 731–766 | title = A proof of Sumner's universal tournament conjecture for large tournaments | volume = 102 | year = 2011b}}.
| last1 = Reid | first1 = K. B. | last2 = Wormald | first2 = N. C. | issue = 2-4 | journal = Studia Scientiarum Mathematicarum Hungarica | mr = 787942 | pages = 377–387 | title = Embedding oriented n-trees in tournaments | volume = 18 | year = 1983}}.
| last = Rosenfeld | first = M. | journal = Journal of Combinatorial Theory | series = Series B | mr = 0285452 | pages = 93–99 | title = Antidirected Hamiltonian paths in tournaments | volume = 12 | year = 1972 | doi=10.1016/0095-8956(72)90035-4}}.
| last = Thomason | first = Andrew | doi = 10.2307/2000567 | issue = 1 | journal = Transactions of the American Mathematical Society | mr = 837805 | pages = 167–180 | title = Paths and cycles in tournaments | volume = 296 | year = 1986}}.
| last = Wormald | first = Nicholas C. | contribution = Subtrees of large tournaments | doi = 10.1007/BFb0071535 | location = Berlin | mr = 731598 | pages = 417–419 | publisher = Springer | series = Lecture Notes in Math. | title = Combinatorial mathematics, X (Adelaide, 1982) | volume = 1036 | year = 1983}}. External links
2 : Graph theory|Conjectures |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。