Authors:Karim A. Adiprasito; Arnau Padrol Pages: 129 - 136 Abstract: Abstract In this note, we prove that every open primary basic semialgebraic set is stably equivalent to the realization space of a neighborly simplicial polytope. This in particular provides the final step for Mnëv‘s proof of the universality theorem for simplicial polytopes. PubDate: 2017-04-01 DOI: 10.1007/s00493-016-3253-9 Issue No:Vol. 37, No. 2 (2017)

Authors:Levent Alpoge Pages: 137 - 142 Abstract: Abstract Let L(n) be the number of Latin squares of order n, and let L even(n) and L odd(n) be the number of even and odd such squares, so that L(n)=L even(n)+L odd(n). The Alon-Tarsi conjecture states that L even(n) ≠ L odd(n) when n is even (when n is odd the two are equal for very simple reasons). In this short note we prove that $$\left {{L^{even}}\left( n \right) - {L^{odd}}\left( n \right)} \right \leqslant L{\left( n \right)^{\frac{1}{2} + o\left( 1 \right)}}$$ , thus establishing the conjecture that the number of even and odd Latin squares, while conjecturally not equal in even dimensions, are equal to leading order asymptotically. Two proofs are given: both proceed by applying a differential operator to an exponential integral over SU(n). The method is inspired by a recent result of Kumar-Landsberg. PubDate: 2017-04-01 DOI: 10.1007/s00493-015-3373-7 Issue No:Vol. 37, No. 2 (2017)

Authors:Diana Ojeda-Aristizabal Pages: 143 - 155 Abstract: Abstract We give a constructive proof of the finite version of Gowers’ FIN k Theorem for both the positive and the general case and analyse the corresponding upper bounds provided by the proofs. PubDate: 2017-04-01 DOI: 10.1007/s00493-015-3223-7 Issue No:Vol. 37, No. 2 (2017)

Authors:Tai Do Duc; Bernhard Schmidt Pages: 167 - 182 Abstract: Abstract Let p be a prime and let A be a subset of F p with A = -A and A \ {0} ≤ 2log3(p). Then there is an element of F p which has a unique representation as a difference of two elements of A. PubDate: 2017-04-01 DOI: 10.1007/s00493-015-3282-9 Issue No:Vol. 37, No. 2 (2017)

Authors:Matthias Hamann Pages: 183 - 222 Abstract: Abstract We classify the finite connected-homogeneous digraphs, as well as the infinite locally finite such digraphs with precisely one end. This completes the classification of all the locally finite connected-homogeneous digraphs. PubDate: 2017-04-01 DOI: 10.1007/s00493-015-2804-9 Issue No:Vol. 37, No. 2 (2017)

Authors:Michael A. Henning; Sandi Klavžar; Douglas F. Rall Pages: 223 - 251 Abstract: Abstract The recently introduced total domination game is studied. This game is played on a graph G by two players, named Dominator and Staller. They alternately take turns choosing vertices of G such that each chosen vertex totally dominates at least one vertex not totally dominated by the vertices previously chosen. Dominator’s goal is to totally dominate the graph as fast as possible, and Staller wishes to delay the process as much as possible. The game total domination number, γtg (G), of G is the number of vertices chosen when Dominator starts the game and both players play optimally. The Staller-start game total domination number, γ′tg (G), of G is the number of vertices chosen when Staller starts the game and both players play optimally. In this paper it is proved that if G is a graph on n vertices in which every component contains at least three vertices, then γtg (G)≤4n/5 and γ′tg (G)≤(4n+2)/5. As a consequence of this result, we obtain upper bounds for both games played on any graph that has no isolated vertices. PubDate: 2017-04-01 DOI: 10.1007/s00493-015-3316-3 Issue No:Vol. 37, No. 2 (2017)

Authors:Massimo Lauria; Pavel Pudlák; Vojtěch Rödl; Neil Thapen Pages: 253 - 268 Abstract: Abstract We say that a graph with n vertices is c-Ramsey if it does not contain either a clique or an independent set of size c log n. We define a CNF formula which expresses this property for a graph G. We show a superpolynomial lower bound on the length of resolution proofs that G is c-Ramsey, for every graph G. Our proof makes use of the fact that every c-Ramsey graph must contain a large subgraph with some properties typical for random graphs. PubDate: 2017-04-01 DOI: 10.1007/s00493-015-3193-9 Issue No:Vol. 37, No. 2 (2017)

Authors:David Perkinson; Qiaoyu Yang; Kuai Yu Pages: 269 - 282 Abstract: Abstract A depth-first search version of Dhar’s burning algorithm is used to give a bijection between the parking functions of a graph and labeled spanning trees, relating the degree of the parking function with the number of inversions of the spanning tree. Specializing to the complete graph solves a problem posed by R. Stanley. PubDate: 2017-04-01 DOI: 10.1007/s00493-015-3191-y Issue No:Vol. 37, No. 2 (2017)

Authors:Joseph A. Thas; Hendrik Van Maldeghem Pages: 283 - 311 Abstract: Abstract We classify all representations of an arbitrary affine plane A of order q in a projective space PG(d,q) such that lines of A correspond with affine lines and/or plane q-arcs and such that for each plane q-arc which corresponds to a line L of A the plane of PG(d,q) spanned by the q-arc does not contain the image of any point off L of A. PubDate: 2017-04-01 DOI: 10.1007/s00493-014-3179-z Issue No:Vol. 37, No. 2 (2017)

