1,721,003 research outputs found
Controlling representations of frame matroids
No full textReport on joint work in progress with Dillon Mayhew, Victoria University of Wellington, New Zealand delivered at the Canadian Discrete and Algorithmic Mathematics (CANDAM) Conference, Winnipeg, Manitoba (June 5-8, 2023).
A matroid is an abstract object that generalises both graphs and vector spaces. Matroids are used to model many types of optimisation problems; often modelling a problem using a matroid can lead to an efficient algorithm for finding optimal solutions. Frame matroids are an important type of matroid, and frame matroids can be represented by biased graphs. Unfortunately, understanding all the biased graph representations of a given frame matroids is difficult, and little is known. We present a theorem which provides a rough biased graphical structure for representations of frame matroids that are sufficiently large, and discuss implications for understanding those substructures that cannot occur in any frame matroid.Conference Presentationmatroid theoryframe matroidsbiased graph
Defining bicircular matroids in monadic logic
No full textWe conjecture that the class of frame matroids can be characterized by a sentence in the monadic second-order logic of matroids, and we prove that there is such a characterization for the class of bicircular matroids. The proof does not depend on an excluded-minor characterization.Peer reviewedFinal article publishe
Golden-Mean and Secret Sharing Matroids
No full textMaximum-sized results are an important part of matroid theory, and results
currently exist for various classes of matroids. Archer conjectured that the
maximum-sized golden-mean matroids fall into three distinct classes, as op-
posed to the one class of all current results. We will prove a partial result
that we hope will lead to a full proof.
In the second part of this thesis, we look at secret sharing matroids, with a
particular emphasis on the class of group-induced p-representable matroids,
as introduced by Matúš. We give new proofs for results of Matúš', relating
to M(K₄), F₇ and F⁻₇. We show that the techniques used do not extend
in some natural ways, and pose some unanswered questions relating to the
structure of secret sharing matroids
Randomness in classes of matroids
No full textThis thesis is inspired by the observation that we have no good random model for matroids. That stands in contrast to graphs, which admit a number of elegant random models. As a result we have relatively little understanding of the properties of a "typical" matroid. Acknowledging the difficulty of the general case, we attempt to gain a grasp on randomness in some chosen classes of matroids.
Firstly, we consider sparse paving matroids, which are conjectured to dominate the class of matroids (that is to say, asymptotically almost all matroids would be sparse paving). If this conjecture were true, then many results on properties of the random sparse paving matroid would also hold for the random matroid. Sparse paving matroids have limited richness of structure, making counting arguments in particular more feasible than for general matroids. This enables us to prove a number of asymptotic results, particularly with regards to minors.
Secondly, we look at Graham-Sloane matroids, a special subset of sparse paving matroids with even more limited structure - in fact Graham-Sloane matroids on a labelled groundset can be randomly generated by a process as simple as independently including certain bases with probability 0.5. Notably, counting Graham-Sloane matroids has provided the best known lower bound on the total number of matroids, to log-log level. Despite the vast size of the class we are able to prove severe restrictions on what minors of Graham-Sloane matroids can look like.
Finally we consider transversal matroids, which arise naturally in the context of other mathematical objects - in particular partial transversals of set systems and partial matchings in bipartite graphs. Although transversal matroids are not in one-to-one correspondence with bipartite graphs, we shall link the two closely enough to gain some useful results through exploiting the properties of random bipartite graphs. Returning to the theme of matroid minors, we prove that the class of transversal matroids of given rank is defined by finitely many excluded series-minors. Lastly we consider some other topics, including the axiomatisability of transversal matroids and related classes
Matroids, Cyclic Flats, and Polyhedra
No full textMatroids have a wide variety of distinct, cryptomorphic axiom systems that are capable of defining them. A common feature of these is that they are able to be efficiently tested, certifying whether a given input complies with such an axiom system in polynomial time. Joseph Bonin and Anna de Mier, rediscovering a theorem first proved by Julie Sims, developed an axiom system for matroids in terms of their cyclic flats and the ranks of those cyclic flats. As with other matroid axiom systems, this is able to be tested in polynomial time. Distinct, non-isomorphic matroids may each have the same lattice of cyclic flats, and so matroids cannot be defined solely in terms of their cyclic flats. We do not have a clean characterisation of families of sets that are cyclic flats of matroids. However, it may be possible to tell in polynomial time whether there is any matroid that has a given lattice of subsets as its cyclic flats. We use Bonin and de Mier’s cyclic flat axioms to reduce the problem to a linear program, and show that determining whether a given lattice is the lattice of cyclic flats of any matroid corresponds to finding integral points in the solution space of this program, these points representing the possible ranks that may be assigned to the cyclic flats. We distinguish several classes of lattice for which solutions may be efficiently found, based upon the nature of the matrix of coefficients of the linear program, and of the polyhedron it defines, and then identify families of lattice that belong to those classes. We define operations and transformations on lattices of sets by examining matroid operations, and examine how these operations affect membership in the aforementioned classes. We conjecture that it is always possible to determine, in polynomial time, whether a given collection of subsets makes up the lattice of cyclic flats of any matroid
Identically Self-Dual Matroids
No full textIn this thesis we focus on identically self-dual matroids and their minors. We show that every sparse paving matroid is a minor of an identically self-dual sparse paving matroid. The same result is true if the property sparse paving is replaced with the property of representability and more specifically, F-representable where F is a field of characteristic 2, an algebraically closed field, or equal to GF(p) for a prime p = 3 (mod 4).
We extend a result of Lindstrom [11] saying that no identically self-dual matroid is regular and simple. We assert that this also applies to all matroids which can be obtained by contracting an identically self-dual matroid.
Finally, we present a characterisation of identically self-dual frame matroids and prove that the class of self-dual matroids is not axiomatisable
On Maximum-Sized Golden-Mean Matroids
No full textA rank-r simple matroid is maximum-sized in a class if it has the largest number of elements out of all simple rank-r matroids in that class. Maximum-sized matroids have been classified for various classes of matroids: regular (Heller, 1957); dyadic (Kung and Oxley, 1988-90); k-regular (Semple, 1998); near-regular and sixth-root-of-unity (Oxley, Vertigan, and Whittle, 1998).
Golden-mean matroids are matroids that are representable over the golden-mean partial field. Equivalently, a golden-mean matroid is a matroid that is representable over GF(4) and GF(5).
Archer conjectured that there are three families of maximum-sized golden-mean matroids. This means that a proof of Archer’s conjecture is likely to be significantly more complex than the proofs of existing maximum-sized characterisations, as they all have only one family.
In this thesis, we consider the four following subclasses of golden-mean matroids: those that are lifts of regular matroids, those that are lifts of nearregular matroids, those that are golden-mean-graphic, and those that have a spanning clique. We close each of these classes under minors, and prove that Archer’s conjecture holds in each of them.
It is anticipated that the last of our theorems will lead to a proof of Archer’s conjecture for golden-mean matroids of sufficiently high rank
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Matroids, Complexity and Computation
No full textThe node deletion problem on graphs is: given a graph and integer k, can we
delete no more than k vertices to obtain a graph that satisfies some property π.
Yannakakis showed that this problem is NP-complete for an infinite family of well-
defined properties. The edge deletion problem and matroid deletion problem are
similar problems where given a graph or matroid respectively, we are asked if we
can delete no more than k edges/elements to obtain a graph/matroid that satisfies
a property π. We show that these problems are NP-hard for similar well-defined
infinite families of properties.
In 1991 Vertigan showed that it is #P-complete to count the number of bases
of a representable matroid over any fixed field. However no publication has been
produced. We consider this problem and show that it is #P-complete to count
the number of bases of matroids representable over any infinite fixed field or finite
fields of a fixed characteristic.
There are many different ways of describing a matroid. Not all of these are
polynomially equivalent. That is, given one description of a matroid, we cannot
create another description for the same matroid in time polynomial in the size of
the first description. Due to this, the complexity of matroid problems can vary
greatly depending on the method of description used. Given one description a
problem might be in P while another description gives an NP-complete problem.
Based on these interactions between descriptions, we create and study the hierarchy
of all matroid descriptions and generalize this to all descriptions of countable
objects
- …
