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 24 for “"binary matroids"”.

  1. Counting Pentagons in Triangle-free Binary Matroids

    A rank-n binary matroid is a spanning subset E of F₂ⁿ\{0}, a triangle is a set of three elements from E which sum to zero, and the density of a rank-n binary matroid is |E|/2ⁿ. We begin by giving a new exposition of a result due to Davydov and Tombak, which states that if E is a rank-n …

    waterloo Repository record for Counting Pentagons in Triangle-free Binary Matroids (opens in a new tab)

  2. On The Density of Binary Matroids Without a Given Minor

    … question: how many elements can a simple binary matroid with no $\PG(t,2)$-minor have? This is a natural analogue of questions asked about the density of graphs in minor-closed classes. We will answer this question by finding the eventual growth rate function of the class of matroids with …

    waterloo Repository record for On The Density of Binary Matroids Without a Given Minor (opens in a new tab)

  3. Formalizing the Excluded Minor Characterization of Binary Matroids in the Lean Theorem Prover

    … are often concerned with representations of matroids over fields. Tutte's seminal theorem proven in 1958 characterizes matroids representable over GF(2) by noncontainment of U2,4 as a matroid minor. In this thesis, we document a formalization of the theorem and its proof in the Lean Theorem …

    waterloo Repository record for Formalizing the Excluded Minor Characterization of Binary Matroids in the Lean Theorem Prover (opens in a new tab)

  4. Matroid Generalizations of Some Graph Results

    … natural cyclic orderings. We investigate the matroids for which a similar cyclic ordering of the circuits is possible. A full characterization of the non-binary matroids with this property is given. Evidence of the difficulty of this problem for binary matroids is presented, along with a …

    lsu-thes Repository record for Matroid Generalizations of Some Graph Results (opens in a new tab)

  5. On Binary And Regular Matroids Without Small Minors

    … consist of excluded-minor results for Binary Matroids and excluded-minor results for Regular Matroids. Structural theorems on the relationship between minors and k-sums of matroids are developed here in order to provide some of these characterizations. Chapter 2 of the dissertation …

    mississippi Repository record for On Binary And Regular Matroids Without Small Minors (opens in a new tab)

  6. Bicircular Matroids with Circuits of at Most Two Sizes

    … that Murty in his paper titled, Equicardinal Matroids and Finite Geometries in 1968, was the first to study matroids with all hyperplanes having the same size. Murty called such a matroid an ``Equicardinal Matroid''. Young renamed such a matroid a ``Matroid Design''. Further work on …

    mississippi Repository record for Bicircular Matroids with Circuits of at Most Two Sizes (opens in a new tab)

  7. Induced-minor-closed classes of matroids

    … consider the class of simple GF(q)-representable matroids that can be built from projective geometries over GF(q) by repeated generalized parallel connections across projective geometries. We show that this class of matroids is closed under induced minors and characterize the class by its …

    lsu-thes Repository record for Induced-minor-closed classes of matroids (opens in a new tab)

  8. Selected Problems on Matroid Minors

    This dissertation begins with an introduction to matroids and graphs. In the first chapter, we develop matroid and graph theory definitions and preliminary results sufficient to discuss the problems presented in the later chapters. These topics include duality, connectivity, matroid minors, and …

    lsu-thes Repository record for Selected Problems on Matroid Minors (opens in a new tab)

  9. Characterizations of Certain Classes of Graphs and Matroids

    … exemplifies a more general theorem about matroids." Most of my work draws inspiration from this assertion, made by Tutte in 1979. In 2004, Ehrenfeucht, Harju and Rozenberg proved that all graphs can be constructed from complete graphs via a sequence of the operations of complementation, …

    lsu-thes Repository record for Characterizations of Certain Classes of Graphs and Matroids (opens in a new tab)

  10. Connectivity of Matroids and Polymatroids

    … Connectivity is a useful property of matroids that allows a matroid to be decomposed naturally into its connected components, which are like blocks in a graph. The Cunningham-Edmonds tree decomposition further gives a way to decompose matroids into 3-connected minors. Much of the …

    lsu-thes Repository record for Connectivity of Matroids and Polymatroids (opens in a new tab)

  11. Recognizing Even-Cycle and Even-Cut Matroids

    Even-cycle and even-cut matroids are classes of binary matroids that generalize respectively graphic and cographic matroids. We give algorithms to check membership for these classes of matroids. We assume that the matroids are 3-connected and are given by their (0,1)-matrix representations. We …

    waterloo Repository record for Recognizing Even-Cycle and Even-Cut Matroids (opens in a new tab)

  12. Comparing 3-Connectedness and Roundness in Matroid Theory

    … in graph theory. There are many broad classes of matroids. Important examples include binary matroids, graphic matroids, regular matroids, uniform matroids, and various levels of connected matroids. Some of the most important problems in matroid theory involve characterizing classes of matroids so …

    csusb Repository record for Comparing 3-Connectedness and Roundness in Matroid Theory (opens in a new tab)

  13. Beta invariant and variations of chain theorems for matroids

    … lower bound of the beta invariant of 3-connected matroids with rank r and the matroids which attain the lower bound. Second we characterize the matroids with beta invariant 5 and 6. For binary matroids we characterize matroids with beta invariant 7. These results extend earlier work of Oxley. …

    mississippi Repository record for Beta invariant and variations of chain theorems for matroids (opens in a new tab)

  14. The structure of 4-separations in 4-connected matroids

    … petals. Specializing to the case of 4-connected matroids, we give a new notion of equivalence of 4-separations that we show will be needed to describe a tree decomposition for 4-connected matroids. Finally, we characterize all internally 4-connected binary matroids M with the property that the …

    lsu-thes Repository record for The structure of 4-separations in 4-connected matroids (opens in a new tab)

  15. Theory and applications of freedom in matroids

    … flats of M*. If ζ(M) is the set of integer polymatroids with underlying matroid structure M, then we show that for any cell e of M ǁ e ǁ= \frac{max\ f \ (e)}{f\in\zeta} We look at freedom in binary matroids and show that for a connected binary matroid M, ǁ e ǁ is the number of connected …

    the-open-u Download PDF for Theory and applications of freedom in matroids (opens in a new tab)

  16. Representations of even-cycle and even-cut matroids

    In this thesis, two classes of binary matroids will be discussed: even-cycle and even-cut matroids, together with problems which are related to their graphical representations. Even-cycle and even-cut matroids can be represented as signed graphs and grafts, respectively. A signed graph is a pair …

    waterloo Repository record for Representations of even-cycle and even-cut matroids (opens in a new tab)

  17. Extremal Problems in Matroid Connectivity

    … minors from a given list of 3-connected matroids. Bixby’s Lemma is a well-known inductive tool in matroid theory that says that each element in a 3-connected matroid can be deleted or contracted to obtain a matroid that is 3-connected up to minimal 2-separations. We consider the binary …

    lsu-thes Repository record for Extremal Problems in Matroid Connectivity (opens in a new tab)

  18. Even Cycle and Even Cut Matroids

    In this thesis we consider two classes of binary matroids, even cycle matroids and even cut matroids. They are a generalization of graphic and cographic matroids respectively. We focus on two main problems for these classes of matroids. We first consider the Isomorphism Problem, that is the …

    waterloo Repository record for Even Cycle and Even Cut Matroids (opens in a new tab)

  19. Some problems in combinatorial geometry

    … parts. The first two chapters deal with infinite matroids and the remaining three chapters with finite matroids.</p> <p>Chapter 1 has two main results. Firstly we prove that there is no duality function on the class of independence spaces which behaves like duality for finite matroids. Secondly we …

    oxford Repository record for Some problems in combinatorial geometry (opens in a new tab)

  20. Matróides binárias com circunferência 6

    … iniciou-se com a publicação dos artigos Matroids Having Small Circumference, Combinatorics, Probability and Compumting (2001) 10, 349-360 e Connected matroids with a small circumference, Discrete Mathematics 259 (2002) 147-161 de Braulio Maia Junior e Manoel Lemos, onde eles construíram …

    brazil-ufpe Repository record for Matróides binárias com circunferência 6 (opens in a new tab)

Page 1 of 2