Genus polynomials and crosscap‐number polynomials for ring‐like graphs

An H‐linear graph is obtained by transforming a collection of copies of a fixed graph H into a chain. An H‐ring‐like graph is formed by binding the two end‐copies of H in such a chain to each other. Genus polynomials have been calculated for bindings of several kinds. In this paper, we substantially generalize the rules for constructing sequences of H‐ring‐like graphs from sequences of H‐linear graphs, and we give a general method for obtaining a recursion for the genus polynomials of the graphs in a sequence of ring‐like graphs. We use Chebyshev polynomials to obtain explicit formulas for the genus polynomials of several such sequences. We also give methods for obtaining recursions for partial genus polynomials and for crosscap‐number polynomials of a bar‐ring of a sequence of disjoint graphs.     

Regular path decompositions of odd regular graphs

Kotzig asked in 1979 what are necessary and sufficient conditions for a d‐regular simple graph to admit a decomposition into paths of length d for odd d>3. For cubic graphs, the existence of a 1‐factor is both necessary and sufficient. Even more, each 1‐factor is extendable to a decomposition of the graph into paths of length 3 where the middle edges of the paths coincide with the 1‐factor. We conjecture that existence of a 1‐factor is indeed a sufficient condition for Kotzig's problem. For general odd regular graphs, most 1‐factors appear to be extendable and we show that for the family of simple 5‐regular graphs with no cycles of length 4, all 1‐factors are extendable. However, for d>3 we found infinite families of d‐regular simple graphs with non‐extendable 1‐factors. Few authors have studied the decompositions of general regular graphs. We present examples and open problems; in particular, we conjecture that in planar 5‐regular graphs all 1‐factors are extendable. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 114–128, 2010     

A semidefinite program approach for computing the maximum eigenvalue of a class of structured tensors and its applications in hypergraphs and copositivity test

Finding the maximum eigenvalue of a symmetric tensor is an important topic in tensor computation and numerical multilinear algebra. In this paper, we introduce a new class of structured tensors called W‐tensors, which not only extends the well‐studied nonnegative tensors by allowing negative entries but also covers several important tensors arising naturally from spectral hypergraph theory. We then show that finding the maximum H‐eigenvalue of an even‐order symmetric W‐tensor is equivalent to solving a structured semidefinite program and hence can be validated in polynomial time. This yields a highly efficient semidefinite program algorithm for computing the maximum H‐eigenvalue of W‐tensors and is based on a new structured sums‐of‐squares decomposition result for a nonnegative polynomial induced by W‐tensors. Numerical experiments illustrate that the proposed algorithm can successfully find the maximum H‐eigenvalue of W‐tensors with dimension up to 10,000, subject to machine precision. As applications, we provide a polynomial time algorithm for computing the maximum H‐eigenvalues of large‐size Laplacian tensors of hyperstars and hypertrees, where the algorithm can be up to 13 times faster than the state‐of‐the‐art numerical method introduced by Ng, Qi, and Zhou in 2009. Finally, we also show that the proposed algorithm can be used to test the copositivity of a multivariate form associated with symmetric extended Z‐tensors, whose order may be even or odd.     

Non‐well‐founded extensions of \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathbf {V}$\end{document}

This paper describes a new and user‐friendly method for constructing models of non‐well‐founded set theory. Given a sufficiently well‐behaved system θ of non‐well‐founded set‐theoretic equations, we describe how to construct a model M_θ for $\mathsf {ZFC}^-$ in which θ has a non‐degenerate solution. We shall prove that this M_θ is the smallest model for $\mathsf {ZFC}^-$ which contains $\mathbf {V}$ and has a non‐degenerate solution of θ.     

A lower‐epiperimetric inequality for area‐minimizing surfaces

