Authors:Ron Aharoni; Tomáš Kaiser; Shira Zerbib Pages: 555 - 572 Abstract: Abstract A d-interval is a union of at most d disjoint closed intervals on a fixed line. Tardos [14] and the second author [11] used topological tools to bound the transversal number τ of a family H of d-intervals in terms of d and the matching number ν of H. We investigate the weighted and fractional versions of this problem and prove upper bounds that are tight up to constant factors. We apply both a topological method and an approach of Alon [1]. For the use of the latter, we prove a weighted version of Turán’s theorem. We also provide proofs of the upper bounds of [11] that are more direct than the original proofs. PubDate: 2017-08-01 DOI: 10.1007/s00493-016-3174-7 Issue No:Vol. 37, No. 4 (2017)

Authors:Peter Allen; Julia Böttcher; Hiệp Hàn; Yoshiharu Kohayakawa; Yury Person Pages: 573 - 616 Abstract: Abstract We study the appearance of powers of Hamilton cycles in pseudorandom graphs, using the following comparatively weak pseudorandomness notion. A graph G is (ε,p,k,ℓ)-pseudorandom if for all disjoint X and Y ⊂ V(G) with X ≥εp k n and Y ≥εp ℓ n we have e(X,Y)=(1±ε)p X Y . We prove that for all β>0 there is an ε>0 such that an (ε,p,1,2)-pseudorandom graph on n vertices with minimum degree at least βpn contains the square of a Hamilton cycle. In particular, this implies that (n,d,λ)-graphs with λ≪d 5/2 n -3/2 contain the square of a Hamilton cycle, and thus a triangle factor if n is a multiple of 3. This improves on a result of Krivelevich, Sudakov and Szabó [27]. We also extend our result to higher powers of Hamilton cycles and establish corresponding counting versions. PubDate: 2017-08-01 DOI: 10.1007/s00493-015-3228-2 Issue No:Vol. 37, No. 4 (2017)

Authors:József Balogh; Neal Bushaw; Maurício Collares; Hong Liu; Robert Morris; Maryam Sharifzadeh Pages: 617 - 632 Abstract: Abstract In 1987, Kolaitis, Prömel and Rothschild proved that, for every fixed r∈ℕ, almost every n-vertex K r+1-free graph is r-partite. In this paper we extend this result to all functions r = r(n) with r ⩽ (logn)1/4. The proof combines a new (close to sharp) supersaturation version of the Erdős-Simonovits stability theorem, the hypergraph container method, and a counting technique developed by Balogh, Bollobás and Simonovits. PubDate: 2017-08-01 DOI: 10.1007/s00493-015-3290-9 Issue No:Vol. 37, No. 4 (2017)

Authors:Alexander Barvinok; Pablo Soberón Pages: 633 - 650 Abstract: Abstract We introduce the partition function of edge-colored graph homomorphisms, of which the usual partition function of graph homomorphisms is a specialization, and present an efficient algorithm to approximate it in a certain domain. Corollaries include effcient algorithms for computing weighted sums approximating the number of k-colorings and the number of independent sets in a graph, as well as an effcient procedure to distinguish pairs of edge-colored graphs with many color-preserving homomorphisms G → H from pairs of graphs that need to be substantially modified to acquire a color-preserving homomorphism G → H. PubDate: 2017-08-01 DOI: 10.1007/s00493-016-3357-2 Issue No:Vol. 37, No. 4 (2017)

Authors:Péter L. Erdős; Dömötör Pálvölgyi; Claude Tardif; Gábor Tardos Pages: 651 - 672 Abstract: Abstract Homomorphism duality pairs play a crucial role in the theory of relational structures and in the Constraint Satisfaction Problem. The case where both classes are finite is fully characterized. The case when both sides are infinite seems to be very complex. It is also known that no finite-infinite duality pair is possible if we make the additional restriction that both classes are antichains. In this paper we characterize the infinite-finite antichain dualities and infinite-finite dualities with trees or forests on the left hand side. This work builds on our earlier papers [6] that gave several examples of infinite-finite antichain duality pairs of directed graphs and [7] giving a complete characterization for caterpillar dualities. PubDate: 2017-08-01 DOI: 10.1007/s00493-015-3003-4 Issue No:Vol. 37, No. 4 (2017)