Authors:Jacob Fox; János Pach; Andrew Suk Abstract: Abstract We establish the following result related to Erdős’s problem on distinct distances. Let V be an n-element planar point set such that any p members of V determine at least \(\left( {\begin{array}{*{20}{c}} p \\ 2 \end{array}} \right) - p + 6\) distinct distances. Then V determines at least \(n^{\tfrac{8} {7} - o(1)}\) distinct distances, as n tends to infinity. PubDate: 2017-03-24 DOI: 10.1007/s00493-016-3637-x

Authors:Morgan Rodgers; Leo Storme; Andries Vansweevelt Abstract: Abstract We look at a generalization of Cameron-Liebler line classes to sets of k-spaces, focusing on results in PG(2k+1, q). Here we obtain a connection to k-spreads which parallels the situation for line classes in PG(3,q). After looking at some characterizations of these sets and some of the difficulties that arise in contrast to the known results for line classes, we give some connections to various other geometric objects including k-spreads and Erdős–Ko–Rado sets, and prove results concerning the existence of these objects. PubDate: 2017-03-24 DOI: 10.1007/s00493-016-3482-y

Authors:Terence Tao; Van Vu Abstract: Abstract Let M n =(ξ ij )1≤i,j≤n be a real symmetric random matrix in which the upper-triangular entries ξ ij , i < j and diagonal entries ξ ii are independent. We show that with probability tending to 1, M n has no repeated eigenvalues. As a corollary, we deduce that the Erdős-Rényi random graph has simple spectrum asymptotically almost surely, answering a question of Babai. PubDate: 2017-03-24 DOI: 10.1007/s00493-016-3363-4

Authors:Shaofei Du; Wenqin Xu; Guiying Yan Abstract: Abstract This paper contributes to the classification of finite 2-arc-transitive graphs. In [12], all the regular covers of complete bipartite graphs K n,n were classified, whose covering transformation group is cyclic and whose fibre-preserving automorphism group acts 2-arc-transitively. In this paper, a further classification is achieved for all the regular covers of K n,n , whose covering transformation group is elementary abelian group of order p 2 and whose fibre-preserving automorphism group acts 2-arc-transitively. As a result, two new infinite families of 2-arc-transitive graphs are found. Moveover, it will be explained that it seems to be infeasible to classify all such covers when the covering transformation group is an elementary abelian group of order p k for an arbitrary integer k. PubDate: 2017-03-24 DOI: 10.1007/s00493-016-3511-x

Authors:Daniel Pellicer Abstract: From a given abstract n-polytope P and a given integer k we derive two abstract polytopes Cl k (P) and \({\widetilde {Cl}_k}\left( P \right)\) of ranks n and n−1, respectively. These constructions generalise the truncation of convex polyhedra and the dual of a geometric construction yielding Petrie’s polyhedron {4,6 4}. We determine sufficient and necessary conditions to guarantee that Cl k (P) and \({\widetilde {Cl}_k}\left( P \right)\) are regular. PubDate: 2017-03-24 DOI: 10.1007/s00493-016-3518-3

Authors:Guus Regts Abstract: Abstract Based on a technique of Barvinok [4,5,6] and Barvinok and Soberón [8,9] we identify a class of edge-coloring models whose partition functions do not evaluate to zero on bounded degree graphs. Subsequently we give a quasi-polynomial time approximation scheme for computing these partition functions. As another application we show that the normalised partition functions of these models are continuous with respect to the Benjamini-Schramm topology on bounded degree graphs. We moreover give quasi-polynomial time approximation schemes for evaluating a large class of graph polynomials, including the Tutte polynomial, on bounded degree graphs. PubDate: 2017-03-24 DOI: 10.1007/s00493-016-3506-7

Authors:Anton Malyshev; Igor Pak 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-03-24 DOI: 10.1007/s00493-016-3306-0

Authors:Adam Sheffer; Endre Szabó; Joshua Zahl Abstract: Abstract We prove an incidence theorem for points and curves in the complex plane. Given a set of m points in R2 and a set of n curves with k degrees of freedom, Pach and Sharir proved that the number of point-curve incidences is \(O\left( {{m^{\frac{k}{{2k - 1}}}}{n^{\frac{{2k - 2}}{{2k - 1}}}} + m + n} \right)\) . We establish the slightly weaker bound \({O_\varepsilon }\left( {{m^{\frac{k}{{2k - 1}} + \varepsilon }}{n^{\frac{{2k - 2}}{{2k - 1}}}} + m + n} \right)\) on the number of incidences between m points and n (complex) algebraic curves in C2 with k degrees of freedom. We combine tools from algebraic geometry and differential geometry to prove a key technical lemma that controls the number of complex curves that can be contained inside a real hypersurface. This lemma may be of independent interest to other researchers proving incidence theorems over C. PubDate: 2017-02-13 DOI: 10.1007/s00493-016-3441-7

Authors:Eli Berger Abstract: Abstract We prove that in any graph containing no subdivision of an infinite clique there exists a partition of the vertices into two parts, satisfying the condition that every vertex has at least as many neighbors in the part not containing it as it has in its own part. PubDate: 2017-02-13 DOI: 10.1007/s00493-015-3261-1

Authors:David Bevan Abstract: Abstract We prove that the set of growth rates of permutation classes includes an inFInite sequence of intervals whose inFImum is θ B ≈ 2:35526, and that it also contains every value at least θ B ≈ 2:35698. These results improve on a theorem of Vatter, who determined that there are permutation classes of every growth rate at least λ A ≈ 2:48187. Thus, we also refute his conjecture that the set of growth rates below λ A is nowhere dense. Our proof is based upon an analysis of expansions of real numbers in non-integer bases, the study of which was initiated by Rényi in the 1950s. In particular, we prove two generalisations of a result of Pedicini concerning expansions in which the digits are drawn from sets of allowed values. PubDate: 2017-02-13 DOI: 10.1007/s00493-016-3349-2