Session II.3 - Real-Number Complexity
Friday, June 16, 14:00 ~ 14:30
Geometry and Complexity of Binomial Inequalities in Combinatorics
Greg Blekherman
Georgia Tech, US - This email address is being protected from spambots. You need JavaScript enabled to view it.
Polynomial inequalities between counts of substructures are of central interest in combinatorics. For example, we may be interested in inequalities involving the numbers of bases of a matroid of different ranks, or numbers of certain subgraphs of a graph. Verifying validity of such inequalities for all objects (e.g. all graphs) is often a hard (undecidable) problem. Binomial inequalities are also very important in combinatorics, but they are potentially simpler. In particular, their exponents form a convex cone. This convex cone often has a simple structure, which may lead to better complexity. I will mainly give examples of this phenomenon and state some open problems.
Joint work with Annie Raymond (University of Massachusetts, USA).