Spelling suggestions: "subject:"discrete mathematics"" "subject:"iscrete mathematics""
101 |
A Combinatorial Miscellany: Antipodes, Parking Cars, and Descent Set PowersHapp, Alexander Thomas 01 January 2018 (has links)
In this dissertation we first introduce an extension of the notion of parking functions to cars of different sizes. We prove a product formula for the number of such sequences and provide a refinement using a multi-parameter extension of the Abel--Rothe polynomial. Next, we study the incidence Hopf algebra on the noncrossing partition lattice. We demonstrate a bijection between the terms in the canceled chain decomposition of its antipode and noncrossing hypertrees. Thirdly, we analyze the sum of the 𝑟th powers of the descent set statistic on permutations and how many small prime factors occur in these numbers. These results depend upon the base 𝑝 expansion of both the dimension and the power of these statistics. Finally, we inspect the ƒ-vector of the descent polytope DPv, proving a maximization result using an analogue of the boustrophedon transform.
|
102 |
Polytopes Associated to Graph LaplaciansMeyer, Marie 01 January 2018 (has links)
Graphs provide interesting ways to generate families of lattice polytopes. In particular, one can use matrices encoding the information of a finite graph to define vertices of a polytope. This dissertation initiates the study of the Laplacian simplex, PG, obtained from a finite graph G by taking the convex hull of the columns of the Laplacian matrix for G. The Laplacian simplex is extended through the use of a parallel construction with a finite digraph D to obtain the Laplacian polytope, PD.
Basic properties of both families of simplices, PG and PD, are established using techniques from Ehrhart theory. Motivated by a well-known conjecture in the field, our investigation focuses on reflexivity, the integer decomposition property, and unimodality of Ehrhart h*-vectors of these polytopes. A systematic investigation of PG for trees, cycles, and complete graphs is provided, which is enhanced by an investigation of PD for cyclic digraphs. We form intriguing connections with other families of simplices and produce G and D such that the h*-vectors of PG and PD exhibit extremal behavior.
|
103 |
Lattice Simplices: Sufficiently ComplicatedDavis, Brian 01 January 2019 (has links)
Simplices are the "simplest" examples of polytopes, and yet they exhibit much of the rich and subtle combinatorics and commutative algebra of their more general cousins. In this way they are sufficiently complicated --- insights gained from their study can inform broader research in Ehrhart theory and associated fields.
In this dissertation we consider two previously unstudied properties of lattice simplices; one algebraic and one combinatorial. The first is the Poincar\'e series of the associated semigroup algebra, which is substantially more complicated than the Hilbert series of that same algebra. The second is the partial ordering of the elements of the fundamental parallelepiped associated to the simplex.
We conclude with a proof-of-concept for using machine learning techniques in algebraic combinatorics. Specifically, we attempt to model the integer decomposition property of a family of lattice simplices using a neural network.
|
104 |
The Linear Cutwidth and Cyclic Cutwidth of Complete n-Partite GraphsCreswell, Stephanie A 01 June 2014 (has links)
The cutwidth of different graphs is a topic that has been extensively studied. The basis of this paper is the cutwidth of complete n-partite graphs. While looking at the cutwidth of complete n-partite graphs, we strictly consider the linear embedding and cyclic embedding. The relationship between the linear cutwidth and the cyclic cutwidth is discussed and used throughout multiple proofs of different cases for the cyclic cutwidth. All the known cases for the linear and cyclic cutwidth of complete bipartite, complete tripartite, and complete n-partite graphs are highlighted.
The main focus of this paper is to expand on the cyclic cutwidth of complete tripartite graphs. Using the relationship of the linear cutwidth and cyclic cutwidth of any graph, we find a lower bound and an upper bound for the cyclic cutwidth of complete tripartite graph K_(r,r,pr) where r is odd and p is a natural number. Throughout this proof there are two cases that develop, p even and p odd. Within each case we have to consider the cuts of multiple regions to find the maximum cut of the cyclic embedding. Once all regions within each case are considered, we discover that the upper and lower bounds are equivalent. This discovery of the cyclic cutwidth of complete tripartite graph K_(r,r,pr) where r is odd and p is a natural number results in getting one step closer to finding the cyclic cutwidth of any complete tripartite graph K_(r,s,t).
|
105 |
Ádám's Conjecture and Arc Reversal ProblemsSalas, Claudio D 01 June 2016 (has links)
A. Ádám conjectured that for any non-acyclic digraph D, there exists an arc whose reversal reduces the total number of cycles in D. In this thesis we characterize and identify structure common to all digraphs for which Ádám's conjecture holds. We investigate quasi-acyclic digraphs and verify that Ádám's conjecture holds for such digraphs. We develop the notions of arc-cycle transversals and reversal sets to classify and quantify this structure. It is known that Ádám's conjecture does not hold for certain infinite families of digraphs. We provide constructions for such counterexamples to Ádám's conjecture. Finally, we address a conjecture of Reid [Rei84] that Ádám's conjecture is true for tournaments that are 3-arc-connected but not 4-arc-connected.
|
106 |
Tutte-Equivalent MatroidsRocha, Maria Margarita 01 September 2018 (has links)
We begin by introducing matroids in the context of finite collections of vectors from a vector space over a specified field, where the notion of independence is linear independence. Then we will introduce the concept of a matroid invariant. Specifically, we will look at the Tutte polynomial, which is a well-defined two-variable invariant that can be used to determine differences and similarities between a collection of given matroids. The Tutte polynomial can tell us certain properties of a given matroid (such as the number of bases, independent sets, etc.) without the need to manually solve for them. Although the Tutte polynomial gives us significant information about a matroid, it does not uniquely determine a matroid. This thesis will focus on non-isomorphic matroids that have the same Tutte polynomial. We call such matroids Tutte-equivalent, and we will study the characteristics needed for two matroids to be Tutte-equivalent. Finally, we will demonstrate methods to construct families of Tutte-equivalent matroids.
|
107 |
Pascal's Triangle, Pascal's Pyramid, and the Trinomial TriangleSaucedo, Antonio, Jr. 01 June 2019 (has links)
Many properties have been found hidden in Pascal's triangle. In this paper, we will present several known properties in Pascal's triangle as well as the properties that lift to different extensions of the triangle, namely Pascal's pyramid and the trinomial triangle. We will tailor our interest towards Fermat numbers and the hockey stick property. We will also show the importance of the hockey stick properties by using them to prove a property in the trinomial triangle.
|
108 |
3-Maps And Their GeneralizationsMcCall, Kevin J 01 January 2018 (has links)
A 3-map is a 3-region colorable map. They have been studied by Craft and White in their paper 3-maps. This thesis introduces topological graph theory and then investigates 3-maps in detail, including examples, special types of 3-maps, the use of 3-maps to find the genus of special graphs, and a generalization known as n-maps.
|
109 |
Computational Circle Packing: Geometry and Discrete Analytic Function TheoryOrick, Gerald Lee 01 May 2010 (has links)
Geometric Circle Packings are of interest not only for their aesthetic appeal but also their relation to discrete analytic function theory. This thesis presents new computational methods which enable additional practical applications for circle packing geometry along with providing a new discrete analytic interpretation of the classical Schwarzian derivative and traditional univalence criterion of classical analytic function theory. To this end I present a new method of computing the maximal packing and solving the circle packing layout problem for a simplicial 2-complex along with additional geometric variants and applications. This thesis also presents a geometric discrete Schwarzian quantity whose value is associated with the classical Schwarzian derivative. Following Hille, I present a characterization of circle packings as the ratio of two linearly independent solutions of a discrete difference equation taking the discrete Schwarzian as a parameter. This characterization then gives a discrete interpretation of the classical univalence criterion of Nehari in the circle packing setting.
|
110 |
Stabilité des relations de surclassement : aspects théoriques et pratiquesVENEZIANO, Thomas 10 September 2012 (has links) (PDF)
La mise en application d'une méthode d'aide multicritère à la décision requiert la fixation de nombreux paramètres dont les erreurs de précision peuvent avoir un impact non négligeable sur la recommandation fournie. Plus particulièrement, en présence d'un décideur novice, qui bien souvent construit ses préférences durant le processus d'aide à la décision, la détermination des paramètres ne peut être faite avec précision par questionnement direct et doit être incluse dans un processus d'élicitation de préférences tenant compte des difficultés et des imprécisions. Les travaux que nous défendons ici s'inscrivent au sein des méthodes d'aide à la décision, plus spécifiquement les méthodes de surclassement. Ils se concentrent autour de la notion de stabilité, qui permet de caractériser la dépendance des relations de surclassement aux paramètres de poids des critères. Une relation est alors dite stable lorsque celle-ci ne dépend pas d'une fixation précise de ces paramètres, mais uniquement de leur préordre. Après un bref état de l'art, nous étudions en détail la notion de stabilité et en déduisons des contraintes mathématiques permettant l'élicitation de jeux de poids des critères maximisant la stabilité et compatibles avec un ensemble d'informations préférentielles fournies par un décideur. Puis, nous définissons un protocole d'élicitation des paramètres, que nous testons avec divers décideurs afin d'en montrer la validé.
|
Page generated in 0.1936 seconds