Editing Universal graph

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
  | last1 = Rado | first1=R. | authorlink1=Richard Rado
  | title = Universal graphs and universal functions
  | journal = Acta Arithmetica
  | volume = 9
  | issue = 4
  | year = 1964
  | pages = 331–340
  | mr = 0172268
  | doi=10.4064/aa-9-4-331-340| doi-access = free
  }}</ref><ref>{{cite conference
  | last1 = Rado | first1=R. | authorlink1=Richard Rado
  | title = Universal graphs
  | date = 1967
  | book-title = A Seminar in Graph Theory
  | publisher = Holt, Rinehart, and Winston
  | pages = 83–85
  | mr = 0214507}}</ref> and is now called the [[Rado graph]] or  random graph.  More recent work<ref>{{cite journal
  |author1=Goldstern, Martin |author2=Kojman, Menachem | title = Universal arrow-free graphs
  | year = 1996
  | journal = [[Acta Mathematica Hungarica]]
  | volume = 1973
  | pages = 319–326
  | doi = 10.1007/BF00052907 | doi-access = free
  | arxiv = math.LO/9409206
  | mr = 1428038
  | issue = 4}}</ref>
<ref>{{cite journal 
  | last1=Cherlin | first1=Greg
  | 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
  | volume = 22
  | year = 1999 
  | pages = 454–491
  | doi =  10.1006/aama.1998.0641 
  | arxiv = math.LO/9809202
  | mr = 1683298
  | issue = 4|s2cid=17529604 }}</ref>
has focused on universal graphs for a graph family {{mvar|F}}: that is, an infinite graph belonging to {{mvar|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.

[[File:Infinite path.svg|thumb|350px|An infinite path is a universal graph for the family of path graphs.]]

A universal graph for a family {{mvar|F}} of graphs can also refer to a member of a sequence of finite graphs that contains all graphs in {{mvar|F}}; for instance, every finite tree is a subgraph of a sufficiently large [[hypercube graph]]<ref>
{{cite journal
  | author = Wu, A. Y.
  | title = Embedding of tree networks into hypercubes
  | journal = Journal of Parallel and Distributed Computing
  | volume = 2
  | year = 1985
  | pages = 238–249
  | doi = 10.1016/0743-7315(85)90026-7
  | 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|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
 | last2 = Chung | first2 = F. R. K. | author2-link = Fan Chung
 | last3 = Erdős | first3 = P. | author3-link = Paul Erdős
 | last4 = Graham | first4 = R. L. | author4-link = Ronald Graham
 | last5 = Spencer | first5 = J. H. | author5-link = Joel Spencer
 | contribution = On graphs which contain all sparse graphs
 | editor1-last = Rosa | editor1-first = Alexander
 | editor2-last = Sabidussi | editor2-first = Gert
 | editor3-last = Turgeon | editor3-first = Jean
 | pages = 21–26
 | series = Annals of Discrete Mathematics
 | title = Theory and practice of combinatorics: a collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday
 | url = http://renyi.hu/~p_erdos/1982-12.pdf
 | volume = 12
 | year = 1982
 | mr = 0806964}}</ref><ref>{{Cite journal
 | last1 = Bhatt | first1 = Sandeep N.
 | last2 = Chung | first2 = Fan R. K. | author2-link = Fan Chung
 | last3 = Leighton | first3 = F. T. | author3-link = F. Thomson Leighton
 | last4 = Rosenberg | first4 = Arnold L. | author4-link = Arnold L. Rosenberg
 | doi = 10.1137/0402014
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | pages = 145–155
 | title = Universal graphs for bounded-degree trees and planar graphs
 | volume = 2
 | year = 1989
 | issue = 2
 | mr = 0990447}}</ref><ref>{{Cite book
 | last = Chung
 | first = Fan R. K.
 | author-link = Fan Chung
 | contribution = Separator theorems and their applications
 | editor1-last = Korte
 | editor1-first = Bernhard
 | editor1-link = Bernhard Korte
 | editor2-last = Lovász
 | editor2-first = László
 | editor2-link = László Lovász
 | editor3-last = Prömel
 | editor3-first = Hans Jürgen
 | editor4-last = Schrijver
 | editor4-first = Alexander
 | display-editors = 3
 | isbn = 978-0-387-52685-0
 | pages = [https://archive.org/details/pathsflowsvlsila0000unse/page/17 17–34]
 | publisher = Springer-Verlag
 | series = Algorithms and Combinatorics
 | title = Paths, Flows, and VLSI-Layout
 | volume = 9
 | year = 1990
 | mr = 1083375
 | 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
 | last1 = Kannan | first1 = Sampath
 | last2 = Naor | first2 = Moni | author2-link = Moni Naor
 | last3 = Rudich | first3 = Steven | author3-link = Steven Rudich
 | doi = 10.1137/0405049
 | issue = 4
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | mr = 1186827
 | pages = 596–603
 | title = Implicit representation of graphs
 | volume = 5
 | year = 1992}}.</ref>

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 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 ==
{{reflist}}

==External links==
*[http://www.theoremoftheday.org/CombinatorialTheory/Panarboreal/TotDPanarboreal.pdf The panarborial formula], "Theorem of the Day" concerning universal graphs for trees

{{DEFAULTSORT:Universal Graph}}
[[Category:Graph families]]
[[Category:Infinite graphs]]