Matching Items (35)
152048-Thumbnail Image.png
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

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
152050-Thumbnail Image.png
Description
In 1959, Iwasawa proved that the size of the $p$-part of the class groups of a $\mathbb{Z}_p$-extension grows as a power of $p$ with exponent ${\mu}p^m+{\lambda}\,m+\nu$ for $m$ sufficiently large. Broadly, I construct conditions to verify if a given $m$ is indeed sufficiently large. More precisely, let $CG_m^i$ (class group)

In 1959, Iwasawa proved that the size of the $p$-part of the class groups of a $\mathbb{Z}_p$-extension grows as a power of $p$ with exponent ${\mu}p^m+{\lambda}\,m+\nu$ for $m$ sufficiently large. Broadly, I construct conditions to verify if a given $m$ is indeed sufficiently large. More precisely, let $CG_m^i$ (class group) be the $\epsilon_i$-eigenspace component of the $p$-Sylow subgroup of the class group of the field at the $m$-th level in a $\mathbb{Z}_p$-extension; and let $IACG^i_m$ (Iwasawa analytic class group) be ${\mathbb{Z}_p[[T]]/((1+T)^{p^m}-1,f(T,\omega^{1-i}))}$, where $f$ is the associated Iwasawa power series. It is expected that $CG_m^i$ and $IACG^i_m$ be isomorphic, providing us with a powerful connection between algebraic and analytic techniques; however, as of yet, this isomorphism is unestablished in general. I consider the existence and the properties of an exact sequence $$0\longrightarrow\ker{\longrightarrow}CG_m^i{\longrightarrow}IACG_m^i{\longrightarrow}\textrm{coker}\longrightarrow0.$$ In the case of a $\mathbb{Z}_p$-extension where the Main Conjecture is established, there exists a pseudo-isomorphism between the respective inverse limits of $CG_m^i$ and $IACG_m^i$. I consider conditions for when such a pseudo-isomorphism immediately gives the existence of the desired exact sequence, and I also consider work-around methods that preserve cardinality for otherwise. However, I primarily focus on constructing conditions to verify if a given $m$ is sufficiently large that the kernel and cokernel of the above exact sequence have become well-behaved, providing similarity of growth both in the size and in the structure of $CG_m^i$ and $IACG_m^i$; as well as conditions to determine if any such $m$ exists. The primary motivating idea is that if $IACG_m^i$ is relatively easy to work with, and if the relationship between $CG_m^i$ and $IACG_m^i$ is understood; then $CG_m^i$ becomes easier to work with. Moreover, while the motivating framework is stated concretely in terms of the cyclotomic $\mathbb{Z}_p$-extension of $p$-power roots of unity, all results are generally applicable to arbitrary $\mathbb{Z}_p$-extensions as they are developed in terms of Iwasawa-Theory-inspired, yet abstracted, algebraic results on maps between inverse limits.
ContributorsElledge, Shawn Michael (Author) / Childress, Nancy (Thesis advisor) / Bremner, Andrew (Committee member) / Fishel, Susanna (Committee member) / Jones, John (Committee member) / Paupert, Julien (Committee member) / Arizona State University (Publisher)
Created2013
151429-Thumbnail Image.png
Description
A central concept of combinatorics is partitioning structures with given constraints. Partitions of on-line posets and on-line graphs, which are dynamic versions of the more familiar static structures posets and graphs, are examined. In the on-line setting, vertices are continually added to a poset or graph while a chain partition

