Matching Items (9)
Description
A tiling is a collection of vertex disjoint subgraphs called tiles. If the tiles are all isomorphic to a graph $H$ then the tiling is an $H$-tiling. If a graph $G$ has an $H$-tiling which covers all of the vertices of $G$ then the $H$-tiling is a perfect $H$-tiling or an $H$-factor. A goal of this study is to extend theorems on sufficient minimum degree conditions for perfect tilings in graphs to directed graphs. Corrádi and Hajnal proved that every graph $G$ on $3k$ vertices with minimum degree $delta(G)ge2k$ has a $K_3$-factor, where $K_s$ is the complete graph on $s$ vertices. The following theorem extends this result to directed graphs: If $D$ is a directed graph on $3k$ vertices with minimum total degree $delta(D)ge4k-1$ then $D$ can be partitioned into $k$ parts each of size $3$ so that all of parts contain a transitive triangle and $k-1$ of the parts also contain a cyclic triangle. The total degree of a vertex $v$ is the sum of $d^-(v)$ the in-degree and $d^+(v)$ the out-degree of $v$. Note that both orientations of $C_3$ are considered: the transitive triangle and the cyclic triangle. The theorem is best possible in that there are digraphs that meet the minimum degree requirement but have no cyclic triangle factor. The possibility of added a connectivity requirement to ensure a cycle triangle factor is also explored. Hajnal and Szemerédi proved that if $G$ is a graph on $sk$ vertices and $delta(G)ge(s-1)k$ then $G$ contains a $K_s$-factor. As a possible extension of this celebrated theorem to directed graphs it is proved that if $D$ is a directed graph on $sk$ vertices with $delta(D)ge2(s-1)k-1$ then $D$ contains $k$ disjoint transitive tournaments on $s$ vertices. We also discuss tiling directed graph with other tournaments. This study also explores minimum total degree conditions for perfect directed cycle tilings and sufficient semi-degree conditions for a directed graph to contain an anti-directed Hamilton cycle. The semi-degree of a vertex $v$ is $min{d^+(v), d^-(v)}$ and an anti-directed Hamilton cycle is a spanning cycle in which no pair of consecutive edges form a directed path.
ContributorsMolla, Theodore (Author) / Kierstead, Henry A (Thesis advisor) / Czygrinow, Andrzej (Committee member) / Fishel, Susanna (Committee member) / Hurlbert, Glenn (Committee member) / Spielberg, Jack (Committee member) / Arizona State University (Publisher)
Created2013
Description
Let T be a tournament with edges colored with any number of colors. A rainbow triangle is a 3-colored 3-cycle. A monochromatic sink of T is a vertex which can be reached along a monochromatic path by every other vertex of T. In 1982, Sands, Sauer, and Woodrow asked if T has no rainbow triangles, then does T have a monochromatic sink? I answer yes in the following five scenarios: when all 4-cycles are monochromatic, all 4-semi-cycles are near-monochromatic, all 5-semi-cycles are near-monochromatic, all back-paths of an ordering of the vertices are vertex disjoint, and for any vertex in an ordering of the vertices, its back edges are all colored the same. I provide conjectures related to these results that ask if the result is also true for larger cycles and semi-cycles. A ruling class is a set of vertices in T so that every other vertex of T can reach a vertex of the ruling class along a monochromatic path. Every tournament contains a ruling class, although the ruling class may have a trivial size of the order of T. Sands, Sauer, and Woodrow asked (again in 1982) about the minimum size of ruling classes in T. In particular, in a 3-colored tournament, must there be a ruling class of size 3? I answer yes when it is required that all 2-colored cycles have an edge xy so that y has a monochromatic path to x. I conjecture that there is a ruling class of size 3 if there are no rainbow triangles in T. Finally, I present the new topic of alpha-step-chromatic sinks along with related results. I show that for certain values of alpha, a tournament is not guaranteed to have an alpha-step-chromatic sink. In fact, similar to the previous results in this thesis, alpha-step-chromatic sinks can only be demonstrated when additional restrictions are put on the coloring of the tournament's edges, such as excluding rainbow triangles. However, when proving the existence of alpha-step-chromatic sinks, it is only necessary to exclude special types of rainbow triangles.
ContributorsBland, Adam K (Author) / Kierstead, Henry A (Thesis advisor) / Czygrinow, Andrzej M (Committee member) / Hurlbert, Glenn H. (Committee member) / Barcelo, Helene (Committee member) / Aen, Arunabha (Committee member) / Arizona State University (Publisher)
Created2011
Description
Almost commuting matrices, i.e. matrices with a sufficiently small commutator, may be nearly commuting, i.e. there may exist matrices close by which do commute. By referencing current literature, this condition is studied for fixed dimension, unitary, self-adjoint, and orthogonal matrices. These proofs are made more accessible and compared to each other, providing insight to possible future progress in the field.
ContributorsMolloy, Riley Phillip (Author) / Spielberg, Jack (Thesis director) / Quigg, John (Committee member) / Barrett, The Honors College (Contributor) / School of Mathematical and Statistical Sciences (Contributor) / Department of Physics (Contributor)
Created2015-05
Description
The theory of frames for Hilbert spaces has become foundational in the study of wavelet analysis and has far-reaching applications in signal and image-processing. Originally, frames were first introduced in the early 1950's within the context of nonharmonic Fourier analysis by Duffin and Schaeffer. It was then in 2000, when M. Frank and D. R. Larson extended the concept of frames to the setting of Hilbert C*-modules, it was in that same paper where they asked for which C*-algebras does every Hilbert C*-module admit a frame. Since then there have been a few direct answers to this question, one being that every Hilbert A-module over a C*-algebra, A, that has faithful representation into the C*-algebra of compact operators admits a frame. Another direct answer by Hanfeng Li given in 2010, is that any C*-algebra, A, such that every Hilbert C*-module admits a frame is necessarily finite dimensional. In this thesis we give an overview of the general theory of frames for Hilbert C*-modules and results answering the frame admittance property. We begin by giving an overview of the existing classical theory of frames in Hilbert spaces as well as some of the preliminary theory of Hilbert C*-modules such as Morita equivalence and certain tensor product constructions of C*-algebras. We then show how some results of frames can be extended to the case of standard frames in countably generated Hilbert C*-modules over unital C*-algebras, namely the frame decomposition property and existence of the frame transform operator. We conclude by going through some proofs/constructions that answer the question of frame admittance for certain Hilbert C*-modules.
ContributorsJaime, Arturo (Author) / Kaliszewski, Steven (Thesis director) / Spielberg, Jack (Committee member) / Aguilar, Konrad (Committee member) / School of Mathematical and Statistical Sciences (Contributor) / Barrett, The Honors College (Contributor)
Created2019-05
Description
Borda's social choice method and Condorcet's social choice method are shown to satisfy different monotonicities and it is shown that it is impossible for any social choice method to satisfy them both. Results of a Monte Carlo simulation are presented which estimate the probability of each of the following social choice methods being manipulable: plurality (first past the post), Borda count, instant runoff, Kemeny-Young, Schulze, and majority Borda. The Kemeny-Young and Schulze methods exhibit the strongest resistance to random manipulability. Two variations of the majority judgment method, with different tie-breaking rules, are compared for continuity. A new variation is proposed which minimizes discontinuity. A framework for social choice methods based on grades is presented. It is based on the Balinski-Laraki framework, but doesn't require aggregation functions to be strictly monotone. By relaxing this restriction, strategy-proof aggregation functions can better handle a polarized electorate, can give a societal grade closer to the input grades, and can partially avoid certain voting paradoxes. A new cardinal voting method, called the linear median is presented, and is shown to have several very valuable properties. Range voting, the majority judgment, and the linear median are also simulated to compare their manipulability against that of the ordinal methods.
ContributorsJennings, Andrew (Author) / Hurlbert, Glenn (Thesis advisor) / Barcelo, Helene (Thesis advisor) / Balinski, Michel (Committee member) / Laraki, Rida (Committee member) / Jones, Don (Committee member) / Arizona State University (Publisher)
Created2010
Description
In Iwasawa theory, one studies how an arithmetic or geometric object grows as its field of definition varies over certain sequences of number fields. For example, let $F/\mathbb{Q}$ be a finite extension of fields, and let $E:y^2 = x^3 + Ax + B$ with $A,B \in F$ be an elliptic curve. If $F = F_0 \subseteq F_1 \subseteq F_2 \subseteq \cdots F_\infty = \bigcup_{i=0}^\infty F_i$, one may be interested in properties like the ranks and torsion subgroups of the increasing family of curves $E(F_0) \subseteq E(F_1) \subseteq \cdots \subseteq E(F_\infty)$. The main technique for studying this sequence of curves when $\Gal(F_\infty/F)$ has a $p$-adic analytic structure is to use the action of $\Gal(F_n/F)$ on $E(F_n)$ and the Galois cohomology groups attached to $E$, i.e. the Selmer and Tate-Shafarevich groups. As $n$ varies, these Galois actions fit into a coherent family, and taking a direct limit one obtains a short exact sequence of modules $$0 \longrightarrow E(F_\infty) \otimes(\mathbb{Q}_p/\mathbb{Z}_p) \longrightarrow \Sel_E(F_\infty)_p \longrightarrow \Sha_E(F_\infty)_p \longrightarrow 0 $$ over the profinite group algebra $\mathbb{Z}_p[[\Gal(F_\infty/F)]]$. When $\Gal(F_\infty/F) \cong \mathbb{Z}_p$, this ring is isomorphic to $\Lambda = \mathbb{Z}_p[[T]]$, and the $\Lambda$-module structure of $\Sel_E(F_\infty)_p$ and $\Sha_E(F_\infty)_p$ encode all the information about the curves $E(F_n)$ as $n$ varies. In this dissertation, it will be shown how one can classify certain finitely generated $\Lambda$-modules with fixed characteristic polynomial $f(T) \in \mathbb{Z}_p[T]$ up to isomorphism. The results yield explicit generators for each module up to isomorphism. As an application, it is shown how to identify the isomorphism class of $\Sel_E(\mathbb{Q_\infty})_p$ in this explicit form, where $\mathbb{Q}_\infty$ is the cyclotomic $\mathbb{Z}_p$-extension of $\mathbb{Q}$, and $E$ is an elliptic curve over $\mathbb{Q}$ with good ordinary reduction at $p$, and possessing the property that $E(\mathbb{Q})$ has no $p$-torsion.
ContributorsFranks, Chase (Author) / Childress, Nancy (Thesis advisor) / Barcelo, Helene (Committee member) / Bremner, Andrew (Committee member) / Jones, John (Committee member) / Spielberg, Jack (Committee member) / Arizona State University (Publisher)
Created2011
Description
This thesis presents a categorical approach to recover and extend some well-known results from the theory of $C^*$-correspondences. First, a detailed study on \emph{the enchilada category} is given. In this category, the objects are $C^*$-algebras, and morphisms are isomorphism classes of $C^*$-correspondences. In the \emph{equivariant enchilada category} $\mathcal{A}(C)$, all objects and morphisms are equipped with a locally compact group action satisfying certain conditions. These categories were used by Echterhoff, Kaliszweski, Quigg, and Raeburn for a study regarding a very fundamental tool to the representation theory: imprimitivity theorems. This work contains a construction of exact sequences in enchilada categories. One of the main results is that the
reduced-crossed-product functor defined from $\mathcal{A}(C)$ to the enchilada category
is
not
exact.
The motivation was
to determine whether one can have a better understanding of the Baum-Connes conjecture.
Along the way numerous results are proven, showing that the enchilada category is rather strange. The next main study regards the functoriality of Cuntz-Pimsner algebras. A construction of a functor that maps $C^*$-correspondences to their Cuntz-Pimsner algebras is presented. The objects in the domain category are $C^*$-correspondences, and the morphisms are the isomorphism classes of $C^*$-correspondences satisfying certain conditions. Applications include a generalization of the well-known result of Muhly and Solel: Morita equivalent $C^*$-correspondences have Morita equivalent Cuntz-Pimsner algebras; as well as a generalization of the result of Kakariadis and Katsoulis: Regular shift equivalent $C^*$-correspondences have Morita equivalent Cuntz-Pimsner algebras.
ContributorsERYUZLU, MENEVSE (Author) / Quigg, John (Thesis advisor) / Kalszewski, Steven (Committee member) / Spielberg, Jack (Committee member) / Williams, Dana (Committee member) / Larsen, Nadia (Committee member) / Arizona State University (Publisher)
Created2021
Description
The author employs bundle theory to investigate dynamics on C*- algebras. Using methods old and new to define dynamics on topological spaces (often with additional structure), implications of the dynamics are investigated in the non-commutative setting, and in suitable situations the dynamics are classified. As a result, new Morita equivalence results are derived and new settings introduced in the study of crossed products, whether by group coactions or by actions of groups and groupoids.
ContributorsHall, Lucas (Author) / Quigg, John (Thesis advisor) / Kaliszewski, S. (Committee member) / Spielberg, Jack (Committee member) / Paupert, Julien (Committee member) / Kotschwar, Brett (Committee member) / Arizona State University (Publisher)
Created2022
Description
This dissertation contains three main results. First, a generalization of Ionescu's theorem is proven. Ionescu's theorem describes an unexpected connection between graph C*-algebras and fractal geometry. In this work, this theorem is extended from ordinary directed graphs to higher-rank graphs. Second, a characterization is given of the Cuntz-Pimsner algebra associated to a tensor product of C*-correspondences. This is a generalization of a result by Kumjian about graphs algebras. This second result is applied to several important special cases of Cuntz-Pimsner algebras including topological graph algebras, crossed products by the integers and crossed products by completely positive maps. The result has meaningful interpretations in each context. The third result is an extension of the second result from an ordinary tensor product to a special case of Woronowicz's twisted tensor product. This result simultaneously characterizes Cuntz-Pimsner algebras of ordinary and graded tensor products and Cuntz-Pimsner algebras of crossed products by actions and coactions of discrete groups, the latter partially recovering earlier results of Hao and Ng and of Kaliszewski, Quigg and Robertson.
ContributorsMorgan, Adam (Author) / Kaliszewski, Steven (Thesis advisor) / Quigg, John (Thesis advisor) / Spielberg, Jack (Committee member) / Kawski, Matthias (Committee member) / Kotschwar, Brett (Committee member) / Arizona State University (Publisher)
Created2016