First introduced by Forman in 1998, discrete Morse theory has become a standard tool in topological combinatorics. The main idea of discrete Morse theory is to pair cells in a cellular complex in a manner that permits cancellation via elementary collapses, reducing the complex under consideration to a homotopy equivalent complex with fewer cells. In chapter 1, we introduce the relevant background for discrete Morse theory. In chapter 2, we define a discrete Morse matching for a family of independence complexes that generalize the matching complexes of suitable "small" grid graphs. Using this matching, we determine the dimensions of the chain spaces for the resulting Morse complexes and derive bounds on the location of non-trivial homology groups. Furthermore, we determine the Euler characteristic for these complexes and prove that several of their homology groups are non-zero. In chapter 3, we introduce the notion of a homomorphism complex for partially ordered sets, placing particular emphasis on maps between chain posets and the Boolean algebras. We extend the notion of folding from general graph homomorphism complexes to the poset case, and we define an iterative discrete Morse matching for these Boolean complexes. We provide formulas for enumerating the number of critical cells arising from this matching as well as for the Euler characteristic. We end with a conjecture on the optimality of our matching derived from connections to 3-equal manifolds

There are four prominent product graphs in graph theory: Cartesian, strong, direct, and lexicographic. Of these four product graphs, the lexicographic product graph is the least studied. Lexicographic products are not commutative but still have some interesting properties. This paper begins with basic definitions of graph theory, including the definition of a graph, that are needed to understand theorems and proofs that come later. The paper then discusses the lexicographic product of digraphs, denoted $G \circ H$, for some digraphs $G$ and $H$. The paper concludes by proving a cancellation property for the lexicographic product of digraphs $G$, $H$, $A$, and $B$: if $G \circ H \cong A \circ B$ and $|V(G)| = |V(A)|$, then $G \cong A$. It also proves additional cancellation properties for lexicographic product digraphs and the author hopes the final result will provide further insight into tournaments.

Submitted by NAÍSA CAMILA GARCIA null (naisacamila@hotmail.com) on 2017-02-23T13:24:13Z No. of bitstreams: 1 Dissertação de Mestrado Naísa.pdf: 926270 bytes, checksum: e0ef770d876850618bb4fff10a0da639 (MD5) / Approved for entry into archive by LUIZA DE MENEZES ROMANETTO (luizamenezes@reitoria.unesp.br) on 2017-03-02T14:21:45Z (GMT) No. of bitstreams: 1 tosti_ncg_me_sjrp.pdf: 926270 bytes, checksum: e0ef770d876850618bb4fff10a0da639 (MD5) / Made available in DSpace on 2017-03-02T14:21:45Z (GMT). No. of bitstreams: 1 tosti_ncg_me_sjrp.pdf: 926270 bytes, checksum: e0ef770d876850618bb4fff10a0da639 (MD5) Previous issue date: 2017-02-17 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / O propósito deste trabalho é estudar alguns corpos abelianos, mais especificamente, as extensões reais maximais contidas nos corpos ciclotômicos de grau 8 e, os subcorpos dos corpos ciclotômicos Q(ζ_7) e Q(ζ_17). Em tais corpos, determinamos base integral, discriminante, grupo de Galois e construimos submódulos de posto máximo do anel dos inteiros algébricos com sua respectiva representação geométrica. Além disso, calculamos a densidade de centro destes reticulados. / The purpose of this work is to investigate some Abelian Number Fields, especifically the maximal extension contained in the cyclotomic fields of degree 8, and the subfields of the cyclotomic fields Q(ζ_7) and Q(ζ_17). In such fields, we compute: integral bases, discriminant, Galois group and submoduli with maximal rank in the ring of algebraic integers, its geometrical realization with the respective center density.