A central concept of combinatorics is partitioning structures with given constraints. Partitions of on-line posets and on-line graphs, which are dynamic versions of the more familiar static structures posets and graphs, are examined. In the on-line setting, vertices are continually added to a poset or graph while a chain partition or coloring (respectively) is maintained. %The optima of the static cases cannot be achieved in the on-line setting. Both upper and lower bounds for the optimum of the number of chains needed to partition a width $w$ on-line poset exist. Kierstead's upper bound of $\frac{5^w-1}{4}$ was improved to $w^{14 \lg w}$ by Bosek and Krawczyk. This is improved to $w^{3+6.5 \lg w}$ by employing the First-Fit algorithm on a family of restricted posets (expanding on the work of Bosek and Krawczyk) . Namely, the family of ladder-free posets where the $m$-ladder is the transitive closure of the union of two incomparable chains $x_1\le\dots\le x_m$, $y_1\le\dots\le y_m$ and the set of comparabilities $\{x_1\le y_1,\dots, x_m\le y_m\}$. No upper bound on the number of colors needed to color a general on-line graph exists. To lay this fact plain, the performance of on-line coloring of trees is shown to be particularly problematic. There are trees that require $n$ colors to color on-line for any positive integer $n$. Furthermore, there are trees that usually require many colors to color on-line even if they are presented without any particular strategy. For restricted families of graphs, upper and lower bounds for the optimum number of colors needed to maintain an on-line coloring exist. In particular, circular arc graphs can be colored on-line using less than 8 times the optimum number from the static case. This follows from the work of Pemmaraju, Raman, and Varadarajan in on-line coloring of interval graphs.
ContributorsSmith, Matthew Earl (Author) / Kierstead, Henry A (Thesis advisor) / Colbourn, Charles (Committee member) / Czygrinow, Andrzej (Committee member) / Fishel, Susanna (Committee member) / Hurlbert, Glenn (Committee member) / Arizona State University (Publisher)
Created2012
153004-Thumbnail Image.png
DescriptionReprising the work of Kolpakov and Martelli, a manifold is constructed by face pairings of a four dimensional polytope, the 24-cell. The resulting geometry is a single cusped hyperbolic 4-manifold of finite volume. A short discussion of its geometry and underlying topology is included.
ContributorsAbram, Christopher (Author) / Paupert, Julien (Thesis advisor) / Kawski, Mattias (Committee member) / Kotschwar, Brett (Committee member) / Arizona State University (Publisher)
Created2014
149703-Thumbnail Image.png
Description
This dissertation studies routing in small-world networks such as grids plus long-range edges and real networks. Kleinberg showed that geography-based greedy routing in a grid-based network takes an expected number of steps polylogarithmic in the network size, thus justifying empirical efficiency observed beginning with Milgram. A counterpart for the grid-based

This dissertation studies routing in small-world networks such as grids plus long-range edges and real networks. Kleinberg showed that geography-based greedy routing in a grid-based network takes an expected number of steps polylogarithmic in the network size, thus justifying empirical efficiency observed beginning with Milgram. A counterpart for the grid-based model is provided; it creates all edges deterministically and shows an asymptotically matching upper bound on the route length. The main goal is to improve greedy routing through a decentralized machine learning process. Two considered methods are based on weighted majority and an algorithm of de Farias and Megiddo, both learning from feedback using ensembles of experts. Tests are run on both artificial and real networks, with decentralized spectral graph embedding supplying geometric information for real networks where it is not intrinsically available. An important measure analyzed in this work is overpayment, the difference between the cost of the method and that of the shortest path. Adaptive routing overtakes greedy after about a hundred or fewer searches per node, consistently across different network sizes and types. Learning stabilizes, typically at overpayment of a third to a half of that by greedy. The problem is made more difficult by eliminating the knowledge of neighbors' locations or by introducing uncooperative nodes. Even under these conditions, the learned routes are usually better than the greedy routes. The second part of the dissertation is related to the community structure of unannotated networks. A modularity-based algorithm of Newman is extended to work with overlapping communities (including considerably overlapping communities), where each node locally makes decisions to which potential communities it belongs. To measure quality of a cover of overlapping communities, a notion of a node contribution to modularity is introduced, and subsequently the notion of modularity is extended from partitions to covers. The final part considers a problem of network anonymization, mostly by the means of edge deletion. The point of interest is utility preservation. It is shown that a concentration on the preservation of routing abilities might damage the preservation of community structure, and vice versa.
ContributorsBakun, Oleg (Author) / Konjevod, Goran (Thesis advisor) / Richa, Andrea (Thesis advisor) / Syrotiuk, Violet R. (Committee member) / Czygrinow, Andrzej (Committee member) / Arizona State University (Publisher)
Created2011
150038-Thumbnail Image.png
Description
In a large network (graph) it would be desirable to guarantee the existence of some local property based only on global knowledge of the network. Consider the following classical example: how many connections are necessary to guarantee that the network contains three nodes which are pairwise adjacent? It turns out

