Authors:Uri Shapira; Reut Zuck Abstract: Using methods of Marklof and Strömbergsson we establish several limit laws for metric parameters of random Cayley graphs of finite abelian groups with respect to a randomly chosen set of generators of a fixed size. Doing so we settle a conjecture of Amir and Gurel- Gurevich. PubDate: 2018-02-07 DOI: 10.1007/s00493-017-3672-2

Authors:Andrey Kupavskii; János Pach; István Tomon Abstract: Two subsets A,B of an n-element ground set X are said to be crossing, if none of the four sets A∩B, A\B, B\A and X\(A∪B) are empty. It was conjectured by Karzanov and Lomonosov forty years ago that if a family F of subsets of X does not contain k pairwise crossing elements, then F =O(kn). For k=2 and 3, the conjecture is true, but for larger values of k the best known upper bound, due to Lomonosov, is F =O(knlogn). In this paper, we improve this bound for large n by showing that F =O k (nlog*n) holds, where log* denotes the iterated logarithm function. PubDate: 2018-02-07 DOI: 10.1007/s00493-017-3792-8

Authors:Bhargav Narayanan; Julian Sahasrabudhe; István Tomon Abstract: A graph on n vertices is said to be C-Ramsey if every clique or independent set of the graph has size at most C logn. The only known constructions of Ramsey graphs are probabilistic in nature, and it is generally believed that such graphs possess many of the same properties as dense random graphs. Here, we demonstrate one such property: for any fixed C > 0, every C-Ramsey graph on n vertices induces subgraphs of at least n2-o(1) distinct sizes. This near-optimal result is closely related to two unresolved conjectures, the first due to Erdős and McKay and the second due to Erdős, Faudree and Sós, both from 1992. PubDate: 2018-02-07 DOI: 10.1007/s00493-017-3755-0

Authors:Carsten Lange; Vincent Pilaud Abstract: An associahedron is a polytope whose vertices correspond to triangulations of a convex polygon and whose edges correspond to flips between them. Using labeled polygons, C. Hohlweg and C. Lange constructed various realizations of the associahedron with relevant properties related to the symmetric group and the permutahedron. We introduce the spine of a triangulation as its dual tree together with a labeling and an orientation. This notion extends the classical understanding of the associahedron via binary trees, introduces a new perspective on C. Hohlweg and C. Lange’s construction closer to J.-L. Loday’s original approach, and sheds light upon the combinatorial and geometric properties of the resulting realizations of the associahedron. It also leads to noteworthy proofs which shorten and simplify previous approaches. PubDate: 2018-02-07 DOI: 10.1007/s00493-015-3248-y

Authors:Péter Komjáth Abstract: If κ is a cardinal, n < ω, then there exists an Abelian group G such that if F : G→κ, then there exist distinct elements ai,α ∈ G (1≤i≤n, α<κ), and a color τ < κ such that if 1≤i0<⋯<i r ≤n, α1,...,α r <κ, then \(F\left( {{a_{{i_1},{\alpha _1}}} + \cdots + {a_{{i_r},{\alpha _r}}}} \right) = \tau \) . PubDate: 2018-02-03 DOI: 10.1007/s00493-016-3706-1

Authors:Victor Chepoi Pages: 1039 - 1055 Abstract: We give a characterization of distance-preserving subgraphs of Johnson graphs, i.e., of graphs which are isometrically embeddable into Johnson graphs (the Johnson graph J(m,∧) has the subsets of cardinality m of a set ∧ as the vertex-set and two such sets A,B are adjacent iff AΔB =2). Our characterization is similar to the characterization of D. Ž. Djoković [11] of distance-preserving subgraphs of hypercubes and provides an explicit description of the wallspace (split system) defining the embedding. PubDate: 2017-12-01 DOI: 10.1007/s00493-016-3421-y Issue No:Vol. 37, No. 6 (2017)

Authors:Maria Chudnovsky; Alex Scott; Paul Seymour Pages: 1057 - 1072 Abstract: We prove a 1985 conjecture of Gyárfás that for all k, ℓ, every graph with sufficiently large chromatic number contains either a clique of cardinality more than k or an induced cycle of length more than ℓ. PubDate: 2017-12-01 DOI: 10.1007/s00493-016-3467-x Issue No:Vol. 37, No. 6 (2017)

