Search

The determinant lower bound of Lovász, Spencer, and Vesztergombi [European J. Combin., 7 (1986), pp. 151-160] is a general way to prove lower bounds on the hereditary discrepancy of a set system. In their paper, Lovász, Spencer, and Vesztergombi asked if hereditary discrepancy can also be bounded from above by a function of the determinant lower bound. This was answered in the negative by Hoffman, and the largest known multiplicative gap between the two quantities for a set system of m subsets of a universe of size n is on the order of max {log n, √log m}. On the other hand, building upon work of Matousek [Proc. Amer. Math. Soc., 141 (2013), pp. 451-460], Jiang and Reis [in Proceedings of the Symposium on Simplicity in Algorithms (SOSA), SIAM, Philadelphia, 2022, pp. 308-313] showed that this gap is always bounded up to constants by √log(m)log(n). This is tight when m is polynomial in n but leaves open the case of large m. We show that the bound of Jiang and Reis is tight for nearly the entire range of m. Our proof amplifies the discrepancy lower bounds of a set system derived from the discrete Haar basis via Kronecker products. [ABSTRACT FROM AUTHOR]

Kovaleva and Spieksma (SIAM J Discrete Math 20(3):48–768, 2006) considered the problem of stabbing a given set of horizontal line segments with the smallest number of horizontal and vertical lines. The standard LP relaxation for this problem is easily shown to have an integrality gap of at most 2 by treating the horizontal and vertical lines separately. However, Kovaleva and Spieksma observed that threshold rounding can be used to obtain an integrality gap of e / (e - 1) ≈ 1.58 which is also shown to be tight. This is one of the rare known examples where the obvious upper bound of 2 on the integrality gap of the standard LP relaxation can be improved. Our goal in this paper is to extend their proof to two other problems where the goal is to stab a set R of objects with horizontal and vertical lines: in the first problem R is a set of horizontal and vertical line segments, and in the second problem R is a set of unit sized squares. The proof of Kovaleva and Spieksma essentially shows the existence of an appropriate threshold which yields the improved approximation factor. We begin by showing that a random threshold picked from an appropriate distribution works. This reduces the problem to finding an appropriate distribution for a desired approximation ratio. In the first problem, we show that the required distribution can be found by solving a linear program. In the second problem, while it seems harder to find the optimal distribution, we show that using the uniform distribution an improved approximation factor can still be obtained by solving a number of linear programs. [ABSTRACT FROM AUTHOR]

In this paper, we investigate representations of links that are either centrally symmetric in R3 or antipodally symmetric in S3. By using the notions of antipodally self-dual and antipodally symmetric maps, introduced and studied by the authors in [L. Montejano, J. L. Ramírez Alfonsín, and I. Rasskin, SIAM J. Discrete Math., 36 (2022), pp. 1551-1566], we are able to present sufficient combinatorial conditions for a link L to admit such representations. The latter naturally provide sufficient conditions for L to be amphichiral. We also introduce another (closely related) method yielding again sufficient conditions for L to be amphichiral. We finally prove that a link L, associated to a map G, is amphichiral if the self-dual pairing of G is not one of 6 specific cases among the classification of the 24 self-dual pairing Cor(G)⊳Aut(G). [ABSTRACT FROM AUTHOR]

Let G be a simple graph with no isolated edges. The neighbor-distinguishing edge coloring of G is a proper edge coloring of G such that any pair of adjacent vertices have different sets consisting of colors assigned on their incident edges. The neighbor-distinguishing index of G , denoted by χ a ′ (G) , is the minimum number of colors in such an edge coloring of G . In this paper, we show that if G is a connected planar graph with maximum degree Δ ≥ 14 , then Δ ≤ χ a ′ (G) ≤ Δ + 1 , and χ a ′ (G) = Δ + 1 if and only if G contains a pair of adjacent vertices of maximum degree. This improves a result in [W. Wang, D. Huang, A characterization on the adjacent vertex distinguishing index of planar graphs with large maximum degree, SIAM J. Discrete Math. 29(2015), 2412–2431], which says that every connected planar graph G with Δ ≥ 16 has Δ ≤ χ a ′ (G) ≤ Δ + 1 , and χ a ′ (G) = Δ + 1 if and only if G contains a pair of adjacent vertices of maximum degree. [ABSTRACT FROM AUTHOR]

