Authors:Anneleen De Schepper; N. S. Narasimha Sastry; Hendrik Van Maldeghem Abstract: The original version of this article unfortunately contained a mistake in the author’s name N. S. Narasimha Sastry. The corrected name is given above. PubDate: 2018-02-09 DOI: 10.1007/s12188-018-0192-y

Authors:Ljuben Mutafchiev Abstract: Assuming that a plane partition of the positive integer n is chosen uniformly at random from the set of all such partitions, we propose a general asymptotic scheme for the computation of expectations of various plane partition statistics as n becomes large. The generating functions that arise in this study are of the form Q(x)F(x), where \(Q(x)=\prod _{j=1}^\infty (1-x^j)^{-j}\) is the generating function for the number of plane partitions. We show how asymptotics of such expectations can be obtained directly from the asymptotic expansion of the function F(x) around \(x=1\) . The representation of a plane partition as a solid diagram of volume n allows interpretations of these statistics in terms of its dimensions and shape. As an application of our main result, we obtain the asymptotic behavior of the expected values of the largest part, the number of columns, the number of rows (that is, the three dimensions of the solid diagram) and the trace (the number of cubes in the wall on the main diagonal of the solid diagram). Our results are similar to those of Grabner et al. (Comb Probab Comput 23:1057–1086, 2014) related to linear integer partition statistics. We base our study on the Hayman’s method for admissible power series. PubDate: 2018-02-06 DOI: 10.1007/s12188-018-0191-z

Authors:Anneleen De Schepper; N. S. Narasimha Sastry; Hendrik Van Maldeghem Abstract: A symplectic polarity of a building \(\varDelta \) of type \(\mathsf {E_6}\) is a polarity whose fixed point structure is a building of type \(\mathsf {F_4}\) containing residues isomorphic to symplectic polar spaces (i.e., so-called split buildings of type \(\mathsf {F_4}\) ). In this paper, we show in a geometric way that every building of type \(\mathsf {E_6}\) contains, up to conjugacy, a unique class of symplectic polarities. We also show that the natural point-line geometry of each split building of type \(\mathsf {F_4}\) fully embedded in the natural point-line geometry of \(\varDelta \) arises from a symplectic polarity. PubDate: 2018-01-16 DOI: 10.1007/s12188-017-0190-5

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: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:Victor Alexandrov Abstract: We choose some special unit vectors \({\mathbf {n}}_1,\ldots ,{\mathbf {n}}_5\) in \({\mathbb {R}}^3\) and denote by \({\mathscr {L}}\subset {\mathbb {R}}^5\) the set of all points \((L_1,\ldots ,L_5)\in {\mathbb {R}}^5\) with the following property: there exists a compact convex polytope \(P\subset {\mathbb {R}}^3\) such that the vectors \({\mathbf {n}}_1,\ldots ,{\mathbf {n}}_5\) (and no other vector) are unit outward normals to the faces of P and the perimeter of the face with the outward normal \({\mathbf {n}}_k\) is equal to \(L_k\) for all \(k=1,\ldots ,5\) . Our main result reads that \({\mathscr {L}}\) is not a locally-analytic set, i.e., we prove that, for some point \((L_1,\ldots ,L_5)\in {\mathscr {L}}\) , it is not possible to find a neighborhood \(U\subset {\mathbb {R}}^5\) and an analytic set \(A\subset {\mathbb {R}}^5\) such that \({\mathscr {L}}\cap U=A\cap U\) . We interpret this result as an obstacle for finding an existence theorem for a compact convex polytope with prescribed directions and perimeters of the faces. PubDate: 2017-12-11 DOI: 10.1007/s12188-017-0189-y

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