Authors:Ron Aharoni; Eli Berger; Dani Kotlar; Ran Ziv Pages: 203 - 211 Abstract: Stein (Pac J Math 59:567–575, 1975) proposed the following conjecture: if the edge set of \(K_{n,n}\) is partitioned into n sets, each of size n, then there is a partial rainbow matching of size \(n-1\) . He proved that there is a partial rainbow matching of size \(n(1-\frac{D_n}{n!})\) , where \(D_n\) is the number of derangements of [n]. This means that there is a partial rainbow matching of size about \((1- \frac{1}{e})n\) . Using a topological version of Hall’s theorem we improve this bound to \(\frac{2}{3}n\) . PubDate: 2017-10-01 DOI: 10.1007/s12188-016-0160-3 Issue No:Vol. 87, No. 2 (2017)

Authors:Béla Bollobás; Alex Scott Pages: 213 - 222 Abstract: A set A of vertices in an r-uniform hypergraph \(\mathcal H\) is covered in \(\mathcal H\) if there is some vertex \(u\not \in A\) such that every edge of the form \(\{u\}\cup B\) , \(B\in A^{(r-1)}\) is in \(\mathcal H\) . Erdős and Moser (J Aust Math Soc 11:42–47, 1970) determined the minimum number of edges in a graph on n vertices such that every k-set is covered. We extend this result to r-uniform hypergraphs on sufficiently many vertices, and determine the extremal hypergraphs. We also address the problem for directed graphs. PubDate: 2017-10-01 DOI: 10.1007/s12188-016-0162-1 Issue No:Vol. 87, No. 2 (2017)

Authors:Reinhard Diestel Pages: 223 - 244 Abstract: We show that an arbitrary infinite graph can be compactified by its \({\aleph _0}\) -tangles in much the same way as the ends of a locally finite graph compactify it in its Freudenthal compactification. In general, the ends then appear as a subset of its \({\aleph _0}\) -tangles. The \({\aleph _0}\) -tangles of a graph are shown to form an inverse limit of the ultrafilters on the sets of components obtained by deleting a finite set of vertices. The \({\aleph _0}\) -tangles that are ends are precisely the limits of principal ultrafilters.The \({\aleph _0}\) -tangles that correspond to a highly connected part, or \({\aleph _0}\) -block, of the graph are shown to be precisely those that are closed in the topological space of its finite-order separations. PubDate: 2017-10-01 DOI: 10.1007/s12188-016-0163-0 Issue No:Vol. 87, No. 2 (2017)

Authors:Matthias Hamann Pages: 245 - 263 Abstract: We look at group actions on graphs and other metric spaces, e. g., at group actions on geodesic hyperbolic spaces. We classify the types of automorphisms on these spaces and prove several results about the density of the hyperbolic limit set of the group in the whole limit set of the group. PubDate: 2017-10-01 DOI: 10.1007/s12188-016-0164-z Issue No:Vol. 87, No. 2 (2017)

Authors:Karl Heuer Pages: 265 - 274 Abstract: In this paper we characterise the graphs containing a \(\mathbb {Z} \times \mathbb {Z}\) grid minor in a similar way as it has been done by Halin for graphs with an \(\mathbb {N} \times \mathbb {Z}\) grid minor. Using our characterisation, we describe the structure of graphs without \(\mathbb {Z} \times \mathbb {Z}\) grid minors in terms of tree-decompositions. PubDate: 2017-10-01 DOI: 10.1007/s12188-016-0165-y Issue No:Vol. 87, No. 2 (2017)

Authors:Neil Hindman; Imre Leader; Dona Strauss Pages: 275 - 287 Abstract: Suppose that we have a finite colouring of \(\mathbb R\) . What sumset-type structures can we hope to find in some colour class' One of our aims is to show that there is such a colouring for which no uncountable set has all of its pairwise sums monochromatic. We also show that there is such a colouring such that there is no infinite set X with \(X+X\) (the pairwise sums from X, allowing repetition) monochromatic. These results assume CH. In the other direction, we show that if each colour class is measurable, or each colour class is Baire, then there is an infinite set X (and even an uncountable X, of size the reals) with \(X+X\) monochromatic. We also give versions for all of these results for k-wise sums in place of pairwise sums. PubDate: 2017-10-01 DOI: 10.1007/s12188-016-0166-x Issue No:Vol. 87, No. 2 (2017)

