• Admin
    UC Research Repository
    View Item 
       
    • UC Home
    • Library
    • UC Research Repository
    • College of Engineering
    • Engineering: Reports
    • View Item
       
    • UC Home
    • Library
    • UC Research Repository
    • College of Engineering
    • Engineering: Reports
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Browse

    All of the RepositoryCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    Statistics

    View Usage Statistics

    Fork-decompositions of matroids

    Thumbnail
    View/Open
    hall_oxley_semple_whittle_ucdms2002-1_report.pdf (2.221Mb)
    Author
    Hall, R.
    Oxley, J.
    Semple, C.
    Whittle, G.
    Date
    2002
    Permanent Link
    http://hdl.handle.net/10092/12526

    One of the central problems in matroid theory is Rota's conjecture that, for all prime powers q, the class of GF(q)-representable matroids has a finite set of excluded minors. This conjecture has been settled for q ≤ 4 but remains open otherwise. Further progress towards this conjecture has been hindered by the fact that, for all q > 5, there are 3-connected GF(q)-representable matroids having arbitrarily many inequivalent GF(q)-representations. This fact refutes a 1988 conjecture of Kahn that 3-connectivity would be strong enough to ensure an absolute bound on the number of such inequivalent representations. This paper introduces fork-connectivity, a new type of self-dual 4-connectivity, which we conjecture is strong enough to guarantee the existence of such a bound but weak enough to allow for an analogue of Seymour's Splitter Theorem. We prove that every fork-connected matroid can be reduced to a vertically 4-connected matroid by a sequence of operations that generalize ∆ - Y and Y - ∆ exchanges. It follows from this that the analogue of Kahn's Conjecture holds for fork-connected matroids if and only if it holds for vertically 4-connected matroids. The class of fork-connected matroids includes the class of 3-connected forked matroids. By taking direct sums and 2-sums of matroids in the latter class, we get the class M of forked matroids, which is closed under duality and minors. The class M is a natural subclass of the class of matroids of branch-width at most 3 and includes the matroids of path-width at most 3. We give a constructive characterization of the members of M and prove that M has finitely many excluded minors.

    Subjects
    Field of Research::01 - Mathematical Sciences::0101 - Pure Mathematics::010104 - Combinatorics and Discrete Mathematics (excl. Physical Combinatorics)
    Collections
    • Engineering: Reports [695]
    Rights
    https://canterbury.libguides.com/rights/theses

    UC Research Repository
    University Library
    University of Canterbury
    Private Bag 4800
    Christchurch 8140

    Phone
    364 2987 ext 8718

    Email
    ucresearchrepository@canterbury.ac.nz

    Follow us
    FacebookTwitterYoutube

    © University of Canterbury Library
    Send Feedback | Contact Us