Authors:Aart Blokhuis; Andries E. Brouwer Pages: 795 - 804 Abstract: Abstract We determine the independence number of the Kneser graph on line-plane flags in the projective space PG(4;q). We also classify the corresponding maximum-size cocliques. PubDate: 2017-10-01 DOI: 10.1007/s00493-016-3438-2 Issue No:Vol. 37, No. 5 (2017)

Authors:Eda Cesaratto; Guillermo Matera; Mariana Pérez Pages: 805 - 836 Abstract: Abstract We estimate the number A λ of elements on a linear family A of monic polynomials of F q [T] of degree n having factorization pattern \(\lambda : = {1^{{\lambda _1}}}{2^{{\lambda _2}}} \cdot \cdot \cdot {n^{{\lambda _n}}}\) . We show that A λ = T(λ)q n-m + O(q n-m-1/2), where T(λ) is the proportion of elements of the symmetric group of n elements with cycle pattern λ and m is the codimension of A. Furthermore, if the family A under consideration is “sparse”, then A λ =T(λ)q n-m +O(q n-m-1). Our estimates hold for fields F q of characteristic greater than 2. We provide explicit upper bounds for the constants underlying the O-notation in terms of λ and A with “good” behavior. Our approach reduces the question to estimate the number of F q -rational points of certain families of complete intersections defined over F q . Such complete intersections are defined by polynomials which are invariant under the action of the symmetric group of permutations of the coordinates. This allows us to obtain critical information concerning their singular locus, from which precise estimates on their number of F q -rational points are established. PubDate: 2017-10-01 DOI: 10.1007/s00493-015-3330-5 Issue No:Vol. 37, No. 5 (2017)

Authors:Daniel W. Cranston; Landon Rabern Pages: 837 - 861 Abstract: Abstract The chromatic number of the plane is the chromatic number of the uncountably infinite graph that has as its vertices the points of the plane and has an edge between two points if their distance is 1. This chromatic number is denoted χ(ℝ2). The problem was introduced in 1950, and shortly thereafter it was proved that 4≤χ(ℝ2)χ≤7. These bounds are both easy to prove, but after more than 60 years they are still the best known. In this paper, we investigate χ f (ℝ2), the fractional chromatic number of the plane. The previous best bounds (rounded to five decimal places) were 3.5556≤χ f (ℝ2)≤4.3599. Here we improve the lower bound to 76/21≈3.6190. PubDate: 2017-10-01 DOI: 10.1007/s00493-016-3380-3 Issue No:Vol. 37, No. 5 (2017)

Authors:Zdeněk Dvořák; Luke Postle Pages: 863 - 886 Abstract: Abstract A graph G is 5/2-critical if G has no circular 5/2-coloring (or equivalently, homomorphism to C 5), but every proper subgraph of G has one. We prove that every 5/2-critical graph on n ≥ 4 vertices has at least $$\frac{{5n - 2}}{4}$$ edges, and list all 5/2-critical graphs achieving this bound. This implies that every planar or projective-planar graph of girth at least 10 is 5/2-colorable. PubDate: 2017-10-01 DOI: 10.1007/s00493-016-3356-3 Issue No:Vol. 37, No. 5 (2017)

Authors:Herbert Edelsbrunner; Alexey Glazyrin; Oleg R. Musin; Anton Nikitenko Pages: 887 - 910 Abstract: Abstract We introduce the Voronoi functional of a triangulation of a finite set of points in the Euclidean plane and prove that among all geometric triangulations of the point set, the Delaunay triangulation maximizes the functional. This result neither extends to topological triangulations in the plane nor to geometric triangulations in three and higher dimensions. PubDate: 2017-10-01 DOI: 10.1007/s00493-016-3308-y Issue No:Vol. 37, No. 5 (2017)