Authors:Wilfried Imrich; Simon M. Smith Pages: 289 - 297 Abstract: This note presents a new, elementary proof of a generalization of a theorem of Halin to graphs with unbounded degrees, which is then applied to show that every connected, countably infinite graph G, with \(\aleph _0 \le {\text {Aut}}(G) < 2^{\aleph _0}\) and subdegree-finite automorphism group, has a finite set F of vertices that is setwise stabilized only by the identity automorphism. A bound on the size of such sets, which are called distinguishing, is also provided. To put this theorem of Halin and its generalization into perspective, we also discuss several related non-elementary, independent results and their methods of proof. PubDate: 2017-10-01 DOI: 10.1007/s12188-016-0167-9 Issue No:Vol. 87, No. 2 (2017)

Authors:H. A. Kierstead; A. V. Kostochka; T. Molla; E. C. Yeager Pages: 299 - 335 Abstract: Corrádi and Hajnal (Acta Math Acad Sci Hung 14:423–439, 1963) proved that for all \(k\ge 1\) and \(n\ge 3k\) , every (simple) graph G on n vertices with minimum degree \(\delta (G)\ge 2k\) contains k disjoint cycles. The degree bound is sharp. Enomoto and Wang proved the following Ore-type refinement of the Corrádi–Hajnal theorem: For all \(k\ge 1\) and \(n\ge 3k\) , every graph G on n vertices contains k disjoint cycles, provided that \(d(x)+d(y)\ge 4k-1\) for all distinct nonadjacent vertices x, y. Very recently, it was refined for \(k\ge 3\) and \(n\ge 3k+1\) : If G is a graph on n vertices such that \(d(x)+d(y)\ge 4k-3\) for all distinct nonadjacent vertices x, y, then G has k vertex-disjoint cycles if and only if the independence number \(\alpha (G)\le n-2k\) and G is not one of two small exceptions in the case \(k=3\) . But the most difficult case, \(n=3k\) , was not handled. In this case, there are more exceptional graphs, the statement is more sophisticated, and some of the proofs do not work. In this paper we resolve this difficult case and obtain the full picture of extremal graphs for the Ore-type version of the Corrádi–Hajnal theorem. Since any k disjoint cycles in a 3k-vertex graph G must be 3-cycles, the existence of such k cycles is equivalent to the existence of an equitable k-coloring of the complement of G. Our proof uses the language of equitable colorings, and our result can be also considered as an Ore-type version of a partial case of the Chen–Lih–Wu Conjecture on equitable colorings. PubDate: 2017-10-01 DOI: 10.1007/s12188-016-0168-8 Issue No:Vol. 87, No. 2 (2017)

Authors:Péter Komjáth Pages: 337 - 341 Abstract: We consider the infinite form of Hadwiger’s conjecture. We give a(n apparently novel) proof of Halin’s 1967 theorem stating that every graph X with coloring number \(>\kappa \) (specifically with chromatic number \(>\kappa \) ) contains a subdivision of \(K_\kappa \) . We also prove that there is a graph of cardinality \(2^\kappa \) and chromatic number \(\kappa ^+\) which does not contain \(K_{\kappa ^+}\) as a minor. Further, it is consistent that every graph of size and chromatic number \(\aleph _1\) contains a subdivision of \(K_{\aleph _1}\) . PubDate: 2017-10-01 DOI: 10.1007/s12188-016-0170-1 Issue No:Vol. 87, No. 2 (2017)

