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]

In this paper, we adopt the augmented Lagrangian method (ALM) to solve convex quadratic second-order cone programming problems (SOCPs). Fruitful results on the efficiency of the ALM have been established in the literature. Recently, it has been shown in [Cui, Sun, and Toh, Math. Program., 178 (2019), pp. 381-415] that if the quadratic growth condition holds at an optimal solution for the dual problem, then the KKT residual converges to zero R-superlinearly when the ALM is applied to the primal problem. Moreover, Cui, Ding, and Zhao [SIAM J. 0ptim., 27 (2017), pp. 2332-2355] provided sufficient conditions for the quadratic growth condition to hold under the metric subregularity and bounded linear regularity conditions for solving composite matrix optimization problems involving spectral functions. Here, we adopt these recent ideas to analyze the convergence properties of the ALM when applied to SOCPs. To the best of our knowledge, no similar work has been done for SOCPs so far. In our paper, we first provide sufficient conditions to ensure the quadratic growth condition for SOCPs. With these elegant theoretical guarantees, we then design an SOCP solver and apply it to solve various classes of SOCPs, such as minimal enclosing ball problems, classical trust-region subproblems, square-root Lasso problems, and DIMACS Challenge problems. Numerical results show that the proposed ALM based solver is efficient and robust compared to the existing highly developed solvers, such as Mosek and SDPT3. [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]

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]

In this paper, through an intuitive vanil la proximal method perspective, we derive a concise unified acceleration framework (UAF) for minimizing a convex function that has H\"older continuous derivatives with respect to general (non-Euclidean) norms. The UAF reconciles two different high-order acceleration approaches, one by Nesterov [Math. Program., 112 (2008), pp. 159-181] and one by Monteiro and Svaiter [SIAM J. Optim., 23 (2013), pp. 1092-1125]. As a result, the UAF unifies the high-order acceleration instances of the two approaches by only two problem-related parameters and two additional parameters for framework design. Meanwhile, the UAF (and its analysis) is the first approach to make high-order methods applicable for high-order smoothness conditions with respect to non-Euclidean norms. Furthermore, the UAF is the first approach that can match the existing lower bound of iteration complexity for minimizing a convex function with H\"older continuous derivatives. For practical implementation, we introduce a new and effective heuristic that significantly simplifies the binary search procedure required by the framework. We use experiments on logistic regression to verify the effectiveness of the heuristic. Finally, the UAF is proposed directly in the general composite convex setting and shows that the existing high-order algorithms can be naturally extended to the general composite convex setting. [ABSTRACT FROM AUTHOR]

This paper provides a probabilistic proof of the comparison result for viscosity solutions of path-dependent semilinear PDEs. We consider the notion of viscosity solutions introduced in [I. Ekren, et al., Ann. Probab., 42 (2014), pp. 204-236], which considers as test functions all those smooth processes which are tangent in mean. When restricted to the Markovian case, this definition induces a larger set of test functions and reduces to the notion of stochastic viscosity solutions analyzed in [E. Bayraktar and M. Sirbu, Proc. Amer. Math. Soc., 140 (2012), pp. 3645-3654; SIAM J. Control Optim., 51 (2013), pp. 4274-4294]. Our main result takes advantage of this enlargement of the test functions and provides an easier proof of comparison. This is most remarkable in the context of the linear path-dependent heat equation. As a key ingredient for our methodology, we introduce a notion of punctual differentiation, similar to the corresponding concept in the standard viscosity solutions [L. A. Caffarelli and X. Cabre, Amer. Math. Soc. Colloq. Publ., 43, AMS, Providence, RI, 1995], and we prove that semimartingales are almost everywhere punctually differentiable. This smoothness result can be viewed as the counterpart of the Aleksandroff smoothness result for convex functions. A similar comparison result was established earlier in [I. Ekren et al., Ann. Probab., 42 (2014), pp. 204-236]. The result of this paper is more general and, more importantly, the arguments that we develop do not rely on any representation of the solution. [ABSTRACT FROM AUTHOR]

