Spelling suggestions: "subject:"discrete mathematics"" "subject:"iscrete mathematics""
21 |
Strongly Eutactic Lattices From Vertex Transitive GraphsXin, Yuxin 01 January 2019 (has links)
In this thesis, we provide an algorithm for constructing strongly eutactic lattices from vertex transitive graphs. We show that such construction produces infinitely many strongly eutactic lattices in arbitrarily large dimensions. We demonstrate our algorithm on the example of the famous Petersen graph using Maple computer algebra system. We also discuss some additional examples of strongly eutactic lattices obtained from notable vertex transitive graphs. Further, we study the properties of the lattices generated by product graphs, complement graphs, and line graphs of vertex transitive graphs. This thesis is based on the research paper written by the author jointly with L. Fukshansky, D. Needell and J. Park.
|
22 |
Fibonomial Tilings and Other Up-Down TilingsBennett, Robert 01 January 2016 (has links)
The Fibonomial coefficients are a generalization of the binomial coefficients with a rather nice combinatorial interpretation. While the ordinary binomial coefficients count lattice paths in a grid, the Fibonomial coefficients count the number of ways to draw a lattice path in a grid and then Fibonacci-tile the regions above and below the path in a particular way. We may forgo a literal tiling interpretation and, instead of the Fibonacci numbers, use an arbitrary function to count the number of ways to "tile" the regions of the grid delineated by the lattice path. When the function is a combinatorial sequence such as the Lucas numbers or the q-numbers, the total number of "tilings" is some multiple of a generalized binomial coefficient corresponding to the sequence chosen.
|
23 |
Realizing the 2-AssociahedronTierney, Patrick N 01 January 2016 (has links)
The associahedron has appeared in numerous contexts throughout the field of mathematics. By representing the associahedron as a poset of tubings, Michael Carr and Satyan L. Devadoss were able to create a gener- alized version of the associahedron in the graph-associahedron. We seek to create an alternative generalization of the associahedron by considering a particle-collision model. By extending this model to what we dub the 2- associahedron, we seek to further understand the space of generalizations of the associahedron.
|
24 |
Exploring the On-line Partitioning of Posets ProblemRosenbaum, Leah F. 09 March 2012 (has links)
One question relating to partially ordered sets (posets) is that of partitioning or dividing the poset's elements into the fewest number of chains that span the poset. In 1950, Dilworth established that the width of the poset - the size of the largest set composed only of incomparable elements - is the minimum number of chains needed to partition that poset. Such a bound in on-line partitioning has been harder to establish, and work has evalutated classes of posets based on their width. This paper reviews the theorems that established val(2)=5 and illustrates them with examples. It also covers some of the work on establishing bounds for on-line partitioning with the Greedy Algorithm. The paper concludes by contributing a bound on incomparable elements in graded, (t+t)-free, finite width posets.
|
25 |
Reed's Conjecture and Cycle-Power GraphsSerrato, Alexa 01 January 2014 (has links)
Reed's conjecture is a proposed upper bound for the chromatic number of a graph. Reed's conjecture has already been proven for several families of graphs. In this paper, I show how one of those families of graphs can be extended to include additional graphs and also show that Reed's conjecture holds for a family of graphs known as cycle-power graphs, and also for their complements.
|
26 |
Επίλυση προβλημάτων στα διακριτά μαθηματικάΧριστόπουλος, Κωνσταντίνος 29 August 2011 (has links)
Στην παρούσα εργασία θα παρουσιαστούν διάφορα προβλήματα, με την επίλυσή τους, τα οποία ανήκουν στο πεδίο των Διακριτών Μαθηματικών. Πιο συγκεκριμένα στο πρώτο κεφάλαιο θα δούμε διάφορα προβλήματα αναδρομής όπου κάποια από αυτά θα είναι παραλλαγές γνωστών προβλημάτων (π.χ.: Ο ΠΥΡΓΟΣ ΤΟΥ HANOI) των οποίων οι (γνωστές) λύσεις θα μας βοηθάνε για να αποδεικνύουμε κάθε φορά αυτό που θέλουμε. Στο δεύτερο κεφάλαιο θα ασχοληθούμε με προβλήματα και ασκήσεις αθροισμάτων, τα οποία είναι παντού στα μαθηματικά, γι'αυτό χρησιμοποιούμε βασικά εργαλεία για να τα λύσουμε, αναπτύσσοντας γενικές τεχνικές έτσι ώστε η διαδικασία να είναι φιλική προς τον αναγνώστη.
Στη συνέχεια στο τρίτο κεφάλαιο θα συναντήσουμε ασκήσεις οι οποίες αφορούν τις ακέραιες συναρτήσεις. Οι ακέραιοι αριθμοί αποτελούν τη ραχοκοκαλιά των Διακριτών Μαθηματικών, και εμείς συχνά χρειάζεται να μετατρέπουμε κλάσματα ή αυθαίρετους πραγματικούς αριθμούς σε ακέραιους. Ο στόχος λοιπόν αυτού του κεφαλαίου είναι να αποκτήσουμε οικειότητα και άνεση με τέτοιου είδους μετατροπές μέσα από τις ασκήσεις και να μάθουμε μερικές από τις αξιοσημείωτες ιδιότητες τους.
Μέσα από τις ασκήσεις του τέταρτου κεφαλαίου γίνεται μια εισαγωγή στη θεωρία αριθμών ένα σημαντικό κλάδο των μαθηματικών που ασχολείται με τις ιδιότητες των ακεραίων. Τέλος στο κεφάλαιο 5 θα συναντήσουμε ασκήσεις και προβλήματα τα οποία βασίζονται στη μελέτη των διωνυμικών συντελεστών οι οποίοι είναι πολύ σημαντικοί στις εφαρμογές και επίσης πιo εύκολοι να τους χειριστούμε σε σύγκριση με άλλες ποσότητες των προηγούμενων κεφαλαίων. / -
|
27 |
On Minimal Non-(2, 1)-Colorable GraphsBosse, Ruth January 2017 (has links)
A graph is (2, 1)-colorable if it allows a partition of its vertices into two classes such that both induce graphs with maximum degree at most one. A non-(2, 1)-colorable graph is minimal if all proper subgraphs are (2, 1)-colorable. We prove that such graphs are 2-edge-connected and that every edge sits in an odd cycle. Furthermore, we show properties of edge cuts and particular graphs which are no induced subgraphs. We demonstrate that there are infinitely many minimal non-(2, 1)-colorable graphs, at least one of order n for all n ≥ 5. Moreover, we present all minimal non-(2, 1)- colorable graphs of order at most seven. We consider the maximum degree of minimal non-(2, 1)-colorable graphs and show that it is at least four but can be arbitrarily large. We prove that the average degree is greater than 8/3 and give sufficient properties for graphs with average degree greater than 14/5. We conjecture that all minimal non-(2, 1)-colorable graphs fulfill these properties.
|
28 |
Gamma-Switchable 2-Colourings of (m,n)-Mixed GraphsKidner, Arnott 31 August 2021 (has links)
A $(m,n)$-mixed graph is a mixed graph whose edges are assigned one of $m$ colours, and whose arcs are assigned one of $n$ colours. Let $G$ be a $(m,n)$-mixed graph and $\pi=(\alpha,\beta,\gamma_1,\gamma_2,\ldots,\gamma_n)$ be a $(n+2)$-tuple of permutations from $S_m \times S_n \times S_2^n$. We define \emph{switching at a vertex $v$ with respect to $\pi$} as follows. Replace each edge $vw$ of colour $\phi$ by an edge $vw$ of colour $\alpha(\phi)$, and each arc $vx$ of colour $\phi$ by an arc $\gamma_\phi(vx)$ of colour $\beta(\phi)$.
In this thesis, we study the complexity of the question: ``Given a $(m,n)$-mixed graph $G$, is there a sequence of switches at vertices of $G$ with respect to the fixed group $\Gamma$ so that the resulting $(m,n)$-mixed graph admits a homomorphism to some $(m,n)$-mixed graph on $2$ vertices?''
We show the following: (1) When restricted to $(m,0)$-mixed graphs $H$ on at most $2$ vertices, the $\Gamma$-switchable homomorphism decision problem is solvable in polynomial time; (2) for each bipartite $(0,n)$-mixed graph $H$, there is a bipartite $(2n,0)$-mixed graph such that the respective $\Gamma$-switchable homomorphism decision problems are polynomially equivalent; (3) For all $(m,n)$-mixed graphs and groups, when $H$ has at most $2$ vertices, the $\Gamma$-switchable homomorphism decision problem is polynomial time solvable; (4) For a yes-instance of the $\Gamma$-switchable homomorphism problem for $(m,0)$-mixed graphs, we can find in quadratic time a sequence of switches on $G$ such that the resulting $(m,0)$-mixed graph admits a homomorphism to $H$.
By proving (1)-(4), we show that the $\Gamma$-switchable $2$-colouring problem for $(m,n)$-mixed graphs is solvable in polynomial time for all finite permutation groups $\Gamma$ and provide a step towards a dichotomy theorem for the complexity of the $\Gamma$-switchable homomorphism decision problem. / Graduate
|
29 |
An extremal construction for (5,24)-multigraphsPersson Eriksson, William January 2022 (has links)
In the mid 1900s the area of extremal graph theory took its first propersteps with the proof of Turán’s theorem. In 1963 Pál Erdős asked for an extension of this fundamental result regarding (n, s, q)-graphs; graphs on n vertices in which any s-set of vertices spans at most q edges, and multiple edges are allowed; and raised the question of determining ex(n, s, q), the maximum number of edges spanning such a graph. More recently, Mubayi and Terry looked at the problem of determining the maximum productof the edges in (n, s, q)-graphs. Their proof was further investigated by Day, Falgas-Ravry and Treglown who, in particular, settled a conjecture of Mubayi and Terry regarding the case (s, q) = (4, 6a+3), for a ∈ Z≥2. In this thesis we look at the case (s, q) = (5, 24), which is mentioned as an open problem at the end of the paper by Day, Falgas-Ravry and Treglown. A hypothetical extremal construction was provided by Victor Falgas-Ravry, and we prove it to be asymptotically optimal.
|
30 |
The place of discrete mathematics in the school curriculum: An analysis of preservice teachers' perceptions of the integration of discrete mathematics into secondary level coursesRivera-Marrero, Olgamary 05 May 2007 (has links)
The integration of discrete mathematics into the secondary school curriculum (grades 7-12) is an important consideration because the mathematical area is dynamic and interesting, providing students the development of mathematical thinking. Also, it provides for teachers the opportunity to develop innovative mathematics instruction. Since the publication of the document Curriculum and Evaluation Standards for School Mathematics (NCTM, 1989), it has been difficult to determine how many schools have integrated discrete mathematics as a separate or as an integrated course in the school mathematics curriculum. Moreover, the mathematics education research community has, for the most part, not focused on teachers' perceptions about teaching and learning discrete mathematics as an area of investigation.
Because of the lack of research in this area, the researcher investigated preservice secondary mathematics teachers' perceptions about discrete mathematics and their reactions to the integration of discrete mathematics into the school curriculum. The researcher purposely selected four preservice secondary teachers who were enrolled in a mathematics course in the fall of 2005. Various data sources were used to get a deep understanding of each participant, including selected coursework, an online survey, and interviews.
Results indicated that these preservice teachers perceive discrete mathematics as meaningful to students, as it emphasizes processes such as problem solving and mathematical thinking, and it provides opportunities to use innovative instruction. Because of this, the preservice teachers believe that discrete mathematics should be integrated in the school mathematics curriculum. In addition, several factors that affect the integration of discrete mathematics in the school were identified. These factors are the state curriculum and testing, the historical emphasis of algebra and calculus in the school curriculum, the National Council of Teachers of Mathematics (1989, 2000) Standards documents' views of discrete mathematics, teachers' views of discrete mathematics, the lack of knowledge of discrete mathematics, and the lack of materials and guidelines for teaching discrete mathematics. / Ph. D.
|
Page generated in 0.0992 seconds