2024 Workshop on (Mostly) Matroids

Complexity of log-concave inequalities in matroids

22 Aug 2024, 09:45

25m

S236 (IBS Science Culture Center)

Presentation (25 min)

Speaker

Swee Hong Chan (Rutgers University)

Description

A sequence of nonnegative real numbers $a_1,a_2,\dots ,a_n$, is log-concave if $a_i^2\ge a_{i-1}{a}_{i+1}$ for all $i$ ranging from 2 to $n-1$. Log-concavity naturally arises in various aspects of mathematics, each characterized by different underlying mechanisms. Examples range from inequalities that are readily provable, such as the binomial coefficients $a_i=(\genfrac{}{}{0ex}{}{n}{i})$, to intricate inequalities that have taken decades to resolve, such as the number of independent sets $a_i$ in a matroid $M$ with $i$ elements (otherwise known as Mason's conjecture). It is then natural to ask if it can be shown that the latter type of inequalities is intrinsically more challenging than the former. In this talk, we provide a rigorous framework to answer this type of questions, by employing a combination of combinatorics, complexity theory, and geometry. This is joint work with Igor Pak and is intended for a general audience.