This paper deals with the nutrient-taxis system derived by a food metric. The system was proposed in [Sun-Ho Choi and Yong-Jung Kim: Chemotactic traveling waves by metric of food, SIAM J. Appl. Math. 75 (2015), 2268–2289] using geometric ideas without gradient sensing, and has a simple form but contains a singular diffusive coefficient on the equation for the organism side. To overcome the difficulty arising from this singular structure, we use a weighted Lp-estimate involving a weighted Gagliardo-Nirenberg type inequality. In the one dimensional setting, it turns out that the system is shown to be globally well-posed in certain Sobolev spaces and the solutions are uniformly bounded. Moreover, the zero viscosity limit of the equation for the nutrient side is considered. For the same initial data and any given finite time interval, a diffusive solution converges to a non-diffusive solution when the diffusion coefficient vanishes. [ABSTRACT FROM AUTHOR]

In this paper we propose a method for computing the Faddeeva function w(z):... erfc(-iz) via truncated modified trapezoidal rule approximations to integrals on the real line. Our starting point is the method due to Matta and Reichel (Math. Comp. 25 (1971), pp. 339-344) and Hunter and Regan (Math. Comp. 26 (1972), pp. 339-541). Addressing shortcomings flagged by Weideman (SIAM. J. Numer. Anal. 31 (1994), pp. 1497-1518), we construct approximations which we prove are exponentially convergent as a function of N+1, the number of quadrature points, obtaining error bounds which show that accuracies of 2x10-15 in the computation of w(z) throughout the complex plane are achieved with N=11, this confirmed by computations. These approximations, moreover, provably achieve small relative errors throughout the upper complex half-plane where w(z) is non-zero. Numerical tests suggest that this new method is competitive, in accuracy and computation times, with existing methods for computing w(z) for complex z [ABSTRACT FROM AUTHOR]

This erratum clarifies that equations (4.21) and (4.23) in Böttcher and Porter [SIAM J. Appl. Math., 81 (2021), pp. 2704-2724] assume that the underlying evolution operator has an orthonormal basis. The results and conclusions of the paper are unaffected by this clarification. [ABSTRACT FROM AUTHOR]

For integers k ≥1 and m ≥2, let g(k,m) be the least integer n ≥1 such that every graph with chromatic number at least n contains a (k + 1)-connected subgraph with chromatic number at least m. Refining the recent result of Gir\~ao and Narayanan [Bull. Lond. Math. Soc., 54 (2022), pp. 868--875] that g(k 1, k) ≤ 7k + 1 for all k≥ 2, we prove that g(k,m) ≤ max(m + 2k 2, (3 + 1/16)k≤) for all k ≥ 1 and m≥2. This sharpens earlier results of Alon et al. [J. Graph Theory, 11 (1987), pp. 367-371], of Chudnovsky [J. Combin. Theory Ser. B, 103 (2013), pp. 567-586], and of Penev, Thomass'e, and Trotignon [SIAM J. Discrete Math., 30 (2016), pp. 592--619]. Our result implies that g(k, k + 1) (3 + 1/16)k for all k \geq 1, making a step closer towards a conjecture of Thomassen [J. Graph Theory, 7 (1983), pp. 261--271] that g(k, k +1)≤3k +1, which was originally a result with a false proof and was the starting point of this research area. [ABSTRACT FROM AUTHOR]