It is well documented that undergraduate students struggle with the more formal and abstract concepts of vector space theory in a first course on linear algebra. Some of these students continue on to classes in abstract algebra, where they learn about algebraic structures such as groups. It is clear to the seasoned mathematician that vector spaces are in fact groups, and so linear transformations are group homomorphisms with extra restrictions. This study explores the question of whether or not students see this connection as well. In addition, I probe the ways in which students’ stated understandings are the same or different across contexts, and how these differences may help or hinder connection making across domains. Students’ understandings are also briefly compared to those of mathematics professors in order to highlight similarities and discrepancies between reality and idealistic expectations. The data for this study primarily comes from clinical interviews with ten undergraduates and three professors. The clinical interviews contained multiple card sorts in which students expressed the connections they saw within and across the domains of linear algebra and abstract algebra, with an emphasis specifically on linear transformations and group homomorphisms. Qualitative data was analyzed using abductive reasoning through multiple rounds of coding and generating themes. Overall, I found that students ranged from having very few connections, to beginning to form connections once placed in the interview setting, to already having a well-integrated morphism schema across domains. A considerable portion of this paper explores the many and varied ways in which students succeeded and failed in making mathematically correct connections, using the language of research on analogical reasoning to frame the discussion. Of particular interest were the ways in which isomorphisms did or did not play a role in understanding both morphisms, how students did not regularly connect the concepts of matrices and linear transformations, and how vector spaces were not fully aligned with groups as algebraic structures.

In this thesis an algebraic structure, called real calculus, is used as a way to represent noncommutative manifolds in an algebraic setting. Several classical geometric concepts are defined for real calculi, such as metrics and affine connections, and real calculus homomorphisms are introduced. These homomorphisms are then used to define embeddings of real calculi representing manifolds, anda notion of minimal embedding is introduced. The motivating example of the thesis is the noncommutative torus as embedded into a localization of the noncommutative 3-sphere, where it is shown that the noncommutative torus is a minimal embedding of the noncommutative 3-sphere for certain perturbations of the standard metric.

Un graphe mixte est un graphe simple tel que un sous-ensemble des arêtes a une orientation. Pour entiers non négatifs j et k, un graphe mixte-(j,k) est un graphe mixte avec j types des arcs and k types des arêtes. La famille de graphes mixte-(j,k) contient graphes simple, (graphes mixte−(0,1)), graphes orienté (graphes mixte−(1,0)) and graphe coloré arête −k (graphes mixte−(0,k)).Un homomorphisme est un application sommet entre graphes mixte−(j,k) que tel les types des arêtes sont conservés et les types des arcs et leurs directions sont conservés. Le nombre chromatique−(j,k) d’un graphe mixte−(j,k) est le moins entier m tel qu’il existe un homomorphisme à une cible avec m sommets. Quand on observe le cas de (j,k) = (0,1), on peut déterminer ces définitions correspondent à les définitions usuel pour les graphes.Dans ce mémoire on etude le nombre chromatique−(j,k) et des paramètres similaires pour diverses familles des graphes. Aussi on etude les coloration incidence pour graphes and digraphs. On utilise systèmes de représentants distincts et donne une nouvelle caractérisation du nombre chromatique incidence. On define le nombre chromatique incidence orienté et trouves un connexion entre le nombre chromatique incidence orienté et le nombre chromatic du graphe sous-jacent. / A mixed graph is a simple graph in which a subset of the edges have been assigned directions to form arcs. For non-negative integers j and k, a (j,k)−mixed graph is a mixed graph with j types of arcs and k types of edges. The collection of (j,k)−mixed graphs contains simple graphs ((0,1)−mixed graphs), oriented graphs ((1,0)−mixed graphs) and k−edge- coloured graphs ((0,k)−mixed graphs).A homomorphism is a vertex mapping from one (j,k)−mixed graph to another in which edge type is preserved, and arc type and direction are preserved. The (j,k)−chromatic number of a (j,k)−mixed graph is the least m such that an m−colouring exists. When (j,k)=(0,1), we see that these definitions are consistent with the usual definitions of graph homomorphism and graph colouring.In this thesis we study the (j,k)−chromatic number and related parameters for different families of graphs, focussing particularly on the (1,0)−chromatic number, more commonly called the oriented chromatic number, and the (0,k)−chromatic number.In addition to considering vertex colourings, we also consider incidence colourings of both graphs and digraphs. Using systems of distinct representatives, we provide a new characterisation of the incidence chromatic number. We define the oriented incidence chromatic number and find, by way of digraph homomorphism, a connection between the oriented incidence chromatic number and the chromatic number of the underlying graph. This connection motivates our study of the oriented incidence chromatic number of symmetric complete digraphs.