This paper provides a probabilistic proof of the comparison result for viscosity solutions of path-dependent semilinear PDEs. We consider the notion of viscosity solutions introduced in [I. Ekren, et al., Ann. Probab., 42 (2014), pp. 204-236], which considers as test functions all those smooth processes which are tangent in mean. When restricted to the Markovian case, this definition induces a larger set of test functions and reduces to the notion of stochastic viscosity solutions analyzed in [E. Bayraktar and M. Sirbu, Proc. Amer. Math. Soc., 140 (2012), pp. 3645-3654; SIAM J. Control Optim., 51 (2013), pp. 4274-4294]. Our main result takes advantage of this enlargement of the test functions and provides an easier proof of comparison. This is most remarkable in the context of the linear path-dependent heat equation. As a key ingredient for our methodology, we introduce a notion of punctual differentiation, similar to the corresponding concept in the standard viscosity solutions [L. A. Caffarelli and X. Cabre, Amer. Math. Soc. Colloq. Publ., 43, AMS, Providence, RI, 1995], and we prove that semimartingales are almost everywhere punctually differentiable. This smoothness result can be viewed as the counterpart of the Aleksandroff smoothness result for convex functions. A similar comparison result was established earlier in [I. Ekren et al., Ann. Probab., 42 (2014), pp. 204-236]. The result of this paper is more general and, more importantly, the arguments that we develop do not rely on any representation of the solution. [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]

We consider the inverse problem for the polynomial map that sends an m$m$‐tuple of quadratic forms in n$n$ variables to the sum of their d$d$th powers. This map captures the moment problem for mixtures ofm$m$centeredn$n$‐variate Gaussians. In the first nontrivial case d=3$d = 3$, we show that for any n∈N$ n\in {\mathbb {N}}$, this map is generically one‐to‐one (up to permutations of q1,...,qm$ q_1,\ldots , q_m$ and third roots of unity) in two ranges: m⩽n2+1$m\leqslant {n\atopwithdelims ()2} + 1$ for n<16$n <16$ and m⩽n+56/n+12−n+12−1$ m\leqslant {n+5 \atopwithdelims ()6}/{n+1 \atopwithdelims ()2}-{n+1 \atopwithdelims ()2}-1$ for n⩾16$n \geqslant 16$, thus proving generic identifiability for mixtures of centered Gaussians from their (exact) moments of degree at most 6$\hskip.001pt 6$. The first result is obtained by the explicit geometry of the tangential contact locus of the variety of sums of cubes of quadratic forms, as described by Chiantini and Ottaviani [SIAM J. Matrix Anal. Appl. 33 (2012), no. 3, 1018–1037], while the second result is accomplished using the link between secant nondefectivity with identifiability, proved by Casarotti and Mella [J. Eur. Math. Soc. (JEMS) (2022)]. The latter approach also generalizes to sums of d$ d$th powers of k$k$‐forms for d⩾3$d \geqslant 3$ and k⩾2$k \geqslant 2$. [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]

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]

For two graphs $F$ and $H$, the relative Turán number ${ex}(H,F)$ is the maximum number of edges in an $F$-free subgraph of $H$. Foucaud, Krivelevich, and Perarnau [SIAM J. Discrete Math., 29 (2015), pp. 65--78] and Perarnau and Reed [Combin. Probab. Comput., 26 (2017), pp. 448--467] studied these quantities as a function of the maximum degree of $H$. In this paper, we study a generalization for uniform hypergraphs. If $F$ is a complete $r$-partite $r$-uniform hypergraph with parts of sizes $s_1,s_2,\dots,s_r$ with each $s_{i + 1}$ sufficiently large relative to $s_i$, then with $1/\beta = \sum_{i = 2}^r \prod_{j = 1}^{i - 1} s_j$ we prove that for any $r$-uniform hypergraph $H$ with maximum degree $\Delta$, ${ex}(H,F)\ge \Delta^{-\beta - o(1)} \cdot e(H).$ This is tight as $\Delta \rightarrow \infty$ up to the $o(1)$ term in the exponent, since we show there exists a $\Delta$-regular $r$-graph $H$ such that ${ex}(H,F)=O(\Delta^{-\beta}) \cdot e(H)$. Similar tight results are obtained when $H$ is the random $n$-vertex $r$-graph $H_{n,p}^r$ with edge-probability $p$, extending results of Balogh and Samotij [J. Lond. Math. Soc., 83 (2011), pp. 1091--1094] and Morris and Saxton [Adv. Math., 298 (2016), pp. 534--580]. General lower bounds for a wider class of $F$ are also obtained. [ABSTRACT FROM AUTHOR]

