Jump to content

Universal graph: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
No edit summary
 
(10 intermediate revisions by 8 users not shown)
Line 1: Line 1:
In [[mathematics]], a '''universal graph''' is an infinite [[Graph (discrete mathematics)|graph]] that contains ''every'' finite (or at-most-[[countable]]) graph as an induced [[Glossary of graph theory#Subgraphs|subgraph]]. A universal graph of this type was first constructed by [[Richard Rado]]<ref>{{cite journal
In [[mathematics]], a '''universal graph''' is an infinite [[Graph (discrete mathematics)|graph]] that contains ''every'' finite (or at-most-[[countable]]) graph as an induced [[Glossary of graph theory#Subgraphs|subgraph]]. A universal graph of this type was first constructed by [[Richard Rado]]<ref>{{cite journal
| author = Rado, R.
| last1 = Rado | first1=R. | authorlink1=Richard Rado
| title = Universal graphs and universal functions
| title = Universal graphs and universal functions
| journal = Acta Arithmetica
| journal = Acta Arithmetica
| volume = 9
| volume = 9
| issue = 4
| year = 1964
| year = 1964
| pages = 331–340
| pages = 331–340
| mr = 0172268
| mr = 0172268
| doi=10.4064/aa-9-4-331-340}}</ref><ref>{{cite conference
| doi=10.4064/aa-9-4-331-340| doi-access = free
}}</ref><ref>{{cite conference
| author = Rado, R.
| last1 = Rado | first1=R. | authorlink1=Richard Rado
| title = Universal graphs
| title = Universal graphs
| date = 1967
| date = 1967
| booktitle = A Seminar in Graph Theory
| book-title = A Seminar in Graph Theory
| publisher = Holt, Rinehart, and Winston
| publisher = Holt, Rinehart, and Winston
| pages = 83–85
| pages = 83–85
Line 17: Line 19:
|author1=Goldstern, Martin |author2=Kojman, Menachem | title = Universal arrow-free graphs
|author1=Goldstern, Martin |author2=Kojman, Menachem | title = Universal arrow-free graphs
| year = 1996
| year = 1996
| journal = Acta Mathematica Hungarica
| journal = [[Acta Mathematica Hungarica]]
| volume = 1973
| volume = 1973
| pages = 319–326
| pages = 319–326
| doi = 10.1007/BF00052907
| doi = 10.1007/BF00052907 | doi-access = free
| arxiv = math.LO/9409206
| arxiv = math.LO/9409206
| mr = 1428038
| mr = 1428038
| issue = 4}}</ref>
| issue = 4}}</ref>
<ref>{{cite journal
<ref>{{cite journal
| last1=Cherlin | first1=Greg
⚫
|author1=Cherlin, Greg |author2=Shelah, Saharon |author3=Shi, Niandong | title = Universal graphs with forbidden subgraphs and algebraic closure
| last2=Shelah | first2=Saharon | authorlink2=Saharon Shelah
| last3=Shi | first3=Niandong
⚫
| title = Universal graphs with forbidden subgraphs and algebraic closure
| journal = Advances in Applied Mathematics
| journal = Advances in Applied Mathematics
| volume = 22
| volume = 22
Line 33: Line 38:
| arxiv = math.LO/9809202
| arxiv = math.LO/9809202
| mr = 1683298
| mr = 1683298
| issue = 4}}</ref>
| issue = 4|s2cid=17529604 }}</ref>
has focused on universal graphs for a graph family {{mvar|F}}: that is, an infinite graph belonging to ''F'' that contains all finite graphs in {{mvar|F}}. For instance, the [[Henson graph]]s are universal in this sense for the {{mvar|i}}-clique-free graphs.
has focused on universal graphs for a graph family {{mvar|F}}: that is, an infinite graph belonging to ''F'' that contains all finite graphs in {{mvar|F}}. For instance, the [[Henson graph]]s are universal in this sense for the {{mvar|i}}-clique-free graphs.


