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-05-19
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 Van der Holst and Pendavingh introduced a graph parameter σ, which coincides with the more famous Colin de Verdière graph parameter μ for small values. However, the definition of a is much more geometric/topological directly reflecting embeddability properties of the graph. They proved μ(G) ≤ σ(G) + 2 and conjectured σ(G) ≤ σ(G) for any graph G. We confirm this conjecture. As far as we know, this is the first topological upper bound on σ(G) which is, in general, tight. Equality between μ and σ does not hold in general as van der Holst and Pendavingh showed that there is a graph G with μ(G) ≤ 18 and σ(G) ≥ 20. We show that the gap appears at much smaller values, namely, we exhibit a graph H for which μ(H) ≥ 7 and σ(H) ≥ 8. We also prove that, in general, the gap can be large: The incidence graphs Hq of finite projective planes of order q satisfy μ(Hq) ∈ O(q3/2) and σ(Hq) ≥ q2. PubDate: 2022-05-19
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 In 1985, Mader conjectured that for every acyclic digraph F there exists K = K(F) such that every digraph D with minimum out-degree at least K contains a subdivision of F. This conjecture remains widely open, even for digraphs F on five vertices. Recently, Aboulker, Cohen, Havet, Lochet, Moura and Thomassé studied special cases of Mader’s problem and made the following conjecture: for every ℓ ≥ 2 there exists K = K(ℓ) such that every digraph D with minimum out-degree at least K contains a subdivision of every orientation of a cycle of length ℓ. We prove this conjecture and answer further open questions raised by Aboulker et al. PubDate: 2022-05-19
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 Kempe switch of a 3-edge-coloring of a cubic graph G on a bicolored cycle C swaps the colors on C and gives rise to a new 3-edge-coloring of G. Two 3-edge-colorings of G are Kempe equivalent if they can be obtained from each other by a sequence of Kempe switches. Fisk proved that any two 3-edge-colorings in a cubic bipartite planar graph are Kempe equivalent. In this paper, we obtain an analog of this theorem and prove that all 3-edge-colorings of a cubic bipartite projective-planar graph G are pairwise Kempe equivalent if and only if G has an embedding in the projective plane such that the chromatic number of the dual triangulation G* is at least 5. As a by-product of the results in this paper, we prove that the list-edge-coloring conjecture holds for cubic graphs G embedded on the projective plane provided that the dual G* is not 4-vertex-colorable. PubDate: 2022-05-19
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 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: 2022-04-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 Besides various asymptotic results on the concept of sum-product bases in the set of non-negative integers ℕ, we investigate by probabilistic arguments the existence of thin sets A, A′ of non-negative integers such that AA + A = ℕ and A′A′ + A′A′ = ℕ. PubDate: 2022-04-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 We describe a family of graphs with queue-number at most 4 but unbounded stack-number. This resolves open problems of Heath, Leighton and Rosenberg (1992) and Blankenship and Oporowski (1999). PubDate: 2022-04-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 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-03-14 DOI: 10.1007/s00493-021-4774-4
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 show that for any n ≥ 13, there exist graphs with chromatic number larger than n whose product has chromatic number n. Our construction is an adaptation of the construction of counterexamples to Hedetniemi’s conjecture devised by Shitov, and adapted by Zhu to graphs with relatively small chromatic numbers. The new tools we introduce are graphs with minimal colourings that are “wide” in the sense of Simonyi and Tardos, and generalised Mycielskians to settle the case n = 13. PubDate: 2022-03-14 DOI: 10.1007/s00493-021-4781-5
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 work out the theory of fractional isomorphism of graphons as a generalization to the classical theory of fractional isomorphism of finite graphs. The generalization is given in terms of homomorphism densities of finite trees and it is characterized in terms of distributions on iterated degree measures, Markov operators, weak isomorphism of a conditional expectation with respect to invariant sub-σ-algebras and isomorphism of certain quotients of given graphons. PubDate: 2022-03-14 DOI: 10.1007/s00493-021-4336-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 For any integer k ≥ 2, we prove combinatorially the following Euler (binomial) transformation identity $${\rm{NC}}_{n + 1}^{(k)}(t) = t\sum\limits_{i = 0}^n {\left({\matrix{n \cr i \cr}} \right)} {\rm{NW}}_i^{(k)}(t),$$ where NC m (k) (t) (resp. NW m (k) (t)) is the sum of weights, tnumber of blocks, of partitions of {1,…,m} without k-crossings (resp. enhanced k-crossings). The special k = 2 and t = 1 case, asserting the Euler transformation of Motzkin numbers are Catalan numbers, was discovered by Donaghey 1977. The result for k = 3 and t = 1, arising naturally in a recent study of pattern avoidance in ascent sequences and inversion sequences, was proved only analytically. PubDate: 2022-03-14 DOI: 10.1007/s00493-021-4262-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 Form an n × n matrix by drawing entries independently from {±1} (or another fixed nontrivial finitely supported distribution in Z) and let φ be the characteristic polynomial. We show, conditionally on the extended Riemann hypothesis, that with high probability φ is irreducible and Gal(φ) ≥ An. PubDate: 2022-03-14 DOI: 10.1007/s00493-020-4657-0
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-03-14 DOI: 10.1007/s00493-021-4729-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 Let V ⊆ [n] be a k-element subset of [n]. The uniform distribution on the 2k strings from {0, 1}n that are set to zero outside of V is called an (n, k)-zero-fixing source. An ϵ-extractor for (n, k)-zero-fixing sources is a mapping F: {0, 1}n → {0, 1}m, for some m, such that F(X) is ϵ-close in statistical distance to the uniform distribution on {0, 1}m for every (n, k)-zero-fixing source X. Zero-fixing sources were introduced by Cohen and Shinkar in [7] in connection with the previously studied extractors for bit-fixing sources. They constructed, for every μ > 0, an efficiently computable extractor that extracts a positive fraction of entropy, i.e., Ω(k) bits, from (n, k)-zero-fixing sources where k ≥ (log log n)2+μ. In this paper we present two different constructions of extractors for zero-fixing sources that are able to extract a positive fraction of entropy for k substantially smaller than log log n. The first extractor works for k ≥ C log log log n, for some constant C. The second extractor extracts a positive fraction of entropy for k ≥ log(i)n for any fixed i ∈ ℕ, where log(i) denotes i-times iterated logarithm. The fraction of extracted entropy decreases with i. The first extractor is a function computable in polynomial time in n; the second one is computable in polynomial time in n when k ≤ α log log n/log log log n, where α is a positive constant. Our results can also be viewed as lower bounds on some Ramsey-type properties. The main difference between the problems about extractors studied here and the standard Ramsey theory is that we study colorings of all subsets of size up to k while in Ramsey theory the sizes are fixed to k. However it is easy to derive results also for coloring of subsets of sizes equal to k. In Corollary 3.1 of Theorem 5.1 we show that for every l ∈ ℕ there exists β < 1 such that for every k and n, n ≤ expl (k), there exists a 2-coloring of k-tuples of elements of [n], \(\psi :\left({\matrix{{[n]} \cr k \cr}} \right) \to \left\{{- 1,1} \right\}\) such that for every V ⊆ [n], V = 2k, we have \(\left {\sum\nolimits_{X \subseteq V,\left X \right = k} {\psi (X)}} \right \le {\beta ^k}\left({\matrix{{2k} \cr k \cr}} \right)\) (Corollary 3.1 is more general — the number of colors may be more than 2). PubDate: 2022-03-14 DOI: 10.1007/s00493-020-4626-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 study c-crossing-critical graphs, which are the minimal graphs that require at least c edge-crossings when drawn in the plane. For every fixed pair of integers with c ≥ 13 and d ≥ 1, we give first explicit constructions of c-crossing-critical graphs containing arbitrarily many vertices of degree greater than d. We also show that such unbounded degree constructions do not exist for c ≤ 12, precisely, that there exists a constant D such that every c-crossing-critical graph with c ≤ 12 has maximum degree at most D. Hence, the bounded maximum degree conjecture of c-crossing-critical graphs, which was generally disproved in 2010 by Dvořák and Mohar (without an explicit construction), holds true, surprisingly, exactly for the values c ≤ 12.1 PubDate: 2022-03-14 DOI: 10.1007/s00493-021-4285-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 The book graph \(B_n^{(k)}\) consists of n copies of Kk+1 joined along a common Kk. The Ramsey numbers of \(B_n^{(k)}\) are known to have strong connections to the classical Ramsey numbers of cliques. Recently, the first author determined the asymptotic order of these Ramsey numbers for fixed k, thus answering an old question of Erdős, Faudree, Rousseau, and Schelp. In this paper, we first provide a simpler proof of this theorem. Next, answering a question of the first author, we present a different proof that avoids the use of Szemerédi’s regularity lemma, thus providing much tighter control on the error term. Finally, we prove a conjecture of Nikiforov, Rousseau, and Schelp by showing that all extremal colorings for this Ramsey problem are quasirandom. PubDate: 2022-03-10 DOI: 10.1007/s00493-021-4409-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 computational problem of determining the covering radius of a rational polytope. This parameter is defined as the minimal dilation factor that is needed for the lattice translates of the correspondingly dilated polytope to cover the whole space. As our main result, we describe a new algorithm for this problem, which is simpler, more efficient and easier to implement than the only prior algorithm of Kannan (1992). Motivated by a variant of the famous Lonely Runner Conjecture, we use its geometric interpretation in terms of covering radii of zonotopes, and apply our algorithm to prove the first open case of three runners with individual starting points. PubDate: 2022-02-18 DOI: 10.1007/s00493-020-4633-8
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 fundamental barrier in extremal hypergraph theory is the presence of many near-extremal constructions with very different structures. Indeed, the classical constructions due to Kostochka imply that the notorious extremal problem for the tetrahedron exhibits this phenomenon assuming Turán’s conjecture. Our main result is to construct a finite family of triple systems \({\cal M}\) , determine its Turán number, and prove that there are two near-extremal \({\cal M}\) -free constructions that are far from each other in edit-distance. This is the first extremal result for a hypergraph family that fails to have a corresponding stability theorem. PubDate: 2022-02-18 DOI: 10.1007/s00493-021-4561-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 In 1959, Grötzsch [5] famously proved that every planar graph of girth at least 4 is 3-colourable (or equivalently, admits a homomorphism to C3). A natural generalization of this is the following conjecture: for every positive integer t, every planar graph of girth at least 4t admits a homomorphism to C2t+1. This is in fact the planar dual of a well-known conjecture of Jaeger [7] which states that every 4t-edge-connected graph admits a modulo (2t + 1)-orientation. Though Jaeger’s original conjecture was disproved in [6], Lovász et al. [10] showed that every 6t-edge connected graph admits a modolo (2t + 1)-flow. The latter result implies that every planar graph of girth at least 6t admits a homomorphism to C2t+1. We improve upon this in the t = 3 case, by showing that every planar graph of girth at least 16 admits a homomorphism to C7. We obtain this through a more general result regarding the density of C7-critical graphs: if G is a C7-critical graph with G ∉ {C3, C5}, then \(e(G) \ge {{17v(G) - 2} \over {15}}\) . PubDate: 2022-02-18 DOI: 10.1007/s00493-020-4177-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 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 DOI: 10.1007/s00493-021-4547-0
Hybrid journal (It can contain Open Access articles)
[2469 journals]
