🚀 go-pugleaf

Lecture Series ``Collegium Logicum''
Kurt Goedel Society
University of Technology, Vienna, Austria


Lecture Announcement
--------------------

PETER KOMJATH
=============
E\"otv\"os University, Budapest

		
Universal Graphs
----------------
Monday, October 17, 1993, 16:45}


ABSTRACT:

If $\cal H$ is a class of graphs then we say that $G\in \cal H$ is 
{\sl universal} in $\cal H$ if every graph in $\cal H$ is isomorphic 
to a(n induced) subgraph of $G$. 
Several results have been proved for various classes on the 
existence/nonexistence of universal graphs. 
The first cases were the class of countable graphs (exists, R.~Rado) 
and the class of locally finite countable graphs (it does not, N.~G.~
de Bruijn). 
Much later  it was shown that there is no universal countable graph 
omitting $C_4$ (the circuit of length 4, J.~Pach) and that was later 
extended to some other classes by  G.~Cherlin, M.~Goldstern, M.~Kojman,
A.~Mekler,  J.~Pach, and the lecturer. 

A folklore result shows that there is no universal graph among 
the graphs of cardinal $\lambda$ which omit $K(\omega)$, the 
complete graph of $\omega$ vertices ($\lambda$ is any 
infinite cardinal). 
With  S.~Shelah we characterized when this holds for omitting 
$K(\kappa)$ in general, under GCH. 
We also gave forcing models showing that if $\kappa>\omega$ 
is a regular cardinal, GCH holds below $\kappa$ but $2^\kappa$ 
is large then the minimal number of graphs of cardinal 
$\kappa$ which omit $K(\omega_1)$ but embed every other 
graph with these properties can be as small as $\kappa^+$ 
and as large as $2^\kappa$.


PLACE:

Seminarraum SEM 181A, Institut fuer Informationssysteme,
Paniglgasse 16, 1. Stock, 1040 Wien.


PETER KOMJATH was born in Budapest, Hungary, in 1953. 
He graduated from the E\"otv\"os University in 1976. 
Earned his ''Candidate'' degree in 1984 with a thesis written 
under the supervision of A.Hajnal. 
Received the Doctor of Sci.Degree from the Hungarian Academy of 
Sciences in 1989. 
He has been with the E\"otv\"os University ever since his graduation, 
between 1976 and 1984 at the Department of Algebra and Number Theory, 
and at the Department of Computer Science since then. 
He is a full professor since 1990 and head of the 
Department of Computer Science since July, 1994. 
He made three longer and several shorter visits to the U.S., Canada, 
and Israel. 
He published about 50 papers in infinitary combinatorics, 
real analysis, and axiomatic set theory. 

------------------------
Kurt-Goedel-Gesellschaft
Technische Universitaet Wien
Institut fuer Computersprachen E185.2
Resselgasse 3/1, A-1040 Wien

Tel: (+43 1) 588 01/4088
Fax: (+43 1) 504 15 89
email: kgs@logic.tuwien.ac.at

Mit Unterstuetzung des
Bundesministeriums fuer Wissenschaft und Forschung