Authors:Matthias Kriesell Pages: 343 - 355 Abstract: For each positive integer k, we give a finite list C(k) of Bondy–Chvátal type conditions on a nondecreasing sequence \(d=(d_1,\dots ,d_n)\) of nonnegative integers such that every graph on n vertices with degree sequence at least d is k-edge-connected. These conditions are best possible in the sense that whenever one of them fails for d then there is a graph on n vertices with degree sequence at least d which is not k-edge-connected. We prove that C(k) is and must be large by showing that it contains p(k) many logically irredundant conditions, where p(k) is the number of partitions of k. Since, in the corresponding classic result on vertex connectivity, one needs just one such condition, this is one of the rare statements where the edge connectivity version is much more difficult than the vertex connectivity version. Furthermore, we demonstrate how to handle other types of edge-connectivity, such as, for example, essential k-edge-connectivity. We prove that any sublist equivalent to C(k) has length at least p(k), where p(k) is the number of partitions of k, which is in contrast to the corresponding classic result on vertex connectivity where one needs just one such condition. Furthermore, we demonstrate how to handle other types of edge-connectivity, such as, for example, essential k-edge-connectivity. Finally, we informally describe a simple and fast procedure which generates the list C(k). Specialized to \(k=3\) , this verifies a conjecture of Bauer, Hakimi, Kahl, and Schmeichel, and for \(k=2\) we obtain an alternative proof for their result on bridgeless connected graphs. The explicit list for \(k=4\) is given, too. PubDate: 2017-10-01 DOI: 10.1007/s12188-016-0171-0 Issue No:Vol. 87, No. 2 (2017)

Authors:André Kündgen; Carsten Thomassen Pages: 357 - 368 Abstract: In this paper we study alternating cycles in graphs embedded in a surface. We observe that 4-vertex-colorability of a triangulation on a surface can be expressed in terms of spanninq quadrangulations, and we establish connections between spanning quadrangulations and cycles in the dual graph which are noncontractible and alternating with respect to a perfect matching. We show that the dual graph of an Eulerian triangulation of an orientable surface other than the sphere has a perfect matching M and an M-alternating noncontractible cycle. As a consequence, every Eulerian triangulation of the torus has a nonbipartite spanning quadrangulation. For an Eulerian triangulation G of the projective plane the situation is different: If the dual graph \(G^*\) is nonbipartite, then \(G^*\) has no noncontractible alternating cycle, and all spanning quadrangulations of G are bipartite. If the dual graph \(G^*\) is bipartite, then it has a noncontractible, M-alternating cycle for some (and hence any) perfect matching, G has a bipartite spanning quadrangulation and also a nonbipartite spanning quadrangulation. PubDate: 2017-10-01 DOI: 10.1007/s12188-016-0172-z Issue No:Vol. 87, No. 2 (2017)

Authors:Claude Laflamme; Maurice Pouzet; Norbert Sauer Pages: 369 - 408 Abstract: A tree is scattered if it does not contain a subdivision of the complete binary tree as a subtree. We show that every scattered tree contains a vertex, an edge, or a set of at most two ends preserved by every embedding of T. This extends results of Halin, Polat and Sabidussi. Calling two trees equimorphic if each embeds in the other, we then prove that either every tree that is equimorphic to a scattered tree T is isomorphic to T, or there are infinitely many pairwise non-isomorphic trees which are equimorphic to T. This proves the tree alternative conjecture of Bonato and Tardif for scattered trees, and a conjecture of Tyomkyn for locally finite scattered trees. PubDate: 2017-10-01 DOI: 10.1007/s12188-016-0169-7 Issue No:Vol. 87, No. 2 (2017)

Authors:W. Mader Pages: 409 - 419 Abstract: It is proved that every non-complete, finite digraph of connectivity number k has a fragment F containing at most k critical vertices. The following result is a direct consequence: every k-connected, finite digraph D of minimum out- and indegree at least \(2k+ m- 1\) for positive integers k, m has a subdigraph H of minimum outdegree or minimum indegree at least \(m-1\) such that \(D - x\) is k-connected for all \(x \in V(H)\) . For \(m = 1\) , this implies immediately the existence of a vertex of indegree or outdegree less than 2k in a k-critical, finite digraph, which was proved in Mader (J Comb Theory (B) 53:260–272, 1991). PubDate: 2017-10-01 DOI: 10.1007/s12188-016-0173-y Issue No:Vol. 87, No. 2 (2017)

Authors:Jaroslav Nešetřil; Vojtěch Rödl Pages: 421 - 433 Abstract: In this paper, we study a Ramsey type problems dealing with the number of ordered subgraphs present in an arbitrary ordering of a larger graph. Our first result implies that for every vertex ordered graph G on k vertices and any stochastic vector \(\overrightarrow{a}\) with k! entries, there exists a graph H with the following property: for any linear order of the vertices of H, the number of induced ordered copies of G in H is asymptotically equal to a convex combination of the entries in \(\overrightarrow{a}\) . This for a particular choice of \(\overrightarrow{a}\) yeilds an earlier result of Angel, Lyons, and Kechris. We also consider a similar question when the ordering of vertices is replaced by the ordering of pairs of vertices. This problem is more complex problem and we prove some partial results in this case. PubDate: 2017-10-01 DOI: 10.1007/s12188-016-0174-x Issue No:Vol. 87, No. 2 (2017)

