A long-standing open conjecture in combinatorics asserts that a Gorenstein lattice polytope with the integer decomposition property (IDP) has a unimodal (Ehrhart) h⁎-polynomial. This conjecture can ...be viewed as a strengthening of a previously disproved conjecture which stated that any Gorenstein lattice polytope has a unimodal h⁎-polynomial. The first counterexamples to unimodality for Gorenstein lattice polytopes were given in even dimensions greater than five by Mustaţǎ and Payne, and this was extended to all dimensions greater than five by Payne. While there exist numerous examples in support of the conjecture that IDP reflexives are h⁎-unimodal, its validity has not yet been considered for families of reflexive lattice simplices that closely generalize Payne's counterexamples. The main purpose of this work is to prove that the former conjecture does indeed hold for a natural generalization of Payne's examples. The second purpose of this work is to extend this investigation to a broader class of lattice simplices, for which we present new results and open problems.
The Eulerian polynomials and derangement polynomials are two well-studied generating functions that frequently arise in combinatorics, algebra, and geometry. When one makes an appearance, the other ...often does so as well, and their corresponding generalizations are similarly linked. This is this case in the theory of subdivisions of simplicial complexes, where the Eulerian polynomial is an h-polynomial and the derangement polynomial is its local h-polynomial. Separately, in Ehrhart theory the Eulerian polynomials are generalized by the h⁎-polynomials of s-lecture hall simplices. Here, we show that derangement polynomials are analogously generalized by the box polynomials, or local h⁎-polynomials, of the s-lecture hall simplices, and that these polynomials are all real-rooted. We then connect the two theories by showing that the local h-polynomials of common subdivisions in algebra and topology are realized as local h⁎-polynomials of s-lecture hall simplices. We use this connection to address some open questions on real-rootedness and unimodality of generating polynomials, some from each side of the story.
Summary
Directed acyclic graphical models are widely used to represent complex causal systems. Since the basic task of learning such a model from data is NP-hard, a standard approach is greedy search ...over the space of directed acyclic graphs or Markov equivalence classes of directed acyclic graphs. As the space of directed acyclic graphs on $p$ nodes and the associated space of Markov equivalence classes are both much larger than the space of permutations, it is desirable to consider permutation-based greedy searches. Here, we provide the first consistency guarantees, both uniform and high dimensional, of a greedy permutation-based search. This search corresponds to a simplex-like algorithm operating over the edge-graph of a subpolytope of the permutohedron, called a directed acyclic graph associahedron. Every vertex in this polytope is associated with a directed acyclic graph, and hence with a collection of permutations that are consistent with the directed acyclic graph ordering. A walk is performed on the edges of the polytope maximizing the sparsity of the associated directed acyclic graphs. We show via simulated and real data that this permutation search is competitive with current approaches.
Subdivisions of shellable complexes Hlavacek, Max; Solus, Liam
Journal of combinatorial theory. Series A,
02/2022, Volume:
186
Journal Article
Peer reviewed
Open access
In geometric, algebraic, and topological combinatorics, the unimodality of combinatorial generating polynomials is frequently studied. Unimodality follows when the polynomial is (real) stable, a ...property often deduced via the theory of interlacing polynomials. Many of the open questions on stability and unimodality of polynomials pertain to the enumeration of faces of cell complexes. In this paper, we relate the theory of interlacing polynomials to the shellability of cell complexes. We first derive a sufficient condition for stability of the h-polynomial of a subdivision of a shellable complex. To apply it, we generalize the notion of reciprocal domains for convex embeddings of polytopes to abstract polytopes and use this generalization to define the family of stable shellings of a polytopal complex. We characterize the stable shellings of cubical and simplicial complexes, and apply this theory to answer a question of Brenti and Welker on barycentric subdivisions for the well-known cubical polytopes. We also give a positive solution to a problem of Mohammadi and Welker on edgewise subdivisions of cell complexes. We end by relating the family of stable line shellings to the combinatorics of hyperplane arrangements. We pose related questions, answers to which would resolve some long-standing problems while strengthening ties between the theory of interlacing polynomials and the combinatorics of hyperplane arrangements.
In algebraic, topological, and geometric combinatorics, inequalities among the coefficients of combinatorial polynomials are frequently studied. Recently, a notion called the alternatingly increasing ...property, which is stronger than unimodality, was introduced. In this paper, we relate the alternatingly increasing property to real-rootedness of the symmetric decomposition of a polynomial to develop a systematic approach for proving the alternatingly increasing property for several classes of polynomials. We apply our results to strengthen and generalize real-rootedness, unimodality, and alternatingly increasing results pertaining to colored Eulerian and derangement polynomials, Ehrhart $h^\ast$-polynomials for lattice zonotopes, $h$-polynomials of barycentric subdivisions of doubly Cohen–Macaulay level simplicial complexes, and certain local $h$-polynomials for subdivisions of simplices. In particular, we prove two conjectures of Athanasiadis.
For a given lattice polytope, two fundamental problems within the field of Ehrhart theory are (1) to determine if its (Ehrhart)
h
∗
-polynomial is unimodal and (2) to determine if its Ehrhart ...polynomial has only positive coefficients. The former property of a lattice polytope is known as Ehrhart unimodality and the latter property is known as Ehrhart positivity. These two properties are often simultaneously conjectured to hold for interesting families of lattice polytopes, yet they are typically studied in parallel. As to answer a question posed at the 2017 Introductory Workshop to the MSRI Semester on Geometric and Topological Combinatorics, the purpose of this note is to show that there is no general implication between these two properties in any dimension greater than two. To do so, we investigate these two properties for families of well-studied lattice polytopes, assessing one property where previously only the other had been considered. Consequently, new examples of each phenomena are developed, some of which provide an answer to an open problem in the literature. The well-studied families of lattice polytopes considered include zonotopes, matroid polytopes, simplices of weighted projective spaces, empty lattice simplices, smooth polytopes, and
s
-lecture hall simplices.
DAG models are statistical models satisfying a collection of conditional independence relations encoded by the nonedges of a directed acyclic graph (DAG) G. Such models are used to model complex ...cause–effect systems across a variety of research fields. From observational data alone, a DAG model G is only recoverable up to Markov equivalence. Combinatorially, two DAGs are Markov equivalent if and only if they have the same underlying undirected graph (i.e., skeleton) and the same set of the induced subDAGs i→j←k, known as immoralities. Hence it is of interest to study the number and size of Markov equivalence classes (MECs). In a recent paper, we introduced a pair of generating functions that enumerate the number of MECs on a fixed skeleton by number of immoralities and by class size, and we studied the complexity of computing these functions. In this paper, we lay the foundation for studying these generating functions by analyzing their structure for trees and other closely related graphs. We describe these polynomials for some well-studied families of graphs including paths, stars, cycles, spider graphs, caterpillars, and balanced binary trees. In doing so, we recover connections to independence polynomials, and extend some classical identities that hold for Fibonacci numbers. We also provide tight lower and upper bounds for the number and size of MECs on any tree. Finally, we use computational methods to show that the number and distribution of high degree nodes in a triangle-free graph dictate the number and size of MECs.
PDF
