Search for: All records

We prove that the tropical surface of the root system A_{n−1} has degree n(n − 1)(n − 2)/2. 

We prove that the number of tropical critical points of an affine matroid (M,e) is equal to the beta invariant of M. Motivated by the computation of maximum likelihood degrees, this number is defined to be the degree of the intersection of the Bergman fan of (M,e) and the inverted Bergman fan of N=(M/e)*, where e is an element of M that is neither a loop nor a coloop. Equivalently, for a generic weight vector w on E-e, this is the number of ways to find weights (0,x) on M and y on N with x+y=w such that on each circuit of M (resp. N), the minimum x-weight (resp. y-weight) occurs at least twice. This answers a question of Sturmfels. 

Chow rings of toric varieties, which originate in intersection theory, feature a rich combinatorial structure of independent interest. We survey four different ways of computing in these rings, due to Billera, Brion, Fulton–Sturmfels, and Allermann–Rau. We illustrate the beauty and power of these methods by giving four proofs of Huh and Huh–Katz’s formula μ_k(M) = deg_M(α^{r−k}β^k) for the coefficients of the reduced characteristic polynomial of a matroid M as the mixed intersection numbers of the hyperplane and reciprocal hyperplane classes α and β in the Chow ring of M. Each of these proofs sheds light on a different aspect of matroid combinatorics, and provides a framework for further developments in the intersection theory of matroids. Our presentation is combinatorial, and does not assume previous knowledge of toric varieties, Chow rings, or intersection theory. This survey was prepared for the Clay Lecture to be delivered at the 2024 British Combinatorics Conference. 

The theory of matroids or combinatorial geometries originated in linear algebra and graph theory, and has deep connections with many other areas, including field theory, matching theory, submodular optimization, Lie combinatorics, and total positivity. Matroids capture the combinatorial essence that these different settings share. In recent years, the (classical, polyhedral, algebraic, and tropical) geometric roots of the field have grown much deeper, bearing new fruits. We survey some recent successes, stemming from three geometric models of a matroid: the matroid polytope, the Bergman fan, and the conormal fan. 

Generalized permutahedra are polytopes that arise in combinatorics, algebraic geometry, representation theory, topology, and optimization. They possess a rich combinatorial structure. Out of this structure we build a Hopf monoid in the category of species. Species provide a unifying framework for organizing families of combinatorial objects. Many species carry a Hopf monoid structure and are related to generalized permutahedra by means of morphisms of Hopf monoids. This includes the species of graphs, matroids, posets, set partitions, linear graphs, hypergraphs, simplicial complexes, and building sets, among others. We employ this algebraic structure to define and study polynomial invariants of the various combinatorial structures. We pay special attention to the antipode of each Hopf monoid. This map is central to the structure of a Hopf monoid, and it interacts well with its characters and polynomial invariants. It also carries information on the values of the invariants on negative integers. For our Hopf monoid of generalized permutahedra, we show that the antipode maps each polytope to the alternating sum of its faces. This fact has numerous combinatorial consequences. We highlight some main applications: We obtain uniform proofs of numerous old and new results about the Hopf algebraic and combinatorial structures of these families. In particular, we give optimal formulas for the antipode of graphs, posets, matroids, hypergraphs, and building sets. They are optimal in the sense that they provide explicit descriptions for the integers entering in the expansion of the antipode, after all coefficients have been collected and all cancellations have been taken into account. We show that reciprocity theorems of Stanley and Billera–Jia–Reiner (BJR) on chromatic polynomials of graphs, order polynomials of posets, and BJR-polynomials of matroids are instances of one such result for generalized permutahedra. We explain why the formulas for the multiplicative and compositional inverses of power series are governed by the face structure of permutahedra and associahedra, respectively, providing an answer to a question of Loday. We answer a question of Humpert and Martin on certain invariants of graphs and another of Rota on a certain class of submodular functions. We hope our work serves as a quick introduction to the theory of Hopf monoids in species, particularly to the reader interested in combinatorial applications. It may be supplemented with Marcelo Aguiar and Swapneel Mahajan’s 2010 and 2013 works, which provide longer accounts with a more algebraic focus. 

Muchos llegamos a la ciencia desde la curiosidad, en búsqueda del entendimiento y de la belleza. Con el tiempo descubrimos que la ciencia es una herramienta tremendamente poderosa. El posible éxito y aplicabilidad de nuestro proyecto científico nos enfrentan a preguntas éticas que no podemos ignorar. En una sociedad profundamente desigual, ¿quién tiene acceso a las tecnologías que puedan resultar? ¿Quién se beneficia y quién se perjudica? ¿Cuál es nuestra responsabilidad como científicxs e ingenierxs? ¿Qué papel jugamos en la construcción de una sociedad más justa y equitativa? Esta es la reflexión de un investigador cuyo trabajo en matemática “pura” encontró aplicaciones inesperadas. 

We introduce the conormal fan of a matroid M \operatorname {M} , which is a Lagrangian analog of the Bergman fan of M \operatorname {M} . We use the conormal fan to give a Lagrangian interpretation of the Chern–Schwartz–MacPherson cycle of M \operatorname {M} . This allows us to express the h h -vector of the broken circuit complex of M \operatorname {M} in terms of the intersection theory of the conormal fan of M \operatorname {M} . We also develop general tools for tropical Hodge theory to prove that the conormal fan satisfies Poincaré duality, the hard Lefschetz theorem, and the Hodge–Riemann relations. The Lagrangian interpretation of the Chern–Schwartz–MacPherson cycle of M \operatorname {M} , when combined with the Hodge–Riemann relations for the conormal fan of M \operatorname {M} , implies Brylawski’s and Dawson’s conjectures that the h h -vectors of the broken circuit complex and the independence complex of M \operatorname {M} are log-concave sequences. 

We prove that the maximum likelihood degree of a matroid M equals its beta invariant β(M). For an element e of M that is neither a loop nor a coloop, this is defined to be the degree of the intersection of the Bergman fan of (M,e) and the inverted Bergman fan of N = (M/e)^⊥. Equivalently, for a generic vector w ∈ R^E−e, this is the number of ways to find weights (0, x) on M and y on N with x + y = w such that on each circuit of M (resp. N), the minimum x-weight (resp. y-weight) occurs at least twice.