<p>Studying properties of random polynomials has marked a shift in algebraic geometry. Instead of worst-case analysis, which often leads to overly pessimistic perspectives, randomness helps perform average-case analysis, and thus obtain a more realistic view. Also, via Erdos' astonishing 'probabilistic method', one can potentially obtain deterministic results by introducing randomness into a question that apriori had nothing to do with randomness. </p> <p><br></p> <p>In this thesis, we study topological questions in real algebraic geometry, o-minimal geometry and random algebraic geometry, with motivation from incidence combinatorics. Specifically, we prove results along two different threads:</p> <p><br></p> <p>1. Topology of semi-algebraic and definable (over any o-minimal structure over R) sets, in both deterministic and random settings.</p><p>2. Topology of random hypersurface arrangements. In this case, we also prove a result that could be of independent interest in random graph theory.</p> <p><br></p> <p>Towards the first thread, motivated by applications in o-minimal incidence combinatorics, we prove bounds (both deterministic and random) on the topological complexity (as measured by the Betti numbers) of general definable hypersurfaces restricted to algebraic sets. Given any sequence of hypersurfaces, we show that there exists a definable hypersurface G, and a sequence of polynomials, such that each manifold in the sequence of hypersurfaces appears as a component of G restricted to the zero set of some polynomial in the sequence of polynomials. This shows that the topology of the intersection of a definable hypersurface and an algebraic set can be made <i>arbitrarily pathological</i>. On the other hand, we show that for random polynomials, the Betti numbers of the restriction of the zero set of a random polynomial to any definable set deviates from a Bezout-type bound with <i>bounded probability</i>.</p> <p><br></p> <p>Progress in o-minimal incidence combinatorics has lagged behind the developments in incidence combinatorics in the algebraic case due to the absence of an o-minimal version of the Guth-Katz <i>polynomial partitioning</i> theorem, and the first part of our work explains why this is so difficult. However, our average result shows that if we can prove that the measure of the set of polynomials which satisfy a certain property necessary for polynomial partitioning is suitably bounded from below, by the <i>probabilistic method</i>, we get an o-minimal polynomial partitioning theorem. This would be a tremendous breakthrough and would enable progress on multiple fronts in model theoretic combinatorics. </p> <p><br></p> <p>Along the second thread, we have studied the average Betti numbers of <i>random hypersurface arrangements</i>. Specifically, we study how the average Betti numbers of a finite arrangement of random hypersurfaces grows in terms of the degrees of the polynomials in the arrangement, as well as the number of polynomials. This is proved using a random Mayer-Vietoris spectral sequence argument. We supplement this result with a better bound on the average Betti numbers when one considers an <i>arrangement of quadrics</i>. This question turns out to be equivalent to studying the expected number of connected components of a certain <i>random graph model</i>, which has not been studied before, and thus could be of independent interest. While our motivation once again was incidence combinatorics, we obtained the first bounds on the topology of arrangements of random hypersurfaces, with an unexpected bonus of a result in random graphs.</p>

If <i>E</i> is an exterior algebra on a finite dimensional vector space and <i>M</i> is a graded <i>E</i>-module, the relationship between the resonance varieties of <i>M</i> and the minimal free resolution of <i>M </i>is studied. In the context of Orlik–Solomon algebras, we give a condition under which elements of the second resonance variety can be obtained. We show that the resonance varieties of a general <i>M</i> are invariant under taking syzygy modules up to a shift. As corollary, it is shown that certain points in the resonance varieties of <i>M</i> can be determined from minimal syzygies of a special form, and we define syzygetic resonance varieties to be the subvarieties consisting of such points. The (depth one) syzygetic resonance varieties of a square-free module <i>M</i> over <i>E</i> are shown to be subspace arrangements whose components correspond to graded shifts in the minimal free resolution of <i>_SM</i>, the square-free module over a commutative polynomial ring <i>S </i>corresponding to <i>M</i>. Using this, a lower bound for the graded Betti numbers of the square-free module<i> M</i> is given. As another application, it is shown that the minimality of certain syzygies of Orlik–Solomon algebras yield linear subspaces of their (syzygetic) resonance varieties and lower bounds for their graded Betti numbers.

<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.

