More Like this

1. Hopf Monoids and Generalized Permutahedra

   https://doi.org/10.1090/memo/1437  

   Aguiar, Marcelo ; Ardila, Federico ( September 2023 , Memoirs of the American Mathematical Society)

   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.

    

   more » « less
2. Determinant Maximization via Matroid Intersection Algorithms

   Brown, A ; Laddha, A. ; Pittu, M. ; Singh, M. ; Tetali, P. ( October 2022 , Annual Symposium on Foundations of Computer Science)

   Determinant maximization problem gives a general framework that models problems arising in as diverse fields as statistics [Puk06], convex geometry [Kha96], fair allocations [AGSS16], combinatorics [AGV18], spectral graph theory [NST19a], network design, and random processes [KT12]. In an instance of a determinant maximization problem, we are given a collection of vectors U = {v1, . . . , vn} ⊂ Rd , and a goal is to pick a subset S ⊆ U of given vectors to maximize the determinant of the matrix ∑i∈S vivi^T. Often, the set S of picked vectors must satisfy additional combinatorial constraints such as cardinality constraint (|S| ≤ k) or matroid constraint (S is a basis of a matroid defined on the vectors). In this paper, we give a polynomial-time deterministic algorithm that returns a r O(r)-approximation for any matroid of rank r ≤ d. This improves previous results that give e O(r^2)-approximation algorithms relying on e^O(r)-approximate estimation algorithms [NS16, AG17,AGV18, MNST20] for any r ≤ d. All previous results use convex relaxations and their relationship to stable polynomials and strongly log-concave polynomials. In contrast, our algorithm builds on combinatorial algorithms for matroid intersection, which iteratively improve any solution by finding an alternating negative cycle in the exchange graph defined by the matroids. While the det(.) function is not linear, we show that taking appropriate linear approximations at each iteration suffice to give the improved approximation algorithm. 

   more » « less
3. Algorithmic Thresholds for Refuting Random Polynomial Systems

   https://doi.org/10.1137/1.9781611977073.49  

   Hsieh, Tim ; Kothari, Pravesh K. ( January 2022 , Proceedings of the annual ACMSIAM symposium on discrete algorithms)

   Consider a system of m polynomial equations {pi(x)=bi}i≤m of degree D≥2 in n-dimensional variable x∈ℝn such that each coefficient of every pi and bis are chosen at random and independently from some continuous distribution. We study the basic question of determining the smallest m -- the algorithmic threshold -- for which efficient algorithms can find refutations (i.e. certificates of unsatisfiability) for such systems. This setting generalizes problems such as refuting random SAT instances, low-rank matrix sensing and certifying pseudo-randomness of Goldreich's candidate generators and generalizations. We show that for every d∈ℕ, the (n+m)O(d)-time canonical sum-of-squares (SoS) relaxation refutes such a system with high probability whenever m≥O(n)⋅(nd)D−1. We prove a lower bound in the restricted low-degree polynomial model of computation which suggests that this trade-off between SoS degree and the number of equations is nearly tight for all d. We also confirm the predictions of this lower bound in a limited setting by showing a lower bound on the canonical degree-4 sum-of-squares relaxation for refuting random quadratic polynomials. Together, our results provide evidence for an algorithmic threshold for the problem at m≳O˜(n)⋅n(1−δ)(D−1) for 2nδ-time algorithms for all δ. 

   more » « less
4. Higher order Kirillov--Reshetikhin modules for 𝐔 q ( A n (1) ), imaginary modules and monoidal categorification

   https://doi.org/10.1515/crelle-2023-0068  

   Brito, Matheus ; Chari, Vyjayanthi ( October 2023 , Journal für die reine und angewandte Mathematik (Crelles Journal))

   We study the family of irreducible modules for quantum affine$𝔰{𝔩}_{n+1}${\mathfrak{sl}_{n+1}}whose Drinfeld polynomials are supported on just one node of the Dynkin diagram. We identify all the prime modules in this family and prove a unique factorization theorem. The Drinfeld polynomials of the prime modules encode information coming from the points of reducibility of tensor products of the fundamental modules associated to$A_m${A_{m}}with$m\le n${m\leq n}. These prime modules are a special class of the snake modules studied by Mukhin and Young. We relate our modules to the work of Hernandez and Leclerc and define generalizations of the category${\mathcal{𝒞}}^{-}${\mathscr{C}^{-}}. This leads naturally to the notion of an inflation of the corresponding Grothendieck ring. In the last section we show that the tensor product of a (higher order) Kirillov–Reshetikhin module with its dual always contains an imaginary module in its Jordan–Hölder series and give an explicit formula for its Drinfeld polynomial. Together with the results of [D. Hernandez and B. Leclerc,A cluster algebra approach toq-characters of Kirillov–Reshetikhin modules,J. Eur. Math. Soc. (JEMS) 18 2016, 5, 1113–1159] this gives examples of a product of cluster variables which are not in the span of cluster monomials. We also discuss the connection of our work with the examples arising from the work of [E. Lapid and A. Mínguez,Geometric conditions for$\mathrm{\square }$\square-irreducibility of certain representations of the general linear group over a non-archimedean local field,Adv. Math. 339 2018, 113–190]. Finally, we use our methods to give a family of imaginary modules in type$D_4${D_{4}}which do not arise from an embedding of$A_r${A_{r}}with$r\le 3${r\leq 3}in$D_4${D_{4}}.

    

   more » « less
5. A Combinatorial Formula for Kazhdan-Lusztig Polynomials of Sparse Paving Matroids

   https://doi.org/10.37236/10602  

   Lee, Kyungyong ; Nasr, George D. ; Radcliffe, Jamie ( October 2021 , The Electronic Journal of Combinatorics)

   We present a combinatorial formula using skew Young tableaux for the coefficients of Kazhdan-Lusztig polynomials for sparse paving matroids. These matroids are known to be logarithmically almost all matroids, but are conjectured to be almost all matroids. We also show the positivity of these coefficients using our formula. In special cases, such as uniform matroids, our formula has a nice combinatorial interpretation. 

   more » « less