Authors:Genghua Fan Pages: 1097 - 1112 Abstract: Let G be a bridgeless graph and denote by cc(G) the shortest length of a cycle cover of G. Let V2(G) be the set of vertices of degree 2 in G. It is known that if cc(G)≤1.4 E(G) for every bridgeless graph G with V2(G) ≤ \(\frac{1}{10}\) E(G) , then the Cycle Double Cover Conjecture is true. The best known result cc(G)≤ \(\frac{5}{3}\) E(G) (≈1.6667 E(G) ) was established over 30 years ago. Recently, it was proved that cc(G) ≤ \(\frac{44}{27}\) E(G) (≈ 1.6296 E(G) ) for loopless graphs with minimum degree at least 3. In this paper, we obtain results on integer 4-flows, which are used to find bounds for cc(G). We prove that if G has minimum degree at least 3 (loops being allowed), then cc(G)<1.6258 E(G) . As a corollary, adding loops to vertices of degree 2, we obtain that cc(G)<1.6466 E(G) for every bridgeless graph G with V2(G) ≤ \(\frac{1}{30}\) E(G) . PubDate: 2017-12-01 DOI: 10.1007/s00493-016-3379-9 Issue No:Vol. 37, No. 6 (2017)

Authors:Ervin Győri; Balázs Keszegh Pages: 1113 - 1124 Abstract: We prove the quarter of a century old conjecture that every K4-free graph with n vertices and [n2/4]+m edges contains m pairwise edge-disjoint triangles. PubDate: 2017-12-01 DOI: 10.1007/s00493-016-3500-0 Issue No:Vol. 37, No. 6 (2017)

Authors:Hongbi Jiang; Daqing Yang Pages: 1125 - 1137 Abstract: The fractional arboricity of a graph G, denoted by Γf (G), is defined as $${\Gamma _f}\left( G \right) = {\max _{H \subseteq G,v\left( H \right) > 1}}\frac{{e\left( H \right)}}{{v\left( H \right) - 1}}$$ . The celebrated Nash-Williams’ Theorem states that a graph G can be partitioned into at most k forests if and only if Γf (G)≤k. The Nine Dragon Tree (NDT) Conjecture [posed by Montassier, Ossona de Mendez, Raspaud, and Zhu, in “Decomposing a graph into forests”, J. Combin. Theory Ser. B 102 (2012) 38-52] asserts that if $${\Gamma _f}\left( G \right) \leqslant k + \frac{d}{{k + d + 1}}$$ , then G decomposes into k+1 forests with one having maximum degree at most d. In this paper, we prove the Nine Dragon Tree (NDT) Conjecture. PubDate: 2017-12-01 DOI: 10.1007/s00493-016-3390-1 Issue No:Vol. 37, No. 6 (2017)

Authors:Tomasz Krawczyk; Bartosz Walczak Pages: 1139 - 1179 Abstract: The main goal of this paper is to formalize and explore a connection between chromatic properties of graphs with geometric representations and competitive analysis of on-line algorithms, which became apparent after the recent construction of triangle-free geometric intersection graphs with arbitrarily large chromatic number due to Pawlik et al. We show that on-line graph coloring problems give rise to classes of game graphs with a natural geometric interpretation. We use this concept to estimate the chromatic number of graphs with geometric representations by finding, for appropriate simpler graphs, on-line coloring algorithms using few colors or proving that no such algorithms exist. We derive upper and lower bounds on the maximum chromatic number that rectangle overlap graphs, subtree overlap graphs, and interval filament graphs (all of which generalize interval overlap graphs) can have when their clique number is bounded. The bounds are absolute for interval filament graphs and asymptotic of the form (log logn)f(ω) for rectangle and subtree overlap graphs, where f(ω) is a polynomial function of the clique number and n is the number of vertices. In particular, we provide the first construction of geometric intersection graphs with bounded clique number and with chromatic number asymptotically greater than log logn. We also introduce a concept of K k -free colorings and show that for some geometric representations, K3-free chromatic number can be bounded in terms of clique number although the ordinary (K2-free) chromatic number cannot. Such a result for segment intersection graphs would imply a well-known conjecture that k-quasi-planar geometric graphs have linearly many edges. PubDate: 2017-12-01 DOI: 10.1007/s00493-016-3414-x Issue No:Vol. 37, No. 6 (2017)