The epiperimetric inequality introduced by E. R. Reifenberg in [3] gives a rate of decay at a point for the decreasing k‐density of area of an area‐minimizing integral k‐cycle. While dilating the cycle at that point, this rate of decay holds once the configuration is close to a tangent cone configuration and above the limiting density corresponding to that configuration. This is why we propose to call the Reifenberg epiperimetric inequality an upper‐epiperimetric inequality. A direct consequence of this upper‐epiperimetric inequality is the statement that any point possesses a unique tangent cone. The upper‐epiperimetric inequality was proven by B. White in [5] for area‐minimizing 2‐cycles in ?ⁿ. In the present paper we introduce the notion of a lower‐epiperimetric inequality. This inequality gives this time a rate of decay for the decreasing k‐density of area of an area‐minimizing integral k‐cycle, while dilating the cycle at a point once the configuration is close to a tangent cone configuration and below the limiting density corresponding to that configuration. Our main result in the present paper is to prove the lower‐epiperimetric inequality for area‐minimizing 2‐cycles in ?ⁿ. As a consequence of this inequality we prove the “splitting before tilting” phenomenon for calibrated 2‐rectifiable cycles, which plays a crucial role in the proof of the regularity of 1‐1 integral currents in [4]. © 2004 Wiley Periodicals, Inc.     

Finding a subdivision of a prescribed digraph of order 4

The problem of when a given digraph contains a subdivision of a fixed digraph F is considered. Bang‐Jensen et al. [4] laid out foundations for approaching this problem from the algorithmic point of view. In this article, we give further support to several open conjectures and speculations about algorithmic complexity of finding F‐subdivisions. In particular, up to five exceptions, we completely classify for which 4‐vertex digraphs F, the F‐subdivision problem is polynomial‐time solvable and for which it is NP‐complete. While all NP‐hardness proofs are made by reduction from some version of the 2‐linkage problem in digraphs, some of the polynomial‐time solvable cases involve relatively complicated algorithms.     

Even and odd holes in cap‐free graphs

It is an old problem in graph theory to test whether a graph contains a chordless cycle of length greater than three (hole) with a specific parity (even, odd). Studying the structure of graphs without odd holes has obvious implications for Berge's strong perfect graph conjecture that states that a graph G is perfect if and only if neither G nor its complement contain an odd hole. Markossian, Gasparian, and Reed have proven that if neither G nor its complement contain an even hole, then G is β‐perfect. In this article, we extend the problem of testing whether G(V, E) contains a hole of a given parity to the case where each edge of G has a label odd or even. A subset of E is odd (resp. even) if it contains an odd (resp. even) number of odd edges. Graphs for which there exists a signing (i.e., a partition of E into odd and even edges) that makes every triangle odd and every hole even are called even‐signable. Graphs that can be signed so that every triangle is odd and every triangle is odd and every hole is odd are called odd‐signable. We derive from a theorem due to Truemper co‐NP characterizations of even‐signable and odd‐signable graphs. A graph is strongly even‐signable if it can be signed so that every cycle of length ≥ 4 with at most one chord is even and every triangle is odd. Clearly a strongly even‐signable graph is even‐signable as well. Graphs that can be signed so that cycles of length four with one chord are even and all other cycles with at most one chord are odd are called strongly odd‐signable. Every strongly odd‐signable graph is odd‐signable. We give co‐NP characterizations for both strongly even‐signable and strongly odd‐signable graphs. A cap is a hole together with a node, which is adjacent to exactly two adjacent nodes on the hole. We derive a decomposition theorem for graphs that contain no cap as induced subgraph (cap‐free graphs). Our theorem is analogous to the decomposition theorem of Burlet and Fonlupt for Meyniel graphs, a well‐studied subclass of cap‐free graphs. If a graph is strongly even‐signable or strongly odd‐signable, then it is cap‐free. In fact, strongly even‐signable graphs are those cap‐free graphs that are even‐signable. From our decomposition theorem, we derive decomposition results for strongly odd‐signable and strongly even‐signable graphs. These results lead to polynomial recognition algorithms for testing whether a graph belongs to one of these classes. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 289–308, 1999     

