Archive for the ‘KAIST Discrete Math Seminar’ Category

« Older Entries
Newer Entries »

Woong Kook, Combinatorial Laplacians and high dimensional tree numbers

Saturday, March 1st, 2014
Combinatorial Laplacians and high dimensional tree numbers
Woong Kook
Seoul National University
2014/05/08 Thursday 4PM-5PM
Room 1409
Combinatorial Laplacians provide important enumeration methods in topological combinatorics. For a finite chain complex \{C_{i},\partial_{i}\}, combinatorial Laplacians \Delta_{i} on C_{i} are defined by

\Delta_{i}=\partial_{i+1}\partial_{i+1}^{t}+\partial_{i}^{t}\partial_{i}\, .

We will review applications of \Delta_{0} in computing the tree numbers for graphs and in solving discrete Laplace equations for networks. In general, the boundary operators \partial_{i} are used to define high-dimensional trees as a generalization of spanning trees for graphs. We will demonstrate an intriguing relation between high-dimensional tree numbers and \det\Delta_{i} for acyclic complexes, based on combinatorial Hodge theory. As an application, a formula for the top-dimensional tree-number of matroid complexes will be derived. If time permits, an important role of combinatorial Laplacians in topological data analysis (TDA) will be briefly discussed.

Tags:
Posted in 2014, KAIST Discrete Math Seminar | Comments Closed

Hiu-Fai Law, F-Matchings in a tree

Friday, February 28th, 2014
F-Matchings in a tree
Hiu-Fai Law
University of Hamburg, Germany
2014/04/28 Monday 4PM-5PM
Room 1409
Given trees F and T, a F-matching is a collection of disjoint copies F in T. Generalizing results from Wagner (2009), Alon et al (2011) proved that the number of F-matchings for fixed F in a random tree T whose size tends to infinity is a.a.s. a multiple of any given integer m>0. We will discuss inverse and extremal problems on the number of F-matchings.

Tags:
Posted in 2014, KAIST Discrete Math Seminar | Comments Closed

Andrew Goodall, Graph polynomials from simple graph sequences

Thursday, February 27th, 2014
Graph polynomials from simple graph sequences
Andrew Goodall
Charles University, Prague
2014/04/14 Monday 4PM-5PM
Room 1409
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.

Tags:
Posted in 2014, KAIST Discrete Math Seminar | Comments Closed

Tomoo Matsumura, Pfaffian Sum formula of the double Schubert polynomials for the symplectic Grassmannians

Wednesday, February 26th, 2014
Pfaffian Sum formula of the double Schubert polynomials for the symplectic Grassmannians
Tomoo Matsumura
KAIST
2014/04/08 Tuesday 4PM-5PM
Room 1409
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.

Tags:
Posted in 2014, KAIST Discrete Math Seminar | Comments Closed

Antoine Vigneron, A conditional lower bound for computing the Gromov hyperbolicity of a discrete metric space

Tuesday, February 25th, 2014
A conditional lower bound for computing the Gromov hyperbolicity of a discrete metric space
Antoine Vigneron
KAUST, Kingdom of Saudi Arabia
2014/03/31 Monday 4PM-5PM
Room 1409
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.

Tags:
Posted in 2014, KAIST Discrete Math Seminar | Comments Closed

« Older Entries
Newer Entries »