No description available.

Let <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D%20=%20(%5Cmathbb%7BP%7D,%20%5Cpreceq)" data-classname="equation_inline" data-title="" /> be a finite poset (partially ordered set) with cardinality <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?n" data-classname="equation_inline" data-title="" />. A linear extension of <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D" data-classname="equation_inline" data-title="" /> is an order-preserving bijection <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Csigma" data-classname="equation_inline" data-title="" />: <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D%20%5Crightarrow%20%5Bn%5D" data-classname="equation_inline" data-title="" />, that is, if <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?x%20%5Cpreceq%20y" data-classname="equation_inline" data-title="" /> in <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D" data-classname="equation_inline" data-title="" /> then <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Csigma(x)%20%5Cle%20%5Csigma(y)" data-classname="equation_inline" data-title="" />. We define the poset probability <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?P(%5Calpha%20%5Cpreceq%20%5Cbeta)" data-classname="equation_inline" data-title="" /> as the proportion of linear extensions where <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Csigma(%5Calpha)%20%5Cle%20%5Csigma(%5Cbeta)" data-classname="equation_inline" data-title="" />. We are primarily interested in <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?P(%5Calpha%20%5Cpreceq%20%5Cbeta)" data-classname="equation_inline" data-title="" /> for incomparable elements <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Calpha%20%5Cparallel%20%5Cbeta" data-classname="equation" data-title="" />. The probability has significance in areas such as information theory. Let <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?e(%5Cmathbb%7BP%7D)" data-classname="equation_inline" data-title="" /> denote the total number of linear extensions of <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D" data-classname="equation_inline" data-title="" />. We prove that the poset probability can be evaluated as <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?P(%5Calpha%20%5Cpreceq%20%5Cbeta)%20=%20%5Cfrac%7B%20%5Csum_%7BT%20%5Cin%20B(%5Calpha,%5Cbeta)%7D%20e(T)%20e(%5Cmathbb%7BP%7D%20%5Csetminus%20(T%20%5Ccup%20%5C%7B%5Calpha%5C%7D))%7D%7Be(%5Cmathbb%7BP%7D)%7D" data-classname="equation" data-title="" /> where <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?B(%5Calpha,%5Cbeta)" data-classname="equation_inline" data-title="" /> is the set of order ideals of <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D" data-classname="equation_inline" data-title="" /> without <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Calpha" data-classname="equation" data-title="" /> or <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cbeta" data-classname="equation" data-title="" />, where we can add <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Calpha" data-classname="equation_inline" data-title="" /> to get a new order ideal of <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D" data-classname="equation_inline" data-title="" />. The practicality of the preceding formula is explored and we show that <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?T%20%5Cin%20B(%5Calpha,%5Cbeta)%20%5CLeftrightarrow%20%5Cleft%5C%7B%20x%20%7C%20x%20%5Cprec%20%5Calpha%20%5Cright%5C%7D%20%5Csubseteq%20T%20%5Ctext%7B%20and%20%7D%20T%20%5Ctext%7B%20order%20ideal%20of%20%7D%0A%5Cleft%5C%7B%20x%20%7C%20%5Calpha%20%5Cnot%20%5Cpreceq%20x,%5C%20%5Cbeta%20%5Cnot%20%5Cpreceq%20x%7D" data-classname="equation" /> The formula is particularly useful for certain classes of posets such as partition posets which are examined in further detail. We apply the formula to prove that, for all partition posets of shape <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Bn,n%5D" data-classname="equation_inline" data-title="" />, the probability obeys <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?P((2,a)%20%5Cpreceq%20(1,a+1))%20=%20%5Cfrac%7B%20C_a%20C_%7Bn-a%7D%7D%20%7BC_n%7D" data-classname="equation" data-title="" /> where <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?C_n" data-classname="equation_inline" data-title="" /> is the nth Catalan number and <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?a%20%3C%20n" data-classname="equation_inline" data-title="" />. We also explore how Monte Carlo methods can be used to estimate <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?P(%5Calpha%20%5Cpreceq%20%5Cbeta)" data-classname="equation_inline" data-title="" />.