Authors:Andrey B. Kupavskii; Alexandr Polyanskii Pages: 1181 - 1205 Abstract: In this paper we prove Schur’s conjecture in ℝ d , which states that any diameter graph G in the Euclidean space ℝ d on n vertices may have at most n cliques of size d. We obtain an analogous statement for diameter graphs with unit edge length on a sphere S r d of radius \(r>1/\sqrt{2}\) . The proof rests on the following statement, conjectured by F. Morić and J. Pach: given two unit regular simplices Δ1, Δ2 on d vertices in ℝ d , either they share d-2 vertices, or there are vertices v1∈Δ1, v2∈Δ2 such that ‖v1-v2‖>1. The same holds for unit simplices on a d-dimensional sphere of radius greater than \(1/\sqrt{2}\) . PubDate: 2017-12-01 DOI: 10.1007/s00493-016-3340-y Issue No:Vol. 37, No. 6 (2017)

Authors:Torsten Mütze; Pascal Su Pages: 1207 - 1219 Abstract: For integers k ≥1 and n≥2k+1 the Kneser graph K(n;k) has as vertices all k-element subsets of [n]:={1;2;:::;n} and an edge between any two vertices (=sets) that are disjoint. The bipartite Kneser graph H(n,k) has as vertices all k-element and (n—k)-element subsets of [n] and an edge between any two vertices where one is a subset of the other. It has long been conjectured that all Kneser graphs and bipartite Kneser graphs except the Petersen graph K(5, 2) have a Hamilton cycle. The main contribution of this paper is proving this conjecture for bipartite Kneser graphs H(n,k). We also establish the existence of cycles that visit almost all vertices in Kneser graphs K(n,k) when n=2k+o(k), generalizing and improving upon previous results on this problem. PubDate: 2017-12-01 DOI: 10.1007/s00493-016-3434-6 Issue No:Vol. 37, No. 6 (2017)

Authors:Orit E. Raz; Micha Sharir Pages: 1221 - 1240 Abstract: We show that the number of unit-area triangles determined by a set S of n points in the plane is O(n20/9), improving the earlier bound O(n9/4) of Apfelbaum and Sharir [2]. We also show, using a somewhat subtle construction, that if S consists of points on three lines, the number of unit-area triangles that S spans can be Ω(n2), for any triple of lines (it is always O(n2) in this case). PubDate: 2017-12-01 DOI: 10.1007/s00493-016-3440-8 Issue No:Vol. 37, No. 6 (2017)

Authors:Venkatesan Guruswami; Euiwoong Lee Abstract: Consider a K-uniform hypergraph H = (V, E). A coloring c: V → {1, 2, …, k} with k colors is rainbow if every hyperedge e contains at least one vertex from each color, and is called perfectly balanced when each color appears the same number of times. A simple polynomial-time algorithmnds a 2-coloring if H admits a perfectly balanced rainbow k-coloring. For a hypergraph that admits an almost balanced rainbow coloring, we prove that it is NP-hard to find an independent set of size ϵ, for any ϵ > 0. Consequently, we cannot weakly color (avoiding monochromatic hyperedges) it with O(1) colors. With k=2, it implies strong hardness for discrepancy minimization of systems of bounded set-size. One of our main technical tools is based on reverse hypercontractivity. Roughly, it says the noise operator increases q-norm of a function when q < 1, which is enough for some special cases of our results. To prove the full results, we generalize the reverse hypercontractivity to more general operators, which might be of independent interest. Together with the generalized reverse hypercontractivity and recent developments in inapproximability based on invariance principles for correlated spaces, we give a recipe for converting a promising test distribution and a suitable choice of an outer PCP to hardness of nding an independent set in the presence of highly-structured colorings. We use this recipe to prove additional results almost in a black-box manner, including: (1) the rst analytic proof of (K − 1 − ϵ)-hardness of K-Hypergraph Vertex Cover with more structure in completeness, and (2) hardness of (2Q+1)-SAT when the input clause is promised to have an assignment where every clause has at least Q true literals. PubDate: 2017-12-14 DOI: 10.1007/s00493-016-3383-0

