A theorem of Edmonds characterizes when a pair of matroids has a common basis. Enumerating the common bases of a pair of matroid is a much harder problem, and includes the #P-complete problem of counting the number of perfect matchings in a bipartite graph. We focus on the problem of counting the common bases in pairs of regular matroids, and describe a class called <i>Pfaffian matroid pairs</i> for which this enumeration problem can be solved. We prove that when a pair of regular matroids is non-Pfaffian, there is a set of common bases which certifies this, and that the number of bases in the certificate is linear in the size of the ground set of the matroids. When both matroids in a pair are series-parallel, we prove that determining if the pair is Pfaffian is equivalent to finding an edge signing in an associated graph, and in the case that the pair is non-Pfaffian, we obtain a characterization of this associated graph. Pfaffian bipartite graphs are a class of graphs for which the number of perfect matchings can be determined; we show that the class of series-parallel Pfaffian matroid pairs is an extension of the class of Pfaffian bipartite graphs. Edmonds proved that the polytope generated by the common bases of a pair of matroids is equal to the intersection of the polytopes generated by the bases for each matroid in the pair. We consider when a similar property holds for the binary space, and give an excluded minor characterization of when the binary space generated by the common bases of two matroids can not be determined from the binary spaces for the individual matroids. As a result towards a description of the lattice of common bases for a pair of matroids, we show that the lattices for the individual matroids determine when all common bases of a pair of matroids intersect a subset of the ground set with fixed cardinality.

A theorem of Edmonds characterizes when a pair of matroids has a common basis. Enumerating the common bases of a pair of matroid is a much harder problem, and includes the #P-complete problem of counting the number of perfect matchings in a bipartite graph. We focus on the problem of counting the common bases in pairs of regular matroids, and describe a class called <i>Pfaffian matroid pairs</i> for which this enumeration problem can be solved. We prove that when a pair of regular matroids is non-Pfaffian, there is a set of common bases which certifies this, and that the number of bases in the certificate is linear in the size of the ground set of the matroids. When both matroids in a pair are series-parallel, we prove that determining if the pair is Pfaffian is equivalent to finding an edge signing in an associated graph, and in the case that the pair is non-Pfaffian, we obtain a characterization of this associated graph. Pfaffian bipartite graphs are a class of graphs for which the number of perfect matchings can be determined; we show that the class of series-parallel Pfaffian matroid pairs is an extension of the class of Pfaffian bipartite graphs. Edmonds proved that the polytope generated by the common bases of a pair of matroids is equal to the intersection of the polytopes generated by the bases for each matroid in the pair. We consider when a similar property holds for the binary space, and give an excluded minor characterization of when the binary space generated by the common bases of two matroids can not be determined from the binary spaces for the individual matroids. As a result towards a description of the lattice of common bases for a pair of matroids, we show that the lattices for the individual matroids determine when all common bases of a pair of matroids intersect a subset of the ground set with fixed cardinality.

Une variété horosphérique est une variété algébrique normale dans laquelle un groupe algébrique réductif opère avec une orbite ouverte fibrée en tores sur une variété de drapeaux. La dimension de ces tores est appelée le rang de la variété horosphérique. En particulier, les variétés toriques et les variétés de drapeaux sont horosphériques. Dans cette thèse, on classifie les variétés horosphériques de Fano en termes de certains polytopes rationnels qui généralisent les polytopes réflexifs considérés par V.Batyrev. Puis on obtient une majoration du degré des variétés horosphériques lisses de Fano, analogue à celle donnée par O.Debarre dans le cas torique. On étend un résultat récent de C.Casagrande : les variétés horosphériques Q-factorielles de Fano ont leur nombre de Picard majoré par deux fois la dimension. On donne aussi de nombreux exemples en rang 2.

We describe combinatorial techniques for studying log Calabi-Yau surfaces. These can be viewed as generalizing the techniques for studying toric varieties in terms of their character and cocharacter lattices. These lattices are replaced by certain integral linear manifolds described in [GHK11], and monomials on toric varieties are replaced with the canonical theta functions defined in [GHK11] using ideas from mirror symmetry. We classify deformation classes of log Calabi-Yau surfaces in terms of the geometry of these integral linear manifolds. We then describe the tropicalizations of theta functions and use them to generalize the dual pairing between the character and cocharacter lattices. We use this to describe generalizations of dual cones, Newton and polar polytopes, Minkowski sums, and finite Fourier series expansions. We hope that these techniques will generalize to higher rank cluster varieties. / text