Minimality conditions on circularly ordered structures

We explore analogues of o‐minimality and weak o‐minimality for circularly ordered sets. Much of the theory goes through almost unchanged, since over a parameter the circular order yields a definable linear order. Working over ?? there are differences. Our main result is a structure theory (with infinitely many doubly transitive examples related to Jordan permutation groups) for ?₀‐categorical weakly circularly minimal structures. There is a 5‐homogeneous (or ‘5‐indiscernible’) example which is not 6‐homogeneous, but any example which is k‐homogeneous for some k ≥ 6 is k‐homogeneous for all k. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Is constraint satisfaction over two variables always easy?

By the breakthrough work of Håstad [J ACM 48(4) (2001), 798–859], several constraint satisfaction problems are now known to have the following approximation resistance property: Satisfying more clauses than what picking a random assignment would achieve is NP‐hard. This is the case for example for Max E3‐Sat, Max E3‐Lin, and Max E4‐Set Splitting. A notable exception to this extreme hardness is constraint satisfaction over two variables (2‐CSP); as a corollary of the celebrated Goemans‐Williamson algorithm [J ACM 42(6) (1995), 1115–1145], we know that every Boolean 2‐CSP has a nontrivial approximation algorithm whose performance ratio is better than that obtained by picking a random assignment to the variables. An intriguing question then is whether this is also the case for 2‐CSPs over larger, non‐Boolean domains. This question is still open, and is equivalent to whether the generalization of Max 2‐SAT to domains of size d, can be approximated to a factor better than (1 ? 1/d²). In an attempt to make progress towards this question, in this paper we prove, first, that a slight restriction of this problem, namely, a generalization of linear inequations with two variables per constraint, is not approximation resistant, and, second, that the Not‐All‐Equal Sat problem over domain size d with three variables per constraint, is approximation resistant, for every d ≥ 3. In the Boolean case, Not‐All‐Equal Sat with three variables per constraint is equivalent to Max 2‐SAT and thus has a nontrivial approximation algorithm; for larger domain sizes, Max 2‐SAT can be reduced to Not‐All‐Equal Sat with three variables per constraint. Our approximation algorithm implies that a wide class of 2‐CSPs called regular 2‐CSPs can all be approximated beyond their random assignment threshold. © 2004 Wiley Periodicals, Inc. Random Struct. Alg. 2004     

On evolutionary equations with material laws containing fractional integrals