We consider the Sasa–Satsuma (SS) and nonlinear Schrödinger (NLS) equations posed along the line, in 1 + 1 dimensions. Both equations are canonical integrable U(1) models, with solitons, multi-solitons and breather solutions Yang (2010 SIAM Mathematical Modeling and Computation). For these two equations, we recognize four distinct localized breather modes: the Sasa–Satsuma for SS, and for NLS the Satsuma–Yajima, Kuznetsov–Ma and Peregrine breathers. Very little is known about the stability of these solutions, mainly because of their complex structure, which does not fit into the classical soliton behavior Grillakis et al (1987 J. Funct. Anal. 74 160–97). In this paper we find the natural H2 variational characterization for each of them. This seems to be the first known variational characterization for these solutions; in particular, the first one obtained for the famous Peregrine breather. We also prove that Sasa–Satsuma breathers are H2 nonlinearly stable, improving the linear stability property previously proved by Pelinovsky and Yang (2005 Chaos 15 037115). Moreover, in the SS case, we provide an alternative understanding of the SS solution as a breather, and not only as an embedded soliton. The method of proof is based in the use of a H2 based Lyapunov functional, in the spirit of Alejo and Muńoz (2013 Commun. Math. Phys. 324 233–62), extended this time to the vector-valued case. We also provide another rigorous justification of the instability of the remaining three nonlinear modes (Satsuma–Yajima, Peregrine and Kuznetsov–Ma), based in the study of their corresponding linear variational structure (as critical points of a suitable Lyapunov functional), and complementing the instability results recently proved e.g. in Muńoz (2017 Proyecciones (Antofagasta) 36 653–83). [ABSTRACT FROM AUTHOR]

In this paper, we combine the S-iteration process introduced by Agarwal et al. (J. Nonlinear Convex Anal., 8(1), 61–79 2007) with the proximal point algorithm introduced by Rockafellar (SIAM J. Control Optim., 14, 877–898 1976) to propose a new modified proximal point algorithm based on the S-type iteration process for approximating a common element of the set of solutions of convex minimization problems and the set of fixed points of nearly asymptotically quasi-nonexpansive mappings in the framework of CAT(0) spaces and prove the △-convergence of the proposed algorithm for solving common minimization problem and common fixed point problem. Our result generalizes, extends and unifies the corresponding results of Dhompongsa and Panyanak (Comput. Math. Appl., 56, 2572–2579 2008), Khan and Abbas (Comput. Math. Appl., 61, 109–116 2011), Abbas et al. (Math. Comput. Modelling, 55, 1418–1427 2012) and many more. [ABSTRACT FROM AUTHOR]

In this paper, the author studies the local existence of strong solutions and their possible blow-up in time for a quasilinear system describing the interaction of a short wave induced by an electron field with a long wave representing an extension of the motion of the director field in a nematic liquid crystal's asymptotic model introduced in [Saxton, R. A., Dynamic instability of the liquid crystal director. In: Current Progress in Hyperbolic Systems (Lindquist, W. B., ed.), Contemp. Math., Vol.100, Amer. Math. Soc., Providence, RI, 1989, pp.325–330] and [Hunter, J. K. and Saxton, R. A., Dynamics of director fields, SIAM J. Appl. Math., 51, 1991, 1498–1521] and studied in [Hunter, J. K. and Zheng, Y., On a nonlinear hyperbolic variational equation I, Arch. Rat. Mech. Anal., 129, 1995, 305–353], [Hunter, J. K. and Zheng, Y., On a nonlinear hyperbolic variational equation II, Arch. Rat. Mech. Anal., 129, 1995, 355–383] and in [Zhang, P. and Zheng, Y., On oscillation of an asymptotic equation of a nonlinear variational wave equation, Asymptotic Anal., 18, 1998, 307–327] and, more recently, in [Bressan, A., Zhang, P. and Zheng, Y., Asymptotic variational wave equations, Arch. Rat. Mech. Anal., 183, 2007, 163–185]. [ABSTRACT FROM AUTHOR]

In this paper, we present two nonmonotone versions of adaptive cubic regularized (ARC) method for unconstrained optimization problems. The proposed methods are a combination of the ARC algorithm with the nonmonotone line search methods introduced by Zhang and Hager [A nonmonotone line search technique and its application to unconstrained optimization, SIAM J. Optim. 14 (2004), pp. 1043–1056] and Ahookhosh et al. [A nonmonotone trust-region line search method for large-scale unconstrained optimization, Appl. Math. Model. 36 (2012), pp. 478–487]. The global convergence analysis for these iterative algorithms is established under suitable conditions. Several numerical examples are given to illustrate the efficiency and robustness of the newly suggested methods. The obtained results show the satisfactory performance of the proposed algorithms when compared to the basic ARC algorithm. [ABSTRACT FROM AUTHOR]