In a large network (graph) it would be desirable to guarantee the existence of some local property based only on global knowledge of the network. Consider the following classical example: how many connections are necessary to guarantee that the network contains three nodes which are pairwise adjacent? It turns out that more than n^2/4 connections are needed, and no smaller number will suffice in general. Problems of this type fall into the category of ``extremal graph theory.'' Generally speaking, extremal graph theory is the study of how global parameters of a graph are related to local properties. This dissertation deals with the relationship between minimum degree conditions of a host graph G and the property that G contains a specified spanning subgraph (or class of subgraphs). The goal is to find the optimal minimum degree which guarantees the existence of a desired spanning subgraph. This goal is achieved in four different settings, with the main tools being Szemeredi's Regularity Lemma; the Blow-up Lemma of Komlos, Sarkozy, and Szemeredi; and some basic probabilistic techniques.
ContributorsDeBiasio, Louis (Author) / Kierstead, Henry A (Thesis advisor) / Czygrinow, Andrzej (Thesis advisor) / Hurlbert, Glenn (Committee member) / Kadell, Kevin (Committee member) / Fishel, Susanna (Committee member) / Arizona State University (Publisher)
Created2011
151231-Thumbnail Image.png
Description
Gray codes are perhaps the best known structures for listing sequences of combinatorial objects, such as binary strings. Simply defined as a minimal change listing, Gray codes vary greatly both in structure and in the types of objects that they list. More specific types of Gray codes are universal cycles

Gray codes are perhaps the best known structures for listing sequences of combinatorial objects, such as binary strings. Simply defined as a minimal change listing, Gray codes vary greatly both in structure and in the types of objects that they list. More specific types of Gray codes are universal cycles and overlap sequences. Universal cycles are Gray codes on a set of strings of length n in which the first n-1 letters of one object are the same as the last n-1 letters of its predecessor in the listing. Overlap sequences allow this overlap to vary between 1 and n-1. Some of our main contributions to the areas of Gray codes and universal cycles include a new Gray code algorithm for fixed weight m-ary words, and results on the existence of universal cycles for weak orders on [n]. Overlap cycles are a relatively new structure with very few published results. We prove the existence of s-overlap cycles for k-permutations of [n], which has been an open research problem for several years, as well as constructing 1- overlap cycles for Steiner triple and quadruple systems of every order. Also included are various other results of a similar nature covering other structures such as binary strings, m-ary strings, subsets, permutations, weak orders, partitions, and designs. These listing structures lend themselves readily to some classes of combinatorial objects, such as binary n-tuples and m-ary n-tuples. Others require more work to find an appropriate structure, such as k-subsets of an n-set, weak orders, and designs. Still more require a modification in the representation of the objects to fit these structures, such as partitions. Determining when and how we can fit these sets of objects into our three listing structures is the focus of this dissertation.
ContributorsHoran, Victoria E (Author) / Hurlbert, Glenn H. (Thesis advisor) / Czygrinow, Andrzej (Committee member) / Fishel, Susanna (Committee member) / Colbourn, Charles (Committee member) / Sen, Arunabha (Committee member) / Arizona State University (Publisher)
Created2012
156198-Thumbnail Image.png
Description
The uncrossing partially ordered set $P_n$ is defined on the set of matchings on $2n$ points on a circle represented with wires. The order relation is $\tau'\leq \tau$ in $P_n$ if and only if $\tau'$ is obtained by resolving a crossing of $\tau$. %This partial order has been studied by

