Archive of posts with tag 'TobiasMuller'

• Tobias Müller, First Order Logic and Random (Geometric) Graphs

  First Order Logic and Random (Geometric) Graphs

  Tobias Müller
  Mathematical Institute, Utrecht University, Utrecht, The Netherlands

  2012/8/16 Thu 4PM-5PM (Room 3433, Bldg. E6-1)

  We say that a graph property is first order expressible if it can be written as a logic sentence using the universal and existential quantifiers with variables ranging over the nodes 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 example, the property that G contains a triangle can be written as
  Exists x,y,z : (x ~ y) AND (x ~ z) AND (y ~ z).</p>

  Starting from the sixties, first order expressible properties have been studied extensively on the most commonly studied model of random graphs, the Erdos-Renyi model. A number of very attractive and surprising results have been obtained, and by now we have a fairly full description of the behaviour of first order expressible properties on this model.
  The Gilbert model of random graphs is obtained as follows. We take n points uniformly at random from the d-dimensional unit torus, and join two points by an edge if and only their distance is at most r.
  In this talk I will discuss joint work with S. Haber which tells a nearly complete story on first order expressible properties of the Gilbert random graph model. In particular we settle several conjectures of McColm and of Agarwal-Spencer.
  (Joint with S. Haber)

  Tags:

  • TobiasMuller