This paper is devoted to the qualitative properties of discretized parabolic operators, such as nonnegativity and nonpositivity preservation, maximum/minimum principles and maximum norm contractivity. In the linear case, earlier papers of the authors (Faragó and Horváth in SIAM Sci Comput 28:2313–2336, 2006, IMA J Numer Anal 29:606–631, 2009) have established the connections between the above qualitative properties and have given sufficient conditions for their validity. The present paper extends the above results to nonlinear discretized parabolic operators, also motivated by the authors' recent paper (Faragó and Horváth in J Math Anal Appl 448:473–497, 2017), which has given related results on the continuous PDE level. A systematic study is presented, ranging from general discrete mesh operators to proper finite element applications. [ABSTRACT FROM AUTHOR]

For a graph G = (V,E), a hypergraph H is called a Berge-G if there is a bijection f : E(G) → E(H) such that e ⊆ f(e) for all e ∈ E(G). The family of Berge-G hypergraphs is denoted by B(G). The maximum number of edges in an n-vertex r-graph with no subhypergraph isomorphic to any Berge-G is denoted by exr(n, B (G)). Gyárfás [SIAM J. Discrete Math., 33 (2019), pp. 383-- 392] showed that for n ≥ 6, ex3(n, B (K4)) = [n/3] [n+1/3] [n+2/3]. However, we found an error in the proof of the result when n ≥ 7. A recent result due to Gerbner, Methuku, and Palmer [European J. Combin., 86 (2020), 103082] implies that for n ≥ 9, ex3(n, B (K4)) = [n/3] [n+1/3] [n+2/3]. In this paper we prove the remaining cases n = 7 and n = 8 for the completeness of the conclusion. [ABSTRACT FROM AUTHOR]

A graph is said to be open-neighborhood conflict-free k-colorable if there exists an assignment of k different colors to some of the vertices such that, for every vertex v, there is a color that is assigned to exactly one vertex among the neighbors of v. The open-neighborhood conflict-free chromatic number χO(G) is the smallest k for which G is open-neighborhood conflict-free k-colorable. Z. Abel et al., [SIAM J. Discrete Math. 32 (2018), pp. 2675--2702] showed that χ O(G) ≤ 8 for every planar graph G and posed two open problems to ask whether χO(G) \leq 4 for every planar graph G and whether χO(G) ≤ 3 for every outerplanar graph G. We present in this paper positive answers for the above two open problems by establishing a stronger result which states that, for every integer k ≥ 2, every minor-k-colorable graph is open-neighborhood conflict-free k-colorable, where a graph G is said to be minor-k-colorable if every minor of G is k-colorable. [ABSTRACT FROM AUTHOR]

This paper aims to provide a robust model for the well-known phenomenon of Kármán vortex street arising in fluid mechanics. The first theoretical attempt to model this pattern was given by von Kármán (1991 Göttinger Nachr., Math. Phys. Kl. 509–17); von Kármán (1912 Göttinger Nachr., Math. Phys. Kl. 547–56). He considered two parallel staggered rows of point vortices, with opposite strength, that translate at the same speed. Following the ideas of Saffman and Schatzman (1981 SIAM J. Sci. Stat. Comput. 2 285–95), we propose to study this phenomenon in the Euler equations by considering two infinite arrows of vortex patches. The key idea is to desingularize the point vortex model proposed by von Kármán. Our construction is flexible and can be extended to more general incompressible models. [ABSTRACT FROM AUTHOR]

This paper considers a system of two conservation laws with a Lipschitz continuous flow and deals with solutions to the Cauchy problems at a node. The system considered is the two-phase traffic model, proposed in [R. M. Colombo, F. Marcellini, and M. Rascle, SIAM J. Appl. Math., 70 (2010), pp. 2652--2666]. We are able to provide global in time existence of solutions at a node with a single incoming road and m outgoing roads. Neither assumptions on the smallness of the total variation of initial data are required, as usual in the case of systems, nor on the range of the initial data. [ABSTRACT FROM AUTHOR]

One important task in image segmentation is to find a region of interest, which is, in general, a solution of a nonlinear and nonconvex problem. The authors of Chan and Esedoglu (Aspects of total variation regularized L 1 function approximation. SIAM J. Appl. Math. 2005;65:1817–1837) proposed a convex T V − L 1 problem for finding such a region Σ and proved that when a binary input f is given, a solution u ∗ to the convex problem gives rise to other solutions 1 { u ∗ ≥ μ } for a.e. μ ∈ (0 , 1) from which they raised a question of whether or not u ∗ must be binary. The same is to ask if the two-phase Mumford–Shah model in image processing has a unique solution with a binary input. In this paper, we will discuss how to construct a non-binary solution that provides a negative answer to the question through a connection of two ideas, one from the two-phase Mumford–Shah model in image segmentation and the other from mean curvature motions discussed in some geometric problems (e.g. Alter, Caselles, Chambolle. A characterization of convex calibrable sets in R N . Math. Ann. 2005;322:329–366; Chambolle. An algorithm for mean curvature motion. Interfaces Free Boundaries 2004;6:195–218) revealing the nature of non-uniqueness in image segmentation. [ABSTRACT FROM AUTHOR]