Litvak-Hinenzon et al. developed the phenomenological model to simulate the horizontal motion of particles in the atmosphere, and a series of their papers (see e.g., Litvak-Hinenzon et al. (Phys. D 164:213-250, 2002; Nonlinearity 15:1149-1177, 2002; SIAM J. Appl. Dyn. Syst. 3:525-573, 2004)) focused on studying the fate of parabolic resonance lower dimensional tori (as part of a quasi-periodic Hamiltonian pitchfork bifurcation (HPB) scenario in the unperturbed phenomenological model) under perturbations. However, the structural stability of quasi-periodic HPB involved therein has not been fully exposed theoretically (Litvak-Hinenzon et al. have only given some numerical explanations). Based on BCKV singularity theory established by Broer et al. (Z. Angew. Math. Phys. 44:389-432, 1993), we consider a more general quasi-periodic HPB triggered by the Z 2 -invariant universal unfolding N b c k v = a y 2 2 − (λ + b I 1) x 2 2 + c x 4 4 with respect to Z 2 -equivariant BCKV-restricted morphisms of the planar singularity a 2 y 2 + c 4 x 4 (the coefficients a , b , c ≠ 0 , the I 1 is regarded as distinguished parameter with respect to the external parameter λ). We prove a KAM (Kolmogorov–Arnold–Moser) theorem concerning parabolic tori in such quasi-periodic HPB, by which Diophantine parabolic tori (and the whole corresponding Diophantine HPB scenario) survive non-integrable and Z 2 -invariant Hamiltonian perturbations, parametrized by pertinent large Cantor sets. In the context of Z 2 -symmetry, our results can be seen as rigorous proof of the structural stability problem of bifurcations of Floquet-tori triggered by the universal unfolding N b c k v with distinguished parameters which is proposed by Broer et al. (Z. Angew. Math. Phys. 44:389-432, 1993). Ultimately, we similarly obtain the structural stability result of quasi-periodic HPB in the phenomenological model mentioned above, which can be utilized as a starting point for a deeper understanding of the various resonances and chaotic dynamics (in the gaps of the Cantor sets), just as Litvak-Hinenzon et al. did for normally parabolic tori undergoing a HPB. • We prove a KAM theorem in a quasi-periodic Hamiltonian pitchfork bifurcation. • We obtain the structural stability of a bifurcation in a phenomenological model. • We verify some of the previous numerical phenomena of Litvak-Hinenzon et al. [ABSTRACT FROM AUTHOR]

Convergence analysis of block iterative solvers for Hermitian eigenvalue problems and closely related research on properties of matrix-based signal filters are challenging and are attracting increased attention due to their recent applications in spectral data clustering and graph-based signal processing. We combine majorization-based techniques pioneered for investigating the Rayleigh--Ritz method in [A. V. Knyazev and M. E. Argentati, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 1521-1537] with tools of classical analysis of the block power method by Rutishauser [Numer. Math., 13 (1969), pp. 4-13] to derive sharp convergence rate bounds of abstract block iterations, wherein tuples of tangents of principal angles or relative errors of Ritz values are bounded using majorization in terms of arranged partial sums and tuples of convergence factors. Our novel bounds are robust in the presence of clusters of eigenvalues, improve previous results, and are applicable to most known block iterative solvers and matrix-based filters, e.g., to block power, Chebyshev, and Lanczos methods combined with polynomial filtering. The sharpness of our bounds is fundamental, implying that the bounds cannot be improved without further assumptions. [ABSTRACT FROM AUTHOR]

Poor mathematical performance is a major issue for children with ADHD. The aim of this study is to assess the impact of attention deficit and hyperactivity in relation to mathematical performance. We probed (1) The relationship among the tendency of attention deficit, hyperactivity symptoms, working memory, and mathematical performance. (2) The mediated model of these variables. Seventy-eight students from three primary schools in Tainan, and Kaohsiung areas were recruited. Teachers filled in SNAP-IV questionnaires according to their observations of inattention, hyperactivity/impulsivity in school. The students received computerized working memory batteries and standardized mathematical tests. Inattention and hyperactivity are both related to poor mathematical performance. Inattention is negatively related to working memory and mathematical performance. Working memory plays a mediated role between inattention and mathematical performance. Poor working memory could be a mediator between inattention which is a core of ADHD tendency and poor mathematical scores. Mathematical performance in children with ADHD might be improved by improving working memory. [ABSTRACT FROM AUTHOR]

We show that for pairs (Q, R) and (S, T) of disjoint subsets of vertices of a graph G, if G is sufficiently large, then there exists a vertex v in V (G) - (Q \cup R \cup S \cup T) such that there are two ways to reduce G by a vertex-minor operation that removes v while preserving the connectivity between Q and R and the connectivity between S and T. Our theorem implies an analogous theorem of Chen and Whittle (SIAM J. Discrete Math., 28 (2014), pp. 1402--1404) for matroids restricted to binary matroids. [ABSTRACT FROM AUTHOR]