Dans cette thèse, nous etudions deux principaux problèmes de la théorie des graphes: problème d’homomorphisme des graphes planaires (signés) et problème de cycle hamiltonien.Comme une extension du théorème des quatre couleurs, il est conjecturé([80], [41]) que chaque graphe signé cohérent planaire de déséquilibré-maille d+1(d>1) admet un homomorphisme à cube projective signé SPC(d) de dimension d. La question suivant étalés naturelle:Est-ce que SPC(d) une borne optimale de déséquilibré-maille d+1 pour tous les graphes signés cohérente planaire de déséquilibré-maille d+1?Au Chapitre 2, nous prouvons que: si (B,Ω) est un graphe signé cohérente dedéséquilibré-maille d qui borne la classe des graphes signés cohérents planaires de déséquilibré-maille d+1, puis |B| ≥2^{d−1}. Notre résultat montre que si la conjecture ci-dessus est vérifiée, alors le SPC(d) est une borne optimale à la fois en terme du nombre des sommets et du nombre de arêtes.Lorsque d=2k, le problème est équivalent aux problème des graphes:est-ce que PC(2k) une borne optimale de impair-maille 2k+1 pour P_{2k+1} (tous les graphes planaires de impair-maille au moins 2k+1)? Notez que les graphes K_4-mineur libres sont les graphes planaires, est PC(2k) aussi une borne optimale de impair-maille 2k+1 pour tous les graphes K_4-mineur libres de impair-maille 2k+1? La réponse est négative, dans[6], est donné une famille de graphes d’ordre O(k^2) que borne les graphes K_4-mineur libres de impair-maille 2k+1. Est-ce que la borne optimale? Au Chapitre 3, nous prouvons que: si B est un graphe de impair-maille 2k+1 qui borne tous les graphes K_4-mineur libres de impair-maille 2k+1, alors |B|≥(k+1)(k+2)/2. La conjonction de nos résultat et le résultat dans [6] montre que l’ordre O(k^2) est optimal. En outre, si PC(2k) borne P_{2k+1}, PC(2k) borne également P_{2r+1}(r>k).Cependant, dans ce cas, nous croyons qu’un sous-graphe propre de P(2k) serait suffisant à borner P_{2r+1}, alors quel est le sous-graphe optimal de PC2k) qui borne P_{2r+1}? Le premier cas non résolu est k=3 et r= 5. Dans ce cas, Naserasr [81] a conjecturé que le graphe Coxeter borne P_{11}. Au Chapitre 4, nous vérifions cette conjecture pour P_{17}.Au Chapitres 5, 6, nous étudions les problèmes du cycle hamiltonien. Dirac amontré en 1952 que chaque graphe d’ordre n est hamiltonien si tout sommet a un degré au moins n/2. Depuis, de nombreux résultats généralisant le théorème de Dirac sur les degré ont été obtenus. Une approche consiste à construire un cycle hamiltonien à partir d'un ensemble de sommets en contrôlant leur position sur le cycle. Dans cette thèse, nous considérons deux conjectures connexes. La première est la conjecture d'Enomoto: si G est un graphe d’ordre n≥3 et δ(G)≥n/2+1, pour toute paire de sommets x,y dans G, il y a un cycle hamiltonien C de G tel que dist_C(x,y)=n/2.Notez que l’ ́etat de degre de la conjecture de Enomoto est forte. Motivé par cette conjecture, il a prouvé, dans [32], qu’une paire de sommets peut être posé des distances pas plus de n/6 sur un cycle hamiltonien. Dans [33], les cas δ(G)≥(n+k)/2 sont considérés, il a prouvé qu’une paire de sommets à une distance entre 2 à k peut être posé sur un cycle hamiltonien. En outre, Faudree et Li ont proposé une conjecture plus générale: si G est un graphe d’ordre n≥3 et δ(G)≥n/2+1, pour toute paire de sommets x,y dans G et tout entier 2≤k≤n/2, il existe un cycle hamiltonien C de G tel que dist_C(x,y)=k. Utilisant de Regularity Lemma et Blow-up Lemma, au chapitre 5, nous donnons une preuve de la conjeture d'Enomoto conjecture pour les graphes suffisamment grand, et dans le chapitre 6, nous donnons une preuve de la conjecture de Faudree et Li pour les graphe suffisamment grand. / In this thesis, we study two main problems in graph theory: homomorphism problem of planar (signed) graphs and Hamiltonian cycle problem.As an extension of the Four-Color Theorem, it is conjectured ([80],[41]) that every planar consistent signed graph of unbalanced-girth d+1(d>1) admits a homomorphism to signed projective cube SPC(d) of dimension d. It is naturally asked that:Is SPC(d) an optimal bound of unbalanced-girth d+1 for all planar consistent signed graphs of unbalanced-girth d+1?In Chapter 2, we prove that: if (B,Ω) is a consistent signed graph of unbalanced-girth d which bounds the class of consistent signed planar graphs of unbalanced-girth d, then |B|≥2^{d-1}. Furthermore,if no subgraph of (B,Ω) bounds the same class, δ(B)≥d, and therefore,|E(B)|≥d·2^{d-2}.Our result shows that if the conjecture above holds, then the SPC(d) is an optimal bound both in terms of number of vertices and number of edges.When d=2k, the problem is equivalent to the homomorphisms of graphs: isPC(2k) an optimal bound of odd-girth 2k+1 for P_{2k+1}(the class of all planar graphs of odd-girth at least 2k+1)? Note that K_4-minor free graphs are planar graphs, is PC(2k) also an optimal bound of odd-girth 2k+1 for all K_4-minor free graphs of odd-girth 2k+1 ? The answer is negative, in [6], a family of graphs of order O(k^2) bounding the K_4-minor free graphs of odd-girth 2k+1 were given. Is this an optimal bound? In Chapter 3, we prove that: if B is a graph of odd-girth 2k+1 which bounds all the K_4-minor free graphs of odd-girth 2k+1,then |B|≥(k+1)(k+2)/2. Our result together with the result in [6] shows that order O(k^2) is optimal.Furthermore, if PC(2k) bounds P_{2k+1},then PC(2k) also bounds P_{2r+1}(r>k). However, in this case we believe that a proper subgraph of PC(2k) would suffice to bound P_{2r+1}, then what’s the optimal subgraph of PC(2k) that bounds P_{2r+1}? The first case of this problem which is not studied is k=3 and r=5. For this case, Naserasr [81] conjectured that the Coxeter graph bounds P_{11} . Supporting this conjecture, in Chapter 4, we prove that the Coxeter graph bounds P_{17}.In Chapter 5,6, we study the Hamiltonian cycle problems. Dirac showed in 1952that every graph of order n is Hamiltonian if any vertex is of degree at least n/2. This result started a new approach to develop sufficient conditions on degrees for a graph to be Hamiltonian. Many results have been obtained in generalization of Dirac’s theorem. In the results to strengthen Dirac’s theorem, there is an interesting research area: to control the placement of a set of vertices on a Hamiltonian cycle such that thesevertices have some certain distances among them on the Hamiltonian cycle.In this thesis, we consider two related conjectures, one is given by Enomoto: if G is a graph of order n≥3, and δ(G)≥n/2+1, then for any pair of vertices x, y in G, there is a Hamiltonian cycle C of G such that dist_C(x, y)=n/2. Motivated by this conjecture, it is proved,in [32],that a pair of vertices are located at distances no more than n/6 on a Hamiltonian cycle. In [33], the cases δ(G) ≥(n+k)/2 are considered, it is proved that a pair of vertices can be located at any given distance from 2 to k on a Hamiltonian cycle. Moreover, Faudree and Li proposed a more general conjecture: if G is a graph of order n≥3, and δ(G)≥n/2+1, then for any pair of vertices x, y in G andany integer 2≤k≤n/2, there is a Hamiltonian cycle C of G such that dist_C(x, y) = k. Using Regularity Lemma and Blow-up Lemma, in Chapter 5, we give a proof ofEnomoto’s conjecture for graphs of sufficiently large order, and in Chapter 6, we give a proof of Faudree and Li’s conjecture for graphs of sufficiently large order.