An implicit-explicit multistep method based on the backward difference formulae (BDF) is proposed for time discretization of parabolic equations with a non-self-adjoint operator. Implicit and explicit schemes are used for the self-adjoint and anti-self-adjoint parts of the operator, respectively. For a k-step method, some correction terms are added to the starting k - 1 steps to maintain kth-order convergence without imposing further compatibility conditions at the initial time. Long-time kth-order convergence for the numerical method is proved under the assumptions that the operator is coercive and that the non-self-adjoint part is low order. Such an operator often appears in practical computation (such as the Stokes--Darcy system) but may violate the standard sectorial angle condition used in the literature for analysis of BDF. In particular, the proposed method and analysis in this paper extend the long-time energy error analysis of the Stokes--Darcy system in Chen et al. [SIAM J. Numer. Anal., 51 (2013), pp. 2563--2584; Numer. Math., 134 (2016), pp. 857--879] to general symmetrized and decoupled BDF methods up to order 6 by using the generating function technique. [ABSTRACT FROM AUTHOR]

Most undergraduates have limited experience with mathematical modeling. In an effort to respond to various initiatives, such as the recommendations outlined in [S. Garfunkel and M. Montgomery, eds., GAIMME: Guidelines for Assessment & Instruction in Mathematical Modeling Education, SIAM, 2016], this paper describes a course on the mathematical models of cancer growth and treatment. Among its aims is to provide a template for a "bridge" course between the traditional calculus and differential equations sequence and more advanced courses in mathematics and statistics. Prerequisites include a course in ordinary differential equations. Linear algebra is a useful corequisite but no previous programming experience is required. The content includes classical models of tumor growth as well as models for the growth of specific cancer types. Relevant research articles are provided for further study. Material for student projects and effective communication is supplied, as well as suggestions for homework assignments and computer labs. This paper aims to assist instructors in developing their own "Mathematics + Cancer" course. [ABSTRACT FROM AUTHOR]

A cut varepsilon-sparsifier of a weighted graph G is a reweighted subgraph of G of (quasi)linear size that preserves the size of all cuts up to a multiplicative factor of varepsilon. Since their introduction by Benczur and Karger [Approximating s-t minimum cuts in O~ (n2) time, in Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (STOC96), 1996, pp. 47-55], cut sparsifiers have proved extremely influential and found various applications. Going beyond cut sparsifiers, Filtser and Krauthgamer [SIAM J. Discrete Math., 31 (2017), pp. 1263--1276] gave a precise classification of which binary Boolean CSPs are sparsifiable. In this paper, we extend their result to binary CSPs on arbitrary finite domains. [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]

A queue layout of a graph consists of a linear order of its vertices and a partition of its edges into queues, so that no two independent edges of the same queue are nested. The queue number of a graph is the minimum number of queues required by any of its queue layouts. A long-standing conjecture by Heath, Leighton and Rosenberg [SIAM J. Discrete Math., 5 (1992), pp. 398--412] states that the queue number of planar graphs is bounded. This conjecture has been partially settled in the positive for several subfamilies of planar graphs (most of which have bounded treewidth). In this paper, we make a further important step towards settling this conjecture. We prove that planar graphs of bounded degree (which may have unbounded treewidth) have bounded queue number. A notable implication of this result is that every planar graph of bounded degree admits a three-dimensional straight-line grid drawing in linear volume. Further implications are that every planar graph of bounded degree has bounded track number, and that every k-planar graph (i.e., every graph that can be drawn in the plane with at most k crossings per edge) of bounded degree has bounded queue number. [ABSTRACT FROM AUTHOR]

