BEGIN:VCALENDAR
VERSION:2.0
PRODID:ILLC Website
BEGIN:VEVENT
UID:/NewsandEvents/Events/Upcoming-Events/newsitem
/5072/29-May-2013-General-Mathematics-Colloquium-T
obias-Mueller
DTSTAMP:20130526T000000
SUMMARY:General Mathematics Colloquium, Tobias Mue
ller
ATTENDEE;ROLE=Speaker:Tobias Mueller
DTSTART:20130529T111500
DTEND:20130529T121500
LOCATION:Room C1.112, Science Park 904, Amsterdam
DESCRIPTION:Abstract. Random graphs have been stu
died for over half a century as useful mathematica
l models for networks and as an attractive bit of
mathematics for its own sake. Almost from the very
beginning of random graph theory there has been i
nterest in studying the behaviour of graph propert
ies that can be expressed as sentences in some log
ic, on random graphs. We say that a graph property
is first order expressible if it can be written a
s a logic sentence using the universal and existen
tial quantifiers with variables ranging over the n
odes of the graph, the usual connectives AND, OR,
NOT, parentheses and the relations = and ~, where
x ~ y means that x and y share an edge. For exampl
e, the property that G contains a triangle can be
written as Exists x,y,z : (x ~ y) AND (x ~ z) AND
(y ~ z). First order expressible properties have b
een studied extensively on the oldest and most com
monly studied model of random graphs, the Erdos-Re
nyi model, and by now we have a fairly full descri
ption of the behaviour of first order expressible
properties on this model. I will describe a number
of striking results that have been obtained for t
he Erdos-Renyi model with surprising links to numb
er theory, before describing some of my own work o
n different models of random graphs, including ran
dom planar graphs and the Gilbert model. (based on
joint works with: P. Heinig, S. Haber, M. Noy, A.
Taraz) For more information, see http://www.scie
nce.uva.nl/research/math/Calendar/colloq/
X-ALT-DESC;FMTTYPE=text/html:\n \n
*Abstract*.

\n Random graphs hav
e been studied for over half a century as\n
useful mathematical models for networks and as an
attractive\n bit of mathematics for its ow
n sake. Almost from the very\n beginning of
random graph theory there has been interest in\n
studying the behaviour of graph properties
that can be\n expressed as sentences in som
e logic, on random graphs. We say\n that a
graph property is first order expressible if it ca
n be\n written as a logic sentence using th
e universal and\n existential quantifiers w
ith variables ranging over the nodes\n of t
he graph, the usual connectives AND, OR, NOT, pare
ntheses\n and the relations = and ~, where
x ~ y means that x and y\n share an edge. F
or example, the property that G contains a\n
triangle can be written as Exists x,y,z : (x ~ y
) AND (x ~ z)\n AND (y ~ z). First order ex
pressible properties have been\n studied ex
tensively on the oldest and most commonly studied\
n model of random graphs, the Erdos-Renyi m
odel, and by now we\n have a fairly full de
scription of the behaviour of first order\n
expressible properties on this model. I will desc
ribe a number\n of striking results that ha
ve been obtained for the\n Erdos-Renyi mode
l with surprising links to number theory,\n
before describing some of my own work on differen
t models of\n random graphs, including rand
om planar graphs and the Gilbert\n model. (
based on joint works with: P. Heinig, S. Haber,\n
M. Noy, A. Taraz)

\n \n For mo
re information, see\n http://www.science.uva.nl/research/mat
h/Calendar/colloq/\n
URL:/NewsandEvents/Events/Upcoming-Events/newsitem
/5072/29-May-2013-General-Mathematics-Colloquium-T
obias-Mueller
END:VEVENT
END:VCALENDAR