Events - 2019

Title: Graph covers with two new eigenvalues

Abstract:

I am going to talk about graph covers. If $Y$ is a cyclic cover of $X$, it turns out that $Y$ has the same spectrum as $X$ plus (possibly) some new eigenvalues. 

Title: Inverses of Trees

Abstract:

A tree is invertible if and only if it has a perfect matching.

Godsil considers an invertible tree T and finds that the inverse of the adjacency matrix has entries in {0, ±1} and is the signed adjacency matrix of a graph which contains T.

Title: Incompressibility of classical distributions

Abstract:

We prove a general, robust, single-letter lower bound on the achievable rate for ensembles of classical states, which holds even when Alice and Bob share free entanglement and allow a constant local error. 

Title: Disjunctive Cuts through the V-Polyhedral Lens

Abstract:

Cutting planes, or cuts, are a critical component of modern integer programming solvers, but existing cuts implemented in solvers are relatively simple compared to those in the literature. We discuss the primary reasons for this disparity, as well as our recently-proposed V-polyhedral framework for mitigating some of these difficulties encountered by prior "stronger" cuts.

Title: Kummer's Theorem on binomial coefficients, etc.

Abstract: 

Some of us like the primes and call ourselves pure mathematicians. Some of us like the Catalan numbers and call ourselves combinatorialists.

Title: A deterministic (1/2 + epsilon)-approximation for submodular maximizztion over a matroid

Abstract:

In 1978, it was shown that a natural greedy algorithm gives a 1/2 approximation to submodular maximization subject to a matroid constraint.

Title: From weakly separated collections to matroid subdivisions

Abstract:

We study arrangements of slightly skewed tropical hyperplanes, called blades, on the vertices of a hypersimplex $\Delta_{k,n}$.

Title: Counting Pentagons in Triangle-free Binary Matroids

Abstract:

Every triangle-free graph with n vertices contains at most (n/5)^5 cycles of length five, and this value is attained by the balanced blowup of the 5-cycle.

Title: Cospectral and strongly cospectral vertices

Abstract:

If $a$ is a vertex in a graph with adjacency matrix $A$, the \textsl{walk module} generated by $a$ is the $A$-invariant subspace spanned by the vectors $A^re_a$, for $r\ge0$.

Title: Maximizing non-monotone submodular functions

Abstract:

Optimization of non-monotone submodular functions has applications in the maximum cut and maximum directed cut problems for graphs.

Title: Interpolated versions of the Central Limit Theorem, and crossings of pair-partitions

Abstract:

Title: Cutting a square into triangles of equal area

Abstract:

Suppose you are given a square and asked to cut it into n triangles of equal area. If n is even the problem is almost trivial, but when n is odd the problem becomes much harder.