Spelling suggestions: "subject:"discrete mathematics"" "subject:"iscrete mathematics""
41 |
Upset Paths and 2-Majority TournamentsAlshaikh, Rana Ali 01 June 2016 (has links)
In 2005, Alon, et al. proved that tournaments arising from majority voting scenarios have minimum dominating sets that are bounded by a constant that depends only on the notion of what is meant by a majority. Moreover, they proved that when a majority means that Candidate A beats Candidate B when Candidate A is ranked above Candidate B by at least two out of three voters, the tournament used to model this voting scenario has a minimum dominating set of size at most three. This result gives 2-majority tournaments some significance among all tournaments and motivates us to investigate when a given tournament can be considered a 2-majority tournament. In this thesis, we prove, among other things, that the presence of an upset path in a tournament allows us to conclude the tournament is realizable as a 2-majority tournament.
|
42 |
PLANAR GRAPHS, BIPLANAR GRAPHS AND GRAPH THICKNESSHearon, Sean M 01 December 2016 (has links)
A graph is planar if it can be drawn on a piece of paper such that no two edges cross. The smallest complete and complete bipartite graphs that are not planar are K5 and K{3,3}. A biplanar graph is a graph whose edges can be colored using red and blue such that the red edges induce a planar subgraph and the blue edges induce a planar subgraph. In this thesis, we determine the smallest complete and complete bipartite graphs that are not biplanar.
|
43 |
Analogues Between Leibniz's Harmonic Triangle and Pascal's Arithmetic TriangleJames, Lacey Taylor 01 June 2019 (has links)
This paper will discuss the analogues between Leibniz's Harmonic Triangle and Pascal's Arithmetic Triangle by utilizing mathematical proving techniques like partial sums, committees, telescoping, mathematical induction and applying George Polya's perspective. The topics presented in this paper will show that Pascal's triangle and Leibniz's triangle both have hockey stick type patterns, patterns of sums within shapes, and have the natural numbers, triangular numbers, tetrahedral numbers, and pentatope numbers hidden within. In addition, this paper will show how Pascal's Arithmetic Triangle can be used to construct Leibniz's Harmonic Triangle and show how both triangles relate to combinatorics and arithmetic through the coefficients of the binomial expansion. Furthermore, combinatorics plays an increasingly important role in mathematics, starting when students enter high school and continuing on into their college years. Students become familiar with the traditional arguments based on classical arithmetic and algebra, however, methods of combinatorics can vary greatly. In combinatorics, perhaps the most important concept revolves around the coefficients of the binomial expansion, studying and proving their properties, and conveying a greater insight into mathematics.
|
44 |
On Latin squares and avoidable arraysAndrén, Lina J. January 2010 (has links)
This thesis consists of the four papers listed below and a survey of the research area. I Lina J. Andrén: Avoiding (m, m, m)-arrays of order n = 2k II Lina J. Andrén: Avoidability of random arrays III Lina J. Andr´en: Avoidability by Latin squares of arrays with even order IV Lina J. Andrén, Carl Johan Casselgren and Lars-Daniel Öhman: Avoiding arrays of odd order by Latin squares Papers I, III and IV are all concerned with a conjecture by Häggkvist saying that there is a constant c such that for any positive integer n, if m ≤ cn, then for every n × n array A of subsets of {1, . . . , n} such that no cell contains a set of size greater than m, and none of the elements 1, . . . , n belongs to more than m of the sets in any row or any column of A, there is a Latin square L on the symbols 1, . . . , n such that there is no cell in L that contains a symbol that belongs to the set in the corresponding cell of A. Such a Latin square is said to avoid A. In Paper I, the conjecture is proved in the special case of order n = 2k . Paper III improves on the techniques of Paper I, expanding the proof to cover all arrays of even order. Finally, in Paper IV, similar methods are used together with a recoloring theorem to prove the conjecture for all orders. Paper II considers another aspect of the problem by asking to what extent way a deterministic result concerning the existence of Latin squares that avoid certain arrays can be used when the sets in the array are assigned randomly. / Denna avhandling inehåller de fyra nedan uppräknade artiklarna, samt en översikt av forskningsområdet. I Lina J. Andrén: Avoiding (m, m, m)-arrays of order n = 2k II Lina J. Andrén: Avoidability of random arrays III Lina J. Andrén: Avoidability by Latin squares of arrays with even order IV Lina J. Andrén, Carl Johan Casselgren and Lars-Daniel Öhman: Avoiding arrays of odd order by Latin squares Artikel I, III och IV behandlar en förmodan av Häggkvist, som säger att det finns en konstant c sådan att för varje positivt heltal n gäller att om m ≤ cn så finns för varje n × n array A av delmängder till {1, . . . ,n} sådan att ingen cell i A i innehåller fler än m symboler, och ingen symbol förekommer i fler än m celler i någon av raderna eller kolumnerna, så finns en latinsk kvadrat L sådan att ingen cell i L innehåller en symbol som förekommer i motsvarande cell i A. En sådan latinsk kvadrat sägs undvika A. Artikel I innehåller ett bevis av förmodan i specialfallet n = 2k. Artikel III använder och utökar metoderna i Artikel I till ett bevis av förmodan för alla latinska kvadrater av jämn ordning. Förmodan visas slutligen för samtliga ordningar i Artikel IV, där bevismetoden liknar den som finns i i Artikel I och III tillsammans med en omfärgningssats. Artikel II behandlar en annan aspekt av problemet genom att undersöka vad ett deterministiskt resultat om existens av latinska kvadrater som undviker en viss typ av array säger om arrayer där mängderna tilldelas slumpmässigt.
|
45 |
Deletion-Induced TriangulationsTaylor, Clifford T 01 January 2015 (has links)
Let d > 0 be a fixed integer and let A ⊆ ℝd be a collection of n ≥ d + 2 points which we lift into ℝd+1. Further let k be an integer satisfying 0 ≤ k ≤ n-(d+2) and assign to each k-subset of the points of A a (regular) triangulation obtained by deleting the specified k-subset and projecting down the lower hull of the convex hull of the resulting lifting. Next, for each triangulation we form the characteristic vector defined by Gelfand, Kapranov, and Zelevinsky by assigning to each vertex the sum of the volumes of all adjacent simplices. We then form a vector for the lifting, which we call the k-compound GKZ-vector, by summing all the characteristic vectors. Lastly, we construct a polytope Σk(A) ⊆ ℝ|A| by taking the convex hull of all obtainable k-compound GKZ-vectors by various liftings of A, and note that $\Sigma_0(\A)$ is the well-studied secondary polytope corresponding to A. We will see that by varying k, we obtain a family of polytopes with interesting properties relating to Minkowski sums, Gale transforms, and Lawrence constructions, with the member of the family with maximal k corresponding to a zonotope studied by Billera, Fillamen, and Sturmfels. We will also discuss the case k = d = 1, in which we can provide a combinatorial description of the vertices allowing us to better understand the graph of the polytope and to obtain formulas for the numbers of vertices and edges present.
|
46 |
Cycle lengths of θ-biased random permutationsShi, Tongjia 01 January 2014 (has links)
Consider a probability distribution on the permutations of n elements. If the probability of each permutation is proportional to θK, where K is the number of cycles in the permutation, then we say that the distribution generates a θ-biased random permutation. A random permutation is a special θ-biased random permutation with θ = 1. The mth moment of the rth longest cycle of a random permutation is Θ(nm), regardless of r and θ. The joint moments are derived, and it is shown that the longest cycles of a permutation can either be positively or negatively correlated, depending on θ. The mth moments of the rth shortest cycle of a random permutation is Θ(nm−θ/(ln n)r−1) when θ < m, Θ((ln n)r) when θ = m, and Θ(1) when θ > m. The exponent of cycle lengths at the 100qth percentile goes to q with zero variance. The exponent of the expected cycle lengths at the 100qth percentile is at least q due to the Jensen’s inequality, and the exact value is derived.
|
47 |
Upper and lower bounds on permutation codes of distance fourSawchuck, Natalie 30 December 2008 (has links)
A permutation array, represented by PA(n, d), is a subset of Sn such that any two distinct elements have a distance of at least d where d is the number of differing positions. We analyze the upper and lower bounds of permutation codes with distance equal to 4. An optimization problem on Young diagrams is used to improve the upper bound for almost all n while the lower bound is improved for small values of n by means of recursive construction methods.
|
48 |
Upper and lower bounds on permutation codes of distance fourSawchuck, Natalie 30 December 2008 (has links)
A permutation array, represented by PA(n, d), is a subset of Sn such that any two distinct elements have a distance of at least d where d is the number of differing positions. We analyze the upper and lower bounds of permutation codes with distance equal to 4. An optimization problem on Young diagrams is used to improve the upper bound for almost all n while the lower bound is improved for small values of n by means of recursive construction methods.
|
49 |
Upper and lower bounds on permutation codes of distance fourSawchuck, Natalie 30 December 2008 (has links)
A permutation array, represented by PA(n, d), is a subset of Sn such that any two distinct elements have a distance of at least d where d is the number of differing positions. We analyze the upper and lower bounds of permutation codes with distance equal to 4. An optimization problem on Young diagrams is used to improve the upper bound for almost all n while the lower bound is improved for small values of n by means of recursive construction methods.
|
50 |
Controllability and Observability of Linear Nabla Discrete Fractional SystemsZhoroev, Tilekbek 01 October 2019 (has links)
The main purpose of this thesis to examine the controllability and observability of the linear discrete fractional systems. First we introduce the problem and continue with the review of some basic definitions and concepts of fractional calculus which are widely used to develop the theory of this subject. In Chapter 3, we give the unique solution of the fractional difference equation involving the Riemann-Liouville operator of real order between zero and one. Additionally we study the sequential fractional difference equations and describe the way to obtain the state-space repre- sentation of the sequential fractional difference equations. In Chapter 4, we study the controllability and observability of time-invariant linear nabla fractional systems.We investigate the time-variant case in Chapter 5 and we define the state transition matrix in fractional calculus. In the last chapter, the results are summarized and directions for future work are stated.
|
Page generated in 0.1189 seconds