Authors:Daniel Horsley Pages: 673 - 696 Abstract: Abstract In 1940 Fisher famously showed that if there exists a non-trivial (v,k,λ)-design, then λ(v-1)⩾k(k-1). Subsequently Bose gave an elegant alternative proof of Fisher’s result. Here, we show that the idea behind Bose’s proof can be generalised to obtain new bounds on the number of blocks in (v,k,λ)-coverings and -packings with λ(v-1)<k(k-1). PubDate: 2017-08-01 DOI: 10.1007/s00493-016-3326-9 Issue No:Vol. 37, No. 4 (2017)

Authors:Michael Krivelevich; Choongbum Lee; Benny Sudakov Pages: 697 - 732 Abstract: Abstract A graph is Hamiltonian if it contains a cycle passing through every vertex exactly once. A celebrated theorem of Dirac from 1952 asserts that every graph on n≥3 vertices with minimum degree at least n/2 is Hamiltonian. We refer to such graphs as Dirac graphs. In this paper we obtain the following strengthening of this result. Given a graph G=(V,E), an incompatibility system F over G is a family F = {F v } v∈V such that for every v∈V, the set F v is a family of unordered pairs F v ⊆ {{e,e′}}: e ≠ e′ ∈ E,e ∩ e′ = {v}}. An incompatibility system is Δ-bounded if for every vertex v and an edge e incident to v, there are at most Δ pairs in F v containing e. We say that a cycle C in G is compatible with F if every pair of incident edges e,e′ of C satisfies {e,e′}∉F v , where v=e ∩ e′. This notion is partly motivated by a concept of transition systems defined by Kotzig in 1968, and can be viewed as a quantitative measure of robustness of graph properties. We prove that there is a constant μ>0 such that for every μn-bounded incompatibility system F over a Dirac graph G, there exists a Hamilton cycle compatible with F. This settles in a very strong form a conjecture of Häggkvist from 1988. PubDate: 2017-08-01 DOI: 10.1007/s00493-016-3328-7 Issue No:Vol. 37, No. 4 (2017)

Authors:Anton Malyshev; Igor Pak Pages: 733 - 765 Abstract: Abstract It is known that random 2-lifts of graphs give rise to expander graphs. We present a new conjectured derandomization of this construction based on certain Mealy automata. We verify that these graphs have polylogarithmic diameter, and present a class of automata for which the same is true. However, we also show that some automata in this class do not give rise to expander graphs. PubDate: 2017-08-01 DOI: 10.1007/s00493-016-3306-0 Issue No:Vol. 37, No. 4 (2017)

Authors:Vojtěch Rödl; Andrzej Ruciński; Mathias Schacht Pages: 767 - 784 Abstract: Abstract For given integers k and r, the Folkman number f(k;r) is the smallest number of vertices in a graph G which contains no clique on k+1 vertices, yet for every partition of its edges into r parts, some part contains a clique of order k. The existence (finiteness) of Folkman numbers was established by Folkman (1970) for r=2 and by Nešetřil and Rödl (1976) for arbitrary r, but these proofs led to very weak upper bounds on f(k;r). Recently, Conlon and Gowers and independently the authors obtained a doubly exponential bound on f(k;2). Here, we establish a further improvement by showing an upper bound on f(k;r) which is exponential in a polynomial of k and r. This is comparable to the known lower bound 2 Ω(rk). Our proof relies on a recent result of Saxton and Thomason (or, alternatively, on a recent result of Balogh, Morris, and Samotij) from which we deduce a quantitative version of Ramsey’s theorem in random graphs. PubDate: 2017-08-01 DOI: 10.1007/s00493-015-3298-1 Issue No:Vol. 37, No. 4 (2017)

Authors:Carsten Thomassen Pages: 785 - 793 Abstract: Abstract Erdős and Hajnal conjectured in 1966 that every graph of uncountable chromatic number contains a subgraph of infinite connectivity. We prove that every graph of uncountable chromatic number has a subgraph which has uncountable chromatic number and infinite edge-connectivity. We also prove that, if each orientation of a graph G has a vertex of infinite outdegree, then G contains an uncountable subgraph of infinite edge-connectivity. PubDate: 2017-08-01 DOI: 10.1007/s00493-016-3436-4 Issue No:Vol. 37, No. 4 (2017)

