Welcome to Combinatorics and Optimization

Title: Random analogues of Erd\H{o}s-Ko-Rado type results.

Abstract: The classical Erd\H{o}s-Ko-Rado (EKR) theorem and its variants can be translated into characterizing maximum co-cliques of graphs in Association schemes. For instance, the classical Erd\H{o}s-Ko-Rado characterizes maximum co-cliques in the Kneser graph. Given a graph $G$, by $G_{p}$, we denote the random subgraph of $G$ in which edges appear independently, each with a probability $p$. In this talk, we consider the following question: for which probabilities is the independence number of $G_{p}$ equal to that of $G$? Bollabas-Narayanan-Raigorodskii investigated the independence numbers of random subgraphs of the Kneser graph. In this talk, we will investigate the independence numbers of random subgraphs of (i) the derangement graph on permutations; and (ii) the perfect matching graphs. The derangement graph is associated with the EKR type result on permutations and the perfect matching graph is associated with EKR type result on perfect matchings. This is joint work with the members of the PIMS Collaborative Research Group on Movement and Symmetry in graphs.   

Title:Arrangements and Likelihood

Abstract: In this talk, we establish connections between hypersurface arrangements and likelihood geometry. The central object is the likelihood correspondence which captures the dependence between data and critical points of the likelihood function of a statistical model parametrized by the polynomials defining the arrangement. In particle physics, this same object is known as the scattering correspondence. The connection to hypersurface arrangements leads to a new description of the prime ideal of the likelihood correspondence, which is often computationally advantageous. This description is based on the Rees algebra of the likelihood module of the arrangement, a module closely related to the module of logarithmic derivations. We present results for generic and graphic arrangements.

I hope this is fine like this. I do not plan to include a pencil-and-paper activity during the pre-talk, but I would like to show some computations. Is it possible to easily switch between blackboard and projector?

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm,

Title:Faster linear algebra using treewidth

Abstract:

: We look at the complexity of solving sparse linear systems as a function of the treewidth of the instance. That is, the sparse matrix is associated with a sparse graph, and solutions can be found faster when that graph has low treewidth. We give a parameterized algorithm in system size and treewidth achieving the conjectured optimal performance.

This is joint work with Daniel Grier.