ﻻ يوجد ملخص باللغة العربية
Stanislaw Ulam asked whether there exists a universal countable planar graph (that is, a countable planar graph that contains every countable planar graph as a subgraph). Janos Pach (1981) answered this question in the negative. We strengthen this result by showing that every countable graph that contains all countable planar graphs must contain (i) an infinite complete graph as a minor, and (ii) a subdivision of the complete graph $K_t$ with multiplicity $t$, for every finite $t$. On the other hand, we construct a countable graph that contains all countable planar graphs and has several key properties such as linear colouring numbers, linear expansion, and every finite $n$-vertex subgraph has a balanced separator of size $O(sqrt{n})$. The graph is $mathcal{T}_6boxtimes P_{!infty}$, where $mathcal{T}_k$ is the universal treewidth-$k$ countable graph (which we define explicitly), $P_{!infty}$ is the 1-way infinite path, and $boxtimes$ denotes the strong product. More generally, for every positive integer $t$ we construct a countable graph that contains every countable $K_t$-minor-free graph and has the above key properties. Our final contribution is a construction of a countable graph that contains every countable $K_t$-minor-free graph as an induced subgraph, has linear colouring numbers and linear expansion, and contains no subdivision of the countably infinite complete graph (implying (ii) above is best possible).
Binary functions are a generalisation of the cocircuit spaces of binary matroids to arbitrary functions. Every rank function is assigned a binary function, and the deletion and contraction operations of binary functions generalise matroid deletion an
Let $mathcal G$ be an addable, minor-closed class of graphs. We prove that the zero-one law holds in monadic second-order logic (MSO) for the random graph drawn uniformly at random from all {em connected} graphs in $mathcal G$ on $n$ vertices, and th
Let $t$ be a positive real number. A graph is called $t$-tough, if the removal of any cutset $S$ leaves at most $|S|/t$ components. The toughness of a graph is the largest $t$ for which the graph is $t$-tough. A graph is minimally $t$-tough, if the t
What is the maximum number of copies of a fixed forest $T$ in an $n$-vertex graph in a graph class $mathcal{G}$ as $nto infty$? We answer this question for a variety of sparse graph classes $mathcal{G}$. In particular, we show that the answer is $The
The asymptotic dimension is an invariant of metric spaces introduced by Gromov in the context of geometric group theory. In this paper, we study the asymptotic dimension of metric spaces generated by graphs and their shortest path metric and show the