The uncrossing partially ordered set $P_n$ is defined on the set of matchings on $2n$ points on a circle represented with wires. The order relation is $\tau'\leq \tau$ in $P_n$ if and only if $\tau'$ is obtained by resolving a crossing of $\tau$. %This partial order has been studied by Alman-Lian-Tran, Huang-Wen-Xie, Kenyon, and Lam. %The posets $P_n$ emerged from studies of circular planar electrical networks. Circular planar electrical networks are finite weighted undirected graphs embedded into a disk, with boundary vertices and interior vertices. By Curtis-Ingerman-Morrow and de Verdi\`ere-Gitler-Vertigan, the electrical networks can be encoded with response matrices. By Lam the space of response matrices for electrical networks has a cell structure, and this cell structure can be described by the uncrossing partial orders. %Lam proves that the posets can be identified with dual Bruhat order on affine permutations of type $(n,2n)$. Using this identification, Lam proves the poset $\hat{P}_n$, the uncrossing poset $P_n$ with a unique minimum element $\hat{0}$ adjoined, is Eulerian. This thesis consists of two sets of results: (1) flag enumeration in intervals in the uncrossing poset $P_n$ and (2) cyclic sieving phenomenon on the set $P_n$.

I identify elements in $P_n$ with affine permutations of type $(0,2n)$. %This identification enables us to explicitly describe the elements in $P_n$ with the elements in $\mathcal{MP}_n$.

Using this identification, I adapt a technique in Reading for finding recursions for the cd-indices of intervals in Bruhat order of Coxeter groups to the uncrossing poset $P_n$. As a result, I produce recursions for the cd-indices of intervals in the uncrossing poset $P_n$. I also obtain a recursion for the ab-indices of intervals in the poset $\hat{P}_n$, the poset $P_n$ with a unique minimum $\hat0$ adjoined. %We define an induced subposet $\mathcal{MP}_n$ of the affine permutations under Bruhat order.

Reiner-Stanton-White defined the cyclic sieving phenomenon (CSP) associated to a finite cyclic group action on a finite set and a polynomial. Sagan observed the CSP on the set of non-crossing matchings with the $q$-Catalan polynomial. Bowling-Liang presented similar results on the set of $k$-crossing matchings for $1\leq k \leq 3$. In this dissertation, I focus on the set of all matchings on $[2n]:=\{1,2,\dots,2n\}$. I find the number of matchings fixed by $\frac{2\pi}{d}$ rotations for $d|2n$. I then find the polynomial $X_n(q)$ such that the set of matchings together with $X_n(q)$ and the cyclic group of order $2n$ exhibits the CSP.
ContributorsKim, Younghwan (Author) / Fishel, Susanna (Thesis advisor) / Bremner, Andrew (Committee member) / Czygrinow, Andrzej (Committee member) / Kierstead, Henry (Committee member) / Paupert, Julien (Committee member) / Arizona State University (Publisher)
Created2018
156583-Thumbnail Image.png
Description
Since the seminal work of Tur ́an, the forbidden subgraph problem has been among the central questions in extremal graph theory. Let ex(n;F) be the smallest number m such that any graph on n vertices with m edges contains F as a subgraph. Then the forbidden subgraph problem asks to

Since the seminal work of Tur ́an, the forbidden subgraph problem has been among the central questions in extremal graph theory. Let ex(n;F) be the smallest number m such that any graph on n vertices with m edges contains F as a subgraph. Then the forbidden subgraph problem asks to find ex(n; F ) for various graphs F . The question can be further generalized by asking for the extreme values of other graph parameters like minimum degree, maximum degree, or connectivity. We call this type of question a Tura ́n-type problem. In this thesis, we will study Tura ́n-type problems and their variants for graphs and hypergraphs.

Chapter 2 contains a Tura ́n-type problem for cycles in dense graphs. The main result in this chapter gives a tight bound for the minimum degree of a graph which guarantees existence of disjoint cycles in the case of dense graphs. This, in particular, answers in the affirmative a question of Faudree, Gould, Jacobson and Magnant in the case of dense graphs.

In Chapter 3, similar problems for trees are investigated. Recently, Faudree, Gould, Jacobson and West studied the minimum degree conditions for the existence of certain spanning caterpillars. They proved certain bounds that guarantee existence of spanning caterpillars. The main result in Chapter 3 significantly improves their result and answers one of their questions by proving a tight minimum degree bound for the existence of such structures.

Chapter 4 includes another Tur ́an-type problem for loose paths of length three in a 3-graph. As a corollary, an upper bound for the multi-color Ramsey number for the loose path of length three in a 3-graph is achieved.
ContributorsYie, Jangwon (Author) / Czygrinow, Andrzej (Thesis advisor) / Kierstead, Henry (Committee member) / Colbourn, Charles (Committee member) / Fishel, Susanna (Committee member) / Spielberg, John (Committee member) / Arizona State University (Publisher)
Created2018
157198-Thumbnail Image.png
Description
In the 1980's, Gromov and Piatetski-Shapiro introduced a technique called "hybridization'' which allowed them to produce non-arithmetic hyperbolic lattices from two non-commensurable arithmetic lattices. It has been asked whether an analogous hybridization technique exists for complex hyperbolic lattices, because certain geometric obstructions make it unclear how to adapt this technique.

In the 1980's, Gromov and Piatetski-Shapiro introduced a technique called "hybridization'' which allowed them to produce non-arithmetic hyperbolic lattices from two non-commensurable arithmetic lattices. It has been asked whether an analogous hybridization technique exists for complex hyperbolic lattices, because certain geometric obstructions make it unclear how to adapt this technique. This thesis explores one possible construction (originally due to Hunt) in depth and uses it to produce arithmetic lattices, non-arithmetic lattices, and thin subgroups in SU(2,1).
ContributorsWells, Joseph (Author) / Paupert, Julien (Thesis advisor) / Kotschwar, Brett (Committee member) / Childress, Nancy (Committee member) / Fishel, Susanna (Committee member) / Kawski, Matthias (Committee member) / Arizona State University (Publisher)
Created2019