February 27th, 2014
Graph polynomials from simple graph sequences
2014/04/14 Monday 4PM-5PM
The chromatic polynomial evaluated at a positive integer n is equal to the number of homomorphisms to the complete graph on n vertices. Many important graph polynomials are likewise determined by counting homomorphisms to a sequence of (multi) graphs, such as the Tutte polynomial and the independence polynomial. We give a powerful construction that produces graph polynomials in this way from sequences of simple graphs. It uses just two fundamental operations (disjoint union and interpretations of relational structures) and starts from a simple set of building blocks (coloured transitive tournaments).This will be illustrated by many examples, some of whose combinatorial properties have been well explored (such as that of the chromatic polynomial), but most of which are new. This is joint work with Jarik Nesetril and Patrice Ossona de Mendez.
February 26th, 2014
Pfaffian Sum formula of the double Schubert polynomials for the symplectic Grassmannians
2014/04/07 Monday 4PM-5PM
It is well-known that the ring of symmetric polynomials has a special basis, consisting of Schur polynomials and being indexed by Young diagrams. There underlies the representation theory of general linear groups and the combinatorics of Young diagrams. The geometry behind it is the geometry of Schubert varieties of Grassmannians of subspaces in a complex vector space. If we change the geometric setup to the case of Grassmannians of isotropic subspaces of a symplectic vector space, we have analogous functions called Schur Q-functions and their slight generalization. I will explain an explicit closed formula to express those functions as sums of Pfaffians and also the geometry and combinatorics behind it. If time allows, I will mention the technique of how we obtained the formula, that involves the so-called divided difference operators. This is a joint work with Takeshi Ikeda.
February 25th, 2014
A conditional lower bound for computing the Gromov hyperbolicity of a discrete metric space
2014/03/31 Monday 4PM-5PM
We show that the Gromov hyperbolicity of a discrete metric space at a fixed base-point cannot be computed in O(n2.05) time, unless there exists a faster algorithm for (max,min) matrix multiplication algorithm than is currently known.
February 25th, 2014
FYI (CS Colloquium)
The Evolution of the Multivariate Revolution
2014/03/24 Mon 4PM – 5:30PM
E3-1 CS Bldg. Room 1501
There has been underway for some decades, with considerable practical consequences, a multivariate revolution in the design of algorithms and the assessment of computational complexity. Parameterized complexity has brought this shift into focus, naming the issues, and offering a multivariate mathematical framework for the central questions that confront the challenge of designing effective algorithms for intrinsically difficult computational problems. Iinternally to this new scientific direction of the central enabling scientific discipline of our time: algorithmics — who lacks a new flood of data? — is a story about how this multivariate revolution has evolved and is still unfolding. The talk will tell the story, in an entertaining way, accessible to students in any field of science that computing serves.
February 24th, 2014
Centrally symmetric polytopes with many faces
2014/03/17 Monday 4PM-5PM
We study the convex hull of the symmetric moment curve Uk(t)=(cost, sint, cos3t, sin3t, …., cos(2k-1)t, sin(2k-1)t) in R2k and provide deterministic constructions of centrally symmetric polytopes with a record high number faces. In particular, we prove the local neighborliness of the symmetric moment curve, meaning that as long as k distinct points t1, …, tk lie in an arc of a certain length φk > π/2, the points Ut1, …, Utk span a face of the convex hull of Uk(t). In this talk, I will use the local neighborliness of the symmetric moment curve to construct d-dimensional centrally symmetric 2-neighborly polytopes with approximately 3d/2 vertices. This is joint work with Alexander Barvinok and Isabella Novik.