Search

In the theory of classical matroids, there are several known equivalent axiomatic systems that define a matroid, which are described as matroid cryptomorphisms. A q-matroid is a q-analogue of a matroid where subspaces play the role of the subsets in the classical theory. In this article we establish cryptomorphisms of q-matroids. In doing so we highlight the difference between classical theory and its q-analogue. We introduce a comprehensive set of q-matroid axiom systems and show cryptomorphisms between them and existing axiom systems of a q-matroid. These axioms are described as the rank, closure, basis, independence, dependence, circuit, hyperplane, flat, open space, spanning space, non-spanning space, and bi-colouring axioms.

This paper extends the concept of filter on X into (X, f), where X is a finite underlying set and f is a symmetric submodular function from $$2^X$$ to N. Then, we show a cryptomorphism between a free ultrafilter and co-tangle on (X, f). The paper also provides game-theoretical interpretations of a branch decomposition tree and a free ultrafilter on (X, f).

We initiate the study of group actions on (possibly infinite) semimatroids and geometric semilattices. To every such action is naturally associated an orbit-counting function, a two-variable “Tutte” polynomial and a poset which, in the representable case, coincides with the poset of connected components of intersections of the associated toric arrangement. In this structural framework we recover and strongly generalize many enumerative results about arithmetic matroids, arithmetic Tutte polynomials and toric arrangements by finding new combinatorial interpretations beyond the representable case. In particular, we thus find a class of natural examples of nonrepresentable arithmetic matroids. Moreover, we discuss actions that give rise to matroids over Z with natural combinatorial interpretations. As a stepping stone toward our results we also prove an extension of the cryptomorphism between semimatroids and geometric semilattices to the infinite case.

Since its first appearence in the book Vorstudien zur Topologie by Johann Benedict Listing of 1847, topology (then and for a long period termed analysis situs ) has been given many facets; among the main ones are considerations of neighborhoods, open sets, and closed sets. We start here, giving the corresponding definitions lifted to point-free as well as quantifier-free versions, showing how they are interrelated, thus exhibiting their cryptomorphism and offering the possibility to transform one version into the other, not least visualizing them via TituRel programs.

We introduce the notion of a quasi-matroidal class of ordered simplicial complexes: an approximation to the idea of a matroid cryptomorphism in the landscape of ordered simplicial complexes. A quasi-matroidal class contains pure shifted simplicial complexes and ordered matroid independence complexes. The essential property is that if a fixed simplicial complex belongs to this class for every ordering of its vertex set, then it is a matroid independence complex. Some examples of such classes appear implicitly in the matroid theory literature. We introduce various such classes that highlight different apsects of matroid theory and its similarities with the theory of shifted simplicial complexes. For example, we lift the study of objects like the Tutte polynomial and nbc complexes to a quasi-matroidal class that allows us to define such objects for shifted complexes. Furthermore, some of the quasi-matroidal classes are amenable to inductive techniques that can't be applied directly in the context of matroid theory. As an example, we provide a suitable setting to reformulate and extend conjecture of Stanley about $h$-vectors of matroids which is expected to be tractable with techniques that are out of reach for matroids alone. This new conjecture holds for pure shifted simplicial complexes and matroids of rank up to 4., Comments are welcome. Long version of "Relaxations of the matroid axioms: Independence, exchange, and Circuits" presented at FPSAC 16

This article is an introduction to matroid theory aimed at algebraic geometers. Matroids are combinatorial abstractions of linear subspaces and hyperplane arrangements. Not all matroids come from linear subspaces; those that do are said to be representable. Still, one may apply linear algebraic constructions to non-representable matroids. There are a number of different definitions of matroids, a phenomenon known as cryptomorphism. In this survey, we begin by reviewing the classical definitions of matroids, develop operations in matroid theory, summarize some results in representability, and construct polynomial invariants of matroids. Afterwards, we focus on matroid polytopes, introduced by Gelfand–Goresky–MacPherson–Serganova, which give a cryptomorphic definition of matroids. We explain certain locally closed subsets of the Grassmannian, thin Schubert cells, which are labeled by matroids, and which have applications to representability, moduli problems, and invariants of matroids following Fink–Speyer. We explain how matroids can be thought of as cohomology classes in a particular toric variety, the permutohedral variety, by means of Bergman fans, and apply this description to give an exposition of the proof of log-concavity of the characteristic polynomial of representable matroids due to the author with Huh.