Authors:David Gajser; Bojan Mohar Abstract: Abstract A graph is normal if it admits a clique cover C and a stable set cover S such that each clique in C and each stable set in S have a vertex in common. The pair (C,S) is a normal cover of the graph. We present the following extremal property of normal covers. For positive integers c, s, if a graph with n vertices admits a normal cover with cliques of sizes at most c and stable sets of sizes at most s, then c+s≥log2(n). For infinitely many n, we also give a construction of a graph with n vertices that admits a normal cover with cliques and stable sets of sizes less than 0.87log2(n). Furthermore, we show that for all n, there exists a normal graph with n vertices, clique number Θ(log2(n)) and independence number Θ(log2(n)). When c or s are very small, we can describe all normal graphs with the largest possible number of vertices that allow a normal cover with cliques of sizes at most c and stable sets of sizes at most s. However, such extremal graphs remain elusive even for moderately small values of c and s. PubDate: 2017-08-14 DOI: 10.1007/s00493-017-3559-2

Authors:Daniel W. Cranston; Landon Rabern Abstract: Abstract A graph G is k-critical if G is not (k − 1)-colorable, but every proper subgraph of G is (k − 1)-colorable. A graph G is k-choosable if G has an L-coloring from every list assignment L with L(v) =k for all v, and a graph G is k-list-critical if G is not (k−1)-choosable, but every proper subgraph of G is (k−1)-choosable. The problem of determining the minimum number of edges in a k-critical graph with n vertices has been widely studied, starting with work of Gallai and culminating with the seminal results of Kostochka and Yancey, who essentially solved the problem. In this paper, we improve the best known lower bound on the number of edges in a k-list-critical graph. In fact, our result on k-list-critical graphs is derived from a lower bound on the number of edges in a graph with Alon–Tarsi number at least k. Our proof uses the discharging method, which makes it simpler and more modular than previous work in this area. PubDate: 2017-08-14 DOI: 10.1007/s00493-016-3584-6

Authors:Rintaro Ikeshita; Shin-ichi Tanigawa Abstract: Abstract A graph G = (V, E) is called (k, ℓ)-sparse if F ≤ k V (F) − ℓ for any nonempty F ⊆ E, where V (F) denotes the set of vertices incident to F. It is known that the family of the edge sets of (k, ℓ)-sparse subgraphs forms the family of independent sets of a matroid, called the (k, ℓ)-count matroid of G. In this paper we shall investigate lifts of the (k, ℓ)- count matroids by using group labelings on the edge set. By introducing a new notion called near-balancedness, we shall identify a new class of matroids whose independence condition is described as a count condition of the form F ≤ k V (F) −ℓ+α ψ (F) for some function α ψ determined by a given group labeling ψ on E. PubDate: 2017-08-14 DOI: 10.1007/s00493-016-3469-8

Authors:Ben Lund Abstract: Abstract Let P be a finite set of points in ℝ d or ℂ d .We answer a question of Purdy on the conditions under which the number of hyperplanes spanned by P is at least the number of (d−2)-flats spanned by P. In answering this question, we define a new measure of the degeneracy of a point set with respect to affine subspaces, termed the essential dimension. We use the essential dimension to give an asymptotic expression for the number of k-flats spanned by P, for 1≤k≤d−1. PubDate: 2017-08-14 DOI: 10.1007/s00493-016-3602-8

Authors:Satoru Iwata; Yu Yokoi Abstract: Abstract In 1995, Galvin provided an elegant proof for the list edge coloring conjecture for bipartite graphs, utilizing the stable matching theorem of Gale and Shapley. In this paper, we generalize Galvin’s result to the setting of supermodular coloring, introduced by Schrijver, with the aid of the monochromatic path theorem of Sands, Sauer andWoodrow. Our result derives a list coloring version of Gupta’s theorem, which can also be proven directly from Galvin’s theorem. PubDate: 2017-08-14 DOI: 10.1007/s00493-017-3670-4