Thesis (PhD)--Stellenbosch University, 2015. / ENGLISH ABSTRACT : In this thesis, a number of combinatorial objects are enumerated. Du and Yin as well as Shin and Zeng (by a different approach) proved an elegant formula for the number of labelled trees with respect to a given in degree sequence, where each edge is oriented from a vertex of lower label towards a vertex of higher label. We refine their result to also take the number of sources (vertices of in degree 0) or sinks (vertices of out degree 0) into account. We find formulas for the mean and variance of the number of sinks or sources in these trees. We also obtain a differential equation and a functional equation satisfied by the generating function for these trees. Analogous results for labelled trees with two marked vertices, related to functional digraphs, are also established. We extend the work to count reachable vertices, sinks and leaf sinks in these trees. Among other results, we obtain a counting formula for the number of labelled trees on n vertices in which exactly k vertices are reachable from a given vertex v and also the average number of vertices that are reachable from a specified vertex in labelled trees of order n. In this dissertation, we also enumerate certain families of set partitions and related tree-like structures. We provide a proof for a formula that counts connected cycle-free families of k set partitions of {1, . . . , n} satisfying a certain coherence condition and then establish a bijection between these families and the set of labelled free k-ary cacti with a given vertex-degree distribution. We then show that the formula also counts coloured Husimi graphs in which there are no blocks of the same colour that are incident to one another. We extend the work to count coloured oriented cacti and coloured cacti. Noncrossing trees and related tree-like structures are also considered in this thesis. Specifically, we establish formulas for locally oriented noncrossing trees with a given number of sources and sinks, and also with given indegree and outdegree sequences. The work is extended to obtain the average number of reachable vertices in these trees. We then generalise the concept of noncrossing trees to find formulas for the number of noncrossing Husimi graphs, cacti and oriented cacti. The study is further extended to find formulas for the number of bicoloured noncrossing Husimi graphs and the number of noncrossing connected cycle-free pairs of set partitions. / AFRIKAANSE OPSOMMING : In hierdie tesis word ’n aantal kombinatoriese objekte geenumereer. Du en Yin asook Shin en Zeng (deur middel van ’n ander benadering) het ’n elegante formule vir die aantal geëtiketteerde bome met betrekking tot ’n gegewe ingangsgraadry, waar elke lyn van die nodus met die kleiner etiket na die nodus met die groter etiket toe georiënteer word. Ons verfyn hul resultaat deur ook die aantal bronne (nodusse met ingangsgraad 0) en putte (nodusse met uitgangsgraad 0) in ag te neem. Ons vind formules vir die gemiddelde en variansie van die aantal putte of bronne in hierdie bome. Ons bepaal verder ’n differensiaalvergelyking en ’n funksionaalvergelyking wat deur die voortbringende funksie van hierdie bome bevredig word. Analoë resultate vir geëtiketteerde bome met twee gemerkte nodusse (wat verwant is aan funksionele digrafieke), is ook gevind. Ons gaan verder voort deur ook bereikbare nodusse, bronne en putte in hierdie bome at te tel. Onder andere verkry ons ’n formule vir die aantal geëtiketteerde bome met n nodusse waarin presies k nodusse vanaf ’n gegewe nodus v bereikbaar is asook die gemiddelde aantal nodusse wat bereikbaar is vanaf ’n gegewe nodus. Ons enumereer in hierdie tesis verder sekere families van versamelingsverdelings en soortgelyke boom-vormige strukture. Ons gee ’n bewys vir ’n formule wat die aantal van samehangende siklus-vrye families van k versamelingsverdelings op {1, . . . , n} wat ’n sekere koherensie-vereiste bevredig, en ons beskryf ’n bijeksie tussen hierdie familie en die versameling van geëtiketteerde vrye k-êre kaktusse met ’n gegewe nodus-graad-verdeling. Ons toon ook dat hierdie formule ook gekleurde Husimi-grafieke tel waar blokke van dieselfde kleur nie insident met mekaar mag wees nie. Ons tel verder ook gekleurde georiënteerde kaktusse en gekleurde kaktusse. Nie-kruisende bome en soortgelyke boom-vormige strukture word in hierdie tesis ook beskou. On bepaal spesifiek formules vir lokaal georiënteerde nie-kruisende bome wat ’n gegewe aantal bronne en putte het asook nie-kruisende bome met gegewe ingangs- en uitgangsgraadrye. Ons gaan voort deur die gemiddelde aantal bereikbare nodusse in hierdie bome te bepaal. Ons veralgemeen dan die konsep van nie-kruisende bome en vind formules vir die aantal nie-kruisende Husimi-grafieke, kaktusse en georiënteerde kaktusse. Laastens vind ons ’n formule vir die aantaal tweegekleurde nie-kruisende Husimi-grafieke en die aantal nie-kruisende samehangende siklus-vrye pare van versamelingsverdelings.