>Magister Scientiae - MSc / This dissertation is a presentation to generalize boundedness and pseudocompactness in pointfree topology. We rst obtain and introduce a boundedness notion for elements of a frame. This is then further inspiration to introduce a de nition of bounded frame homomorphism whose domain may be any frame E, not just the frame of open sets of the reals.

We consider constrained variants of graph homomorphisms such as embeddings, monomorphisms, full homomorphisms, surjective homomorpshims, and locally constrained homomorphisms. We also introduce a new variation on this theme which derives from relations between graphs and is related to multihomomorphisms. This gives a generalization of surjective homomorphisms and naturally leads to notions of R-retractions, R-cores, and R-cocores of graphs. Both \\mbox{R-cores} and R-cocores of graphs are unique up to isomorphism and can be computed in polynomial time. The theory of the graph homomorphism order is well developed, and from it we consider analogous notions defined for orders induced by constrained homomorphisms. We identify corresponding cores, prove or disprove universality, characterize gaps and dualities. We give a new and significantly easier proof of the universality of the homomorphism order by showing that even the class of oriented cycles is universal. We provide a systematic approach to simplify the proofs of several earlier results in this area. We explore in greater detail locally injective homomorphisms on connected graphs, characterize gaps and show universality. We also prove that for every $d\\geq 3$ the homomorphism order on the class of line graphs of graphs with maximum degree $d$ is universal.