A graph G is called (2,k)‐connected if G is 2k‐edge‐connected and G−v is k‐edge‐connected for every vertex v. The study of (2,2)‐connected graphs is motivated by a theorem of Thomassen [J. Combin. Theory Ser. A 110 (2015), pp. 67–78] (that was a conjecture of Frank [SIAM J. Discrete Math. 5 (1992), no. 1, pp. 25–53]), which states that a graph has a 2‐vertex‐connected orientation if and only if it is (2,2)‐connected. In this paper, we provide a construction of the family of (2,k)‐connected graphs for k even, which generalizes the construction given by Jordán [J. Graph Theory 52 (2006), pp. 217–229] for (2,2)‐connected graphs. We also solve the corresponding connectivity augmentation problem: given a graph G and an integer k≥2, what is the minimum number of edges to be added to make G(2,k)‐connected. Both these results are based on a new splitting‐off theorem for (2,k)‐connected graphs. [ABSTRACT FROM AUTHOR]

Targeted environmental and ecosystem management remain crucial in control of dengue. However, providing detailed environmental information on a large scale to effectively target dengue control efforts remains a challenge. An important piece of such information is the extent of the presence of potential dengue vector breeding sites, which consist primarily of open containers such as ceramic jars, buckets, old tires, and flowerpots. In this paper we present the design and implementation of a pipeline to detect outdoor open containers which constitute potential dengue vector breeding sites from geotagged images and to create highly detailed container density maps at unprecedented scale. We implement the approach using Google Street View images which have the advantage of broad coverage and of often being two to three years old which allows correlation analyses of container counts against historical data from manual surveys. Containers comprising eight of the most common breeding sites are detected in the images using convolutional neural network transfer learning. Over a test set of images the object recognition algorithm has an accuracy of 0.91 in terms of F-score. Container density counts are generated and displayed on a decision support dashboard. Analyses of the approach are carried out over three provinces in Thailand. The container counts obtained agree well with container counts from available manual surveys. Multi-variate linear regression relating densities of the eight container types to larval survey data shows good prediction of larval index values with an R-squared of 0.674. To delineate conditions under which the container density counts are indicative of larval counts, a number of factors affecting correlation with larval survey data are analyzed. We conclude that creation of container density maps from geotagged images is a promising approach to providing detailed risk maps at large scale. [ABSTRACT FROM AUTHOR]

A variety of powerful extremal results have been shown for the chromatic number of triangle-free graphs. Three noteworthy bounds are in terms of the number of vertices, edges, and maximum degree given by Poljak and Tuza [SIAM J. Discrete Math., 7 (1994), pp. 307--313] and Johansson. There have been comparatively fewer works extending these types of bounds to graphs with a small number of triangles. One noteworthy exception is a result of Alon, Krivelevich, and Sudakov [J. Combin. Theory Ser. B, 77 (1999), pp. 73--82] bounding the chromatic number for graphs with low degree and few triangles per vertex; this bound is nearly the same as for triangle-free graphs. This type of parametrization is much less rigid and has appeared in dozens of combinatorial constructions. In this paper, we show a similar type of result for X (G) as a function of the number of vertices n, the number of edges m, as well as the triangle count (both local and global measures). Our results smoothly interpolate between the generic bounds true for all graphs and bounds for triangle-free graphs. Our results are tight for most of these cases; we show how an open problem regarding fractional chromatic number and degeneracy in triangle-free graphs can resolve the small remaining gap in our bounds. [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]

M. A. Henning and A. Yeo conjectured in [SIAM J. Discrete Math., 26 (2012), pp. 687{694] that a bipartite digraph of minimum out-degree at least 3 contains two vertex disjoint directed cycles of different lengths. In this paper, we disprove this conjecture. Further, we classify strong tournaments and strong bipartite tournaments of minimum out-degree 3 without two vertex disjoint directed cycles of different lengths. [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]

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]

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]

We extend the Mobile Server problem introduced in Feldkord and Meyer auf der Heide (TOPC 6(3), 14:1–14:17 2019) to a model where k identical mobile resources, here named servers, answer requests appearing at points in the Euclidean space. To reduce communication costs, the positions of the servers can be adapted by a limited distance ms per round for each server. The costs are measured similarly to the classical Page Migration problem: i.e., answering a request induces costs proportional to the distance to the nearest server, and moving a server induces costs proportional to the distance multiplied with a weight D. We show that, in our model, no online algorithm can have a constant competitive ratio: i.e., one which is independent of the input length n, even if an augmented moving distance of (1 + δ)ms is allowed for the online algorithm. Therefore we investigate a restriction of the power of the adversary dictating the sequence of requests: We demand locality of requests: i.e., that consecutive requests come from points in the Euclidean space with distance bounded by some constant mc. We show constant lower bounds on the competitiveness in this setting (independent of n, but dependent on k, ms and mc). On the positive side, we present a deterministic online algorithm with bounded competitiveness when an augmented moving distance and locality of requests is assumed. Our algorithm simulates any given algorithm for the classical k-Page Migration problem as guidance for its servers and extends it by a greedy move of one server in every round. The resulting competitive ratio is polynomial in the number of servers k, the ratio between mc and ms, the inverse of the augmentation factor 1/δ and the competitive ratio of the simulated k-Page Migration algorithm. We also show how to directly adapt the Double Coverage algorithm (Chrobak et al. SIAM J. Discrete Math. 4(2), 172–181 11) for the k-Server problem to receive an algorithm with improved competitiveness on the line. [ABSTRACT FROM AUTHOR]

