For a given lattice polytope, two fundamental problems within the field of Ehrhart theory are to (1) determine if its (Ehrhart) \(h^\ast\)-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.
Directed acyclic graphical models, or DAG 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 sub-polytope of the permutohedron, called a DAG 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.
Characteristic imsets are 0-1 vectors which correspond to Markov equivalence classes of directed acyclic graphs. The study of their convex hull, named the characteristic imset polytope, has led to ...new and interesting geometric perspectives on the important problem of causal discovery. In this paper we begin the study of the associated toric ideal. We develop a new generalization of the toric fiber product, which we call a quasi-independence gluing, and show that under certain combinatorial homogeneity conditions, one can iteratively compute a Gr\"obner basis via lifting. For faces of the characteristic imset polytope associated to trees, we apply this technique to compute a Gr\"obner basis for the associated toric ideal. We end with a study of the characteristic ideal of the cycle and propose directions for future work.
We consider the problem of characterizing Bayesian networks up to unconditional equivalence, i.e., when directed acyclic graphs (DAGs) have the same set of unconditional \(d\)-separation statements. ...Each unconditional equivalence class (UEC) is uniquely represented with an undirected graph whose clique structure encodes the members of the class. Via this structure, we provide a transformational characterization of unconditional equivalence; i.e., we show that two DAGs are in the same UEC if and only if one can be transformed into the other via a finite sequence of specified moves. We also extend this characterization to the essential graphs representing the Markov equivalence classes (MECs) in the UEC. UECs partition the space of MECs and are easily estimable from marginal independence tests. Thus, a characterization of unconditional equivalence has applications in methods that involve searching the space of MECs of Bayesian networks.
We construct Bayesian and frequentist finite-sample goodness-of-fit tests for three different variants of the stochastic blockmodel for network data. Since all of the stochastic blockmodel variants ...are log-linear in form when block assignments are known, the tests for the \emph{latent} block model versions combine a block membership estimator with the algebraic statistics machinery for testing goodness-of-fit in log-linear models. We describe Markov bases and marginal polytopes of the variants of the stochastic blockmodel, and discuss how both facilitate the development of goodness-of-fit tests and understanding of model behavior. The general testing methodology developed here extends to any finite mixture of log-linear models on discrete data, and as such is the first application of the algebraic statistics machinery for latent-variable models.
Let \(k, n\) and \(r\) be positive integers with \(k < n\) and \(r\leq\lfloor\frac{n}{k}\rfloor\). We determine the facets of the \(r\)-stable \(n,k\)-hypersimplex. As a result, it turns out that the ...\(r\)-stable \(n,k\)-hypersimplex has exactly \(2n\) facets for every \(r<\lfloor\frac{n}{k}\rfloor\). We then utilize the equations of the facets to study when the \(r\)-stable hypersimplex is Gorenstein. For every \(k>0\) we identify an infinite collection of Gorenstein \(r\)-stable hypersimplices, consequently expanding the collection of \(r\)-stable hypersimplices known to have unimodal Ehrhart \(\delta\)-vectors.
A long-standing open conjecture in combinatorics asserts that a Gorenstein lattice polytope with the integer decomposition property (IDP) has a unimodal (Ehrhart) \(h^\ast\)-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^\ast\)-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^\ast\)-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.
Multivariate distributions are fundamental to modeling. Discrete copulas can be used to construct diverse multivariate joint distributions over random variables from estimated univariate marginals. ...The space of discrete copulas admits a representation as a convex polytope which can be exploited in entropy-copula methods relevant to hydrology and climatology. To allow for an extensive use of such methods in a wide range of applied fields, it is important to have a geometric representation of discrete copulas with desirable stochastic properties. In this paper, we show that the families of ultramodular discrete copulas and their generalization to convex discrete quasi-copulas admit representations as polytopes. We draw connections to the prominent Birkhoff polytope, alternating sign matrix polytope, and their most extensive generalizations in the discrete geometry literature. In doing so, we generalize some well-known results on these polytopes from both the statistics literature and the discrete geometry literature.
Hypersimplices are well-studied objects in combinatorics, optimization, and
representation theory. For each hypersimplex, we define a new family of
subpolytopes, called r-stable hypersimplices, and ...show that a well-known
regular unimodular triangulation of the hypersimplex restricts to a
triangulation of each r-stable hypersimplex. For the case of the second
hypersimplex defined by the two-element subsets of an n-set, we provide a
shelling of this triangulation that sequentially shells each r-stable
sub-hypersimplex. In this case, we utilize the shelling to compute the Ehrhart
h*-polynomials of these polytopes, and the hypersimplex, via independence
polynomials of graphs. For one such r-stable hypersimplex, this computation
yields a connection to CR mappings of Lens spaces via Ehrhart-MacDonald
reciprocity.
Two directed acyclic graphs (DAGs) are called Markov equivalent if and only if they have the same underlying undirected graph (i.e. skeleton) and the same set of immoralities. Using observational ...data, a DAG model can only be determined up to Markov equivalence, and so it is desirable to understand the size and number of Markov equivalence classes (MECs) combinatorially. In this paper, we address this enumerative question using a pair of generating functions that encode the number and size of MECs on a skeleton \(G\), and in doing so we connect this problem to classical problems in combinatorial optimization. The first is a graph polynomial that counts the number of MECs on \(G\) by their number of immoralities. Using connections to the independent set problem, we show that computing a DAG on \(G\) with the maximum possible number of immoralities is NP-hard. The second generating function counts the MECs on \(G\) according to their size. Via computer enumeration, we show that this generating function is distinct for every connected graph on \(p\) nodes for all \(p\leq 10\).