We develop a formal construction of a pointwise divergence-free basis in the nonconforming virtual element method of arbitrary order for the Stokes problem introduced in Zhao et al. (SIAM J. Numer. Anal. 57(6):2730–2759, 2019). The proposed construction can be seen as a generalization of the divergence-free basis in Crouzeix-Raviart finite element space (Brenner, Math. Comp. 55(192):411–437, 1990; Thomasset, 1981) to the virtual element space. Using the divergence-free basis obtained from our construction, we can eliminate the pressure variable from the mixed system and obtain a symmetric positive definite system. Several numerical tests are presented to confirm the efficiency and the accuracy of our construction. [ABSTRACT FROM AUTHOR]

A new computational framework for evaluation of the gamma function Γ(z) over the complex plane is developed. The algorithm is based on interpolation by rational functions, and generalizes the classical methods of Lanczos (SIAM J. Numer. Anal. B 1:86–96, (1964) and Spouge (SIAM J. Numer. Anal., 31(3):931–944, (1994) (which we show are also interpolatory). This framework utilizes the exact poles of the gamma function. By relaxing this condition and allowing the poles to vary, a near-optimal rational approximation is possible, which is demonstrated using the adaptive Antoulous Anderson (AAA) algorithm, developed in Nakatsukasa et al. (Appl. Math. Comp., 40:1494-1522, (2016)) and Nakatsukasa and Trefethen (SIAM J. Sci. Comp., 42(5):A3157–A3179, (2020)). The resulting approximations are competitive with Stirling's formula in terms of overall efficiency. [ABSTRACT FROM AUTHOR]

A numerical semigroup S is cyclotomic if its semigroup polynomial P S is a product of cyclotomic polynomials. The number of irreducible factors of P S (with multiplicity) is the polynomial length ℓ (S) of S. We show that a cyclotomic numerical semigroup is complete intersection if ℓ (S) ≤ 2 . This establishes a particular case of a conjecture of Ciolan et al. (SIAM J Discrete Math 30(2):650–668, 2016) claiming that every cyclotomic numerical semigroup is complete intersection. In addition, we investigate the relation between ℓ (S) and the embedding dimension of S. [ABSTRACT FROM AUTHOR]

The crossing number of a graph G, denoted by cr(G), is defined as the smallest possible number of edge-crossings in a drawing of G in the plane. The cone CG, obtained from G by adding a new vertex adjacent to all the vertices in G. Let ϕ s (k) = min { c r (C G) - c r (G) } , where the minimum is taken over all the simple graphs G with crossing number k. Alfaro et al. (SIAM J Discrete Math, 32: 2080–2093, 2018) determined ϕ s (k) ≤ k for k ≥ 3 , and proved ϕ s (3) = 3 , ϕ s (4) = 4 and ϕ s (5) = 5 . In this work, we improve the upper bound for ϕ s (k) and our main result includes the following, slightly surprising, fact: ϕ s (6) = 5 and ϕ s (7) = 6 . [ABSTRACT FROM AUTHOR]

For the solution of large sparse unsymmetric systems, Duff et al. [SIAM J. Sci. Comput., 37 (2015), pp. A1248-A1269] proposed an approach based on the block Cimmino iterations [Numer. Math., 35 (1980), pp. 1-12], in which the solution is computed in a single iteration, so we call it a pseudodirect solver. In this approach, matrices are augmented with additional variables and constraints so that a partitioning of the matrix in blocks of rows defines mutually orthogonal subspaces. The augmented system can then be solved efficiently with a sum of projections onto these orthogonal subspaces. The purpose of this manuscript is to extend this method to the minimum norm solution of underdetermined systems and to the solution of least-squares problems. In the latter case, a partitioning of the matrix in blocks of columns rather than rows is used, and the system must be suitably augmented to define mutually orthogonal subspaces again to recover the least-squares solution of the original problem. This article proves the equivalence between the solution of the original and the augmented system. In order to complete the extension to overdetermined systems, we also propose an iterative block conjugate gradient acceleration [SIAM J. Sci. Comput., 16 (1995), pp. 1478-1511] for the solution of least-squares problems. The efficiency of both the iterative and the augmented pseudodirect approaches, as implemented in the ABCD-Solver, is illustrated on large rectangular matrices from the SuiteSparse Matrix Collection. [ABSTRACT FROM AUTHOR]