Authors:M. A. Bahmanian; Mike Newman Abstract: We consider when a given r-factorization of the complete uniform hypergraph on m vertices K m h can be extended to an s-factorization of K n h . The case of r = s = 1 was first posed by Cameron in terms of parallelisms, and solved by Häggkvist and Hellgren. We extend these results, which themselves can be seen as extensions of Baranyai's Theorem. For r=s, we show that the “obvious” necessary conditions, together with the condition that gcd(m,n,h)=gcd(n,h) are sufficient. In particular this gives necessary and sufficient conditions for the case where r=s and h is prime. For r<s we show that the obvious necessary conditions, augmented by gcd(m,n,h)=gcd(n,h), n≥2m, and \(1 \leqslant \frac{s}{r} \leqslant \frac{m}{k}\left[ {1 - \left( {\begin{array}{*{20}{c}} {m - k} \\ h \end{array}} \right)/\left( {\begin{array}{*{20}{c}} m \\ h \end{array}} \right)} \right]\) are sufficient, where k=gcd(m,n,h). We conclude with a discussion of further necessary conditions and some open problems. PubDate: 2017-12-09 DOI: 10.1007/s00493-017-3396-3

Authors:Chidambaram Annamalai Abstract: Haxell’s condition [14] is a natural hypergraph analog of Hall’s condition, which is a wellknown necessary and sufficient condition for a bipartite graph to admit a perfect matching. That is, when Haxell’s condition holds it forces the existence of a perfect matching in the bipartite hypergraph. Unlike in graphs, however, there is no known polynomial time algorithm to find the hypergraph perfect matching that is guaranteed to exist when Haxell’s condition is satisfied. We prove the existence of an efficient algorithm to find perfect matchings in bipartite hypergraphs whenever a stronger version of Haxell’s condition holds. Our algorithm can be seen as a generalization of the classical Hungarian algorithm for finding perfect matchings in bipartite graphs. The techniques we use to achieve this result could be of use more generally in other combinatorial problems on hypergraphs where disjointness structure is crucial, e.g., Set Packing. PubDate: 2017-12-09 DOI: 10.1007/s00493-017-3567-2

Authors:Péter Pál Pach; Csaba Sándor Abstract: In this paper we investigate how small the density of a multiplicative basis of order h can be in {1,2,...,n} and in ℤ+. Furthermore, a related problem of Erdős is also studied: How dense can a set of integers be, if none of them divides the product of h others' PubDate: 2017-12-09 DOI: 10.1007/s00493-016-3588-2

Authors:Marcel Celaya Abstract: Let Λ⊂R n be a lattice which contains the integer lattice Z n . We characterize the space of linear functions R n →R which vanish on the lattice points of Λ lying in the half-open unit cube [0, 1) n . We also find an explicit formula for the dimension of the linear span of Λ∩[0,1) n . The results in this paper generalize and are based on the Terminal Lemma of Reid, which is in turn based upon earlier work of Morrison and Stevens on the classification of four dimensional isolated Gorenstein terminal cyclic quotient singularities. PubDate: 2017-12-09 DOI: 10.1007/s00493-017-3562-7

Authors:Shubhangi Saraf; Ilya Volkovich Abstract: We study the problem of identity testing for multilinear ΣΠΣΠ(k) circuits, i.e., multilinear depth-4 circuits with fan-in k at the top + gate. We give the first polynomial-time deterministic identity testing algorithm for such circuits when k=O(1). Our results also hold in the black-box setting. The running time of our algorithm is \({\left( {ns} \right)^{{\text{O}}\left( {{k^3}} \right)}}\) , where n is the number of variables, s is the size of the circuit and k is the fan-in of the top gate. The importance of this model arises from [11], where it was shown that derandomizing black-box polynomial identity testing for general depth-4 circuits implies a derandomization of polynomial identity testing (PIT) for general arithmetic circuits. Prior to our work, the best PIT algorithm for multilinear ΣΠΣΠ(k) circuits [31] ran in quasi-polynomial-time, with the running time being \({n^{{\rm O}\left( {{k^6}\log \left( k \right){{\log }^2}s} \right)}}\) . We obtain our results by showing a strong structural result for multilinear ΣΠΣΠ(k) circuits that compute the zero polynomial. We show that under some mild technical conditions, any gate of such a circuit must compute a sparse polynomial. We then show how to combine the structure theorem with a result by Klivans and Spielman [33], on the identity testing for sparse polynomials, to yield the full result. PubDate: 2017-12-09 DOI: 10.1007/s00493-016-3460-4