Search

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]

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]

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]

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]

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]

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]

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]

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 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]

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]

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]

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]

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]

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]

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 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]

This note is an erratum for the paper On the Inequalities of Projected Volumes and the Constructible Region [SIAM J. Discrete Math., 33 (2019), pp. 694--711]. There is a mistake in the proof of Theorem 4 in Section 3. However, Theorem 4 is itself correct (a proof can be found in [Inequalities on Projected Volumes, arxiv.org/abs/1909.12858, 2019] by Leader, Randelovic, and Raty), and all the other results of the paper stand. [ABSTRACT FROM AUTHOR]