BEGIN:VCALENDAR VERSION:2.0 PRODID:ILLC Website X-WR-TIMEZONE:Europe/Amsterdam BEGIN:VTIMEZONE TZID:Europe/Amsterdam X-LIC-LOCATION:Europe/Amsterdam BEGIN:DAYLIGHT TZOFFSETFROM:+0100 TZOFFSETTO:+0200 TZNAME:CEST DTSTART:19700329T020000 RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU END:DAYLIGHT BEGIN:STANDARD TZOFFSETFROM:+0200 TZOFFSETTO:+0100 TZNAME:CET DTSTART:19701025T030000 RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU END:STANDARD END:VTIMEZONE BEGIN:VEVENT UID:/NewsandEvents/Archives/2013/newsitem/5072/29- May-2013-General-Mathematics-Colloquium-Tobias-Mue ller DTSTAMP:20130526T000000 SUMMARY:General Mathematics Colloquium, Tobias Mue ller ATTENDEE;ROLE=Speaker:Tobias Mueller DTSTART;TZID=Europe/Amsterdam:20130529T111500 DTEND;TZID=Europe/Amsterdam: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)