Tropicalizing the Graph Profile of Some Almost-Stars
Maria Dascălu, Annie Raymond · SIAM Journal on Discrete Mathematics · 2024
Abstract. Many important problems in extremal combinatorics can be stated as certifying polynomial inequalities in graph homomorphism numbers, and in particular, many ask to certify pure binomial inequalities. For a fixed collection of graphs [Formula: see text], the tropicalization of the graph profile of [Formula: see text] essentially records all valid pure binomial inequalities involving graph homomorphism numbers for graphs in [Formula: see text]. Building upon ideas and techniques described by Blekherman and Raymond in 2022, we compute the tropicalization of the graph profile for the graph containing a single vertex as well as stars where one edge is subdivided. This allows pure binomial inequalities in homomorphism numbers (or densities) for these graphs to be verified through an explicit linear program where the number of variables is equal to the number of edges in the biggest graph involved.