Line 45: Line 50:
| pages = 238–249
| pages = 238–249
| doi = 10.1016/0743-7315(85)90026-7
| doi = 10.1016/0743-7315(85)90026-7
| issue = 3}}</ref>
| issue = 3 }}</ref>
so a hypercube can be said to be a universal graph for trees. However it is not the smallest such graph: it is known that there is a universal graph for {{mvar|n}}-vertex trees, with only {{mvar|n}}&nbsp;vertices and {{math|O(''n''&nbsp;log&nbsp;''n'')}} edges, and that this is optimal.<ref>{{cite journal|first1=F. R. K.|last1=Chung|author1-link=Fan Chung|first2=R. L.|last2=Graham|author2-link=Ronald Graham|title=On universal graphs for spanning trees|journal=Journal of the London Mathematical Society|volume=27|year=1983|pages=203–211|url=http://www.math.ucsd.edu/~fan/mypaps/fanpap/35universal.pdf|doi=10.1112/jlms/s2-27.2.203|issue=2|mr=0692525}}.</ref> A construction based on the [[planar separator theorem]] can be used to show that {{mvar|n}}-vertex [[planar graph]]s have universal graphs with {{math|O(''n''<sup>3/2</sup>)}} edges, and that bounded-degree planar graphs have universal graphs with {{math|O(''n''&nbsp;log&nbsp;''n'')}} edges.<ref>{{Cite book
so a hypercube can be said to be a universal graph for trees. However it is not the smallest such graph: it is known that there is a universal graph for {{mvar|n}}-vertex trees, with only {{mvar|n}}&nbsp;vertices and {{math|O(''n''&nbsp;log&nbsp;''n'')}} edges, and that this is optimal.<ref>{{cite journal|first1=F. R. K.|last1=Chung|author1-link=Fan Chung|first2=R. L.|last2=Graham|author2-link=Ronald Graham|title=On universal graphs for spanning trees|journal=Journal of the London Mathematical Society|volume=27|year=1983|pages=203–211|url=http://www.math.ucsd.edu/~fan/mypaps/fanpap/35universal.pdf|doi=10.1112/jlms/s2-27.2.203|issue=2|mr=0692525|citeseerx=10.1.1.108.3415}}.</ref> A construction based on the [[planar separator theorem]] can be used to show that {{mvar|n}}-vertex [[planar graph]]s have universal graphs with {{math|O(''n''<sup>3/2</sup>)}} edges, and that bounded-degree planar graphs have universal graphs with {{math|O(''n''&nbsp;log&nbsp;''n'')}} edges.<ref>{{Cite book
| last1 = Babai | first1 = L. | author1-link = László Babai
| last1 = Babai | first1 = L. | author1-link = László Babai
| last2 = Chung | first2 = F. R. K. | author2-link = Fan Chung
| last2 = Chung | first2 = F. R. K. | author2-link = Fan Chung
Line 75: Line 80:
| issue = 2
| issue = 2
| mr = 0990447}}</ref><ref>{{Cite book
| mr = 0990447}}</ref><ref>{{Cite book
| last = Chung | first = Fan R. K. | author-link = Fan Chung
| last = Chung
| first = Fan R. K.
| author-link = Fan Chung
| contribution = Separator theorems and their applications
| contribution = Separator theorems and their applications
| editor1-last = Korte | editor1-first = Bernhard | editor1-link = Bernhard Korte
| editor1-last = Korte
| editor1-first = Bernhard
| editor1-link = Bernhard Korte
| editor2-last = Lovász | editor2-first = László | editor2-link = László Lovász
| editor2-last = Lovász
| editor2-first = László
| editor2-link = László Lovász
| editor3-last = Prömel | editor3-first = Hans Jürgen
| editor3-last = Prömel
| editor3-first = Hans Jürgen
| editor4-last = Schrijver | editor4-first = Alexander| display-editors = 3
| editor4-last = Schrijver
| editor4-first = Alexander
| display-editors = 3
| isbn = 978-0-387-52685-0
| isbn = 978-0-387-52685-0
| pages = 17–34
| pages = [https://archive.org/details/pathsflowsvlsila0000unse/page/17 17–34]
| publisher = Springer-Verlag
| publisher = Springer-Verlag
| series = Algorithms and Combinatorics
| series = Algorithms and Combinatorics
Line 88: Line 102:
| volume = 9
| volume = 9
| year = 1990
| year = 1990
| mr = 1083375
⚫
| mr = 1083375}}</ref> [[Sumner's conjecture]] states that [[tournament (graph theory)|tournaments]] are universal for [[polytree]]s, in the sense that every tournament with {{math|2''n''&nbsp;&minus;&nbsp;2}} vertices contains every polytree with {{mvar|n}} vertices as a subgraph.<ref>[http://www.math.uiuc.edu/~west/openp/univtourn.html Sumner's Universal Tournament Conjecture], Douglas B. West, retrieved 2010-09-17.</ref>
| url = https://archive.org/details/pathsflowsvlsila0000unse/page/17
}}</ref> It is also possible to construct universal graphs for planar graphs that have {{math|''n''<sup>1+''o''(1)</sup>}} vertices.<ref>{{citation
| last1 = Dujmović | first1 = Vida
| last2 = Esperet | first2 = Louis
| last3 = Joret | first3 = Gwenaël
| last4 = Gavoille | first4 = Cyril
| last5 = Micek | first5 = Piotr
| last6 = Morin | first6 = Pat
| arxiv = 2003.04280
| title = Adjacency Labelling for Planar Graphs (And Beyond)
| journal = Journal of the ACM
| year = 2021| volume = 68
| issue = 6
| pages = 1–33
| doi = 10.1145/3477542
}}</ref>
⚫
[[Sumner's conjecture]] states that [[tournament (graph theory)|tournaments]] are universal for [[polytree]]s, in the sense that every tournament with {{math|2''n''&nbsp;&minus;&nbsp;2}} vertices contains every polytree with {{mvar|n}} vertices as a subgraph.<ref>[http://www.math.uiuc.edu/~west/openp/univtourn.html Sumner's Universal Tournament Conjecture], Douglas B. West, retrieved 2010-09-17.</ref>


A family {{mvar|F}} of graphs has a universal graph of polynomial size, containing every {{mvar|n}}-vertex graph as an [[induced subgraph]], if and only if it has an [[implicit graph|adjacency labelling scheme]] in which vertices may be labeled by {{math|''O''(log&nbsp;''n'')}}-bit bitstrings such that an algorithm can determine whether two vertices are adjacent by examining their labels. For, if a universal graph of this type exists, the vertices of any graph in {{mvar|F}} may be labeled by the identities of the corresponding vertices in the universal graph, and conversely if a labeling scheme exists then a universal graph may be constructed having a vertex for every possible label.<ref>{{citation
A family {{mvar|F}} of graphs has a universal graph of polynomial size, containing every {{mvar|n}}-vertex graph as an [[induced subgraph]], if and only if it has an [[implicit graph|adjacency labelling scheme]] in which vertices may be labeled by {{math|''O''(log&nbsp;''n'')}}-bit bitstrings such that an algorithm can determine whether two vertices are adjacent by examining their labels. For, if a universal graph of this type exists, the vertices of any graph in {{mvar|F}} may be labeled by the identities of the corresponding vertices in the universal graph, and conversely if a labeling scheme exists then a universal graph may be constructed having a vertex for every possible label.<ref>{{citation
Line 105: Line 136:
In older mathematical terminology, the phrase "universal graph" was sometimes used to denote a [[complete graph]].
In older mathematical terminology, the phrase "universal graph" was sometimes used to denote a [[complete graph]].


The notion of universal graph has been adapted and used for solving mean payoff games<ref>{{Cite journal|last=Czerwiński|first=Wojciech|last2=Daviaud|first2=Laure|last3=Fijalkow|first3=Nathanaël|last4=Jurdziński|first4=Marcin|last5=Lazić|first5=Ranko|last6=Parys|first6=Paweł|date=2018-07-27|title=Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games|url=http://arxiv.org/abs/1807.10546|journal=arXiv:1807.10546 [cs]}}</ref>.
The notion of universal graph has been adapted and used for solving mean payoff games.<ref>{{cite book|last1=Czerwiński|first1=Wojciech|last2=Daviaud|first2=Laure|last3=Fijalkow|first3=Nathanaël|last4=Jurdziński|first4=Marcin|last5=Lazić|first5=Ranko|last6=Parys|first6=Paweł|date=2018-07-27|title=Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms|chapter=Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games|pages=2333–2349|doi=10.1137/1.9781611975482.142|arxiv=1807.10546|isbn=978-1-61197-548-2|s2cid=51865783}}</ref>


== References ==
== References ==

Latest revision as of 17:36, 25 September 2022

In mathematics, a universal graph is an infinite graph that contains every finite (or at-most-countable) graph as an induced subgraph. A universal graph of this type was first constructed by Richard Rado[1][2] and is now called the Rado graph or random graph. More recent work[3] [4] has focused on universal graphs for a graph family F: that is, an infinite graph belonging to F that contains all finite graphs in F. For instance, the Henson graphs are universal in this sense for the i-clique-free graphs.

A universal graph for a family F of graphs can also refer to a member of a sequence of finite graphs that contains all graphs in F; for instance, every finite tree is a subgraph of a sufficiently large hypercube graph[5] so a hypercube can be said to be a universal graph for trees. However it is not the smallest such graph: it is known that there is a universal graph for n-vertex trees, with only n vertices and O(n log n) edges, and that this is optimal.[6] A construction based on the planar separator theorem can be used to show that n-vertex planar graphs have universal graphs with O(n3/2) edges, and that bounded-degree planar graphs have universal graphs with O(n log n) edges.[7][8][9] It is also possible to construct universal graphs for planar graphs that have n1+o(1) vertices.[10] Sumner's conjecture states that tournaments are universal for polytrees, in the sense that every tournament with 2n − 2 vertices contains every polytree with n vertices as a subgraph.[11]

A family F of graphs has a universal graph of polynomial size, containing every n-vertex graph as an induced subgraph, if and only if it has an adjacency labelling scheme in which vertices may be labeled by O(log n)-bit bitstrings such that an algorithm can determine whether two vertices are adjacent by examining their labels. For, if a universal graph of this type exists, the vertices of any graph in F may be labeled by the identities of the corresponding vertices in the universal graph, and conversely if a labeling scheme exists then a universal graph may be constructed having a vertex for every possible label.[12]

In older mathematical terminology, the phrase "universal graph" was sometimes used to denote a complete graph.

The notion of universal graph has been adapted and used for solving mean payoff games.[13]

References

[edit]
  1. ^ Rado, R. (1964). "Universal graphs and universal functions". Acta Arithmetica. 9 (4): 331–340. doi:10.4064/aa-9-4-331-340. MR 0172268.
  2. ^ Rado, R. (1967). "Universal graphs". A Seminar in Graph Theory. Holt, Rinehart, and Winston. pp. 83–85. MR 0214507.
  3. ^ Goldstern, Martin; Kojman, Menachem (1996). "Universal arrow-free graphs". Acta Mathematica Hungarica. 1973 (4): 319–326. arXiv:math.LO/9409206. doi:10.1007/BF00052907. MR 1428038.
  4. ^ Cherlin, Greg; Shelah, Saharon; Shi, Niandong (1999). "Universal graphs with forbidden subgraphs and algebraic closure". Advances in Applied Mathematics. 22 (4): 454–491. arXiv:math.LO/9809202. doi:10.1006/aama.1998.0641. MR 1683298. S2CID 17529604.
  5. ^ Wu, A. Y. (1985). "Embedding of tree networks into hypercubes". Journal of Parallel and Distributed Computing. 2 (3): 238–249. doi:10.1016/0743-7315(85)90026-7.
  6. ^ Chung, F. R. K.; Graham, R. L. (1983). "On universal graphs for spanning trees" (PDF). Journal of the London Mathematical Society. 27 (2): 203–211. CiteSeerX 10.1.1.108.3415. doi:10.1112/jlms/s2-27.2.203. MR 0692525..
  7. ^ Babai, L.; Chung, F. R. K.; Erdős, P.; Graham, R. L.; Spencer, J. H. (1982). "On graphs which contain all sparse graphs". In Rosa, Alexander; Sabidussi, Gert; Turgeon, Jean (eds.). Theory and practice of combinatorics: a collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday (PDF). Annals of Discrete Mathematics. Vol. 12. pp. 21–26. MR 0806964.
  8. ^ Bhatt, Sandeep N.; Chung, Fan R. K.; Leighton, F. T.; Rosenberg, Arnold L. (1989). "Universal graphs for bounded-degree trees and planar graphs". SIAM Journal on Discrete Mathematics. 2 (2): 145–155. doi:10.1137/0402014. MR 0990447.
  9. ^ Chung, Fan R. K. (1990). "Separator theorems and their applications". In Korte, Bernhard; Lovász, László; Prömel, Hans Jürgen; et al. (eds.). Paths, Flows, and VLSI-Layout. Algorithms and Combinatorics. Vol. 9. Springer-Verlag. pp. 17–34. ISBN 978-0-387-52685-0. MR 1083375.
  10. ^ Dujmović, Vida; Esperet, Louis; Joret, Gwenaël; Gavoille, Cyril; Micek, Piotr; Morin, Pat (2021), "Adjacency Labelling for Planar Graphs (And Beyond)", Journal of the ACM, 68 (6): 1–33, arXiv:2003.04280, doi:10.1145/3477542
  11. ^ Sumner's Universal Tournament Conjecture, Douglas B. West, retrieved 2010-09-17.
  12. ^ Kannan, Sampath; Naor, Moni; Rudich, Steven (1992), "Implicit representation of graphs", SIAM Journal on Discrete Mathematics, 5 (4): 596–603, doi:10.1137/0405049, MR 1186827.
  13. ^ Czerwiński, Wojciech; Daviaud, Laure; Fijalkow, Nathanaël; Jurdziński, Marcin; Lazić, Ranko; Parys, Paweł (2018-07-27). "Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games". Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 2333–2349. arXiv:1807.10546. doi:10.1137/1.9781611975482.142. ISBN 978-1-61197-548-2. S2CID 51865783.
[edit]
Retrieved from "https://en.wikipedia.org/enwiki/w/index.php?title=Universal_graph&oldid=1112303554"