Seminars in August 2012

  • 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:

  • Luis Serrano, The down operator and expansions of near rectangular k-Schur functions
    The down operator and expansions of near rectangular k-Schur functions
    Luis Serrano
    Department of Mathematics, Université du Québec à Montréal, Montreal, Quebec, Canada
    2012/8/7 Tue 4PM-5PM
    We prove that the Lam-Shimozono “down operator” on the affine Weyl group induces a derivation of the affine Fomin-Stanley subalgebra of the affine nilCoxeter algebra. We use this to verify a conjecture of Berg, Bergeron, Pon and Zabrocki describing the expansion of k-Schur functions of “near rectangles” in the affine nilCoxeter algebra. Consequently, we obtain a combinatorial interpretation of the corresponding k-Littlewood–Richardson coefficients. This can be found in arxiv:1112.4460 and arxiv:1112.4460.
    Tags:

Monthly Archives