Describing the equality conditions of the Alexandrov–Fenchel inequality has been a major open problem for decades. We prove that for a natural class of convex polytopes, the equality cases of the AF inequality are not in unless the polynomial hierarchy collapses to a finite level. This is the first hardness result for the problem. The proof involves Stanley’s order polytopes and a delicate analysis of linear extensions of finite posets, with some number theoretic results added to the mix. We also give applications to combinatorial interpretations of the defect of Stanley’s log-concave inequality for the number of linear extensions.

Can you decide if there is a coincidence in the numbers counting two different combinatorial objects? For example, can you decide if two regions in R3 have the same number of domino tilings? There are two versions of the problem, with 2×1×1 and 2×2×1 boxes. We prove that in both cases the coincidence problem is not in the polynomial hierarchy unless the polynomial hierarchy collapses to a finite level. While the conclusions are the same, the proofs are notably different and generalize in different directions. We proceed to explore the coincidence problem for counting independent sets and matchings in graphs, matroid bases, order ideals and linear extensions in posets, permutation patterns, and the Kronecker coefficients. We also make a number of conjectures for counting other combinatorial objects such as plane triangulations, contingency tables, standard Young tableaux, reduced factorizations and the Littlewood–Richardson coefficients.

Abstract. We explore inequalities on linear extensions of posets and make them effective in different ways. First, we study the Björner–Wachs inequality and generalize it to inequalities on order polynomials and their q-analogues via direct injections and Fortuin–Kasteleyn–Ginibre inequalities. Second, we give an injective proof of Sidorenko’s inequality with computational complexity significance, namely, that the difference is in #P. Third, we generalize actions of Coxeter groups on restricted linear extensions, leading to vanishing and uniqueness conditions for the generalized Stanley inequality. We also establish several new inequalities on order polynomials and prove an asymptotic version of Graham’s inequality.

We study rotor walks on transient graphs with initial rotor configuration sampled from the oriented wired uniform spanning forest (OWUSF) measure. We show that the expected number of visits to any vertex by the rotor walk is at most equal to the expected number of visits by the simple random walk. In particular, this implies that this walk is transient. When these two numbers coincide, we show that the rotor configuration at the end of the process also has the law of OWUSF. Furthermore, if the graph is vertex-transitive, we show that the average number of visits by $n$ consecutive rotor walks converges to the Green's function of the simple random walk as $n$ tends to infinity. This answers a question posed by Florescu et al. (2014).