Authors:Jacob Fox; László Miklós Lovász Pages: 911 - 951 Abstract: Abstract We determine the order of the tower height for the partition size in a version of Szemerédi’s regularity lemma. This addresses a question of Gowers. PubDate: 2017-10-01 DOI: 10.1007/s00493-016-3274-4 Issue No:Vol. 37, No. 5 (2017)

Authors:Konstantin Golubev Pages: 953 - 964 Abstract: Abstract In [3] A. J. Hoffman proved a lower bound on the chromatic number of a graph in the terms of the largest and the smallest eigenvalues of its adjacency matrix. In this paper, we prove a higher dimensional version of this result and give a lower bound on the chromatic number of a pure d-dimensional simplicial complex in the terms of the spectra of the higher Laplacian operators. PubDate: 2017-10-01 DOI: 10.1007/s00493-016-3137-z Issue No:Vol. 37, No. 5 (2017)

Authors:Mark Jerrum; Kitty Meeks Pages: 965 - 990 Abstract: Abstract We consider the problem of counting, in a given graph, the number of induced k-vertex subgraphs which have an even number of edges, and also the complementary problem of counting the k-vertex induced subgraphs having an odd number of edges. We demonstrate that both problems are #W[1]-hard when parameterised by k, in fact proving a somewhat stronger result about counting subgraphs with a property that only holds for some subset of k-vertex subgraphs which have an even (respectively odd) number of edges. On the other hand, we show that each of the problems admits an FPTRAS. These approximation schemes are based on a surprising structural result, which exploits ideas from Ramsey theory. PubDate: 2017-10-01 DOI: 10.1007/s00493-016-3338-5 Issue No:Vol. 37, No. 5 (2017)

Authors:Bhargav P. Narayanan; Julian Sahasrabudhe; István Tomon Pages: 991 - 1010 Abstract: Abstract We investigate the following generalisation of the ‘multiplication table problem’ of Erdős: given a bipartite graph with m edges, how large is the set of sizes of its induced subgraphs' Erdős’s problem of estimating the number of distinct products ab with a,b ≤ n is precisely the problem under consideration when the graph in question is the complete bipartite graph K n,n . In this note, we prove that the set of sizes of the induced subgraphs of any bipartite graph with m edges contains Ω(m/(logm)12) distinct elements. PubDate: 2017-10-01 DOI: 10.1007/s00493-016-3322-0 Issue No:Vol. 37, No. 5 (2017)

Authors:James H. Schmerl Pages: 1011 - 1026 Abstract: Abstract Given a polynomial p(x 0,x 1,...,x k−1) over the reals ℝ, where each x i is an n-tuple of variables, we form its zero k-hypergraph H=(ℝ n , E), where the set E of edges consists of all k-element sets {a 0,a 1,...,a k−1}⊆ℝ n such that p(a 0,a 1,...,a k−1)=0. Such hypergraphs are precisely the algebraic hypergraphs. We say (as in [13]) that p(x 0,x 1,...,x k−1) is avoidable if the chromatic number χ(H) of its zero hypergraph H is countable, and it is κ-avoidable if χ(H≤κ. Avoidable polynomials were completely characterized in [13]. For any infinite κ, we characterize the κ-avoidable algebraic hypergraphs. Other results about algebraic hypergraphs and their chromatic numbers are also proved. PubDate: 2017-10-01 DOI: 10.1007/s00493-016-3393-y Issue No:Vol. 37, No. 5 (2017)

Authors:Carsten Thomassen Pages: 1027 - 1037 Abstract: Abstract We give an elementary proof of the theorem of Nash-Williams that a graph has an edge-decomposition into cycles if and only if it does not contain an odd cut. We also prove that every bridgeless graph has a collection of cycles covering each edge at least once and at most 7 times. The two results are equivalent in the sense that each can be derived from the other. PubDate: 2017-10-01 DOI: 10.1007/s00493-016-3424-8 Issue No:Vol. 37, No. 5 (2017)

Authors:Venkatesan Guruswami; Euiwoong Lee Abstract: 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: 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: 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: 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: 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: 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

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