<p>This thesis deals with combinatorial and geometric aspects of linear optimization, and consists of two parts.</p> <p>In the first part, we address a conjecture formulated in 2008 and stating that the largest possible average diameter of a bounded cell of a simple hyperplane arrangement of n hyperplanes in dimension d is not greater than the dimension d. The average diameter is the sum of the diameters of each bounded cell divided by the total number of bounded cells, and then we consider the largest possible average diameter over all simple hyperplane arrangements. This quantity can be considered as an indication of the average complexity of simplex methods for linear optimization. Previous results in dimensions 2 and 3 suggested that a specific type of extensions, namely the covering extensions, of the cyclic arrangement might achieve the largest average diameter. We introduce a method for enumerating the covering extensions of an arrangement, and show that covering extensions of the cyclic arrangement are not always among the ones achieving the largest diameter.</p> <p>The software tool we have developed for oriented matroids computation is used to exhibit a counterexample to the hypothesized minimum number of external facets of a simple arrangement of n hyperplanes in dimension d; i.e. facets belonging to exactly one bounded cell of a simple arrangement. We determine the largest possible average diameter, and verify the conjectured upper bound, in dimensions 3 and 4 for arrangements defined by no more than 8 hyperplanes via the associated uniform oriented matroids formulation. In addition, these new results substantiate the hypothesis that the largest average diameter is achieved by an arrangement minimizing the number of external facets.</p> <p>The second part focuses on the colourful simplicial depth, i.e. the number of colourful simplices in a colourful point configuration. This question is closely related to the colourful linear programming problem. We show that any point in the convex hull of each of (d+1) sets of (d+1) points in general position in R^d is contained in at least (d+1)²/2 simplices with one vertex from each set. This improves the previously established lower bounds for d>=4 due to Barany in 1982, Deza et al in 2006, Barany and Matousek in 2007, and Stephen and Thomas in 2008.</p> <p>We also introduce the notion of octahedral system as a combinatorial generalization of the set of colourful simplices. Configurations of low colourful simplicial depth correspond to systems with small cardinalities. This construction is used to find lower bounds computationally for the minimum colourful simplicial depth of a configuration, and, for a relaxed version of the colourful depth, to provide a simple proof of minimality.</p> / Doctor of Philosophy (PhD)

The purpose of this thesis is to generalize Filippov's operation, and to get more useful results. It includes two main parts: The C-Filippov operation for the finite and countable cases and the Filippov operation with different measures. In the first chapter, we give brief information about the importance of Filippov's operation, our goal and the ideas behind our generalizations. In the second chapter, we give some sufficient background notes. In the third chapter, we introduce the Filippov operation, explain how to calculate the Filippov of a function and give some sufficient properties of it. In the fourth chapter, we introduce a generalization of the Filippov operation, the C-Filippov, and give some of its properties which we need for the next chapter. In the fifth chapter, in the first main part, we discuss some properties of the C-Filippov for special cases and observe the differences and common properties between the Filippov and C-Filippov operations. Finally, in the sixth chapter, we present the other generalization of the Filippov operation which is Filippov with different measures. We observe the properties of the corresponding Filippovs when we know the relationship between the measures. We finish the thesis by summarizing our work and discussing future work.

In this dissertation we discuss three problems. We first show the classical q-Stirling numbers of the second kind can be expressed more compactly as a pair of statistics on a subset of restricted growth words. We extend this enumerative result via a decomposition of a new poset which we call the Stirling poset of the second kind. The Stirling poset of the second kind supports an algebraic complex and a basis for integer homology is determined. A parallel enumerative, poset theoretic and homological study for the q-Stirling numbers of the first kind is done. We also give a bijective argument showing the (q, t)-Stirling numbers of the first and second kind are orthogonal. In the second part we give combinatorial proofs of q-Stirling identities via restricted growth words. This includes new proofs of the generating function of q-Stirling numbers of the second kind, the q-Vandermonde convolution for Stirling numbers and the q-Frobenius identity. A poset theoretic proof of Carlitz’s identity is also included. In the last part we discuss a new expression for q-binomial coefficients based on the weighting of certain 01-permutations via a new bistatistic related to the major index. We also show that the bistatistics between the inversion number and major index are equidistributed. We generalize this idea to q-multinomial coefficients evaluated at negative q values. An instance of the cyclic sieving phenomenon related to flags of unitary spaces is also studied.

