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: Let d be a positive integer and U ⊂ ℤd finite. We study $$\beta (U): = \mathop {\inf }\limits_{\mathop {A,B \ne \phi }\limits_{{\rm{finite}}} } {{\left {A + B + U} \right } \over {{{\left A \right }^{1/2}}{{\left B \right }^{1/2}}}},$$ and other related quantities. We employ tensorization, which is not available for the doubling constant, ∣U + U∣/∣U∣. For instance, we show $$\beta (U) = \left U \right ,$$ whenever U is a subset of {0,1}d. Our methods parallel those used for the Prékopa—Leindler inequality, an integral variant of the Brunn—Minkowski inequality. PubDate: 2022-01-14
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: 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-01-14
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: 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-01-14
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: The asymptotic spectrum of graphs, introduced by Zuiddam (Combinatorica, 2019), is the space of graph parameters that are additive under disjoint union, multiplicative under the strong product, normalized and monotone under homomorphisms between the complements. He used it to obtain a dual characterization of the Shannon capacity of graphs as the minimum of the evaluation function over the asymptotic spectrum and noted that several known upper bounds, including the Lovász number and the fractional Haemers bounds are in fact elements of the asymptotic spectrum (spectral points). We show that every spectral point admits a probabilistic refinement and characterize the functions arising in this way. This reveals that the asymptotic spectrum can be parameterized with a convex set and the evaluation function at every graph is logarithmically convex. One consequence is that for any incomparable pair of spectral points f and g there exists a third one h and a graph G such that h(G) < min{f(G),g(G)}, thus h gives a better upper bound on the Shannon capacity of G. In addition, we show that the (logarithmic) probabilistic refinement of a spectral point on a fixed graph is the entropy function associated with a convex corner. PubDate: 2021-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: We show that the maximum cardinality of an equiangular line system in 14 and 16 dimensions is 28 and 40, respectively, thereby solving a longstanding open problem. We also improve the upper bounds on the cardinality of equiangular line systems in 19 and 20 dimensions to 74 and 94, respectively. PubDate: 2021-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: Pokrovskiy conjectured that there is a function f: ℕ → ℕ such that any 2k-strongly-connected tournament with minimum out and in-degree at least f(k) is k-linked. In this paper, we show that any (2k + 1)-strongly-connected tournament with minimum out-degree at least some polynomial in k is k-linked, thus resolving the conjecture up to the additive factor of 1 in the connectivity bound, but without the extra assumption that the minimum in-degree is large. Moreover, we show the condition on high minimum out-degree is necessary by constructing arbitrarily large tournaments that are (2.5k − 1)-strongly-connected tournaments but are not k-linked. PubDate: 2021-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: Gardner conjectured that if two bounded measurable sets A, B ⊂ ℝn are equidecomposable by a set of isometries Γ generating an amenable group then A and B admit a measurable equidecomposition by all isometries. Cieśla and Sabok asked if there is a measurable equidecomposition using isometries only in the group generated by Γ. We answer this question negatively. PubDate: 2021-11-25
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: We break the exponential barrier for triangulations of the real projective space, constructing a trianglation of ℝPn with \({e^{\left({{1 \over 2} + o(1)} \right)\sqrt n \log n}}\) vertices. PubDate: 2021-11-25
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: 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: 2021-11-25
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: In this note we investigate how to use an initial portion of the intersection array of a distance-regular graph to give an upper bound for the diameter of the graph. We prove three new diameter bounds. Our bounds are tight for the Hamming d-cube, doubled Odd graphs, the Heawood graph, Tutte’s 8-cage and 12-cage, the generalized dodecagons of order (1, 3) and (1, 4), the Biggs-Smith graph, the Pappus graph, the Wells graph, and the dodecahedron. PubDate: 2021-11-25
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: We prove a sharp upper bound on the number of shortest cycles contained inside any connected graph in terms of its number of vertices, girth, and maximal degree. Equality holds only for Moore graphs, which gives a new characterization of these graphs. In the case of regular graphs, our result improves an inequality of Teo and Koh. We also show that a subsequence of the Ramanujan graphs of Lubotzky-Phillips-Sarnak have super-linear kissing numbers. PubDate: 2021-11-25
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: A ladder is a 2 × k grid graph. When does a graph class \({\cal C}\) exclude some ladder as a minor' We show that this is the case if and only if all graphs G in \({\cal C}\) admit a proper vertex coloring with a bounded number of colors such that for every 2-connected subgraph H of G, there is a color that appears exactly once in H. This type of vertex coloring is a relaxation of the notion of centered coloring, where for every connected subgraph H of G, there must be a color that appears exactly once in H. The minimum number of colors in a centered coloring of G is the treedepth of G, and it is known that classes of graphs with bounded treedepth are exactly those that exclude a fixed path as a subgraph, or equivalently, as a minor. In this sense, the structure of graphs excluding a fixed ladder as a minor resembles the structure of graphs without long paths. Another similarity is as follows: It is an easy observation that every connected graph with two vertex-disjoint paths of length k has a path of length k+1. We show that every 3-connected graph which contains as a minor a union of sufficiently many vertex-disjoint copies of a 2×k grid has a 2×(k+1) grid minor. Our structural results have applications to poset dimension. We show that posets whose cover graphs exclude a fixed ladder as a minor have bounded dimension. This is a new step towards the goal of understanding which graphs are unavoidable as minors in cover graphs of posets with large dimension. PubDate: 2021-11-25
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: One of the oldest results in modern graph theory, due to Mantel, asserts that every triangle-free graph on n vertices has at most ⌊n2/4⌋ edges. About half a century later Andrásfai studied dense triangle-free graphs and proved that the largest triangle-free graphs on n vertices without independent sets of size αn, where 2/5 ≤ α < 1/2, are blow-ups of the pentagon. More than 50 further years have elapsed since Andrásfai’s work. In this article we make the next step towards understanding the structure of dense triangle-free graphs without large independent sets. Notably, we determine the maximum size of triangle-free graphs G on n vertices with α(G) ≥ 3n/8 and state a conjecture on the structure of the densest triangle-free graphs G with α(G) > n/3. We remark that the case α(G) α n/3 behaves differently, but due to the work of Brandt this situation is fairly well understood. PubDate: 2021-11-24
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: In 1916, Schur introduced the Ramsey number r(3; m), which is the minimum integer n > 1 such that for any m-coloring of the edges of the complete graph Kn, there is a monochromatic copy of K3. He showed that r(3; m) ≤ O(m!), and a simple construction demonstrates that r(3; m) ≥ 2Ω(m). An old conjecture of Erdős states that r(3; m) = 2Θ(m). In this note, we prove the conjecture for m-colorings with bounded VC-dimension, that is, for m-colorings with the property that the set system induced by the neighborhoods of the vertices with respect to each color class has bounded VC-dimension. PubDate: 2021-11-20
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: We study substitutive systems generated by nonprimitive substitutions and show that transitive subsystems of substitutive systems are substitutive. As an application we obtain a complete characterisation of the sets of words that can appear as common factors of two automatic sequences defined over multiplicatively independent bases. This generalises the famous theorem of Cobham. PubDate: 2021-11-20
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: In this note we study and obtain factorization theorems for colorings of matrices and Grassmannians over ℝ and ℂ, which can be considered metric versions of the Dual Ramsey Theorem for Boolean matrices and of the Graham-Leeb-Rothschild Theorem for Grassmannians over a finite field. PubDate: 2021-11-20
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: We prove that the number of directions contained in a set of the form A × B ⊂ AG(2,p), where p is prime, is at least A B − min{ A , B } + 2. Here A and B are subsets of GF(p) each with at least two elements and A B <p. This bound is tight for an infinite class of examples. Our main tool is the use of the Rédei polynomial with Szőnyi’s extension. As an application of our main result, we obtain an upper bound on the clique number of a Paley graph, matching the current best bound obtained recently by Hanson and Petridis. PubDate: 2021-11-20
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: 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: 2021-11-15
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: We prove that a formula predicted on the basis of non-rigorous physics arguments [Zdeborová and Krzakala: Phys. Rev. E (2007)] provides a lower bound on the chromatic number of sparse random graphs. The proof is based on the interpolation method from mathematical physics. In the case of random regular graphs the lower bound can be expressed algebraically, while in the case of the binomial random we obtain a variational formula. As an application we calculate improved explicit lower bounds on the chromatic number of random graphs for small (average) degrees. Additionally, we show how asymptotic formulas for large degrees that were previously obtained by lengthy and complicated combinatorial arguments can be re-derived easily from these new results. PubDate: 2021-10-26
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: A cap of spherical radius α on a unit d-sphere S is the set of points within spherical distance α from a given point on the sphere. Let \({\cal F}\) be a finite set of caps lying on S. We prove that if no hyperplane through the center of S divides \({\cal F}\) into two non-empty subsets without intersecting any cap in \({\cal F}\) , then there is a cap of radius equal to the sum of radii of all caps in \({\cal F}\) covering all caps of \({\cal F}\) provided that the sum of radii is less than π/2. This is the spherical analog of the so-called Circle Covering Theorem by Goodman and Goodman and the strengthening of Fejes Tóth’s zone conjecture proved by Jiang and the author. PubDate: 2021-10-01
Hybrid journal (It can contain Open Access articles)
[2484 journals]
