1.) Valuations and the Hopf Monoid of Generalized Permutahedra (with Federico Ardila)

The goal of this paper is to show that valuation theory and Hopf theory are compatible on the class of generalized permutahedra. We prove that the Hopf structure GP+ on these polyhedra descends, modulo the inclusion-exclusion relations, to an indicator Hopf monoid I(GP+) of generalized permutahedra that is isomorphic to the Hopf monoid of weighted ordered set partitions. This quotient Hopf monoid I(GP+) is cofree. It is the terminal object in the category of Hopf monoids with polynomial characters; this partially explains the ubiquity of generalized permutahedra in the theory of Hopf monoids. This Hopf theoretic framework offers a simple, unified explanation for many new and old valuations on generalized permutahedra and their subfamilies. Examples include, for matroids: the Chern-Schwartz-MacPherson cycles, Eur's volume polynomial, the Kazhdan-Lusztig polynomial, the motivic zeta function, and the Derksen-Fink invariant; for posets: the order polynomial, Poincare polynomial, and poset Tutte polynomial; for generalized permutahedra: the universal Tutte character and the corresponding class in the Chow ring of the permutahedral variety. We obtain several algebraic and combinatorial corollaries; for example: the existence of the valuative character group of GP+, and the indecomposability of a nestohedron into smaller nestohedra.

2.) The Universal Valuation of Coxeter Matroids (with Chris Eur and Mariel Supina)

Coxeter matroids generalize matroids just as flag varieties of Lie groups generalize Grassmannians. Valuations of Coxeter matroids are functions that behave well with respect to subdivisions of a Coxeter matroid into smaller ones. We compute the universal valuative invariant of Coxeter matroids. A key ingredient is the family of Coxeter Schubert matroids, which correspond to the Bruhat cells of flag varieties. In the process, we compute the universal valuation of generalized Coxeter permutohedra, a larger family of polyhedra that model Coxeter analogues of combinatorial objects such as matroids, clusters, and posets.

3.) Poset Hopf Monoids

We initiate the study of a large class of species monoids and comonoids which come equipped with a poset structure that is compatible with the multiplication and comultiplication maps. We show that if a monoid and a comonoid are related through a Galois connection, then they are dual to each other. This duality is best understood by introducing a new basis constructed through Mobius inversion. We use this new basis to give uniform proofs for cofreeness and calculations of primitives for the Hopf monoids of set partitions, graphs, hypergraphs, and simplicial complexes. Further, we show that the monoid and comonoid of a Hopf monoid are related through a Galois connection if and only if the Hopf monoid is linearized, commutative, and cocommutative. In these cases, we give a grouping-free formula for the antipode in terms of an evaluation of the characteristic polynomial of a related poset. This gives new proofs for the antipodes of the Hopf monoids of graphs, hypergraphs, set partitions, and simplicial complexes.

4.) Geometry of Random Tournaments (with Brett Kolesnik)

A tournament is an orientation of a graph. Each edge represents a match, directed towards the winner. The score sequence lists the number of wins by each team. Landau (1953) characterized score sequences of the complete graph. Moon (1963) showed that the same conditions are necessary and sufficient for the mean score sequences of random tournaments. We present short and natural proofs of these results that work for any graph using zonotopes from convex geometry. A zonotope is a linear image of a cube. Moon's Theorem follows by identifying elements of the cube with distributions and the linear map as the expectation operator. Our proof of Landau's Theorem combines zonotopal tilings with the theory of mixed subdivisions. We also show that any mean score sequence can be realized by a tournament that is random within a subforest and deterministic otherwise.

5.) Dependent Random Graphs and Multiparty Pointer Jumping (with Joshua Brody)

We initiate a study of a relaxed version of the standard Erdos-Renyi random graph model, where each edge may depend on a few other edges. We call such graphs "dependent random graphs". Our main result in this direction is a thorough understanding of the clique number of dependent random graphs. We also obtain bounds for the chromatic number. Surprisingly, many of the standard properties of random graphs also hold in this relaxed setting. We show that with high probability, a dependent random graph will contain a clique of size (1-o(1))lognlog(1/p), and the chromatic number will be at most nlog(1/1-p)logn. As an application and second main result, we give a new communication protocol for the k-player Multiparty Pointer Jumping (MPJ_k) problem in the number-on-the-forehead (NOF) model. Multiparty Pointer Jumping is one of the canonical NOF communication problems, yet even for three players, its communication complexity is not well understood. Our protocol for MPJ_3 costs O(nloglognlogn) communication, improving on a bound of Brody and Chakrabarti [BC08]. We extend our protocol to the non-Boolean pointer jumping problem MPJ^k, achieving an upper bound which is o(n) for any k>=4 players. This is the first o(n) bound for MPJ^k and improves on a bound of Damm, Jukna, and Sgall [DJS98] which has stood for almost twenty years.