A well‐posedness result for a time‐shift invariant class of evolutionary operator equations involving material laws with fractional time‐integrals of order α ? ]0, 1[ is considered. The fractional derivatives are defined via a function calculus for the (time‐)derivative established as a normal operator in a suitable L² type space. Employing causality, we show that the fractional derivatives thus obtained coincide with the Riemann‐Liouville fractional derivative. We exemplify our results by applications to a fractional Fokker‐Planck equation, equations describing super‐diffusion and sub‐diffusion processes, and a Kelvin‐Voigt type model in fractional visco‐elasticity. Moreover, we elaborate a suitable perspective to deal with initial boundary value problems. Copyright © 2014 John Wiley & Sons, Ltd.     

The structure of 4‐strong tournaments containing exactly three out‐arc pancyclic vertices

Yao et al. (Discrete Appl Math 99 (2000), 245–249) proved that every strong tournament contains a vertex u such that every out‐arc of u is pancyclic and conjectured that every k‐strong tournament contains k such vertices. At present, it is known that this conjecture is true for k = 1, 2, 3 and not true for k?4. In this article, we obtain a sufficient and necessary condition for a 4‐strong tournament to contain exactly three out‐arc pancyclic vertices, which shows that a 4‐strong tournament contains at least four out‐arc pancyclic vertices except for a given class of tournaments. Furthermore, our proof yields a polynomial algorithm to decide if a 4‐strong tournament has exactly three out‐arc pancyclic vertices.     

Two‐level Fourier analysis of multigrid for higher‐order finite‐element discretizations of the Laplacian

In this paper, we employ local Fourier analysis (LFA) to analyze the convergence properties of multigrid methods for higher‐order finite‐element approximations to the Laplacian problem. We find that the classical LFA smoothing factor, where the coarse‐grid correction is assumed to be an ideal operator that annihilates the low‐frequency error components and leaves the high‐frequency components unchanged, fails to accurately predict the observed multigrid performance and, consequently, cannot be a reliable analysis tool to give good performance estimates of the two‐grid convergence factor. While two‐grid LFA still offers a reliable prediction, it leads to more complex symbols that are cumbersome to use to optimize parameters of the relaxation scheme, as is often needed for complex problems. For the purposes of this analytical optimization as well as to have simple predictive analysis, we propose a modification that is “between” two‐grid LFA and smoothing analysis, which yields reasonable predictions to help choose correct damping parameters for relaxation. This exploration may help us better understand multigrid performance for higher‐order finite element discretizations, including for Q₂‐Q₁ (Taylor‐Hood) elements for the Stokes equations. Finally, we present two‐grid and multigrid experiments, where the corrected parameter choice is shown to yield significant improvements in the resulting two‐grid and multigrid convergence factors.     

Some limit analysis of a three dimensional viscous compressible capillary model for plasma

In this study, we discuss some limit analysis of a viscous capillary model of plasma, which is expressed as a so‐called the compressible Navier‐Stokes‐Poisson‐Korteweg equation. First, the existence of global smooth solutions for the initial value problem to the compressible Navier‐Stokes‐Poisson‐Korteweg equation with a given Debye length λ and a given capillary coefficient κ is obtained. We also show the uniform estimates of global smooth solutions with respect to the Debye length λ and the capillary coefficient κ. Then, from Aubin lemma, we show that the unique smooth solution of the 3‐dimensional Navier‐Stokes‐Poisson‐Korteweg equations converges globally in time to the strong solution of the corresponding limit equations, as λ tends to zero, κ tends to zero, and λ and κ simultaneously tend to zero. Moreover, we also give the convergence rates of these limits for any given positive time one by one.     

Analytical and numerical solutions of a two‐dimensional multi‐term time‐fractional Oldroyd‐B model

In this paper, we consider a two‐dimensional multi‐term time‐fractional Oldroyd‐B equation on a rectangular domain. Its analytical solution is obtained by the method of separation of variables. We employ the finite difference method with a discretization of the Caputo time‐fractional derivative to obtain an implicit difference approximation for the equation. Stability and convergence of the approximation scheme are established in the L_∞ ‐norm. Two examples are given to illustrate the theoretical analysis and analytical solution. The results indicate that the present numerical method is effective for this general two‐dimensional multi‐term time‐fractional Oldroyd‐B model.     

Comparison of multigrid algorithms for high‐order continuous finite element discretizations

We present a comparison of different multigrid approaches for the solution of systems arising from high‐order continuous finite element discretizations of elliptic partial differential equations on complex geometries. We consider the pointwise Jacobi, the Chebyshev‐accelerated Jacobi, and the symmetric successive over‐relaxation smoothers, as well as elementwise block Jacobi smoothing. Three approaches for the multigrid hierarchy are compared: (1) high‐order h‐multigrid, which uses high‐order interpolation and restriction between geometrically coarsened meshes; (2) p‐multigrid, in which the polynomial order is reduced while the mesh remains unchanged, and the interpolation and restriction incorporate the different‐order basis functions; and (3) a first‐order approximation multigrid preconditioner constructed using the nodes of the high‐order discretization. This latter approach is often combined with algebraic multigrid for the low‐order operator and is attractive for high‐order discretizations on unstructured meshes, where geometric coarsening is difficult. Based on a simple performance model, we compare the computational cost of the different approaches. Using scalar test problems in two and three dimensions with constant and varying coefficients, we compare the performance of the different multigrid approaches for polynomial orders up to 16. Overall, both h‐multigrid and p‐multigrid work well; the first‐order approximation is less efficient. For constant coefficients, all smoothers work well. For variable coefficients, Chebyshev and symmetric successive over‐relaxation smoothing outperform Jacobi smoothing. While all of the tested methods converge in a mesh‐independent number of iterations, none of them behaves completely independent of the polynomial order. When multigrid is used as a preconditioner in a Krylov method, the iteration number decreases significantly compared with using multigrid as a solver. Copyright © 2015 John Wiley & Sons, Ltd.     

On measure‐valued solutions to a two‐dimensional gravity‐driven avalanche flow model

This paper concerns measure‐valued solutions for the two‐dimensional granular avalanche flow model introduced by Savage and Hutter. The system is similar to the isentropic compressible Euler equations, except for a Coulomb–Mohr friction law in the source term. We will partially follow the study of measure‐valued solutions given by DiPerna and Majda. However, due to the multi‐valued nature of the friction law, new more sensitive measures must be introduced. The main idea is to consider the class of x‐dependent maximal monotone graphs of non‐single‐valued operators and their relation with 1‐Lipschitz, Carathéodory functions. This relation allows to introduce generalized Young measures for x‐dependent maximal monotone graph. Copyright © 2005 John Wiley & Sons, Ltd.     

A fast direct solver for elliptic problems with a divergence constraint

A fast direct solution method for a discretized vector‐valued elliptic partial differential equation with a divergence constraint is considered. Such problems are typical in many disciplines such as fluid dynamics, elasticity and electromagnetics. The method requires the problem to be posed in a rectangle and boundary conditions to be either periodic boundary conditions or the so‐called slip boundary conditions in one co‐ordinate direction. The arising saddle‐point matrix has a separable form when bilinear finite elements are used in the discretization. Based on a result for so‐called p‐circulant matrices, the saddle‐point matrix can be transformed into a block‐diagonal form by fast Fourier transformations. Thus, the fast direct solver has the same structure as methods for scalar‐valued problems which are based on Fourier analysis and, therefore, it has the same computational cost ??(N log N). Numerical experiments demonstrate the good efficiency and accuracy of the proposed method. Copyright © 2002 John Wiley & Sons, Ltd.     

Vanishing viscosity limit of the Navier‐Stokes equations to the euler equations for compressible fluid flow

We establish the vanishing viscosity limit of the Navier‐Stokes equations to the isentropic Euler equations for one‐dimensional compressible fluid flow. For the Navier‐Stokes equations, there exist no natural invariant regions for the equations with the real physical viscosity term so that the uniform sup‐norm of solutions with respect to the physical viscosity coefficient may not be directly controllable. Furthermore, convex entropy‐entropy flux pairs may not produce signed entropy dissipation measures. To overcome these difficulties, we first develop uniform energy‐type estimates with respect to the viscosity coefficient for solutions of the Navier‐Stokes equations and establish the existence of measure‐valued solutions of the isentropic Euler equations generated by the Navier‐Stokes equations. Based on the uniform energy‐type estimates and the features of the isentropic Euler equations, we establish that the entropy dissipation measures of the solutions of the Navier‐Stokes equations for weak entropy‐entropy flux pairs, generated by compactly supported C² test functions, are confined in a compact set in H^?1, which leads to the existence of measure‐valued solutions that are confined by the Tartar‐Murat commutator relation. A careful characterization of the unbounded support of the measure‐valued solution confined by the commutator relation yields the reduction of the measurevalued solution to a Dirac mass, which leads to the convergence of solutions of the Navier‐Stokes equations to a finite‐energy entropy solution of the isentropic Euler equations with finite‐energy initial data, relative to the different end‐states at infinity. © 2010 Wiley Periodicals, Inc.