Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userUbiquity in graphs III: Ubiquity of locally finite graphs with extensive tree-decompositions
188
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A graph $G$ is said to be ubiquitous, if every graph $Gamma$ that contains arbitrarily many disjoint $G$-minors automatically contains infinitely many disjoint $G$-minors. The well-known Ubiquity conjecture of Andreae says that every locally finite graph is ubiquitous. In this paper we show that locally finite graphs admitting a certain type of tree-decomposition, which we call an extensive tree-decomposition, are ubiquitous. In particular this includes all locally finite graphs of finite tree-width, and also all locally finite graphs with finitely many ends, all of which have finite degree. It remains an open question whether every locally finite graph admits an extensive tree-decomposition.
rate research
Read More
A graph $G$ is said to be $preceq$-ubiquitous, where $preceq$ is the minor relation between graphs, if whenever $Gamma$ is a graph with $nG preceq Gamma$ for all $n in mathbb{N}$, then one also has $aleph_0 G preceq Gamma$, where $alpha G$ is the disjoint union of $alpha$ many copies of $G$. A well-known conjecture of Andreae is that every locally finite connected graph is $preceq$-ubiquitous. In this paper we give a sufficient condition on the structure of the ends of a graph~$G$ which implies that $G$ is $preceq$-ubiquitous. In particular this implies that the full grid is $preceq$-ubiquitous.
Let $triangleleft$ be a relation between graphs. We say a graph $G$ is emph{$triangleleft$-ubiquitous} if whenever $Gamma$ is a graph with $nG triangleleft Gamma$ for all $n in mathbb{N}$, then one also has $aleph_0 G triangleleft Gamma$, where $alpha G$ is the disjoint union of $alpha$ many copies of $G$. The emph{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, which is the first of a series of papers making progress towards the Ubiquity Conjecture, 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.
A recent result of Condon, Kim, K{u}hn and Osthus implies that for any $rgeq (frac{1}{2}+o(1))n$, an $n$-vertex almost $r$-regular graph $G$ has an approximate decomposition into any collections of $n$-vertex bounded degree trees. In this paper, we prove that a similar result holds for an almost $alpha n$-regular graph $G$ with any $alpha>0$ and a collection of bounded degree trees on at most $(1-o(1))n$ vertices if $G$ does not contain large bipartite holes. This result is sharp in the sense that it is necessary to exclude large bipartite holes and we cannot hope for an approximate decomposition into $n$-vertex trees. Moreover, this implies that for any $alpha>0$ and an $n$-vertex almost $alpha n$-regular graph $G$, with high probability, the randomly perturbed graph $Gcup mathbf{G}(n,O(frac{1}{n}))$ has an approximate decomposition into all collections of bounded degree trees of size at most $(1-o(1))n$ simultaneously. This is the first result considering an approximate decomposition problem in the context of Ramsey-Turan theory and the randomly perturbed graph model.
We provide a gentle introduction, aimed at non-experts, to Borel combinatorics that studies definable graphs on topological spaces. This is an emerging field on the borderline between combinatorics and descriptive set theory with deep connections to many other areas. After giving some background material, we present in careful detail some basic tools and results on the existence of Borel satisfying assignments: Bore
This paper is motivated by the following question: what are the unavoidable induced subgraphs of graphs with large treewidth? Aboulker et al. made a conjecture which answers this question in graphs of bounded maximum degree, asserting that for all $k$ and $Delta$, every graph with maximum degree at most $Delta$ and sufficiently large treewidth contains either a subdivision of the $(ktimes k)$-wall or the line graph of a subdivision of the $(ktimes k)$-wall as an induced subgraph. We prove two theorems supporting this conjecture, as follows. 1. For $tgeq 2$, a $t$-theta is a graph consisting of two nonadjacent vertices and three internally disjoint paths between them, each of length at least $t$. A $t$-pyramid is a graph consisting of a vertex $v$, a triangle $B$ disjoint from $v$ and three paths starting at $v$ and disjoint otherwise, each joining $v$ to a vertex of $B$, and each of length at least $t$. We prove that for all $k,t$ and $Delta$, every graph with maximum degree at most $Delta$ and sufficiently large treewidth contains either a $t$-theta, or a $t$-pyramid, or the line graph of a subdivision of the $(ktimes k)$-wall as an induced subgraph. This affirmatively answers a question of Pilipczuk et al. asking whether every graph of bounded maximum degree and sufficiently large treewidth contains either a theta or a triangle as an induced subgraph (where a theta means a $t$-theta for some $tgeq 2$). 2. A subcubic subdivided caterpillar is a tree of maximum degree at most three whose all vertices of degree three lie on a path. We prove that for every $Delta$ and subcubic subdivided caterpillar $T$, every graph with maximum degree at most $Delta$ and sufficiently large treewidth contains either a subdivision of $T$ or the line graph of a subdivision of $T$ as an induced subgraph.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