Gulisashvili et al. [Quant. Finance, 2018, 18(10), 1753–1765] provide short term asymptotics for the mass at zero under the uncorrelated stochastic-alpha-beta-rho (SABR) model by approximating the integrated variance with a moment-matched lognormal distribution. We improve the accuracy of the numerical integration by using Gauss–Hermite quadrature. We further obtain the option price by similarly integrating the constant elasticity of variance (CEV) option prices without resorting to the small-strike volatility smile asymptotics of De Marco et al. [SIAM J. Financ. Math., 2017, 8(1), 709–737]. For the uncorrelated SABR model, the new option pricing method is accurate and arbitrage-free across all strike prices. [ABSTRACT FROM AUTHOR]

We present a deterministic (1+o(1))-approximation O(n1/2+o(1) + D1+o(1))-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the CONGEST model); here n is the number of nodes in the network and D is its (hop) diameter. This is the first non-trivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized (1+o(1))-approximation Õ(√n1/2D1/4+D)-time algorithm of Nanongkai [STOC 2014] by a factor of as large as n1/8, and (ii) the O(є-1logє-1)-approximation factor of Lenzen and Patt-Shamir's Õ(n1/2+є+D)-time algorithm [STOC 2013, pp. 381-390] within the same running time. (Throughout, we use Õ(.) to hide polylogarithmic factors in n.) Our running time matches the known time lower bound of Ω(√n/log n + D) [M. Elkin, SIAM J. Comput., 36 (2006), pp. 433-456], thus essentially settling the status of this problem which was raised at least a decade ago [M. Elkin, SIGACT News, 35 (2004), pp. 40-57]. It also implies a (2+o(1))-approximation O(n1/2+o(1)+D1+o(1))-time algorithm for approximating a network's weighted diameter which almost matches the lower bound by Holzer and Pinsker [in Proceedings of OPODIS, 2015, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2016, 6]. In achieving this result, we develop two techniques which might be of independent interest and useful in other settings: (i) a deterministic process that replaces the "hitting set argument" commonly used for shortest paths computation in various settings, and (ii) a simple, deterministic construction of an (no(1), o(1))-hop set of size n1+o(1). We combine these techniques with many distributed algorithmic techniques, some of which are from problems that are not directly related to shortest paths, e.g., ruling sets [A. V. Goldberg, S. A. Plotkin, and G. E. Shannon, SIAM J. Discrete Math., 1 (1988), pp. 434-446], source detection [C. Lenzen and D. Peleg, in Proceedings of PODC, 2013, pp. 375-382], and partial distance estimation [C. Lenzen and B. Patt-Shamir, in Proceedings of PODC, 2015, pp. 153-162]. Our hop set construction also leads to single-source shortest paths algorithms in two other settings: (i) a (1+o(1))-approximation no(1)-time algorithm on congested cliques, and (ii) a (1+o(1))-approximation no(1)-pass n1+o(1)-space streaming algorithm. The first result answers an open problem in [D. Nanongkai, in Proceedings of STOC, 2014, pp. 565-573]. The second result partially answers an open problem raised by McGregor in 2006 [List of Open Problems in Sublinear Algorithms: Problem 14]. [ABSTRACT FROM AUTHOR]

The separation dimension of a graph G is the minimum positive integer d for which there is an embedding of G into ℝd, such that every pair of disjoint edges are separated by some axis-parallel hyperplane. We prove a conjecture of Alon et al. [SIAM J. Discrete Math. 2015] by showing that every graph with maximum degree Δ has separation dimension less than 20Δ, which is best possible up to a constant factor. We also prove that graphs with separation dimension 3 have bounded average degree and bounded chromatic number, partially resolving an open problem by Alon et al. [J. Graph Theory 2018]. [ABSTRACT FROM AUTHOR]

