Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 638 for “"Minors"”.
-
Exploring Matroid Minors
… but have the property that each of their proper minors is in the class; that is, minor-minimal matroids that are not in the minor-closed class. These minor-minimal matroids that are not in the minor-closed class are called excluded minors. In this thesis, we construct interesting minor-closed …
-
Grid Minors and Products
… we study relationships between treewidth, grid minors, and graph products. We show that the Cartesian product of any two graphs, each connected and each having n vertices, contains an Ω(√n) × Ω(√n) grid minor. This result is tight: the lexicographic product (which includes the Cartesian product …
-
Graph minors and algorithms
… edge deletions, and edge contractions. Graph minors have been studied for several decades as a way of characterizing classes of graphs. Recent work by Robertson and Seymour has provided further motivation for studying both mathematical and computational aspects of graph minor theory.
-
Extremal Functions for Kt-s Minors and Coloring Graphs with No Kt-s Minors
… we first study the extremal functions for K8-4 minors, K9-6 minors, and K10-12 minors. We show that every graph on n ≥ 9 vertices with at least 4.5n-12 edges has a K8-4 minor, every graph on n ≥ 9 vertices with at least 5n-14 edges has a K9-6 minor, and every graph on n ≥ 10 vertices with at …
-
Clique minors in dense matroids
The objective of this thesis is to bound the number of points a $U_{2,\ell+2}$- and $M(K_{k+1})$-minor-free matroid has. We first prove that a sufficiently large matroid will contain a structure called a tower. We then use towers to find a complete minor in a matroid with no $U_{2,\ell+2}$-minor.
-
Local Structure for Vertex-Minors
… vertex-minor; the conjecture is like the Graph Minors Structure Theorem of Robertson and Seymour but for vertex-minors instead of minors. We take a step towards proving the conjecture by determining the "local structure''. Our first main theorem is a grid theorem for vertex-minors, and our …
-
Coloring Graphs with Forbidden Minors
… Mader's bound for the extremal function for Kt-minors is true. Additionally, we show that any graph with no K−8 - minor is 9-colorable, and any graph with no K=8-minor is 8-colorable. The Kempe-chain method developed for our proofs of the above results may be of independent interest. We also use …
-
Capturing elements in matroid minors
In this dissertation, we begin with an introduction to a matroid as the natural generalization of independence arising in three different fields of mathematics. In the first chapter, we develop graph theory and matroid theory terminology necessary to the topic of this dissertation. In Chapter 2 and …
-
Selected Problems on Matroid Minors
… topics include duality, connectivity, matroid minors, and Cunningham and Edmonds's tree decomposition for connected matroids. One of the most well-known excluded-minor results in matroid theory is Tutte's characterization of binary matroids. The class of binary matroids is one of the most …
-
Ramsey Theory Using Matroid Minors
… to force the existence of certain specified minors in that matroid? This question cannot be answered for an arbitrary collection of specified minors. However, there are results from the literature for which the number N exists for certain collections of minors. We first encode totally …
-
On coaxial minors of determinants
Thesis (M.A.)--University of Kansas, Mathematics, 1922. ; Includes bibliographical references.
-
Reconstruction of functions from minors
… notions of functions of several arguments and minors give immediately rise to the following reconstruction problem: Is a function f: A^n→B uniquely determined, up to permutation of arguments, by its identification minors, i.e., the minors obtained by identifying a pair of arguments? We review …
-
Minors and planar embeddings of digraphs
… local rotation. Three different variations of minors are presented, each of which produces a finite set of obstructions to clustered planarity. These variations include new operations on digraphs, and measures which refine the partial ordering. Tournaments are digraphs with exactly one edge …
-
Interpreting for minors in legal settings
The questioning of vulnerable individuals such as minors requires special training and a particular set of skills for the encounter to be conducted in a child-sensitive fashion. While it is known that in many instances interpreters and professionals working in legal settings lack training in how to …
-
Connectivity, tree-decompositions and unavoidable-minors
… the very general, yet wildly qualitative, Graph Minors Structure Theorem. This thesis introduces a refinement of the notion of tree-width. Tree-width is a measure of how “tree-like” a graph is. Essentially, a graph is tree-like if it can be decomposed across a collection of non-crossing …
-
Unavoidable minors in graphs and matroids
… we ensure the presence of more highly structured minors. In particular, for all positive integers k, every 2-connected graph G has a series minor isomorphic to a k-edge cycle or K_{2,k}. In 1993, Oxley, Oporowski, and Thomas extended this result to 3- and internally 4-connected graphs identifying …
-
Excluded minors for nearly-paving matroids
… is to determine the complete list of excluded minors for the minor-closed class. For example, the class of planar graphs is characterized (Kuratowski’s Theorem) by graphs that do not have any minor that is isomorphic to K_5 or K_3,3. In this presentation, we introduce several fundamental …
-
The Extremal Function for K10 Minors
We prove that every graph on n >= 8 vertices and at least 8n-35 edges either has a K10 minor or is isomorphic to some graph included in a few families of exceptional graphs.
-
Applications of Hypergraphic Matrix Minors via Contributors
Hypergrahic matrix-minors via contributors can be utilized in a variety of ways. Specifically, this thesis illustrates that they are useful in extending Kirchhoff-type Laws to signed graphs and to reinterpret Hadamard's maximum determinant problem. First, we discuss how the incidence-oriented …
-
On the Excluded Minors for Dyadic Matroids
… is a natural step to finding the excluded minors for $GF(5)$-representability. In this thesis we characterize the ternary matroids $M$ that are excluded minors for dyadic matroids and contains a 3-separation. We will show that one side of the separation has size at most four, and that $M$ …
Page 1 of 32