In this dissertation we study the excedance permutation statistic. We start by extending the classical excedance statistic of the symmetric group to the affine symmetric group eSn and determine the generating function of its distribution. The proof involves enumerating lattice points in a skew version of the root polytope of type A. Next we study the excedance set statistic on the symmetric group by defining a related algebra which we call the excedance algebra. A combinatorial interpretation of expansions from this algebra is provided. The second half of this dissertation deals with the topology of the Frobenius complex, that is the order complex of a poset whose definition was motivated by the classical Frobenius problem. We determine the homotopy type of the Frobenius complex in certain cases using discrete Morse theory. We end with an enumeration of Q-factorial posets. Open questions and directions for future research are located at the end of each chapter.

The main theme of this dissertation is the study of polytopes arising from binary multi-way contingency tables and characteristic imsets for Bayesian networks. Firstly, we study on three-way tables whose entries are independent Bernoulli ran- dom variables with canonical parameters under no three-way interaction generalized linear models. Here, we use the sequential importance sampling (SIS) method with the conditional Poisson (CP) distribution to sample binary three-way tables with the sufficient statistics, i.e., all two-way marginal sums, fixed. Compared with Monte Carlo Markov Chain (MCMC) approach with a Markov basis (MB), SIS procedure has the advantage that it does not require expensive or prohibitive pre-computations. Note that this problem can also be considered as estimating the number of lattice points inside the polytope defined by the zero-one and two-way marginal constraints. The theorems in Chapter 2 give the parameters for the CP distribution on each column when it is sampled. In this chapter, we also present the algorithms, the simulation results, and the results for Samson’s monks data. Bayesian networks, a part of the family of probabilistic graphical models, are widely applied in many areas and much work has been done in model selections for Bayesian networks. The second part of this dissertation investigates the problem of finding the optimal graph by using characteristic imsets, where characteristic imsets are defined as 0-1 vector representations of Bayesian networks which are unique up to Markov equivalence. Characteristic imset polytopes are defined as the convex hull of all characteristic imsets we consider. It was proven that the problem of finding optimal Bayesian network for a specific dataset can be converted to a linear programming problem over the characteristic imset polytope [51]. In Chapter 3, we first consider characteristic imset polytopes for all diagnosis models and show that these polytopes are direct product of simplices. Then we give the combinatorial description of all edges and all facets of these polytopes. At the end of this chapter, we generalize these results to the characteristic imset polytopes for all Bayesian networks with a fixed underlying ordering of nodes. Chapter 4 includes discussion and future work on these two topics.

This dissertation demonstrates a procedure to view any quasitoric manifold as a “minimal” sub-manifold of an ambient quasitoric manifold of codimension two via the wedge construction applied to the quotient polytope. These we term wedge quasitoric manifolds. We prove existence utilizing a construction on the quotient polytope and characteristic matrix and demonstrate conditions allowing the base manifold to be viewed as dual to the first Chern class of the wedge manifold. Such dualization allows calculations of KO characteristic classes as in the work of Ochanine and Fast. We also examine the Todd genus as it relates to two types of wedge quasitoric manifolds. Background matter on polytopes and toric topology, as well as spin and complex cobordism are provided.

The entropy of a graph is a functional depending both on the graph itself and on a probability distribution on its vertex set. This graph functional originated from the problem of source coding in information theory and was introduced by J. K\"{o}rner in 1973. Although the notion of graph entropy has its roots in information theory, it was proved to be closely related to some classical and frequently studied graph theoretic concepts. For example, it provides an equivalent definition for a graph to be perfect and it can also be applied to obtain lower bounds in graph covering problems. In this thesis, we review and investigate three equivalent definitions of graph entropy and its basic properties. Minimum entropy colouring of a graph was proposed by N. Alon in 1996. We study minimum entropy colouring and its relation to graph entropy. We also discuss the relationship between the entropy and the fractional chromatic number of a graph which was already established in the literature. A graph $G$ is called \emph{symmetric with respect to a functional $F_G(P)$} defined on the set of all the probability distributions on its vertex set if the distribution $P^*$ maximizing $F_G(P)$ is uniform on $V(G)$. Using the combinatorial definition of the entropy of a graph in terms of its vertex packing polytope and the relationship between the graph entropy and fractional chromatic number, we prove that vertex transitive graphs are symmetric with respect to graph entropy. Furthermore, we show that a bipartite graph is symmetric with respect to graph entropy if and only if it has a perfect matching. As a generalization of this result, we characterize some classes of symmetric perfect graphs with respect to graph entropy. Finally, we prove that the line graph of every bridgeless cubic graph is symmetric with respect to graph entropy.

