Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Balanced weighing matrices with parameters $$\left({1 + 18 \cdot {{{9^{m + 1}} - 1} \over 8},{9^{m + 1}},4 \cdot {9^m}} \right),$$ for each nonzero integer m are constructed. This is the first infinite class not belonging to those with classical parameters. It is shown that any balanced weighing matrix is equivalent to a five-class association scheme. PubDate: 2022-12-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Kim, Kühn, Osthus and Tyomkyn (Trans. Amer. Math. Soc. 371 (2019), 4655–4742) greatly extended the well-known blow-up lemma of Komlós, Sárközy and Szemerédi by proving a ‘blow-up lemma for approximate decompositions’ which states that multipartite quasirandom graphs can be almost decomposed into any collection of bounded degree graphs with the same multipartite structure and slightly fewer edges. This result has already been used by Joos, Kim, Kühn and Osthus to prove the tree packing conjecture due to Gyárfás and Lehel from 1976 and Ringel’s conjecture from 1963 for bounded degree trees as well as implicitly in the recent resolution of the Oberwolfach problem (asked by Ringel in 1967) by Glock, Joos, Kim, Kühn and Osthus. Here we present a new and significantly shorter proof of the blow-up lemma for approximate decompositions. In fact, we prove a more general theorem that yields packings with stronger quasirandom properties which is useful for potential applications. PubDate: 2022-12-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract A zero-one matrix M contains a zero-one matrix A if one can delete some rows and columns of M, and turn some 1-entries into 0-entries such that the resulting matrix is A. The extremal number of A, denoted by ex(n, A), is the maximum number of 1-entries in an n × n sized matrix M that does not contain A. A matrix A is column-t-partite (or row-t-partite), if it can be cut along the columns (or rows) into t submatrices such that every row (or column) of these submatrices contains at most one 1-entry. We prove that if A is column-t-partite, then \({\rm{ex}}(n,A) < {n^{2 - {1 \over t} + {1 \over {{t^2}}} + o(1)}}\) and if A is both column- and row-t-partite, then \({\rm{ex}}(n,A) < {n^{2 - {1 \over t} + o(1)}}\) . Our proof combines a novel density-increment-type argument with the celebrated dependent random choice method. Results about the extremal numbers of zero-one matrices translate into results about the Turán numbers of bipartite ordered graphs. In particular, a zero-one matrix with at most t 1-entries in each row corresponds to a bipartite ordered graph with maximum degree t in one of its vertex classes. Our results are partially motivated by a well-known result of Füredi (1991) and Alon, Krivelevich, Sudakov (2003) stating that if H is a bipartite graph with maximum degree t in one of the vertex classes, then \({\rm{ex}}(n,H) = O({n^{2 - {1 \over t}}})\) . The aim of the present paper is to establish similar general results about the extremal numbers of ordered graphs. PubDate: 2022-12-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Motivated by the work of Lovász and Szegedy on the convergence and limits of dense graph sequences [10], we investigate the convergence and limits of finite trees with respect to sampling in normalized distance. We introduce dendrons (a notion based on separable real trees) and show that the sampling limits of finite trees are exactly the dendrons. We also prove that the limit dendron is unique. PubDate: 2022-12-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Let Qn be the n-dimensional Hamming cube and N = 2n. We prove that the number of maximal independent sets in Qn is asymptotically $$2n{2^{N/4}},$$ as was conjectured by Ilinca and the first author in connection with a question of Duffus, Frankl and Rödl. The value is a natural lower bound derived from a connection between maximal independent sets and induced matchings. The proof that it is also an upper bound draws on various tools, among them “stability” results for maximal independent set counts and old and new results on isoperimetric behavior in Qn. PubDate: 2022-12-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Baker and Wang define the so-called Bernardi action of the sandpile group of a ribbon graph on the set of its spanning trees. This potentially depends on a fixed vertex of the graph but it is independent of the base vertex if and only if the ribbon structure is planar, moreover, in this case the Bernardi action is compatible with planar duality. Earlier, Chan, Church and Grochow and Chan, Glass, Macauley, Perkinson, Werner and Yang proved analogous results about the rotor-routing action. Baker and Wang moreover showed that the Bernardi and rotor-routing actions coincide for plane graphs. We clarify this still confounding picture by giving a canonical definition for the planar Bernardi/rotor-routing action, and also a canonical description of the isomorphism between sandpile groups of planar dual graphs. Our definition implies the compatibility with planar duality via an extremely short argument. We also uncover hidden symmetries of the problem by proving our results in the slightly more general setting of balanced plane digraphs. Any balanced plane digraph gives rise to a trinity, i.e., a triangulation of the sphere with a three-coloring of the 0-simplices. Our most important tool is a group associated to trinities, introduced by Cavenagh and Wanless, and a result of a subset of the authors characterizing the Bernardi bijection in terms of spanning trees dual to arborescences. PubDate: 2022-10-26 DOI: 10.1007/s00493-021-4798-9
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We give a short, topological proof that all graphs admit tree-decompositions displaying their topological ends. PubDate: 2022-10-10 DOI: 10.1007/s00493-022-4987-1
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Let f be a degree d polynomial in n variables defined over a finite field k of characteristic p and let N be the number of zeros of f in kn. The Chevalley-Warning theorem asserts that if d<n, then N is divisible by p. In this note we show a version of the result for d = n. PubDate: 2022-10-10 DOI: 10.1007/s00493-022-5043-x
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Harris’s correlation inequality states that any two monotone functions on the Boolean hy-percube are positively correlated. Talagrand [11] started a line of works in search of quantitative versions of this fact by providing a lower bound on the correlation in terms of the influences of the functions. A famous conjecture of Chvátal [2] was found by Friedgut, Kahn, Kalai and Keller [5] to be equivalent to a certain strengthening of Talagrand’s bound, conjectured to hold true when one of the functions is antipodal (i.e., g(x) = 1 − g(−x). Motivated by this conjecture, we strengthen some of those bounds by giving estimates that also involve the second order Fourier coefficients of the functions. In particular, we show that the bounds due to Talagrand and due to Keller, Mossel and Sen [8] can be improved when one of the functions is antipodal. Our proofs follow a different route than the ones in the literature, and the analysis is carried out in the Gaussian setting. PubDate: 2022-10-10 DOI: 10.1007/s00493-021-4417-9
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We study the complexity of cutting planes and branching schemes from a theoretical point of view. We give some rigorous underpinnings to the empirically observed phenomenon that combining cutting planes and branching into a branch-and-cut framework can be orders of magnitude more efficient than employing these tools on their own. In particular, we give general conditions under which a cutting plane strategy and a branching scheme give a provably exponential advantage in efficiency when combined into branch-and-cut. The efficiency of these algorithms is evaluated using two concrete measures: number of iterations and sparsity of constraints used in the intermediate linear/convex programs. To the best of our knowledge, our results are the first mathematically rigorous demonstration of the superiority of branch-and-cut over pure cutting planes and pure branch-and-bound. PubDate: 2022-10-10 DOI: 10.1007/s00493-022-4884-7
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We say a pair of integers (a, b) is findable if the following is true. For any δ > 0 there exists a p0 such that for any prime p ≥ p0 and any red-blue colouring of ℤ/pℤ in which each colour has density at least δ, we can find an arithmetic progression of length a + b inside ℤ/pℤ whose first a elements are red and whose last b elements are blue. Szemeredi’s Theorem on arithmetic progressions implies that (0, k) and (1, k) are find-able for any k. We prove that (2, k) is also findable for any k. However, the same is not true of (3, k). Indeed, we give a construction showing that (3,30000) is not findable. We also show that (14, 14) is not findable. PubDate: 2022-10-10 DOI: 10.1007/s00493-022-4901-x
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Ovoids of the non-degenerate quadric Q(4,q) of PG(4,q) have been studied since the end of the’ 80s. They are rare objects and, beside the classical example given by an elliptic quadric, only three classes are known for q odd, one class for q even, and a sporadic example for q = 35. It is well known that to any ovoid of Q(4,q) a bivariate polynomial f (x,y) can be associated. In this paper we classify ovoids of Q(4,q) whose corresponding polynomial f (x, y) has “low degree” compared with q, in particular, \(\deg \left( f \right) < {\left( {{1 \over {6.3}}q} \right)^{{3 \over {13}}}} - 1\) . Finally, as an application, two classes of permutation polynomials in characteristic 3 are obtained. PubDate: 2022-10-10 DOI: 10.1007/s00493-022-5005-3
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We study the class of all finite directed graphs (digraphs) up to primitive positive constructibility. The resulting order has a unique maximal element, namely the digraph P1 with one vertex and no edges. The digraph P1 has a unique maximal lower bound, namely the digraph P2 with two vertices and one directed edge. Our main result is a complete description of the maximal lower bounds of P2; we call these digraphs submaximal. We show that every digraph that is not equivalent to P1 and P2 is below one of the submaximal digraphs. PubDate: 2022-10-10 DOI: 10.1007/s00493-022-4918-1
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Recently, Ben Green proved that the two-color van der Waerden number ω(3, k) is bounded from below by \({k^{{b_0}\left( k \right)}}\) where \({b_0}\left( k \right) = {c_0}{\left( {{{\log \,k} \over {\log \log \,k}}} \right)^{1/3}}\) . We prove a new lower bound of kb(k) with \(b\left( k \right) = {{c\log \,k} \over {\log \log \,k}}\) . This is done by modifying Green’s argument, replacing a complicated result about random quadratic forms with an elementary probabilistic result. PubDate: 2022-10-10 DOI: 10.1007/s00493-022-4925-2
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract A d-partite hypergraph is called fractionally balanced if there exists a non-negative, not identically zero, function on its edge set that has constant degrees in each vertex side. Using a topological version of Hall’s theorem we prove lower bounds on the matching number of such hypergraphs. These bounds yield rainbow versions of the KKM theorem for products of simplices, which in turn are used to obtain some results on multiple-cake division, and on rainbow matchings in families of d-intervals. PubDate: 2022-10-10 DOI: 10.1007/s00493-021-4808-y
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We prove a common generalization of the celebrated Sauer-Spencer packing theorem and a theorem of Brandt concerning finding a copy of a tree inside a graph. This proof leads to the characterization of the extremal graphs in the case of Brandt’s theorem: If G is a graph and F is a forest, both on n vertices, and 3Δ(G) + ℓ* (F) ≤ n, then G and F pack unless n is even, \(G = {n \over 2}{K_2}\) and F = K1,n−1 where ℓ*(F) is the difference between the number of leaves and twice the number of nontrivial components of F. PubDate: 2022-10-10 DOI: 10.1007/s00493-022-4932-3
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We prove a conjecture of Geelen that every proper vertex-minor-closed class of graphs is χ-bounded. PubDate: 2022-10-10 DOI: 10.1007/s00493-021-4767-3
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Let m be a positive integer, q be a prime power, and PG(2,q) be the projective plane over the finite field \({\mathbb{F}_q}\) . Finding complete m-arcs in PG(2,q) of size less than q is a classical problem in finite geometry. In this paper we give a complete answer to this problem when q is relatively large compared with m, explicitly constructing the smallest m-arcs in the literature so far for any m ≥ 8. For any fixed m, our arcs \({{\cal A}_{q,m}}\) satisfy \(\left {{{\cal A}_{q,m}}} \right - q \to - \infty \) as q grows. To produce such m-arcs, we develop a Galois theoretical machinery that allows the transfer of geometric information of points external to the arc, to arithmetic one, which in turn allows to prove the m-completeness of the arc. PubDate: 2022-10-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract The orbifold Euler characteristic of the moduli space \({{\cal M}_{g;1}}\) of genus g smooth curves with one marked point (g ≥ 1) was calculated by Harer and Zagier: \(\chi ({{\cal M}_{g;1}}) = \zeta (1 - 2g) = - {B_{2g}}/(2g)\) , where ζ is the Riemann zeta function and B2g is the (2g)th Bernoulli number. We give a shorter proof of this result using only formal power series and classical combinatorics. PubDate: 2022-10-01
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract A set of positive integers is primitive (or 1-primitive) if no member divides another. Erdős proved in 1935 that the weighted sum ∑1/(n log n) for n ranging over a primitive set A is universally bounded over all choices for A. In 1988 he asked if this universal bound is attained by the set of prime numbers. One source of difficulty in this conjecture is that ∑n−λ over a primitive set is maximized by the primes if and only if λ is at least the critical exponent τ1 ≈ 1.14. A set is k-primitive if no member divides any product of up to k other distinct members. One may similarly consider the critical exponent τk for which the primes are maximal among k-primitive sets. In recent work the authors showed that τ2 < 0.8, which directly implies the Erdős conjecture for 2-primitive sets. In this article we study the limiting behavior of the critical exponent, proving that τk tends to zero as k → ∞. PubDate: 2022-10-01
Hybrid journal (It can contain Open Access articles)
[2467 journals]
