Universality for and in Induced-Hereditary Graph Properties

Izak Broere; Johannes Heidema

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 1, page 33-47
  • ISSN: 2083-5892

Abstract

top
The well-known Rado graph R is universal in the set of all countable graphs I, since every countable graph is an induced subgraph of R. We study universality in I and, using R, show the existence of 2 א0 pairwise non-isomorphic graphs which are universal in I and denumerably many other universal graphs in I with prescribed attributes. Then we contrast universality for and universality in induced-hereditary properties of graphs and show that the overwhelming majority of induced-hereditary properties contain no universal graphs. This is made precise by showing that there are 2(2א0 ) properties in the lattice K ≤ of induced-hereditary properties of which only at most 2א0 contain universal graphs. In a final section we discuss the outlook on future work; in particular the question of characterizing those induced-hereditary properties for which there is a universal graph in the property.

How to cite

top

Izak Broere, and Johannes Heidema. "Universality for and in Induced-Hereditary Graph Properties." Discussiones Mathematicae Graph Theory 33.1 (2013): 33-47. <http://eudml.org/doc/267920>.

@article{IzakBroere2013,
abstract = {The well-known Rado graph R is universal in the set of all countable graphs I, since every countable graph is an induced subgraph of R. We study universality in I and, using R, show the existence of 2 א0 pairwise non-isomorphic graphs which are universal in I and denumerably many other universal graphs in I with prescribed attributes. Then we contrast universality for and universality in induced-hereditary properties of graphs and show that the overwhelming majority of induced-hereditary properties contain no universal graphs. This is made precise by showing that there are 2(2א0 ) properties in the lattice K ≤ of induced-hereditary properties of which only at most 2א0 contain universal graphs. In a final section we discuss the outlook on future work; in particular the question of characterizing those induced-hereditary properties for which there is a universal graph in the property.},
author = {Izak Broere, Johannes Heidema},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {countable graph; universal graph; induced-hereditary property},
language = {eng},
number = {1},
pages = {33-47},
title = {Universality for and in Induced-Hereditary Graph Properties},
url = {http://eudml.org/doc/267920},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Izak Broere
AU - Johannes Heidema
TI - Universality for and in Induced-Hereditary Graph Properties
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 1
SP - 33
EP - 47
AB - The well-known Rado graph R is universal in the set of all countable graphs I, since every countable graph is an induced subgraph of R. We study universality in I and, using R, show the existence of 2 א0 pairwise non-isomorphic graphs which are universal in I and denumerably many other universal graphs in I with prescribed attributes. Then we contrast universality for and universality in induced-hereditary properties of graphs and show that the overwhelming majority of induced-hereditary properties contain no universal graphs. This is made precise by showing that there are 2(2א0 ) properties in the lattice K ≤ of induced-hereditary properties of which only at most 2א0 contain universal graphs. In a final section we discuss the outlook on future work; in particular the question of characterizing those induced-hereditary properties for which there is a universal graph in the property.
LA - eng
KW - countable graph; universal graph; induced-hereditary property
UR - http://eudml.org/doc/267920
ER -

References

top
  1. [1] M. Borowiecki, I. Broere, M. Frick, G. Semanišin and P. Mihók, A survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50. doi:10.7151/dmgt.1037[Crossref] Zbl0902.05026
  2. [2] I. Broere and J. Heidema, Constructing an abundance of Rado graphs, Util. Math. 84 (2011) 139-152. Zbl1228.05220
  3. [3] I. Broere and J. Heidema, Some universal directed labelled graphs, Util. Math. 84 (2011) 311-324. Zbl1228.05250
  4. [4] I. Broere and J. Heidema, Universal H-colourable graphs, accepted for publication in Graphs Combin. doi:10.1007/s00373-012-1216-5[Crossref] Zbl1272.05136
  5. [5] I. Broere and J. Heidema, Induced-hereditary graph properties, homogeneity, extensibility and universality, accepted for publication in J. Combin. Math. Combin. Comput. Zbl1274.05400
  6. [6] I. Broere, J. Heidema and P. Mihók, Constructing universal graphs for inducedhereditary graph properties, accepted for publication in Math. Slovaca. Zbl1324.05135
  7. [7] I. Broere, J. Heidema and P. Mihók, Universality in graph properties with degree restrictions, accepted for publication in Discuss. Math. Graph Theory. Zbl1274.05334
  8. [8] P.J. Cameron, The random graph revisited, http://www.math.uni-bielefeld.de/rehmann/ECM/cdrom/3ecm/pdfs/pant3/camer.pdf Zbl1023.05124
  9. [9] G. Cherlin and P. Komjáth, There is no universal countable pentagon-free graph, J. Graph Theory 18 (1994) 337-341. doi:10.1002/jgt.3190180405[Crossref] Zbl0805.05044
  10. [10] G. Cherlin, S. Shelah and N. Shi, Universal graphs with forbidden subgraphs and algebraic closure, Adv. Appl. Math. 22 (1999) 454-491. doi:10.1006/aama.1998.0641[Crossref] Zbl0928.03049
  11. [11] G. Cherlin and N. Shi, Graphs omitting a finite set of cycles, J. Graph Theory 21 (1996) 351-355. doi:10.1002/(SICI)1097-0118(199603)21:3h351::AID-JGT11i3.0.CO;2-K[Crossref] Zbl0845.05060
  12. [12] M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas, The strong perfect graph theorem, Ann. Math. 164 (2006) 51-229. doi:10.4007/annals.2006.164.51[Crossref] Zbl1112.05042
  13. [13] B.A. Davey and H.A. Priestly, Introduction to Lattices and Order, Second Edition, (Cambridge University Press, New York, 2008). 
  14. [14] R. Diestel, Graph Theory, Fourth Edition, Graduate Texts in Mathematics, 173, (Springer, Heidelberg, 2010). 
  15. [15] R. Fraïssé, Sur l’extension aux relations de quelques propriétiés connues des ordres, C. R. Acad. Sci. Paris 237 (1953) 508-510. Zbl0053.02904
  16. [16] A. Hajnal and J. Pach, Monochromatic paths in infinite coloured graphs, in: Colloquia Mathematica Societatis J´anos Bolyai 37, Finite and infinite sets, Eger (Hungary) (1981), 359-369. 
  17. [17] C.W. Henson, A family of countable homogeneous graphs Pacific J. Math. 38 (1971) 69-83. doi:10.2140/pjm.1971.38.69[Crossref] 
  18. [18] P. Komjáth and J. Pach, Universal graphs without large bipartite subgraphs, Mathematika 31 (1984) 282-290. doi:10.1112/S002557930001250X[Crossref] Zbl0551.05057
  19. [19] F.R. Madelaine, Universal structures and the logic of forbidden patterns, Log. Methods Comput. Sci. 5 (2:13) (2009) 1-25. doi:10.2168/LMCS-5(2:13)2009[Crossref][WoS] 
  20. [20] P. Mihók, J. Miškuf and G. Semanišin, On universal graphs for hom-properties, Discuss. Math. Graph Theory 29 (2009) 401-409. doi:10.7151/dmgt.1455[Crossref] Zbl1194.05041
  21. [21] R. Rado, Universal graphs and universal functions, Acta Arith. 9 (1964) 331-340. Zbl0139.17303

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.