In this thesis, we undertake a combinatorial study of certain aspects of triangulations of cartesian products of simplices, particularly in relation to their relevance in toric algebra and to their underlying product structure. The first chapter reports joint work with Samu Potka. The object of study is a class of homogeneous toric ideals called cut ideals of graphs, that were introduced by Sturmfels and Sullivant 2006. Apart from their inherent appeal to combinatorial commutative algebra, these ideals also generalize graph statistical models for binary data and are related to some statistical models for phylogenetic trees. Specifically, we consider minimal free resolutions for the cut ideals of trees. We propose a method to combinatorially estimate the Betti numbers of the ideals in this class. Using this method, we derive upper bounds for some of the Betti numbers, given by formulas exponential in the number of vertices of the tree. Our method is based on a common technique in commutative algebra whereby arbitrary homogeneous ideals are deformed to initial monomial ideals, which are easier to analyze while conserving some of the information of the original ideals. The cut ideal of a tree on n vertices turns out to be isomorphic to the Segre product of the cut ideals of its n-1 edges (in particular, its algebraic properties do not depend on its shape). We exploit this product structure to deform the cut ideal of a tree to an initial monomial ideal with a simple combinatorial description: it coincides with the edge ideal of the incomparability graph of the power set of the edges of the tree. The vertices of the incomparability graph are subsets of the edges of the tree, and two subsets form an edge whenever they are incomparable. In order to obtain algebraic information about these edge ideals, we apply an idea introduced by Dochtermann and Engström in 2009 that consists in regarding the edge ideal of a graph as the (monomial) Stanley-Reisner ideal of the independence complex of the graph. Using Hochster\'s formula for computting Betti numbers of Stanley-Reisner ideals by means of simplicial homology, the computation of the Betti numbers of these monomial ideals is turned to the enumeration of induced subgraphs of the incomparability graph. That the resulting values give upper bounds for the Betti numbers of the cut ideals of trees is an important well-known result in commutative algebra. In the second chapter, we focus on some combinatorial features of triangulations of the point configuration obtained as the cartesian product of two standard simplices. These were explored in collaboration with César Ceballos and Arnau Padrol, and had a two-fold motivation. On the one hand, we intended to understand the influence of the product structure on the set of triangulations of the cartesian product of two point configurations; on the other hand, the set of all triangulations of the product of two simplices is an intricate and interesting object that has attracted attention both in discrete geometry and in other fields of mathematics such as commutative algebra, algebraic geometry, enumerative geometry or tropical geometry. Our approach to both objectives is to examine the circumstances under which a triangulation of the polyhedral complex given by the the product of an (n-1)-simplex times the (k-1)-skeleton of a (d-1)-simplex extends to a triangulation of an (n-1)-simplex times a (d-1)-simplex. We refer to the former as a partial triangulation of the product of two simplices. Our main result says that if d >= k > n, a partial triangulation always extends to a uniquely determined triangulation of the product of two simplices. A somewhat unexpected interpretation of this result is as a finiteness statement: it asserts that if d is sufficiently larger than n, then all partial triangulations are uniquely determined by the (compatible) triangulations of its faces of the form “(n-1)-simplex times n-simplex”. Consequently, one can say that in this situation ‘\'triangulations of an (n-1)-simplex times a (d-1)-simplex are not much more complicated than triangulations of an (n-1)-simplex times an n-simplex\'\'. The uniqueness assertion of our main result holds already when d>=k>=n. However, the same is not true for the existence assertion; namely, there are non extendable triangulations of an (n-1)-simplex times the boundary of an n-simplex that we explicitly construct. A key ingredient towards this construction is a triangulation of the product of two (n-1)-simplices that can be seen as its ``second simplest triangulation\'\' (the simplest being its staircase triangulation). It seems to be knew, and we call it the Dyck path triangulation. This triangulation displays symmetry under the cyclic group of order n that acts by simultaneously cycling the indices of the points in both factors of the product. Next, we exhibit a natural extension of the Dyck path triangulation to a triangulation of an (n-1)-simplex times an n-simplex that, in a sense, enjoys some sort of ‘\'rigidity\'\' (it also seems new). Performing a ‘\'local modification\'\' on the restriction of this extended triangulation to the polyhedral complex given by (n-1)-simplex times the boundary of an n-simplex yields the non-extendable partial triangulation. The thesis includes two appendices on basic commutative algebra and triangulations of point configuration, included to make it slightly self-contained.

A sweep-plane algorithm by Lawrence for convex polytope computation is adapted to generate random tuples on simple polytopes. In our method an affine hyperplane is swept through the given polytope until a random fraction (sampled from a proper univariate distribution) of the volume of the polytope is covered. Then the intersection of the plane with the polytope is a simple polytope with smaller dimension. In the second part we apply this method to construct a black-box algorithm for log-concave and T-concave multivariate distributions by means of transformed density rejection. (author's abstract) / Series: Preprint Series / Department of Applied Statistics and Data Processing