Search

Applying a recent extension (2015) of a structure theorem of Robertson, Seymour and Thomas from 1993, in this paper we establish Robertson's magic-tree conjecture from 1997. [ABSTRACT FROM AUTHOR]

Let ⊲ be a relation between graphs. We say a graph G is ⊲ -ubiquitous if whenever Γ is a graph with n G ⊲ Γ for all n ∈ N , then one also has ℵ 0 G ⊲ Γ , where αG is the disjoint union of α many copies of G. The Ubiquity Conjecture of Andreae, a well-known open problem in the theory of infinite graphs, asserts that every locally finite connected graph is ubiquitous with respect to the minor relation. In this paper we show that all trees are ubiquitous with respect to the topological minor relation, irrespective of their cardinality. This answers a question of Andreae from 1979. [ABSTRACT FROM AUTHOR]

Using a new technique, we prove a rich family of special cases of the matroid intersection conjecture. Roughly, we prove the conjecture for pairs of tame matroids which have a common decomposition by 2-separations into finite parts. [ABSTRACT FROM AUTHOR]

A hypergroup is stringent if a ⊞ b is a singleton whenever a ≠ − b. A hyperfield is stringent if the underlying additive hypergroup is. Every doubly distributive skew hyperfield is stringent, but not vice versa. We present a classification of stringent hypergroups, from which a classification of doubly distributive skew hyperfields follows. It follows from our classification that every such hyperfield is a quotient of a skew field. [ABSTRACT FROM AUTHOR]

Abstract We present an algebraic framework which simultaneously generalizes the notion of linear subspaces, matroids, valuated matroids, oriented matroids, and regular matroids. To do this, we first introduce algebraic objects which we call tracts ; they generalize both hyperfields in the sense of Krasner and partial fields in the sense of Semple and Whittle. We then define matroids over tracts; in fact, there are (at least) two natural notions of matroid in this general context, which we call weak and strong matroids. We give "cryptomorphic" axiom systems for such matroids in terms of circuits, Grassmann–Plücker functions, and dual pairs, and establish some basic duality results. We then explore sufficient criteria for the notions of weak and strong matroids to coincide. This is the case whenever vectors and covectors are orthogonal, and is closely related to the notion of "perfect fuzzy rings" from [15]. For example, if F is a particularly nice kind of tract called a doubly distributive partial hyperfield, we show that the notions of weak and strong matroid over F coincide. Our theory of matroids over tracts is closely related to but more general than "matroids over fuzzy rings" in the sense of Dress and Dress–Wenzel [12–15]. [ABSTRACT FROM AUTHOR]

Abstract Two graphs G and H are hypomorphic if there exists a bijection φ : V (G) → V (H) such that G − v ≅ H − φ (v) for each v ∈ V (G). A graph G is reconstructible if H ≅ G for all H hypomorphic to G. Nash-Williams proved that all locally finite connected graphs with a finite number ⩾2 of ends are reconstructible, and asked whether locally finite connected graphs with one end or countably many ends are also reconstructible. In this paper we construct non-reconstructible connected graphs of bounded maximum degree with one and countably many ends respectively, answering the two questions of Nash-Williams about the reconstruction of locally finite graphs in the negative. [ABSTRACT FROM AUTHOR]

We show that any infinite matroid can be reconstructed from the torsos of a tree-decomposition over its 2-separations, together with local information at the ends of the tree. We show that if the matroid is tame then this local information is simply a choice of whether circuits are permitted to use that end. The same is true if each torso is planar, with all gluing elements on a common face. [ABSTRACT FROM AUTHOR]

The notion of thin sums matroids was invented to extend the notion of representability to non-finitary matroids. A matroid is tame if every circuit–cocircuit intersection is finite. We prove that a tame matroid is a thin sums matroid over a finite field k if and only if all its finite minors are representable over k . [ABSTRACT FROM AUTHOR]

We show that any graph that contains k edge-disjoint double rays for any k ∈ N contains also infinitely many edge-disjoint double rays. This was conjectured by Andreae in 1981. [ABSTRACT FROM AUTHOR]

Building on the recent axiomatisation of infinite matroids with duality, we present a theory of representability for infinite matroids. This notion of representability allows for infinite sums, and is preserved under duality. [ABSTRACT FROM AUTHOR]

Abstract: We construct some matroids that have a circuit and a cocircuit with infinite intersection. This answers a question of Bruhn, Diestel, Kriesell, Pendavingh and Wollan. It further shows that the axiom system for matroids proposed by Dress in 1986 does not axiomatize all infinite matroids. We show that one of the matroids we define is a thin sums matroid whose dual is not a thin sums matroid, answering a natural open problem in the theory of thin sums matroids. [Copyright &y& Elsevier]

The class of quasi-graphic matroids recently introduced by Geelen, Gerards, and Whittle generalises each of the classes of frame matroids and lifted-graphic matroids introduced earlier by Zaslavsky. For each biased graph (G , B) Zaslavsky defined a unique lift matroid L (G , B) and a unique frame matroid F (G , B) , each on ground set E (G). We show that in general there may be many quasi-graphic matroids on E (G) and describe them all: for each graph G and partition (B , L , F) of its cycles such that B satisfies the theta property and each cycle in L meets each cycle in F , there is a quasi-graphic matroid M (G , B , L , F) on E (G). Moreover, every quasi-graphic matroid arises in this way. We provide cryptomorphic descriptions in terms of subgraphs corresponding to circuits, cocircuits, independent sets, and bases. Equipped with these descriptions, we prove some results about quasi-graphic matroids. In particular, we provide alternate proofs that do not require 3-connectivity of two results of Geelen, Gerards, and Whittle for 3-connected matroids from their introductory paper: namely, that every quasi-graphic matroid linearly representable over a field is either lifted-graphic or frame, and that if a matroid M has a framework with a loop that is not a loop of M then M is either lifted-graphic or frame. We also provide sufficient conditions for a quasi-graphic matroid to have a unique framework. Zaslavsky has asked for those matroids whose independent sets are contained in the collection of independent sets of F (G , B) while containing those of L (G , B) , for some biased graph (G , B). Adding a natural (and necessary) non-degeneracy condition defines a class of matroids, which we call biased-graphic. We show that the class of biased-graphic matroids almost coincides with the class of quasi-graphic matroids: every quasi-graphic matroid is biased-graphic, and if M is a biased-graphic matroid that is not quasi-graphic then M is a 2-sum of a frame matroid with one or more lifted-graphic matroids. [ABSTRACT FROM AUTHOR]