Tutte seminar - Bert Gerards

On the structure of binary matroids

Abstract:

Given a separable strongly self-concordant function $f:\R^n \rightarrow \R$, we show the associated spectral function $F(X)= (f \circ \lambda)(X)$ is also strongly self-concordant function. In addition, there is a universal constant $\mathcal{O}$ such that, if $f(x)$ is separable self-concordant barrier then $\mathcal{O}^2F(X)$ is a self-concordant barrier. We estimate that for the universal constant we have $\mathcal{O} \le 22$. This generalizes the relationship between the standard logarithmic barriers $-\sum_{i=1}^n\log x_i$ and $-\log \det X$ and gives a partial solution to a conjecture of L. Tunçel.

This is a joint work with Javier Peña, Carnegie Mellon University.