An artinian standard graded algebra has the weak Lefschetz property if the multiplication by a general linear form induces maps of maximal rank between consecutive degree components. It has the strong Lefschetz property if the multiplication by powers of a general linear form also induce maps of maximal rank between the appropriate degree components. These properties are mainly studied for the constraints they place, when present, on the Hilbert series of the algebra. While the majority of research on the Lefschetz properties has focused on characteristic zero, we primarily consider the presence of the properties in positive characteristic. We study the Lefschetz properties by considering the prime divisors of determinants of critical maps. First, we consider monomial complete intersections in a finite number of variables. We provide two complements to a result of Stanley. We next consider monomial almost complete intersections in three variables. We connect the characteristics in which the weak Lefschetz property fails with the prime divisors of the signed enumeration of lozenge tilings of a punctured hexagon. Last, we study how perturbations of a family of monomial algebras can change or preserve the presence of the Lefschetz properties. In particular, we introduce a new strategy for perturbations rooted in techniques from algebraic geometry.

In this dissertation we will look at properties of two different posets from different perspectives. The first poset is the Rees product of the face lattice of the n-cube with the chain. Specifically we study the Möbius function of this poset. Our proof techniques include straightforward enumeration and a bijection between a set of labeled augmented skew diagrams and barred signed permutations which label the maximal chains of this poset. Because the Rees product of this poset is Cohen-Macaulay, we find a basis for the top homology group and a representation of the top homology group over the symmetric group both indexed by the set of labeled augmented skew diagrams. We also show that the Möbius function of the Rees product of a graded poset with the t-ary tree and the Rees product of its dual with the t-ary tree coincide. We discuss labelings for Rees and Segre products in general, particularly the Rees product of the face lattice of a polytope with the chain. We also look at cases where the Möbius function of a poset is equal to the permanent of a matrix and we consider local h-vectors for the barycentric subdivision of the n-cube. In each section we state open conjectures. The second poset in this dissertation is the Dowling lattice. In particular we look at the k = 1 case, that is, the partition lattice. We study inequalities on the flag vector of the partition lattice via a weighted boustrophedon transform and determine a more generalized version for the Dowling lattice. We generalize a determinantal formula of Niven and conclude with conjectures and avenues of study.

Ce travail porte sur les séries à coefficients entiers positifs, sur les séries N-rationnelles et est centré autour de deux types de questions : le problème de la hauteur d'étoile et l'étude des propriétés des distributions de longueurs des codes. On étudie le problème de la hauteur d'étoile de séries rationnelles particulières : les séries N-rationnelles en une variable. On caractérise de différentes façons les séries N-rationnelles qui sont de hauteur d'étoile 1, et on donne un critère permettant de décider de la hauteur d'étoile d'une classe importante de séries N-rationnelles en une variable. L'étude de la hauteur d'étoile des séries N-rationnelles en une variable repose sur l'utilisation des propriétés de leurs représentations par des matrices. On établit, en particulier, à partir d'un résultat d'Handelman, une caractérisation du rayon spectral d'une matrice compagnon irréductible à coefficients entiers positifs. On étudie, ensuite, les distributions de longueurs des codes circulaires et des codes préfixes. On prouve trois nouveaux résultats concernant les codes circulaires. On généralise, dans plusieurs directions, la caractérisation des distributions de longueurs des codes circulaires établie dans le cas d'un alphabet fini par Schützenberger. D'une part, on remplace l'alphabet fini par un alphabet quelconque dont les éléments ont des poids, ce qui permet d'étendre le résultat à deux distributions de longueurs. D'autre part, on restreint les conditions, ce qui permet d'établir la décidabilité dans le cas d'une distribution finie. On donne une nouvelle formulation de cette caractérisation. Ce résultat, établi par des méthodes combinatoires, met en évidence la décidabilité dans le cas d'une distribution finie. On établit une condition nécessaire et suffisante pour qu'une suite d'entiers positifs soit la distribution de longueur d'un code circulaire maximal sur un alphabet fini. Enfin, on met en évidence les liens entre les séries génératrices des codes préfixes rationnels et une classe de séries N-rationnelles : les DOL-séries. On donne une condition suffisante pour qu'une suite N-rationnelle soit la distribution de longueurs d'un code rationnel préfixe maximal sur un alphabet à k lettres.