This thesis investigates the practical aspects of implementing Query Containment algorithms for the query language XPath. Query Containment is the problem to decide if the results of one query are a subset of the results of another query for any database. Query Containment algorithms can be used for the purpose of optimising the querying process in database systems. Two algorithms have been implemented and compared, The Canonical Model and The Homomorphism Technique. The algorithms have been compared with respect to speed, ease of implementation, accuracy and usability in database systems. Benchmark tests were developed to measure the execution times of the algorithms on a specific set of queries. A simple database system was developed to investigate the performance gain of using the algorithms. It was concluded that The Homomorphism Technique outperforms The Canonical Model in every test case with respect to speed. The Canonical Model is however more accurate than The Homomorphism Technique. Both algorithms were easy to implement, but The Homomorphism Technique was easier. In the database system, there was performance to be gained by using Query Containment algorithms for a certain type of queries, but in most cases there was a performance loss. A database system that utilises Query Containment algorithms for optimisation would for every issued query have to evaluate if such an algorithm should be used. / Denna rapport undersöker de praktiska aspekterna av att implementera Query Containment-algoritmer för queryspråket XPath. Query Containment är problemet att avgöra om resultaten av en query är en delmängd av resultaten av en annan query, oavsett databas. Query Containment-algoritmer kan användas för ändamålet att optimera queryingprocessen i databassystem. Två algoritmer har implementerats och jämförts, The Canonical Model och The Homomorphism Technique. Algoritmerna har jämförts med avseende på hastighet, lätthet att implementera, exakthet och användbarhet i riktiga databassystem. Prestandatester utvecklades för att mäta exekveringstider för algoritmerna på specifikt framtagna queries. Ett enkelt databassystem utvecklades för att undersöka prestandavinsten av att använda algoritmerna. Slutsatsen att The Homomorphism Technique presterar bättre än The Canonical Model i samtliga testfall med avseende på hastighet drogs. The Canonical Model är dock mer exakt än The Homomorphism Technique. Båda algoritmerna var lätta att implementera, men The Homomorphism Technique var lättare. I databassystemet fanns det en prestandavinst i att använda Query Containment-algoritmer för en viss typ av queries, men i de flesta fall var det en prestandaförlust. Ett databassystem som använder Query Containment-algoritmer för optimering bör för varje query avgöra om en sådan algoritm ska användas.