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