1,720,965 research outputs found
Matching variables to equations in infinite linear equation systems
No full textA fundamental result in linear algebra states that if a homogenous linear equation system has only the trivial solution, then there are at most as many variables as equations. We prove the following generalisation of this phenomenon. If a possibly infinite homogenous linear equation system with finitely many variables in each equation has only the trivial solution, then there exists an injection from the variables to the equations that maps each variable to an equation in which it appears. © 2022 The Authors11Nsciescopu
Representations of Infinite Tree Sets
No full textTree sets are abstract structures that can be used to model various tree-shaped objects in combinatorics. Finite tree sets can be represented by finite graph-theoretical trees. We extend this representation theory to infinite tree sets. First we characterise those tree sets that can be represented by tree sets arising from infinite trees; these are precisely those tree sets without a chain of order type omega + 1. Then we introduce and study a topological generalisation of infinite trees which can have limit edges, and show that every infinite tree set can be represented by the tree set admitted by a suitable such tree-like space11Nsciescopu
Enlarging vertex-flames in countable digraphs
Full text link© 2021 The Author(s)A rooted digraph is a vertex-flame if for every vertex v there is a set of internally disjoint directed paths from the root to v whose set of terminal edges covers all ingoing edges of v. It was shown by Lovász that every finite rooted digraph admits a spanning subdigraph which is a vertex-flame and large, where the latter means that it preserves the local connectivity to each vertex from the root. Calvillo-Vives rediscovered and extended this theorem proving that every vertex-flame of a given finite rooted digraph can be extended to be large. The analogue of Lovász' result for countable digraphs was shown by the third author where the notion of largeness is interpreted in a structural way as in the infinite version of Menger's theorem. We give a common generalisation of this and Calvillo-Vives' result by showing that in every countable rooted digraph each vertex-flame can be extended to a large vertex-flame.11Nsciescopu
A Cantor-Bernstein-type theorem for spanning trees in infinite graphs
Full text linkWe show that if a graph admits a packing and a covering both consisting of ? many spanning trees, where ? is some infinite cardinal, then the graph also admits a decomposition into ? many spanning trees. For finite ? the analogous question remains open, however, a slightly weaker statement is proved. ? 2021 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).11Nsciescopu
Characterising <i>k</i>-connected sets in infinite graphs
No full textA k-connected set in an infinite graph, where k > 0 is an integer, is a set of vertices such that any two of its subsets of the same size ≤ k can be connected by disjoint paths inthe whole graph. We characterise the existence of k-connected sets of arbitrary but fixed infinite cardinality via the existence of certain minors and topological minors. We also prove a duality theorem for the existence of such k-connected sets: if a graph contains no such k-connected set, then it has a tree-decomposition which, whenever it exists, precludes the existence of such a k-connected set.<br/
On the infinite Lucchesi–Younger conjecture I
Full text link© 2021 The Authors. Journal of Graph Theory published by Wiley Periodicals LLCA dicut in a directed graph is a cut for which all of its edges are directed to a common side of the cut. A famous theorem of Lucchesi and Younger states that in every finite digraph the least size of an edge set meeting every dicut equals the maximum number of disjoint dicuts in that digraph. In this first paper out of a series of two papers, we conjecture a version of this theorem using a more structural description of this min-max property for finite dicuts in infinite digraphs. We show that this conjecture can be reduced to countable digraphs where the underlying undirected graph is 2-connected, and we prove several special cases of the conjecture.11Nsciescopu
Base Partition for Mixed Families of Finitary and Cofinitary Matroids
Full text linkLet M = (Mi: i ∈ K) be a finite or infinite family consisting of matroids on a common ground set E each of which may be finitary or cofinitary. We prove the following Cantor-Bernstein-type result: If there is a collection of bases, one for each Mi, which covers the set E, and also a collection of bases which are pairwise disjoint, then there is a collection of bases which partition E. We also show that the failure of this Cantor-Bernstein-type statement for arbitrary matroid families is consistent relative to the axioms of set theory ZFC.11Nsciescopu
Topological ubiquity of trees
No full textLet ⊲ be a relation between graphs. We say a graph G is ⊲-ubiquitous if whenever Γ is a graph with for all , then one also has , 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.<br/
Obstructions for bounded branch-depth in matroids
No full textDeVos, Kwon, and Oum introduced the concept of branch-depth of matroids as a
natural analogue of tree-depth of graphs. They conjectured that a matroid of
sufficiently large branch-depth contains the uniform matroid or the
cycle matroid of a large fan graph as a minor. We prove that matroids with
sufficiently large branch-depth either contain the cycle matroid of a large fan
graph as a minor or have large branch-width. As a corollary, we prove their
conjecture for matroids representable over a fixed finite field and
quasi-graphic matroids, where the uniform matroid is not an option
- …