Authors:Eli Berger; Zdenĕk Dvořák; Sergey Norin Abstract: Abstract Let Q n be the 3-dimensional n×n×n grid with all non-decreasing diagonals (including the facial ones) in its constituent unit cubes. Suppose that a set S ⊆ V (Q n ) separates the left side of the grid from the right side. We show that S induces a subgraph of tree-width at least \(\frac{n}{{\sqrt {18} }} = - 1\) . We use a generalization of this claim to prove that the vertex set of Q n cannot be partitioned to two parts, each of them inducing a subgraph of bounded tree-width. PubDate: 2017-08-14 DOI: 10.1007/s00493-017-3548-5

Authors:Maria Axenovich; Jonathan Rollin; Torsten Ueckerdt Abstract: Abstract It is well-known that the graphs not containing a given graph H as a subgraph have bounded chromatic number if and only if H is acyclic. Here we consider ordered graphs, i.e., graphs with a linear ordering ≺ on their vertex set, and the function $${f_ \prec }\left( H \right) = \sup \left\{ {\chi \left( G \right) G \in For{b_ \prec }\left( H \right)} \right\},$$ where Forb≺(H) denotes the set of all ordered graphs that do not contain a copy of H. If H contains a cycle, then as in the case of unordered graphs, f ≺(H)=∞. However, in contrast to the unordered graphs, we describe an infinite family of ordered forests H with f ≺(H) =∞. An ordered graph is crossing if there are two edges uv and u′v′ with u ≺ u′ ≺ v ≺ v′. For connected crossing ordered graphs H we reduce the problem of determining whether f ≺(H) ≠∞ to a family of so-called monotonically alternating trees. For non-crossing H we prove that f ≺(H) ≠∞ if and only if H is acyclic and does not contain a copy of any of the five special ordered forests on four or five vertices, which we call bonnets. For such forests H, we show that f ≺(H)⩽2 V(H) and that f ≺(H)⩽2 V (H) −3 if H is connected. PubDate: 2017-08-14 DOI: 10.1007/s00493-017-3593-0

Authors:Victor A. Vassiliev Abstract: Abstract We describe the homotopy types of complexes of partite graphs and hypergraphs with a fixed set of vertices covered by their edges. PubDate: 2017-08-14 DOI: 10.1007/s00493-017-3508-0

Authors:Gwenaël Joret; Piotr Micek; Veit Wiechert Abstract: Abstract We prove that posets of bounded height whose cover graphs belong to a fixed class with bounded expansion have bounded dimension. Bounded expansion, introduced by Nešetřil and Ossona de Mendez as a model for sparsity in graphs, is a property that is naturally satisfied by a wide range of graph classes, from graph structure theory (graphs excluding a minor or a topological minor) to graph drawing (e.g. graphs with bounded book thickness). Therefore, our theorem generalizes a number of results including the most recent one for posets of bounded height with cover graphs excluding a fixed graph as a topological minor. We also show that the result is in a sense best possible, as it does not extend to nowhere dense classes; in fact, it already fails for cover graphs with locally bounded treewidth. PubDate: 2017-08-14 DOI: 10.1007/s00493-017-3638-4

Authors:Elchanan Mossel; Joe Neeman; Allan Sly Abstract: Abstract We study a random graph model called the “stochastic block model” in statistics and the “planted partition model” in theoretical computer science. In its simplest form, this is a random graph with two equal-sized classes of vertices, with a within-class edge probability of q and a between-class edge probability of q′. A striking conjecture of Decelle, Krzkala, Moore and Zdeborová [9], based on deep, non-rigorous ideas from statistical physics, gave a precise prediction for the algorithmic threshold of clustering in the sparse planted partition model. In particular, if q=a/n and q′=b/n, s=(a−b)/2 and d=(a+b)/2, then Decelle et al. conjectured that it is possible to efficiently cluster in a way correlated with the true partition if s 2>d and impossible if s 2<d. By comparison, until recently the best-known rigorous result showed that clustering is possible if s 2>Cdlnd for sufficiently large C. In a previous work, we proved that indeed it is information theoretically impossible to cluster if s 2 ≤ d and moreover that it is information theoretically impossible to even estimate the model parameters from the graph when s 2 < d. Here we prove the rest of the conjecture by providing an efficient algorithm for clustering in a way that is correlated with the true partition when s 2>d. A different independent proof of the same result was recently obtained by Massoulié [20]. PubDate: 2017-08-14 DOI: 10.1007/s00493-016-3238-8