U ovom diplomskom radu proučavamo razne definicije pojma matroida. Za definicije koje su međusobno ekvivalentne, ali ta ekvivalencija nije očita, kažemo da su kriptomorfne. Za matroid M definiramo sedam ključnih pojmova: nezavisni skupovi, baze, ciklusi, funkcija ranga, ravnine, hiperravnine i operator zatvarača. Najprije definiramo matroid preko nezavisnih skupova i upoznajemo matroide nastale iz matrica i iz grafova. Zatim uspostavljamo kriptomorfizam između nezavisnih skupova i baza i na taj način pokazujemo da matroid možemo definirati i preko baza. Navodimo i kriptomorfizme između nezavisnih skupova i ciklusa, između nezavisnih skupova i funkcije ranga, funkcije ranga i operatora zatvarača, ravnina i operatora zatvarača, ravnina i hiperravnina. Uspostavljanjem kriptomorfizma između tih pojmova pokazujemo da se svaki od tih pojmova može koristiti kao polazište u definiranju matroida. U posljednjem poglavlju, nezavisne skupove matroida definiramo preko greedy algoritma. Ta veza daje nam dodatan uvid u važnost i posebnost matroida. This thesis is a study of various definitions of matroids. Definitions that are equivalent, but the equivalence is not obvious, are called cryptomorphic. For the matroid M the following seven key concepts are defined: independent sets, bases, cycles, rank function, planes, hyperplanes and closure operator. First we define matroids in terms of independent sets and elaborate matroids coming from matrices and graphs. Then, we explain cryptomorphism between independent sets and bases, thus showing that a matroid can be defined in terms of bases. Next, cryptomorphisms between independent sets and cycles, between independent sets and rank function, rank function and closure operator, planes and closure operator, planes and hyperplanes are established. By establishing cryptomorphisms between these concepts it is shown that each of them can be used as a starting point in defining matroids. In the last chapter, independent sets of matroids are defined through the greedy algorithm. This connection gives us further insight into the importance and uniqueness of matroids.

Concept lattices fulfil one of the aims of classification by providing a description by attributes of each class of objects. We introduce here two new similarity/dissimilarity measures: a similarity measure between concepts (elements) of a lattice and a dissimilarity measure between concept lattices defined on the same set of objects and attributes. Both measures are based on the overhanging relation previously introduced by the author, which are a cryptomorphism of lattices.

We introduce an idempotent analogue of the exterior algebra for which the theory of tropical linear spaces (and valuated matroids) can be seen in close analogy with the classical Grassmann algebra formalism for linear spaces. The top wedge power of a tropical linear space is its Plucker vector, which we view as a tensor, and a tropical linear space is recovered from its Plucker vector as the kernel of the corresponding wedge multiplication map. We prove that an arbitrary d-tensor satisfies the tropical Plucker relations (valuated exchange axiom) if and only if the d-th wedge power of the kernel of wedge-multiplication is free of rank one. This provides a new cryptomorphism for valuated matroids, including ordinary matroids as a special case., Comment: 20 pages, 2 figures, final version to appear in Manuscripta Mathematica

Let D be a dependent set in a combinatorial geometry G ( S ). The core of D is the set { x ∈ D : D x is independent}. An order filter F of subsets of S is the set of dependent sets of a geometry iff for all D ∈ F , either core D is empty or core D ∈ F . This new cryptomorphism is particularly useful in the study of extensions and strong maps.

Publisher Summary This chapter discusses cryptomorphisms of non-indexed algebras and relational systems. For universal algebras of a fixed type, there exists a sufficiently well-developed theory. In the abstract Galois theory for operations and relations, which goes back to M. Krasner, there are also many connections between non-indexed algebras and relational systems. The notion of cryptomorphism was introduced by G. Birkhoff for algebras. The chapter presents Λ-cryptomorphisms where Λ can be thought as a set of a kind of generalized superposition operators. The theory of Λ-cryptomorphisms is still at its very beginning. Λ-cryptomorphisms can be uniquely decomposed into Λ-cryptomonomorphisms and Λ-cryptoepimorphisms. Λ-cryptomorphisms of relational systems seem to be more widely applicable for describing connections between non-indexed relational systems than those of algebras.