In this dissertation, we exhibit two instances of polyhedra in combinatorial convex geometry. The first instance arises in the context of Ehrhart theory, and the polyhedra are the central objects of study. The second instance arises in algebraic statistics, and the polyhedra act as a conduit through which we study a nonpolyhedral problem. In the first case, we examine combinatorial and algebraic properties of the Ehrhart h*-polynomial of the r-stable (n,k)-hypersimplices. These are a family of polytopes which form a nested chain of subpolytopes within the (n,k)-hypersimplex. We show that a well-studied unimodular triangulation of the (n,k)-hypersimplex restricts to a triangulation of each r-stable (n,k)-hypersimplex within. We then use this triangulation to compute the facet-defining inequalities of these polytopes. In the k=2 case, we use shelling techniques to devise a combinatorial interpretation of the coefficients of the h*-polynomials in terms of independent sets of certain graphs. From this, we then extract some results on unimodality. We also characterize the Gorenstein r-stable (n,k)-hypersimplices, and we conclude that these also have unimodal h*-polynomials. In the second case, for a graph G on p vertices we consider the closure of the cone of concentration matrices of G. The extreme rays of this cone, and their associated ranks, have applications in maximum likelihood estimation for the undirected Gaussian graphical model associated to G. Consequently, the extreme ranks of this cone have been well-studied. Yet, there are few graph classes for which all the possible extreme ranks are known. We show that the facet-normals of the cut polytope of G can serve to identify extreme rays of this nonpolyhedral cone. We see that for graphs without K5 minors each facet-normal of the cut polytope identifies an extreme ray in the cone, and we determine the rank of this extreme ray. When the graph is also series-parallel, we find that all possible extreme ranks arise in this fashion, thereby extending the collection of graph classes for which all the possible extreme ranks are known.

Une carte est le plongement d'un graphe dans une surface, à un homéomorphisme près. Ainsi, une carte est un objet topologique énumérable, en fonction du nombre de ses sommets, de ses arêtes et de ses faces. Les cartes admettent des symétries internes qui rendent leur énumération difficile. On n'envisage dans ce travail que l'énumération des cartes pointées, le pointage supprimant toutes les symétries. Le nombre exact de cartes pointées sur une surface donnée n'est connu que pour les surfaces de petit genre, comme la sphère (genre 0), le tore ou le plan projectif (genre 1). En effet, la complexité des méthodes de calcul de ces nombres augmente rapidement avec le genre des surfaces. Un travail important de cette thèse a été de convertir l'une de ces méthodes de calcul en une preuve de l'existence d'une structure commune à toutes les séries génératrices de cartes pointées de genre non nul. Pour chaque surface orientable, on réduit le problème à la détermination d'un polynôme, dont le degré est majoré par une fonction simple du genre de la surface. Un résultat analogue est obtenu pour les cartes pointées sur les surfaces non orientables. Des conséquences pratiques et une implantation logicielle de tous ces résultats sont décrites. De nouvelles formules explicites d'énumération sont données. Indépendamment, une bijection géométrique nouvelle est exposée, entre certaines cartes 2-coloriables et les partitions de polygones, énumérées par les nombres de Schröder.

L'idée directrice de ce travail est de montrer que bon nombre de requêtes peuvent être exprimées comme une navigation dans des graphes.

The capacity of a directed hypergraph is a particular numerical quantity associated with a hypergraph. It is of interest because of certain important connections to longstanding conjectures in theoretical computer science related to fast matrix multiplication and perfect hashing as well as various longstanding conjectures in extremal combinatorics. We give an overview of the concept of the capacity of a hypergraph and survey a few basic results regarding this quantity. Furthermore, we discuss the Lovász number of an undirected graph, which is known to upper bound the capacity of the graph (and in practice appears to be the best such general purpose bound). We then elaborate on some attempted generalizations/modifications of the Lovász number to undirected hypergraphs that we have tried. It is not currently known whether these attempted generalizations/modifications upper bound the capacity of arbitrary hypergraphs. An important method for proving lower bounds on hypergraph capacity is to exhibit a large independent set in a strong power of the hypergraph. We examine methods for this and show a barrier to attempts to usefully generalize certain of these methods to hypergraphs. We then look at cap sets: independent sets in powers of a certain hypergraph. We examine certain structural properties of them with the hope of finding ones that allow us to prove upper bounds on their size. Finally, we consider two interesting generalizations of capacity and use one of them to formulate several conjectures about connections between cap sets and sunflower-free sets.

The Poincare-Miranda Theorem is a topological result about the existence of a zero of a function under particular boundary conditions. In this thesis, we explore proofs of the Poincare-Miranda Theorem that are discrete in nature - that is, they prove a continuous result using an intermediate lemma about discrete objects. We explain a proof by Tkacz and Turzanski that proves the Poincare-Miranda theorem via the Steinhaus Chessboard Theorem, involving colorings of partitions of n-dimensional cubes. Then, we develop a new proof of the Poincare-Miranda Theorem that relies on a polytopal generalization of Sperner's Lemma of Deloera - Peterson - Su. Finally, we extend these discrete ideas to attempt to prove the existence of a zero with the boundary condition of Morales.