Matching Items (37)
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 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
Description
This study contributes to the ongoing discussion of Mathematical Knowledge for Teaching (MKT). It investigates the case of Rico, a high school mathematics teacher who had become known to his colleagues and his students as a superbly effective mathematics teacher. His students not only developed excellent mathematical skills, they also developed deep understanding of the mathematics they learned. Moreover, Rico redesigned his curricula and instruction completely so that they provided a means of support for his students to learn mathematics the way he intended. The purpose of this study was to understand the sources of Rico's effectiveness. The data for this study was generated in three phases. Phase I included videos of Rico's lessons during one semester of an Algebra II course, post-lesson reflections, and Rico's self-constructed instructional materials. An analysis of Phase I data led to Phase II, which consisted of eight extensive stimulated-reflection interviews with Rico. Phase III consisted of a conceptual analysis of the prior phases with the aim of creating models of Rico's mathematical conceptions, his conceptions of his students' mathematical understandings, and his images of instruction and instructional design. Findings revealed that Rico had developed profound personal understandings, grounded in quantitative reasoning, of the mathematics that he taught, and profound pedagogical understandings that supported these very same ways of thinking in his students. Rico's redesign was driven by three factors: (1) the particular way in which Rico himself understood the mathematics he taught, (2) his reflective awareness of those ways of thinking, and (3) his ability to envision what students might learn from different instructional approaches. Rico always considered what someone might already need to understand in order to understand "this" in the way he was thinking of it, and how understanding "this" might help students understand related ideas or methods. Rico's continual reflection on the mathematics he knew so as to make it more coherent, and his continual orientation to imagining how these meanings might work for students' learning, made Rico's mathematics become a mathematics of students--impacting how he assessed his practice and engaging him in a continual process of developing MKT.
ContributorsLage Ramírez, Ana Elisa (Author) / Thompson, Patrick W. (Thesis advisor) / Carlson, Marilyn P. (Committee member) / Castillo-Chavez, Carlos (Committee member) / Saldanha, Luis (Committee member) / Middleton, James A. (Committee member) / Arizona State University (Publisher)
Created2011
Description
In this mixed-methods study, I examined the relationship between professional development based on the Common Core State Standards for Mathematics and teacher knowledge, classroom practice, and student learning. Participants were randomly assigned to experimental and control groups. The 50-hour professional development treatment was administered to the treatment group during one semester, and then a follow-up replication treatment was administered to the control group during the subsequent semester. Results revealed significant differences in teacher knowledge as a result of the treatment using two instruments. The Learning Mathematics for Teaching scales were used to detect changes in mathematical knowledge for teaching, and an online sorting task was used to detect changes in teachers' knowledge of their standards. Results also indicated differences in classroom practice between pairs of matched teachers selected to participate in classroom observations and interviews. No statistical difference was detected between the groups' student assessment scores using the district's benchmark assessment system. This efficacy study contributes to the literature in two ways. First, it provides an evidence base for a professional development model designed to promote effective implementation of the Common Core State Standards for Mathematics. Second, it addresses ways to impact and measure teachers' knowledge of curriculum in addition to their mathematical content knowledge. The treatment was designed to focus on knowledge of curriculum, but it also successfully impacted teachers' specialized content knowledge, knowledge of content and students, and knowledge of content and teaching.
ContributorsRimbey, Kimberly A (Author) / Middleton, James A. (Thesis advisor) / Sloane, Finbarr (Committee member) / Atkinson, Robert K (Committee member) / Arizona State University (Publisher)
Created2013
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 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
Description
The research indicated effective mathematics teaching to be more complex than assuming the best predictor of student achievement in mathematics is the mathematical content knowledge of a teacher. This dissertation took a novel approach to addressing the idea of what it means to examine how a teacher's knowledge of mathematics impacts student achievement in elementary schools. Using a multiple case study design, the researcher investigated teacher knowledge as a function of the Mathematics Teaching Cycle (NCTM, 2007). Three cases (of two teachers each) were selected using a compilation of Learning Mathematics for Teaching (LMT) measures (LMT, 2006) and Developing Mathematical Ideas (DMI) measures (Higgins, Bell, Wilson, McCoach, & Oh, 2007; Bell, Wilson, Higgins, & McCoach, 2010) and student scores on the Arizona Assessment Collaborative (AzAC). The cases included teachers with: a) high knowledge & low student achievement v low knowledge & high student achievement, b) high knowledge & average achievement v low knowledge & average achievement, c) average knowledge & high achievement v average knowledge & low achievement, d) two teachers with average achievement & very high student achievement. In the end, my data suggested that MKT was only partially utilized across the contrasting teacher cases during the planning process, the delivery of mathematics instruction, and subsequent reflection. Mathematical Knowledge for Teaching was utilized differently by teachers with high student gains than those with low student gains. Because of this insight, I also found that MKT was not uniformly predictive of student gains across my cases, nor was it predictive of the quality of instruction provided to students in these classrooms.
ContributorsBurke, Margaret Kathleen (Author) / Middleton, James A. (Thesis advisor) / Sloane, Finbarr (Thesis advisor) / Battey, Daniel S (Committee member) / Arizona State University (Publisher)
Created2013
Description
Research on combinatorics education is sparse when compared with other fields in mathematics education. This research attempted to contribute to the dearth of literature by examining students' reasoning about enumerative combinatorics problems and how students conceptualize the set of elements being counted in such problems, called the solution set. In particular, the focus was on the stable patterns of reasoning, known as ways of thinking, which students applied in a variety of combinatorial situations and tasks. This study catalogued students' ways of thinking about solution sets as they progressed through an instructional sequence. In addition, the relationships between the catalogued ways of thinking were explored. Further, the study investigated the challenges students experienced as they interacted with the tasks and instructional interventions, and how students' ways of thinking evolved as these challenges were overcome. Finally, it examined the role of instruction in guiding students to develop and extend their ways of thinking. Two pairs of undergraduate students with no formal experience with combinatorics participated in one of the two consecutive teaching experiments conducted in Spring 2012. Many ways of thinking emerged through the grounded theory analysis of the data, but only eight were identified as robust. These robust ways of thinking were classified into three categories: Subsets, Odometer, and Problem Posing. The Subsets category encompasses two ways of thinking, both of which ultimately involve envisioning the solution set as the union of subsets. The three ways of thinking in Odometer category involve holding an item or a set of items constant and systematically varying the other items involved in the counting process. The ways of thinking belonging to Problem Posing category involve spontaneously posing new, related combinatorics problems and finding relationships between the solution sets of the original and the new problem. The evolution of students' ways of thinking in the Problem Posing category was analyzed. This entailed examining the perturbation experienced by students and the resulting accommodation of their thinking. It was found that such perturbation and its resolution was often the result of an instructional intervention. Implications for teaching practice are discussed.
ContributorsHalani, Aviva (Author) / Roh, Kyeong Hah (Thesis advisor) / Fishel, Susanna (Committee member) / Saldanha, Luis (Committee member) / Thompson, Patrick (Committee member) / Zandieh, Michelle (Committee member) / Arizona State University (Publisher)
Created2013
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
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
Description
Every graph can be colored with one more color than its maximum degree. A well-known theorem of Brooks gives the precise conditions under which a graph can be colored with maximum degree colors. It is natural to ask for the required conditions on a graph to color with one less color than the maximum degree; in 1977 Borodin and Kostochka conjectured a solution for graphs with maximum degree at least 9: as long as the graph doesn't contain a maximum-degree-sized clique, it can be colored with one fewer than the maximum degree colors. This study attacks the conjecture on multiple fronts. The first technique is an extension of a vertex shuffling procedure of Catlin and is used to prove the conjecture for graphs with edgeless high vertex subgraphs. This general approach also bears more theoretical fruit. The second technique is an extension of a method Kostochka used to reduce the Borodin-Kostochka conjecture to the maximum degree 9 case. Results on the existence of independent transversals are used to find an independent set intersecting every maximum clique in a graph. The third technique uses list coloring results to exclude induced subgraphs in a counterexample to the conjecture. The classification of such excludable graphs that decompose as the join of two graphs is the backbone of many of the results presented here. The fourth technique uses the structure theorem for quasi-line graphs of Chudnovsky and Seymour in concert with the third technique to prove the Borodin-Kostochka conjecture for claw-free graphs. The fifth technique adds edges to proper induced subgraphs of a minimum counterexample to gain control over the colorings produced by minimality. The sixth technique adapts a recoloring technique originally developed for strong coloring by Haxell and by Aharoni, Berger and Ziv to general coloring. Using this recoloring technique, the Borodin-Kostochka conjectured is proved for graphs where every vertex is in a large clique. The final technique is naive probabilistic coloring as employed by Reed in the proof of the Borodin-Kostochka conjecture for large maximum degree. The technique is adapted to prove the Borodin-Kostochka conjecture for list coloring for large maximum degree.
ContributorsRabern, Landon (Author) / Kierstead, Henry (Thesis advisor) / Colbourn, Charles (Committee member) / Czygrinow, Andrzej (Committee member) / Fishel, Susanna (Committee member) / Hurlbert, Glenn (Committee member) / Arizona State University (Publisher)
Created2013
Description
This dissertation describes an investigation of four students' ways of thinking about functions of two variables and rate of change of those two-variable functions. Most secondary, introductory algebra, pre-calculus, and first and second semester calculus courses do not require students to think about functions of more than one variable. Yet vector calculus, calculus on manifolds, linear algebra, and differential equations all rest upon the idea of functions of two (or more) variables. This dissertation contributes to understanding productive ways of thinking that can support students in thinking about functions of two or more variables as they describe complex systems with multiple variables interacting. This dissertation focuses on modeling the way of thinking of four students who participated in a specific instructional sequence designed to explore the limits of their ways of thinking and in turn, develop a robust model that could explain, describe, and predict students' actions relative to specific tasks. The data was collected using a teaching experiment methodology, and the tasks within the teaching experiment leveraged quantitative reasoning and covariation as foundations of students developing a coherent understanding of two-variable functions and their rates of change. The findings of this study indicated that I could characterize students' ways of thinking about two-variable functions by focusing on their use of novice and/or expert shape thinking, and the students' ways of thinking about rate of change by focusing on their quantitative reasoning. The findings suggested that quantitative and covariational reasoning were foundational to a student's ability to generalize their understanding of a single-variable function to two or more variables, and their conception of rate of change to rate of change at a point in space. These results created a need to better understand how experts in the field, such as mathematicians and mathematics educators, thinking about multivariable functions and their rates of change.
ContributorsWeber, Eric David (Author) / Thompson, Patrick (Thesis advisor) / Middleton, James (Committee member) / Carlson, Marilyn (Committee member) / Saldanha, Luis (Committee member) / Milner, Fabio (Committee member) / Van de Sande, Carla (Committee member) / Arizona State University (Publisher)
Created2012