Authors:Guus Regts; Alexander Schrijver; Bart Sevenster Pages: 435 - 443 Abstract: We characterize the virtual link invariants that can be described as partition function of a real-valued R-matrix, by being weakly reflection positive. Weak reflection positivity is defined in terms of joining virtual link diagrams, which is a specialization of joining virtual link diagram tangles. Basic techniques are the first fundamental theorem of invariant theory, the Hanlon–Wales theorem on the decomposition of Brauer algebras, and the Procesi–Schwarz theorem on inequalities for closed orbits. PubDate: 2017-10-01 DOI: 10.1007/s12188-016-0175-9 Issue No:Vol. 87, No. 2 (2017)

Authors:William T. Trotter Pages: 445 - 454 Abstract: This paper continues a recent resurgence of interest in combinatorial properties of a poset that are associated with graph properties of its cover graph and order diagram. The following two theorems appearing in a 1977 paper of Trotter and Moore have played important roles in motivating this more modern research: (1) The dimension of a poset is at most 3 when its cover graph is at tree; (2) The dimension of a poset is at most 3 when the poset has a zero and its order diagram is planar. Although the underlying ideas lay dormant for more than 30 years, the first of these two results has become the base case for recent results bounding the dimension of a poset in terms of (a) the tree-width of its cover graph, and (b) the maximum dimension of its blocks. The second result is the base case for bounding the dimension of a planar poset in terms of the number of minimal elements. Continuing with this line of research, we show that every poset whose cover graph is a tree is a circle order, i.e., it has a representation as a family of circular disks in the Euclidean plane partially ordered by inclusion. PubDate: 2017-10-01 DOI: 10.1007/s12188-016-0176-8 Issue No:Vol. 87, No. 2 (2017)

Authors:Hansjörg Geiges; Christian Lange Abstract: We classify the Seifert fibrations of any given lens space L(p, q). Starting from any pair of coprime non-zero integers \(\alpha _1^0,\alpha _2^0\) , we give an algorithmic construction of a Seifert fibration \(L(p,q)\rightarrow S^2(\alpha \alpha _1^0 ,\alpha \alpha _2^0 )\) , where the natural number \(\alpha \) is determined by the algorithm. This algorithm produces all possible Seifert fibrations, and the isomorphisms between the resulting Seifert fibrations are described completely. Also, we show that all Seifert fibrations are isomorphic to certain standard models. PubDate: 2017-10-23 DOI: 10.1007/s12188-017-0188-z

Authors:Michael Müger Abstract: Motivated by analytic number theory, we explore remainder versions of Ikehara’s Tauberian theorem yielding power law remainder terms. More precisely, for \(f:[1,\infty )\rightarrow {\mathbb R}\) non-negative and non-decreasing we prove \(f(x)-x=O(x^\gamma )\) with \(\gamma <1\) under certain assumptions on f. We state a conjecture concerning the weakest natural assumptions and show that we cannot hope for more. PubDate: 2017-09-12 DOI: 10.1007/s12188-017-0187-0

Authors:Humio Ichimura Abstract: Let p be an odd prime number and \(\ell \) an odd prime number dividing \(p-1\) . We denote by \(F=F_{p,\ell }\) the real abelian field of conductor p and degree \(\ell \) , and by \(h_F\) the class number of F. For a prime number \(r \ne p,\,\ell \) , let \(F_{\infty }\) be the cyclotomic \(\mathbb {Z}_r\) -extension over F, and \(M_{\infty }/F_{\infty }\) the maximal pro-r abelian extension unramified outside r. We prove that \(M_{\infty }\) coincides with \(F_{\infty }\) and consequently \(h_F\) is not divisible by r when r is a primitive root modulo \(\ell \) and r is smaller than an explicit constant depending on p. PubDate: 2017-09-11 DOI: 10.1007/s12188-017-0186-1