Recently it was shown that, if the subtree and chain reduction rules have been applied exhaustively to two unrooted phylogenetic trees, the reduced trees will have at most 15 k - 9 taxa where k is the TBR (Tree Bisection and Reconnection) distance between the two trees, and that this bound is tight. Here, we propose five new reduction rules and show that these further reduce the bound to 11 k - 9 . The new rules combine the "unrooted generator" approach introduced in Kelk and Linz (SIAM J Discrete Math 33(3):1556–1574, 2019) with a careful analysis of agreement forests to identify (i) situations when chains of length 3 can be further shortened without reducing the TBR distance, and (ii) situations when small subtrees can be identified whose deletion is guaranteed to reduce the TBR distance by 1. To the best of our knowledge these are the first reduction rules that strictly enhance the reductive power of the subtree and chain reduction rules. [ABSTRACT FROM AUTHOR]

We study Leja sequences on the unit disc and resulting mapped sequences to conventional domain, ellipses and real intervals, for the problem of relaxation of Richardson iteration. Using simple considerations, we establish upper and lower estimates for the growth of associated Newton polynomials and the so-called residual polynomials. These results broaden the understanding of such sequences and add to results established in Calvetti et al. (Numer. Math. 67(1), 21–40, 1994), Calvetti and Reichel (Numerical Algorithms 11(1-4), 79–98, 1996; J. Comput. Appl. Math. 71(2), 267–286 1996), Fischer and Reichel (Numer. Math. 54(2), 225–242, 1989), Nachtigal et al. (SIAM Journal on Matrix Analysis and Applications 13(3), 796–825, 1992), Reichel (SIAM J. Numer. Anal. 25(6), 1359–1368, 1988), Tal-Ezer (J. Sci. Comput. 4(1), 25–60, 1989). We also propose adaptive strategies for the selection of relaxation parameters that build on fast strategies (Balgama et al., Electron. Trans. Numer. Anal. 7, 124–140, 1998; Reichel, Linear Algebra and its Applications 154-156(C), 389–414, 1991) which are known to be suitable for the problem. In particular a Leja ordering is enforced on the mapped sequences. New strategies for conveniently confining the spectrums of certain matrices arising in PDEs discretization is described and demonstrate the flexibility of the Richardson iteration. [ABSTRACT FROM AUTHOR]

It can be shown that the stress produced by a spatially uniform dislocation density field in a body comprising a linear elastic material under no loads vanishes. We prove that the same result does not hold in general in the geometrically nonlinear case. This problem of mechanics establishes the purely geometrical result that the curl of a sufficiently smooth two-dimensional rotation field cannot be a non-vanishing constant on a domain. It is classically known in continuum mechanics, stated first by the brothers Cosserat (SIAM J. Appl. Math. 25(3):483–491, 1973), that if a second order tensor field on a simply connected domain is at most a curl-free field of rotations, then the field is necessarily constant on the domain. It is shown here that, at least in dimension 2, this classical result is in fact a special case of a more general situation where the curl of the given rotation field is only known to be at most a constant. [ABSTRACT FROM AUTHOR]

The purpose of this note is to correct the statement of Theorem 1.1 in [J. A. Barceló et al., SIAM J. Appl. Math., 78 (2018), pp. 2714--2736] which consider any dimension d ≥ 2, since the proof given fails in dimension d = 2. The gap in the proof is in Lemma 2.5 of [J. A. Barceló et al., SIAM J. Appl. Math., 78 (2018), pp. 2714--2736] where an estimate for the resolvent of the Laplace operator (Δ + k²)-1 in Rd is stated for k small and any dimension d ≥ 2. However, this estimate is only true for d ≥ 3. [ABSTRACT FROM AUTHOR]

For the past decade, researchers have documented the effects of textbooks on achievement in developing countries, but no research has explored the mechanisms that account for this contribution. This paper analyzes longitudinal data from a national sample of eighth- grade mathematics classrooms in Thailand and explores the effects of textbooks and other factors on student achievement gain. The results indicate that textbooks may affect achievement by substituting for additional postsecondary mathematics education of teachers and by delivering a more comprehensive curriculum. [ABSTRACT FROM AUTHOR]

We show that the expected size of the maximum agreement subtree of two n-leaf trees, uniformly random among all trees with the shape, is\Theta (\surd n). To derive the lower bound, we prove a global structural result on a decomposition of rooted binary trees into subgroups of leaves called blobs. To obtain the upper bound, we generalize a first moment argument from [D. I. Bernstein, et al., SIAM J. Discrete Math., 29 (2015), pp. 2065--2074] for random tree distributions that are exchangeable and not necessarily sampling consistent. [ABSTRACT FROM AUTHOR]